Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
V.3.2. Relations entre les valeurs optimales et les solutions
de programmes linéaires en dualité
Th´ eor` eme. Considérons
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax b
x 0
et
(D)
⎧
⎪ ⎨
⎪ ⎩
Minimiser b, y
A y c
y 0.
(i) Si x est admissible pour (P) et si y est admissible pour (D), alors c, x
b, y .
(ii) Si x est admissible pour (P), si y est admissible pour (D) et si c, x =
b, y, alors x est une solution de (P) et y est une solution de (D).
Revoyons ce même théorème avec une autre forme de (P), et donc de (D).
Th´ eor` eme. Considérons
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser c, x
Ax = b
x 0
et
(D)
⎧
⎨
⎩
Maximiser b, y
A y c.
(i) Si x est admissible pour (P) et si y est admissible pour (D), alors c, x
b, y .
(ii) Si x est admissible pour (P), si y est admissible pour (D) et si c, x =
b, y, alors x et y sont solutions de (P) et de (D) respectivement.
Revenons au couple (P) – (D) de problèmes en dualité du premier théorème,
c’est-à-dire celui explicité en (5.17) ; on a à leur sujet le résultat fondamental
suivant :
Th´ eor` eme. (i) Si l’un des problèmes (P) ou (D) a une valeur optimale finie, alors
il en est de même de l’autre, et les valeurs optimales sont égales.
(ii) Si le supremum dans (P) est +∞, alors l’ensemble-contrainte de (D) est
vide ; si l’infimum dans (D) est −∞, alors c’est que l’ensemble-contrainte de (P)
est vide.
Tous les cas possibles sont rassemblés dans le tableau synoptique ci-dessous ;
pour englober tous les cas de valeurs optimales dans (P) ou (D) (+∞ et −∞
éventuellement), on conviendra que inf φ = +∞ et sup φ = −∞.
172