V.3. La dualité en programmation linéaire
Ainsi un polyèdre convexe fermé C décrit comme en (5.16) a toujours des
points extrémaux, et si la forme linéaire c, ·· est majorée sur C, il y a toujours
au moins un point extrémal maximisant c, ·· sur C.
V.3. La dualité en programmation linéaire
V.3.1. Formulations de problèmes duaux
Commençons par un programme linéaire écrit sous forme canonique :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax b
x 0
→ (D)
⎧
⎪ ⎨
⎪ ⎩
Minimiser b, y
A y c
y 0
(5.17)
(D) est appelé problème dual (ou programme linéaire dual ) de (P).
Dans le cas de programmes linéaires (P) écrits sous forme standard, les problèmes duaux (D) se présentent comme suit :
(P)
⎧
⎪ ⎨
⎪ ⎩
Maximiser c, x
Ax = b
x 0
→ (D)
⎧
⎪ ⎨
⎪ ⎩
Minimiser b, y
A y c
(5.18)
(P)
⎧
⎪ ⎨
⎪ ⎩
Minimiser c, x
Ax = b
x 0
→ (D)
⎧
⎪ ⎨
⎪ ⎩
Maximiser b, y
A y c
(5.19)
À côté de la transformation « symétrique » (5.17), retenons dans les transformations « asymétriques » (5.18) et (5.19) les points suivants : « maximiser »
devient « minimiser » et vice versa ; les contraintes du type égalité deviennent des
contraintes du type inégalité, il n’y a plus de conditions de signe sur les variables
duales y.
171