Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
* Exercice V.22. Montrer que si le programme linéaire
(P)
Max c, x
Ax = 0, x 0
a une valeur optimale finie, alors x = 0 est certainement solution de (P).
Solution : L’ensemble-contrainte de (P) n’est pas vide (il contient 0) et, par
hypothèse, val(P) < +∞.
Le problème dual de (P) s’écrit :
(D)
Min 0, y
A y c
,
et donc 0 = val(D) = val(P).
Par conséquent, x = 0 est une solution de (P).
** Exercice V.23. Soit le programme linéaire suivant dans R 4 :
(P α )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Min 3x 1 + 4x 2 + x 3 + x 4
x 1 + x 2 + x 3 − x 4 2
−2x 1 + 2x 2 + x 3 + x 4 α
x 1 0, . . . , x 4 0
, où α est un paramètre réel.
1 ◦ ) Écrire le problème dual (D α ) de (P α ).
2 ◦ ) Résoudre (D α ) suivant les valeurs de α ; en déduire les solutions de (P α ).
Solution : 1 ◦ ) (D α ) se formule comme suit :
(D α )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Max 2y 1 + αy 2
y 1 − 2y 2 3, y 1 + 2y 2 4,
y 1 + y 2 1, −y 1 + y 2 1,
y 1 0, y 2 0.
206
* Exercice V.22. Montrer que si le programme linéaire
(P)
Max c, x
Ax = 0, x 0
a une valeur optimale finie, alors x = 0 est certainement solution de (P).
Solution : L’ensemble-contrainte de (P) n’est pas vide (il contient 0) et, par
hypothèse, val(P) < +∞.
Le problème dual de (P) s’écrit :
(D)
Min 0, y
A y c
,
et donc 0 = val(D) = val(P).
Par conséquent, x = 0 est une solution de (P).
** Exercice V.23. Soit le programme linéaire suivant dans R 4 :
(P α )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Min 3x 1 + 4x 2 + x 3 + x 4
x 1 + x 2 + x 3 − x 4 2
−2x 1 + 2x 2 + x 3 + x 4 α
x 1 0, . . . , x 4 0
, où α est un paramètre réel.
1 ◦ ) Écrire le problème dual (D α ) de (P α ).
2 ◦ ) Résoudre (D α ) suivant les valeurs de α ; en déduire les solutions de (P α ).
Solution : 1 ◦ ) (D α ) se formule comme suit :
(D α )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Max 2y 1 + αy 2
y 1 − 2y 2 3, y 1 + 2y 2 4,
y 1 + y 2 1, −y 1 + y 2 1,
y 1 0, y 2 0.
206