V.3. La dualité en programmation linéaire
Commentaire : Cette correspondance entre points extrémaux de ˜
C ⊂ R n ×R m et
de sa projection C sur R n est particulière ; elle est sans espoir pour des convexes
fermés en général (cf. Exercice VI.7).
* Exercice V.5. Soit C le polyèdre convexe fermé de R 2 décrit à l’aide des inégalités suivantes :
x 1 +
8
3
x 2 4, x 1 + x 2 2, 2x 1 3, x 1 0, x 2 0.
1 ◦ ) Écrire C sous la forme standard (c’est-à-dire comme la projection sur
R 2 d’un polyèdre convexe fermé ˜
C de R 5 d’équation : A˜ x = ˜ b, ˜
x 0).
2 ◦ ) Quels sont les points extrémaux de ˜
C ? En déduire les points extrémaux
de C.
Commentaire : Grâce à une représentation graphique de C, on voit facilement
que les points extrémaux de C sont
0
0
,
3/2
0
,
0
3/2
,
4/5
6/5
,
3/2
1/2
. Le
but de l’exercice est de retrouver ces points en utilisant la caractérisation des
points extrémaux d’un polyèdre convexe fermé d’équation : A˜ x = ˜ b, ˜
x 0 (revoir
l’Exercice V.4 à ce sujet).
Solution : 1 ◦ ) En introduisant les variables d’écart u 1 , u 2 , u 3 , on peut dire :
(x = (x 1 , x 2 ) ∈ C) ⇔ (Il existe u 1 , u 2 , u 3 tels que (x 1 , x 2 , u 1 , u 2 , u 3 ) ∈ ˜
C),
où ˜
C est décrit comme suit :
x 1 +
8
3 x 2 + u 1 = 4, x 1 + x 2 + u 2 = 2, 2x 1 + u 3 = 3,
x 1 0, x 2 0, u 1 0, u 2 0, u 3 0.
Les points extrémaux de C s’obtiennent par projection sur R 2 des points
extrémaux de ˜
C :
(x = (x 1 , x 2 ) est extrémal dans C) ⇔ (˜ x = (x 1 , x 2 , u 1 , u 2 , u 3 ) est extrémal
dans ˜
C) (cf. Exercice V.4).
Comme ˜
C est décrit sous la forme A˜ x = ˜ b, ˜
x 0, avec A ∈ M 3,5 (R) de
rang 3, il suffit, pour avoir les points extrémaux de ˜
C, de repérer ses éléments
de base admissibles. Ce sont :
x =
3
2 ,
1
2 ,
7
6 , 0, 0
correspondant à la base {1, 2, 3} ,
x =
4
5 ,
6
5 , 0, 0,
7
5
correspondant à la base {1, 2, 5} ,
x =
3
2 , 0,
5
2 ,
1
2 , 0
correspondant à la base {1, 3, 4} ,
x = (0, 0, 4, 2, 3) correspondant à la base {3, 4, 5} ,
x =
0,
3
2 , 0,
1
2 , 3
correspondant à la base {2, 4, 5} .
179