Programmation linéaire
Résolution graphique
Résolution graphique
• Envisageable pour des problèmes ne comportant que deux variables.
• Revenons au problème du restaurateur :
Min z = – 8x – 6y
s.a.
5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
x, y ≥ 0
2
Résolution graphique
• Traçons la droite 5 x + 3 y 30
5x + 3y = 30 2 x + 3 y 24
1x + 3 y 18
y
L’ensemble des points qui x 0, y 0
satisfont la contrainte
5x + 3y ≤ 30
10
se trouvent sous cette droite car
l’origine x = 0, y = 0 en fait
partie
6 x
3
Domaine réalisable
• Traçons la droite 5 x + 3 y 30
2x + 3y = 24 2 x + 3 y 24
1x + 3 y 18
y
L’ensemble des points qui x 0, y 0
satisfont la contrainte
2x + 3y ≤ 24
10
se trouvent sous cette droite car
8
l’origine x = 0, y = 0 en fait
partie
6 12 x
4
Domaine réalisable
• Traçons la droite 5 x + 3 y 30
x + 3y = 18 2 x + 3 y 24
1x + 3 y 18
y
L’ensemble des points qui x 0, y 0
satisfont la contrainte
x + 3y ≤ 18
10
se trouvent sous cette droite car
8
l’origine x = 0, y = 0 en fait
partie 6
6 12 18 x
5
Domaine réalisable
• L’ensemble des points réalisables
pour le système
y
5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
x, y ≥ 0
correspond à un polytope.
6
6 x
6
Résolution
• Considérons l’objectif : y = -8/6 x – z/6 5 x + 3 y 30
z = –8x – 6y. Droites de pente – 8/6 2 x + 3 y 24
1x + 3 y 18
y
x = 0 et y = 0 => z = 0 x 0, y 0
6
• Plus on s’éloigne de l’origine,
plus la valeur de z diminue.
6 x
7
Résolution
• Considérons l’objectif : 5 x + 3 y 30
z = –8x – 6y. 2 x + 3 y 24
1x + 3 y 18
y
x = 0 et y = 0 => z = 0 x 0, y 0
x = 0 et y = 6 => z = – 36
6
• Plus on s’éloigne de l’origine,
plus la valeur de z diminue.
6 x
8
Résolution
• Considérons l’objectif : 5 x + 3 y 30
z = –8x – 6y. 2 x + 3 y 24
1x + 3 y 18
y
x = 0 et y = 0 => z = 0 x 0, y 0
x = 0 et y = 6 => z = – 36
x = 6 et y = 0 => z = – 48
6
• Plus on s’éloigne de l’origine, plus la
valeur de z diminue.
6 x
9
Résolution
5 x + 3 y = 30 5 x + 3 y 30
• Considérons l’objectif : x = 3 x = 3
x + 3 y = 18 y = 5 2 x + 3 y 24
z = –8x – 6y. + =
= 12
3 3 y 18
4x
1x + 3 y 18
y
x = 0 et y = 0 => z = 0 x 0, y 0
x = 0 et y = 6 => z = – 36
x = 6 et y = 0 => z = – 48 solution optimale:
x = 3 et y = 5
x = 3 et y = 5 => z = – 54
valeur optimale:
z = – 54
6
• Plus on s’éloigne de l’origine,
plus la valeur de z diminue.
• Impossible d’aller plus loin sans
sortir du domaine réalisable. 6 x
10
Lien avec l’algorithme du simplexe
Lors de la résolution du problème du
restaurateur avec l’algorithme du simplexe:
La solution initiale est 5x + 3y ≤ 30
x = y = 0 avec z = 0 y 5x + 3y + u = 30
En augmentant x, la solution devient
x = 6, y = 0 avec z = – 48 2x + 3y ≤ 24
En augmentant y, la solution devient 2x + 3y + p = 24
x = 3, y = 5 avec z = – 54
x + 3y ≤ 18
En fait, les solutions de base correspondent
aux « coins » (points extrêmes) du polytope. 6 x + 3y + h = 18
•
Dans le pire cas, l’algorithme du simplexe
aurait visité 4 solutions avant d’identifier la
solution optimale • •
6 x
11
Forme originale versus forme standard
5 5!
• Il y a = = 10 solutions de base différentes dans l’espace
2 3! 2!
des variables x, y, u, p, h (forme standard).
• Par ailleurs, le polytope ne possède que 4 coins, soit 4 solutions dans l’espace des
variables x et y (forme originale).
• Comment expliquer cette apparente contradiction?
12
Forme originale versus forme standard
Min z = – 8x – 6y Min z = – 8x – 6y
s.a. s.a.
5x + 3y ≤ 30 5x + 3y + u = 30
2x + 3y ≤ 24 2x + 3y + p = 24
x + 3y ≤ 18 x + 3y + h = 18
x, y ≥ 0 x, y, u, p, h ≥ 0
(x, y) x = 0, y = 0 u = 30, p = 24, h =18
(y, u) x = 6, y = 0 u = 0, p = 12, h =12
(u, h) x = 3, y = 5 u = 0, p = 3, h = 0
(x, h) x = 0, y = 6 u = 12, p = 6, h = 0
(x, u) x=0 u= 0
x = 0, y = 10 u= 0
x = 0, y = 10 u= 0, p = -6
x = 0, y = 10 u= 0, p = -6, h = -12
13
Forme originale versus forme standard
(x, y) x = 0, y = 0 u = 30, p = 24, h =18
(y, u) x = 6, y = 0 u = 0, p = 12, h =12
(u, h) x = 3, y = 5 u = 0, p = 3, h = 0
(x, h) x = 0, y = 6 u = 12, p = 6, h= 0
(x, u) x = 0, y = 10 u = 0, p = -6, h = -12
(x, p) x = 0, y = 8 u = 6, p = 0, h=-6
(y, p) x = 12, y = 0 u = -30, p = 0, h = 6
(y, h) x = 18, y = 0 u = -60, p = -12, h = 0
(u, p) x = 2, y = 20/3 u = 0, p = 0, h = -4
(p, h) x = 6, y = 4 u = -12, p = 0, h=0
• En fait, il y a 4 solutions de base réalisables qui peuvent être visitées par l’algorithme du
simplexe et 6 solutions de base non réalisables.
• Les 4 solutions de base réalisables correspondent aux 4 coins du polytope dans l’espace
des variables x et y.
14
