Dualité
71
3.4. THEOREMES SUR LA DUALITE
Nous allons examiner un certain nombre de théorèmes importants mettant en évidence
les rapports étroits qui lient un programme linéaire à son dual.
Théorème I : Si un programme linéaire et son dual admettent tous deux une
solution réalisable, chacun d'eux a un optimum fini.
Soit un programme linéaire et son dual :
Primal
Dual
(I)
(II)
b
Ax
c
yA
0
x
0
y
Soit et
deux solutions réalisables respectivement de (I) et (II).
On a :
mais comme
est positif, on peut écrire aussi
donc
(1)
De même, puisque est la solution réalisable de (II), on a :
c
A
y o
et comme est positif ou nul :
o
o
o
cx
Ax
y
d'où
(2)
Au total, on a l'inégalité très importante :
(3)
pour toute solution réalisable de (I) et toute solution réalisable
de (II).
En conséquence, s'il existe une solution réalisable
de (II), toute solution réalisable de
(I), si elle existe, est telle que
La fonction est donc bornée sur le domaine des solutions réalisables de (I) et y admet
donc un maximum fini. De même, l'existence d'une solution réalisable de (I) implique
que admet un minimum fini sur le domaine des solutions réalisables de (II).
Si max est le maximum de et min le minimum de , on a
(4)
pour toute solution réalisable de (I) et toute solution réalisable de (II).