Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Réécrivons ce résultat pour la formulation symétrique de programmes linéaires
en dualité (de (5.17)) :
(P)
⎧
⎨
⎩
Maximiser c, x
Ax b
x 0
(D)
⎧
⎨
⎩
Minimiser b, y
A y c
y 0.
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
et
(a i , x − b i ) y i = 0
pour tout i = 1, . . . , m
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
,
où les a i (resp. les a
j ) désignent les vecteurs-lignes de A (resp. de A ).
Toujours pour le couple (P) – (D) de (5.17), considérons le lagrangien
L : R n × R m → R
(x, y) −→ L(x, y) := c, x − −y, Ax − b
= c, x −
m
i=1
y i (a i , x − b i ) .
(Ici, dans (P), on maximise c, x – ou on minimise − −c, x – ce qui explique le
changement de signe par rapport au formalisme du chapitre IV et induit quelques
adaptations dans les définitions et résultats qui y sont rappelés.)
Un point-selle (ou col) de L sur (R + )
n × (R + )
m est un couple (x, y) ∈ (R + )
n ×
(R + )
m tel que
L(x, y) L(x, y) L(x, y) pour tout (x, y) ∈
R
+
n ×
R
+
m
(d’où L(x, y) = max x0 L(x, y) = min
y0
L(x, y)).
Th´ eor` eme. Soient x ∈ (R + )
n et y ∈ (R + )
m . Il y a alors équivalence entre les
assertions suivantes :
(i) x est une solution de (P) et y est une solution de (D) ;
(ii) (x, y) est un point-selle de L sur (R + )
n × (R + )
m .
Lorsque ceci a lieu
L(x, y) = max dans (P) = min dans (D).
174