V.3. La dualité en programmation linéaire
Du résultat de la 1 re question, il vient ceci : pour k suffisamment grand,
l’ensemble des solutions de (P k ) est contenu dans l’ensemble des solutions (P).
Figure 13.
** Exercice V.17. Soit C le polyèdre convexe compact de R 4 décrit comme suit :
⎧
⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎩
x 1 +
4
3 x 2 + 2x 3 =
3
2
x 2 + 3x 3 =
3
2
x 1 + x 2 + x 3 + x 4 = 1
x 1 0, . . . , x 4 0.
1 ◦ ) Lister les points extrémaux de C.
2 ◦ ) Résoudre
(P)
Min 3x 1 + x 2 + x 3 + x 4
(x 1 , x 2 , x 3 , x 4 ) ∈ C.
3 ◦ ) Pour ε > 0 suffisamment petit (disons 0 < ε <
1
10 ), on remplace
4
3 par
4
3 − ε dans la 1 re équation définissant C, ce qui donne un nouveau polyèdre C ε .
Résoudre à présent
(P ε )
Min 3x 1 + x 2 + x 3 + x 4
(x 1 , x 2 , x 3 , x 4 ) ∈ C ε .
Conclusions ?
197