Chapitre 2 : Résolution graphique et analyse de sensibilité
CHAPITRE 2
Résolution Graphique et analyse de
sensibilité
I. Introduction
Après avoir illustrer par des exemples, comment un problème pratique peut être
modélisé par un programme linéaire, l’étape qui va suivre sera certainement celle
de la résolution de ce problème mathématique. La méthode graphique est l’une
des premières méthodes utilisées à ce sujet.
Si on parle de résolution graphique alors on doit se limiter à une représentation à
deux variables et au plus à trois variables. Ceci indique que dans ce chapitre on
examinera seulement les programmes linéaires à deux variables de décision.
II. Système d’axes
Une des conditions de la réussite de notre représentation graphique est le choix
d'un système d’axes. Un mauvais choix peut rendre notre représentation non claire
et imprécise.
A cause des contraintes de non-négativité des variables de décision, nous nous
intéressons seulement au cadran positif (voir figure ci-dessus).
Cette région s’appelle la région des solutions possibles du problème.
Prenons l’exemple 2 relatif au problème de médecine. Le programme linéaire est
le suivant :
Min x1 x2
s.c. 2 x1 x2 12
5 x1 8 x2 74
x1 6 x2 24
x1 0, x2 0
Cours de recherche opérationnelle Slim GUERMAZI 11
Chapitre 2 : Résolution graphique et analyse de sensibilité
Un bon choix se base sur une lecture des différents paramètres du programme
linéaire. Dans notre cas, on ne peut qualifier de bon, le choix de 20 comme unité
dans les deux axes.
Pour l’exemple, on peut choisir le système d’axes suivant :
x2
12
6
3
x1
6 12 24
III. Représentation graphique des contraintes
Parmi les solutions possibles d’un problème, il y a ceux qui vont satisfaire toutes
les contraintes du programme, appelés solutions réalisables, et ceux qui vont
satisfaire une partie ou aucune de ces contraintes, appelés solutions non
réalisables.
Une représentation graphique des inégalités (des contraintes) va nous permettre
de déterminer l’ensemble des solutions réalisables.
Revenons à l’exemple 2 du problème de médecine.
Une des contraintes de ce problème est celle relative au grain d’aspirine :
2 x1 x2 12 .
L’ensemble des solutions qui vérifient cette inégalité est le même que celui qui
vérifie 2x1 x2 12 et 2x1 x2 12 .
x2
12
6
3
x1
6 12 24
L’ensemble des solutions qui correspond à l’équation est l’ensemble des points
de la droite l définie par x2 2x1 12 . Cette droite admet une valeur de la pente
égale à –2 et intercepte l’axe des ordonnées en 12 (voir figure ci-dessus).
L’inégalité 2x1 x2 12 correspond à un demi-plan limité par la droite
x2 2 x1 12 . Or cette droite divise le plan en deux demi-plans ouverts donc quel
est le demi-plan à choisir ?
Cours de recherche opérationnelle Slim GUERMAZI 12
Chapitre 2 : Résolution graphique et analyse de sensibilité
x2
12 1
6
3
x1
6 12 24
Pour ce faire, il suffit de prendre un point de l’un des demi-plans (c’est à dire
n’appartenant pas à la droite x2 2x1 12 ) et voir s’il vérifie l’inégalité
2 x1 x2 12 . Par exemple le point de coordonnées (0,0) ne vérifie pas l’inégalité
2 x1 x2 12 donc le demi-plan 1 au-dessus de la droite est celui recherché (voir
figure ci-dessus).
L’espace hachuré représente le demi-plan fermé des solutions qui vérifient la
contrainte 2x1 x2 12 .
Si on fait de même pour les deux autres contraintes du problème (voir figures
ci-dessous), on obtient les deux autres demi-plans 2 et 3 relatifs aux solutions
vérifiant respectivement les contraintes 5x1 8x2 74 et x1 6x2 24 .
3 2
9.25
6
4
3
x1 x1
6 12 24 6 14,8 24
Une solution possible du problème est dite réalisable si et seulement si elle vérifie
toutes les contraintes, c’est à dire si elle appartient aux trois demi-plans relatifs à
chaque contrainte du programme linéaire, en d’autre terme à
1 2 3 (voir figure).
x2
Ensemble des
12 solutions
réalisables
x1
6 12 24
Définition : Un ensemble E non vide est dit convexe si et seulement si pour tout
élément x et y de E et pour tout [0,1], x + (1-) yE.
On peut vérifier facilement que chacun des demi-plans 1, 2 , 3 est convexe en
vérifiant que pour toute paire de points P1 et P2, l’ensemble des points qui forment
le segment [P1P2] appartient au demi-plan.
Théorème : L’intersection d’ensembles convexes (non vide) est convexe.
Cours de recherche opérationnelle Slim GUERMAZI 13
Chapitre 2 : Résolution graphique et analyse de sensibilité
Propositions : L’ensemble des solutions réalisables (non vide) est convexe.
IV. Représentation de la fonction objectif
Soit z la valeur de la fonction objectif du problème de médecine z x1 x2 .
Pour z=0, la fonction objectif est représentée de la manière suivante :
x2
12
x1
6 24
x1 x 2 0
Pour z=6, c’est à dire que le nombre de pilules à prescrire est égale à 6 pilules. La
fonction objectif est représentée comme suit :
x2
12
x1
6 24
x1 x 2 6
Chaque point du segment qui relie les points (6,0) à (0,6) représente des solutions
qui engendrent une prescription avec 6 pilules des deux tailles.
On peut tracer une infinité de droites qui représentent les différentes valeurs de la
fonction objectif, toutes ces droites ont le même coefficient directeur (-1). Par
suite elles sont parallèles entre elles. De plus on peut diminuer la valeur de z
indéfiniment dans le sens indiqué dans la figure ci-dessous.
x2
12
x1
6
z 18
z6 z 12
Le problème est de connaître qu’elle est la droite qui correspond à la valeur
minimal de la fonction objectif ?
V. Recherche de la solution optimale
a. Résolution graphique
Si nous retraçons l’ensemble des droites parallèles relatives à différentes valeurs
de la fonction objectif sur la figure qui représente l’ensemble des solutions
Cours de recherche opérationnelle Slim GUERMAZI 14
Chapitre 2 : Résolution graphique et analyse de sensibilité
réalisables, on peut localiser la solution optimale. Elle correspond à la solution
réalisable qui intercepte la droite à la plus petite valeur de z.
x2
12
B
x1
6 12
Z=10
Dans notre exemple, la solution optimale est l’intersection des deux contraintes
2 x1 x2 12 et 5x1 8x2 74 . Une évaluation des coordonnées de ce point revient à
résoudre le système linéaire suivant :
2 x1 x 2 12
5 x1 8 x 2 74
Elle correspond d’après le graphique au point (2,8). Donc la prescription optimale
est de 2 pilules de petite taille et 8 pilules de grande taille. Le nombre de pilules
(la valeur de la fonction objectif) est égale à 10.
b. Résolution par énumération :
On remarque que la solution optimale du problème de médecine est un point
extrême qui se trouve sur le bord de l’ensemble des solutions. Une telle solution
est dite solution réalisable de base.
On peut admettre le résultat suivant : « Si un programme linéaire admet une
solution optimale alors il existe une solution réalisable de base pour laquelle la
fonction objectif atteint la valeur optimale »
Une méthode de résolution du programme linéaire consiste donc à déterminer les
solutions réalisables de base (les points d’intersection des droites qui forment les
contraintes) et à calculer pour chaque point la valeur de la fonction objectif. La
solution du programme linéaire est la solution à qui on associe la valeur optimale
de la fonction objectif.
x2
12 A
B
3 C D
x1
6 12
Dans le problème de médecine, l’ensemble des solutions réalisables de base
présente 4 points extrêmes A(0,12), B(2,8), C(23/11,126/11) et D(24,0). La valeur
de la fonction objectif associée respectivement à A, B, C et D est 12, 10, 149/11
et 24. On vérifie bien que B est la solution optimale du problème avec une valeur
optimale égale à 10.
Cours de recherche opérationnelle Slim GUERMAZI 15
Chapitre 2 : Résolution graphique et analyse de sensibilité
VI. Exemples
Dans cette section on donne quelques exemples de résolution graphique de
problèmes linéaires relatifs au différents cas possibles :
Problème de maximisation
Max 100 x1 200 x2 x2 (2)
(4)
s.c. x1 x2 150 (1) A
B
4 x1 2 x2 440 (2)
110
C
(3)
x1 4 x2 480 (3) Z=0 30
D (1)
x1 90 (4) 40
E x1
x1 0, x2 0
la solution optimale est B(40,110)
Problème avec solution non bornée
Max - 2 x1 3 x 2 x2
s.c. x1 5 (1) (2)
2 x1 3 x 2 6 (2)
x1 0, x 2 0
5 x1
Z=0
(1)
On peut augmenter la valeur de la fonction objectif dans la direction des flèches
indéfiniment donc la solution est non bornée
Problème impossible
Min 3 x1 2 x 2 x2
s.c. x1 2 x 2 2 (1)
2 x1 4 x 2 8 (2)
x1 0, x 2 0
x1
(2)
(1)
Cours de recherche opérationnelle Slim GUERMAZI 16
Chapitre 2 : Résolution graphique et analyse de sensibilité
L’espace des solutions réalisables est vide, il est l’intersection des deux zones
grises de la figure ci-dessus
Problème à solutions multiples
Max x1 3 x 2 x2
(2)
s.c. 2 x1 6 x 2 30 (1) (1)
A (3)
x1 10 (2) B
x2 4 (3)
10 x1
x1 0, x 2 0
Z=0
L’ensemble des points décrit par le segment [AB] représente les solutions
optimales du problème linéaire
Problème de dégénerescence
Max x1 x 2 x2
(2)
s.c. 3 x1 2 x 2 40 (1) (1)
B (3)
x1 10
A
(2)
x2 5 (3)
x1 0, x 2 0 O C x1
Z=0
La solution optimale B(10,5) est dite dégénérée si trois contraintes concourent
en ce point.
VII. Analyse de sensibilité
Une analyse de sensibilité se résume à la recherche des intervalles de variations
possibles des paramètres du programme linéaire sans que la solution optimale ne
soit modifiée.
Question : De combien peut-on faire varier la quantité de codéine dans le
problème de médecine sans changer la solution optimale.
Réponse :
Cours de recherche opérationnelle Slim GUERMAZI 17
Chapitre 2 : Résolution graphique et analyse de sensibilité
x2
12
B
x1
6 12
Z=10
On peut changer la valeur du second membre de la troisième contrainte jusqu'à ce
que la droite de coefficient directeur –1/6 touche le point optimal (2,8). C’est à
dire qu’on peut varier le second membre de la troisième contrainte de 24 jusqu'à
50 sans changer la solution optimale.
Question : De combien peut-on faire varier le profit engendré par la culture d’un
hectare de tomates, dans le problème de l'agriculture, sans changer la solution
optimale ?
Réponse :
x2 (2)
(4)
A
B
110
C
(3)
Z=0 30
D (1)
E x1
40
Soit la variation du profit engendré par la culture d’un hectare de tomate. La
fonction objectif est égale à (100 ) x1 200x2
La solution demeure optimale si la pente de la fonction objectif reste toujours
comprise entre la pente de la contrainte (1) et (3). Ceci est équivalent à dire que :
200 1
1 50 100
100 4
On peut vérifier aussi que si :
50 alors la solution optimale est A
50 alors le problème est à solutions multiples : [AB]
50 100 alors la solution optimale est B
100 alors le problème est à solutions multiples : [BC]
100 300 alors la solution optimale est C
300 alors le problème est à solutions multiples : [CD]
300 alors la solution optimale est D
Cours de recherche opérationnelle Slim GUERMAZI 18
