Chapitre 2
Résolution graphique d’un programme
linéaire
▪ Représentation d’éléments
▪ Représentation d’un programme linéaire
▪ Exemples
▪ Propriétés des programmes linéaires
© Khaled Jabeur 2012 Cours Programmation Linéaire 1
Représentation graphique d’un programme linéaire
• On peut représenter un programme linéaire graphiquement s’il a
deux variables (ou moins…), par exemple x1, x2.
• Dans ce cas, chaque décision (choix de valeurs pour x1, x2) peut
être représentée par un point ou un vecteur dans le plan cartésien
x2
x1o
x2o x = o
o
x2
x1o x1
2
© Khaled Jabeur 2012
Le gradient d’une fonction f (x) en un point xº est le vecteur formé par
les dérivées partielles de f en ce point:
f ( x o )
x1
f ( x o ) = M
f ( x o
)
xn
Si la fonction f (x) est affine, son gradient est constant (il est indépendant
du point xº) :
a1
f ( x ) = a1x1 + a2 x2 + L + an xn + b f ( x ) = M
a
n
Le gradient de f en un point indique dans quelle direction la fonction
s’accroît le plus vite.
5
Exemple :
5
f ( x1 ,x2 ) =
−7 gradient
f ( x1 ,x2 ) = 5x1 − 7 x2 + 3
−7
© Khaled Jabeur 2012 3
Égalités et inégalités linéaires
f ( x1 , x2 ) = a1 x1 + a2 x2
c une constante donnée
x2
f ( x1 , x2 ) = c f ( x1 , x2 ) c f ( x1 , x2 ) c
a1
a2
x1
© Khaled Jabeur 2012 4
Programme linéaire: exemple 1
Max Z = x1 + x2
S.l.c.: x1 + 2 x2 6
x1 4
x2 2
x1 0
x2 0
1. Dessiner les contraintes
2. Identifier le domaine réalisable
3. Examiner les valeurs de l’objectif dans le domaine réalisable
4. Trouver toutes les solutions optimales
© Khaled Jabeur 2012 5
Contrainte: x1+2x2 6
Frontière: x1+2x2 = 6 Droite: trouver 2 points
x1 = 0 x2 = 3 → P = x2 = 0 x1 = 6 → Q =
0 6
3 0
x2
P
x1 + 2 x2 = 6
1
x1
0 Q
© P. Lang H2006 6
Contrainte: x1+2x2 6
Inégalité: demi-plan Zone interdite:
x2
x1 + 2 x2 = 6
x1
0
© P. Lang H2006 7
Autres contraintes
x1 = 4 x2 = 2 x1 = 0 x2 = 0
x1 4 x2 2 x1 0 x2 0
x2
x1
0
© P. Lang H2006 8
Domaine réalisable
Points A, B, C, D, E situés aux « coins » du domaine réalisable
= points extrêmes.
x2
B C
Domaine
réalisable D
A E
x1
0
© P. Lang H2006 9
Valeurs possibles de la fonction objectif
•Si on fixe l’objectif à une valeur k, on obtient une courbe de niveau = droite.
•Si la droite contient des points réalisables, la valeur k peut être atteinte par
l’objectif.
x2
C réalisables tels que Z = 3
Points
B
Points réalisables tels que Z = 1 Décision optimale
D x1 = 4
x2 = 1
Z =5
A x1
0 x1 + x2 x1 E+ x2 x1 + x2 = 5
x1 + x2 = 1 =© P.3Lang H2006
=4 10
Si on change l’objectif…
…on change l’orientation des courbes de niveau et du gradient.
x2
Décision optimale
C
B
A x1
0 E
© P. Lang H2006 11
Si on change l’objectif…
…on change l’orientation des courbes de niveau et du gradient.
x2
Décision optimale
C
B
A x1
0 E
© P. Lang H2006 12
Cas particulier
L’objectif est: Max Z = x1 + 2 x2
x2
C Décisions optimales multiples
B
A x1
0 E
© P. Lang H2006 13
Exemple 2
Max Z = x1 + x2
S.l.c.: −2 x1 + x2 1
x1 − 2 x2 1
x1 0
x2 0
© Khaled Jabeur 2012 14
−2 x1 + x2 1 x1 − 2 x2 1 x1 0 x2 0
© Khaled Jabeur 2012 15
Max Z = x1 + x2
Solution sans borne
© Khaled Jabeur 2012 16
Exemple 3
Max Z = x1 + x2
S.l.c.: − x1 + 2 x2 2
2 x1 − x2 2
x1 + x2 2
© Khaled Jabeur 2012 17
Exemple 3
Max Z = x1 + x2
S.l.c.: − x1 + 2 x2 2
2 x1 − x2 2
x1 + x2 2
© Khaled Jabeur 2012 18
Exemple 3
Max Z = x1 + x2
S.l.c.: − x1 + 2 x2 2
2 x1 − x2 2
x1 + x2 2
Aucune décision
n’est réalisable.
Le domaine réalisable
est vide.
19
© Khaled Jabeur 2012
Programmes linéaires: cas possibles de solution
(« Solution » = décision)
1. Pas de solution 2. Solution(s) 3. Une ou plusieurs
réalisable sans borne solution(s) optimales finies
3.a Une 3.b Plusieurs
Le problème n’est
Le problème est réalisable.
pas réalisable.
© Khaled Jabeur 2012 20
Propriétés fondamentales
Propriété 1 (solutions optimales)
S’il existe une (ou plusieurs) solutions optimales finies (cas 3),
et si le domaine réalisable a (au moins) un point extrême,
alors il existe (au moins) un point extrême qui est optimal.
Propriété 2 (existence de points extrêmes)
Si le domaine réalisable est borné et non vide, alors il a au moins un point
extrême.
Conséquence: si le domaine réalisable est borné et non vide, pour trouver
une solution optimale, il suffit d’inspecter tous les points extrêmes.
© Khaled Jabeur 2012 21
Exemple 1:
Point extreme Coordonnées ( x1 , x2 ) Z = x1 + x2
A (0,0) 0
B (0, 2) 2
C (2, 2) 4
D (4,1) 5 Solution optimale unique
E (4,0) 4
© Khaled Jabeur 2012 22
