V.3. La dualité en programmation linéaire
(1, 1, . . . , 1) est admissible pour (P), (0, . . . , 0) est admissible pour (D) :
donc
val(P) = val(D) ∈ R.
2 ◦ ) Soit y = (y 1 , . . . , y n ) admissible pour (D). Pour k 2,
y k + y k+1 + . . . + y n y 1 + . . . + y n (puisque tous les y i sont 0)
1
(d’après la 1 re contrainte de
type inégalité dans (D).)
< k.
D’après les relations de complémentarité liant les solutions du problème
primal (P) et celles du dual (D), on a :
⎛
⎜
⎝
x = (x 1 , . . . , x n ) solution de (P)
et
y = (y 1 , . . . , y n ) solution de (D)
⎞
⎟
⎠ ⇒
[a
k , y − c k ] · x k = 0
pour tout k = 1, . . . , n
.
Or, ici, a
k , y = y k + y k+1 + . . . + y n < k = c k pour tout k = 2, . . . , n. En
conséquence, x k = 0 pour tout k = 2, . . . , n.
3 ◦ ) Si x est solution de (P), c, x = x 1 . Résoudre (P) revient donc à minimiser x 1 sous les contraintes x 1 1, x 1 2, . . . , x 1 n et x 1 0 ; d’où
x 1 = n.
La solution de (P) est donc x = (n, 0, . . . , 0), et val(P) = val(D) = n.
*** Exercice V.25. On considère le programme linéaire suivant
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser c, x
Ax = b
x 0
, où c ∈ R
n , b ∈ R
m et A ∈ M m,n (R),
et son problème dual
(D)
Maximiser b, y
A y c
présenté sous la forme standard dans R m × R n :
( ˜
D)
⎧
⎪ ⎨
⎪ ⎩
Maximiser b, y
A y + u = c
u 0
(y ∈ R
m , u ∈ R
n ).
209