V.3. La dualité en programmation linéaire
Pour extraire de A une matrice A I(x) de rang n, il n’y a pas beaucoup de
choix :
• A I(x) = −I n , ce qui correspond à x = 0 ;
• A I(x) a [a 1 , . . . , a n ] pour première ligne et n − 1 lignes prises dans −I n ;
ceci revient, pour x, à avoir n − 1 composantes nulles (mettons, toutes sauf
la j e ) et a j x j = b 0 (relation qui vient de a, x = b 0 ).
3 ◦ ) Les points extrémaux de C, solutions de (P), sont ceux de la forme
(0, . . . , 0,
b 0
a j 0
, 0, . . . , 0), où
c j 0 b 0
a j 0
= max j
c j b 0
a j
; supposons qu’il y en ait k.
Par conséquent, la face-solution de (P) est l’enveloppe convexe de ces k points
extrémaux.
4 ◦ ) Si a 1 = a 2 = . . . = a n = b 0 = 1, les points extrémaux de
C :=
⎧
⎨
⎩
x = (x 1 , . . . , x n ) ∈ R
n
|
n
j=1
x j 1, x j 0 pour tout j = 1, . . . , n
⎫
⎬
⎭
sont 0 et les n vecteurs de base canonique e 1 , . . . , e n .
Pour n = 3, les choix successifs de c conduisent à une face-solution de (P)
qui est :
– le sommet (0, 0, 1) lorsque c 1 = (0, 0, 1) ;
– l’arête de C joignant (0, 0, 1) à (0, 1, 0) lorsque c 2 = (0, 1, 1) ;
– la facette de C enveloppe convexe de (0, 0, 1) , (0, 1, 0) et (0, 0, 1) lorsque
c 3 = (1, 1, 1) .
Figure 11.
193