78
Recherche opérationnelle
Or, aux variables principales du primal
(
correspondent les variables
d'écart du dual, et aux variables d'écart du primal correspondent les variables principales
du dual (ensemble d'indices ).
Le programme (
, dual de
, donc de
peut s'écrire, en ajoutant les variables
d'écart, et en indiçant convenablement :
L'optimum de ce programme est donné par
, puisque
et
.
On a donc ci-dessus l'écriture à l'optimum du programme dual du programme (I). En
rapprochant (16) des équations (14) et (15), on a donc :
(17)
et le théorème est ainsi démontré.
3.5. PASSAGE DU PRIMAL AU DUAL SUR UN EXEMPLE
Reprenons le cas de notre usine de camions que nous avons examiné dans les deux
chapitres précédents. Le programme s'écrivait :