V.3. La dualité en programmation linéaire
2 ◦ ) (D α ) est un programme linéaire dans R 2 ; il se résout graphiquement :
Valeur du paramètre
Solutions
Valeur optimale
α < 2
y = (1, 0)
2
α = 2
{y = (y 1 , 1 − y 1 ) | 0 y 1 1}
2
α > 2
y = (0, 1)
α
On est dans une situation où val(P α ) = val (D α ).
Les deux premières contraintes de (D α ) sont inactives en y solution de
(D α ) ; donc x 1 = x 2 = 0 nécessairement pour toute solution x = (x 1 , x 2 , x 3 , x 4 )
de (P α ).
Sachant cela et connaissant val(P α ), on détermine x 3 et x 4 .
• α < 2. On cherche x 3 et x 4 tels que
x 3 + x 4 = 2, x 3 − x 4 2,
x 3 + x 4 α
x 3 0, x 4 0.
Il s’ensuit x 3 = 2 et x 4 = 0. La seule solution de (P α ) est donc
x = (0, 0, 2, 0) .
• α 2. Les solutions x de (P α ) sont de la forme
x = (0, 0, β, α − β) , avec 1 +
α
2
β α.
C’est donc une arête du polyèdre des contraintes, qui se réduit à un sommet
pour α = 2.
** Exercice V.24. 0n considère le programme linéaire suivant :
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser x 1 + 2x 2 + 3x 3 + . . . + nx n
x 1 1, x 1 + x 2 2, x 1 + x 2 + x 3 3, . . . , x 1 + x 2 + . . . + x n n,
x i 0 pour tout i = 1, 2, . . . , n.
1 ◦ ) Décrire d’une manière détaillée le problème dual (D) de (P).
2 ◦ ) Montrer que tout élément admissible y = (y 1 , . . . , y n ) de (D) (et donc
toute solution de (D)) vérifie
y k + y k+1 + . . . + y n < k pour tout k = 2, . . . , n.
207