V.3. La dualité en programmation linéaire
On admettra que, sous les hypothèses qui ont été faites, (P ˜
D) σ a effectivement une solution (x(σ), y(σ), u(σ)) et que (x(σ), y(σ), u(σ)) a une limite quand
σ → 0, limite qui sera notée (x ∗ , y ∗ , u ∗ ).
3 ◦ ) Montrer que (x ∗ , y ∗ , u ∗ ) est solution de (P ˜
D) et que, de plus :
« Pour tout i = 1, . . . , n, l’une des deux composantes du couple (x ∗
i , u ∗
i ) est
nulle tandis que l’autre est strictement positive » .
4 ◦ ) Illustration. Considérons le programme linéaire suivant dans (R 3 ) :
(P)
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Minimiser x 1 + x 2 + x 3
−x 1 + x 2 = 0
x 3 = 1
x 1 0, x 2 0, x 3 0.
Illustrer sur cet exemple les résultats obtenus dans les questions précédentes
en déterminant (x(σ), y(σ), u(σ)) ainsi que (x ∗ , y ∗ , u ∗ ).
Solution : On rappelle au préalable le lien qui existe entre les solutions de
(D) et celles de ( ˜
D) :
(y est solution de (D)) ⇒ ((y, c − A
y) est solution de ( ˜
D)) ;
((y, u) est solution de ( ˜
D)) ⇒ (u = c − A
y et y est solution de (D)).
Notons aussi qu’en raison du caractère injectif de A (dû au fait que A est
surjective),
⎛
⎜
⎝
(y 1 , u) solution de ( ˜
D)
et
(y 2 , u) solution de ( ˜
D)
⎞
⎟
⎠ ⇒ (y 1 = y 2 ) .
1 ◦ ) Soit x admissible pour (P) et (y, u) admissible pour ( ˜
D). Alors
u = c − A y de sorte que
x, u =
x, c − A
y
= x, c − −Ax, y
= x, c − −b, y .
Mais puisque y est admissible pour (D), c, x b, y , d’où x, u 0.
Avoir x, u = 0 équivaut à avoir c, x = b, y . Ceci traduit le fait que x
est solution de (P) et y est solution de (D) (soit encore (y, u = c − A y) est
solution de ( ˜
D)).
211