V.3. La dualité en programmation linéaire
Solution : 1 ◦ ) Soit (y, z) admissible pour ( ˆ
P) ; (y, z) = (0, 0) en raison de la
contrainte d, y + δz = 1 ; donc si on suppose z = 0, alors y = 0. Mais alors
on aurait un y = 0 vérifiant y 0 et Ay 0, c’est-à-dire une direction non
nulle dans le cône asymptote de C. Ce qui contredit le caractère borné de C.
2 ◦ ) Si (y, z) est une solution de ( ˆ
P), x := y/z 0 et Ax b. Donc x ∈ C.
Montrons que x est effectivement une solution de (P).
Considérons x ∈ C ; alors le couple
x
d,x+δ ,
1
d,x+δ
est admissible
pour ( ˆ
P), et comme (y, z) est une solution de ( ˆ
P),
c, y + γz
c,
x
d, x + δ
+
γ
d, x + δ
=
c, x + γ
d, x + δ
·
Divisons le membre de gauche par 1 = d, y + δz pour obtenir
c, y + γz =
c, y + γz
d, y + δz
=
c, x + γ
d, x + δ
·
D’où le résultat annoncé.
* Exercice V.21. Considérons le programme linéaire (P) suivant dans R 5 :
(P)
⎧
⎪ ⎨
⎪ ⎩
Max c, x
Ax b
x 0
, où A =
⎡
⎢
⎣
2 1 1 0 0
1 2 0 1 0
0 1 0 0 1
⎤
⎥
⎦ , c =
⎛
⎜
⎜
⎜
⎜
⎝
4
5
0
0
0
⎞
⎟
⎟
⎟
⎟
⎠
, b =
⎛
⎝
8
7
3
⎞
⎠ .
Quel est le problème dual (D) de (P) ?
Vérifier que x = (3, 2, 0, 0, 1) et y = (1, 2, 0) sont solutions de (P) et (D)
respectivement.
Solution : Le problème dual (D) de (P) s’ecrit :
(D)
⎧
⎪ ⎨
⎪ ⎩
Min b, y
A y c
y 0.
On constate que les x et y proposés sont admissibles pour (P) et (D) respectivement, avec, de plus, l’égalité c, x = b, y = 22. En conséquence, x et
y sont solutions de (P) et (D) respectivement.
205
Solution : 1 ◦ ) Soit (y, z) admissible pour ( ˆ
P) ; (y, z) = (0, 0) en raison de la
contrainte d, y + δz = 1 ; donc si on suppose z = 0, alors y = 0. Mais alors
on aurait un y = 0 vérifiant y 0 et Ay 0, c’est-à-dire une direction non
nulle dans le cône asymptote de C. Ce qui contredit le caractère borné de C.
2 ◦ ) Si (y, z) est une solution de ( ˆ
P), x := y/z 0 et Ax b. Donc x ∈ C.
Montrons que x est effectivement une solution de (P).
Considérons x ∈ C ; alors le couple
x
d,x+δ ,
1
d,x+δ
est admissible
pour ( ˆ
P), et comme (y, z) est une solution de ( ˆ
P),
c, y + γz
c,
x
d, x + δ
+
γ
d, x + δ
=
c, x + γ
d, x + δ
·
Divisons le membre de gauche par 1 = d, y + δz pour obtenir
c, y + γz =
c, y + γz
d, y + δz
=
c, x + γ
d, x + δ
·
D’où le résultat annoncé.
* Exercice V.21. Considérons le programme linéaire (P) suivant dans R 5 :
(P)
⎧
⎪ ⎨
⎪ ⎩
Max c, x
Ax b
x 0
, où A =
⎡
⎢
⎣
2 1 1 0 0
1 2 0 1 0
0 1 0 0 1
⎤
⎥
⎦ , c =
⎛
⎜
⎜
⎜
⎜
⎝
4
5
0
0
0
⎞
⎟
⎟
⎟
⎟
⎠
, b =
⎛
⎝
8
7
3
⎞
⎠ .
Quel est le problème dual (D) de (P) ?
Vérifier que x = (3, 2, 0, 0, 1) et y = (1, 2, 0) sont solutions de (P) et (D)
respectivement.
Solution : Le problème dual (D) de (P) s’ecrit :
(D)
⎧
⎪ ⎨
⎪ ⎩
Min b, y
A y c
y 0.
On constate que les x et y proposés sont admissibles pour (P) et (D) respectivement, avec, de plus, l’égalité c, x = b, y = 22. En conséquence, x et
y sont solutions de (P) et (D) respectivement.
205