FSJES AC
COURS DE RECHERCHE OPERATIONNELLE
PARTIE 2
REPRESENTATION ET RESOLUTION GRAPHIQUE D’ UN
PROGRAMME LINEAIRE
SEMESTRE 6
GESTION E1E2E3 / ECONOMIE ET GESTION E1E2
2020-2021
[Link]
1
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.
Donc on se limite à une représentation de deux variables .
TECHNIQUES DE RESOLUTION GRAPHIQUE
A – système d’axe
Parmi les conditions de réussite de la représentation graphique est le système d’axe. Un mauvais
choix peut rendre notre représentation non clair et imprécise.
A cause de non négativité des variables de décisions , nous nous intéressons seulement au cadran
positif. ( voir figure ci-dessous )
X2
X1
Cette région s’appelle la région des solutions possibles du problème.
B - EXEMPLES
On traitera dans cette partie deux exemples qui serviront à illustrer la méthode de résolution
graphique
B -1- Problème de maximisation
Considérons l’exemple suivant : = 25 + 15
Sous les contraintes suivantes : + ≤ 120
3 + ≤ 140
≥ 0 , ≥ 0
PREMIERE METHODE
a- Représentation des lignes de contraintes et l’ensemble des solutions réalisables
b- Représentation de la fonction objectif et localisation de la solution optimale
c- Calculer la solution optimale
2
a-Représentation des lignes de contraintes et l’ensemble des solutions réalisables
parmi les solutions possibles d’un problème, il y a celles qui vont satisfaire toutes les contraintes
du programme appelés solutions réalisables et celles qui vont une partie ou aucune partie de ces
contraintes , appelés solutions non réalisables.
Revenons à l’exemple précédent : les solutions qui vérifient l’inégalité 2 + 2 ≤ 240 est
Equivalent à l’ensemble des solutions qui vérifient 2 + = 240 et 2 + > 240
L’ensemble des solutions à l’équation est l’ensemble des points de la droite = −2 + 240
Cette droite qui a une pente de -2.
L’inégalité 2 + > 240 correspond à un demi plan limité par la droite = −2 + 240 .
Or cette droit divise le plan en deux demi plan, donc quel est le demi plan à choisir ?
Pour ce faire il suffit de prendre un point de l’un des demi plans (qui n’appartient pas à la droite
= −2 + 240 ) et voir s’il vérifie l’inégalité 2 + > 240.
X2
120
120 X1
On fait la même chose pour l’autre contrainte , on obtient deux demi plans correspondants aux
solutions vérifiant les deux contraintes.
X2
140
120
140/3 120 X1
3
b-Représentation de la fonction objectif et localisation de la solution optimale
la fonction = 25 + 15 représente pour Z fixé l’équation des courbes de niveau ( de droites
de pente -5/3 ) .Maximiser Z revient à déplacer la courbe de niveau le plus loin possible de l’origine
puisque les coéfficients de sont positifs.
Alors Z = 0 , la fonction objectif est représentée de l a manière suivante :
Z=0
Les limites imposés par étant données et représentées graphiquement par le domaine de
solutions réalisables. On ne peut pas augmenter indéfiniment la valeur de l fonction objectif.
Pour maximiser Z on cherche la plus haute courbe de niveau qui a une intersection non vide avec le
domaine de solutions réalisables.
4
Le point qui maximise le domaine est le point M.
c-Calcule de la solution optimale
graphiquement le point M est l’intersection des deux droites d’équations 2 + 2 = 0
et 3 + = 0 , donc les coordonnées de M c’est la solution du système :
2 + 2 =0
3 + =0
∗
Donc : = 10 et = 110 et = 1900.
DEUXIEME METHODE ( ENUMERATION DES SOMMETS )
On remarque que la solution optimale ne peut être que sur le bord du domaine des solutions
réalisables . de plus elle est dans le cas général donnée par un point anguleux correspondant aux
intersections des droites de contraintes. Une telle solution est appelée solution de base. Eci nous
amène à proposer ce qui suit :
- Représenter les lignes de contraintes et les solutions réalisables
- Localiser toutes les solutions de base
- Calculer la valeur de Z pour chaque point et choisir la solution optimale.
Dans l’exemple précédent, le domaine est délimité par quatre points anguleux O, A, M, B.
O ( 0,0 ) correspond à Z = 0
A( 140/3 , 0 ) correspond à Z = 3500/3
M ( 10 , 110 ) correspond à Z = 1900
B ( 0 , 120 ) correspond à Z = 1800.
∗
Donc la solution optimale est = 1900
B -1- Problème de minimisation
Première méthode
Le problème de minimisation ne diffère du problème de minimisation que par a recherche de la
courbe de niveau qui donne la plus petite valeur de Z , tut en satisfaisant toutes les contraintes
du programme.
Exp : = 24 + 20
Sous + ≥ 30
+2 ≥ 40
≥ 0 , ≥ 0
5
X2
30 C
20
0 A
30 40 X1
Z=0
Z=0 est une droite de pente -6/5 , pour le problème de minimisation , on cherche la courbe de
niveau la plus proche de 0 , minimiser Z revient à trouver la première courbe de niveau qui a une
intersection non vide avec le domaine des solutions réalisables.
Dans l’exemple précédent le point C qui minimise le domaine, ce point a pour coordonnées C (0,30)
et ∗ = 600
Deuxième méthode
le domaine est délimité par quatre points anguleux O, A, B, C
O (0,0) correspond à Z = 0
A(40,0) correspond à Z = 960
B(20,10) correspond à Z = 680
∗
C(0,30) correspond à Z = 600 , donc = 600.
ANALYSE DE SENSIBILITE
Une analyse de sensibilité se résume à la recherche des intervalles de variations possibles des
paramètres du PL sans que la solution optimale ne soit modifiée.
L’analyse de sensibilité peut être motivée par plusieurs raisons :
- Les données du problème ne sont pas connues avec exactitude
- On souhaite évaluer les conséquences d’un changement de politique qui modifierait les
données du problème.
6
Exemple :
= 1000 + 2000
4 +2 ≤ 440 droite D1
+4 ≤ 480 droite D2
+ ≤ 150 droite D3
≤ 90 droite D4
≥ 0 , ≥ 0
M1 c’est l’intersection entre D3 et D2 +4 = 480 La solution est M1(40,110)
+ = 150
M2 c’est l’intersection entre D3 et D1 4 +2 = 440 La solution est M2(70,80)
+ = 150
M3 c’est l’intersection entre D4 et D1 4 +2 = 440 La solution est M3(90,40)
= 90
Donc : M1(40,110) correspond à Z = 260000
M2(70,80) correspond à Z = 230000
M3(90,40) correspond à z = 170000
O(0,0) correspond à Z = 0
E(90,0) correspond à Z = 90000
7
C(0,120) correspond à Z = 240000
∗
Finalement le point M1 qui maximise le domaine, = 260000. M1 est l’intersection entre D2 et D3.
La pente de D2 est -1/4 et la pente de D3 est -1.
Si on modifie un paramètre dans la fonction objectif par exemple le coefficient de la fonction devient
= (1000 + ) 1 + 2000 2
( )
Pour Z=0 la pente est : la solution demeure optimale si la pente de la fonction objectif reste comprise entre la pente de D2
( )
et D3. Donc −1 ≤ ≤ −1/4 ce qui donne : −500 ≤ ≤ 1000
Exercice Résoudre = +
+ ≤
≥ 0 , ≥ 0
Solution
Exercice1
∗
Le point qui maximise le domaine est (2,3) donc = 11
