V.3. La dualité en programmation linéaire
L’ensemble-contrainte
L’ensemble
de (P) n’est pas vide
contrainte
(P) a des
(P) n’a pas
de (P)
solutions de solutions
est vide
L’ensemble- (D) a
O.K.
contrainte
des
max = min Impossible
Impossible
de (D)
solutions (P) (D)
n’est pas
D n’a
inf dans (D) =
vide
pas de Impossible Impossible
sup dans (P) =
solutions
−∞
sup dans (P) Cas « pathologique »
L’ensemble-contrainte Impossible
=
possible :
de (D)
inf dans (D) sup dans (P) = −∞
est vide
= +∞
inf dans (D) = +∞
V.3.3. Caractérisation simultanée des solutions du problème primal
et du problème dual
Considérons par exemple le couple de problèmes en dualité de (5.19) :
(P)
⎧
⎨
⎩
Minimiser c, x
Ax = b
x 0
et (D)
⎧
⎨
⎩
Maximiser b, y
A y c.
Th´ eor` eme. Soient x et y des points admissibles pour (P) et (D) respectivement.
Alors :
x est solution de (P)
et y est solution de (D)
⇔
a
j , y − c j
x j = 0
pour tout j = 1, . . . , n
,
où les a
j désignent les vecteurs-lignes de A .
Une manière équivalente de dire ce qui est exprimé dans l’assertion de droite
de l’équivalence est :
x j > 0 ⇒
a
j , y
= c j
et
a
j , y
< c j ⇒ x j = 0
.
173