Chapitre 8 • La programmation linéaire
346
En mul ti pliant par –1 cha cune des contraintes du « dual du dual », ainsi que sa fonc -
tion éco no mique (ce qui la ramène à une maxi mi sa tion), le lec teur reconnaî tra... le
primal (au nom près des variables : nom mées t j ici, au lieu de x j pré cé dem ment).
D’une manière géné rale, on a le théorème suivant :
Théo rème 1 : le dual du dual d’un pro gramme linéaire, coïn cide avec le primal.
2)Onmontreaussique:Théorème 2 : pour deux pro grammes linéaires en dua lité (un primal et un dual),
un et un seul des trois cas sui vants se trouve réa lisé :
• Cas1.Leprimaletledualontdessolu tionsopti malesfinies,res pec ti ve mentx* et
y*. Alors, à l’opti mum, les valeurs des fonc tions éco no miques du primal et du dual
sont égales :
z
*
= z9, soit c ∙ x* = y* ∙ b
Ce cas est, de loin, le plus fré quent dans les appli ca tions concrètes ; c’est le cas de
notre exemple, comme nous allons le voir plus loin.
• Cas2.L’undesdeuxPLn’apasdesolu tionadmis sible(c’est-
à-direqu’ilestimpos -
sible),l’autreenadmet
tantaumoinsune,maissonopti
mumestrejetéàl’infini.
• Cas3.Nileprimalniledualn’ontdesolu tionsadmis sibles.
– Illus tra tion du cas 1
Le lec teur se repor tera à notre exemple du pro blème de l’ate lier.
– Illus tra tion du cas 2
(P) d
–x 1 +
x 2 <
1
(D) d
–y 1 –
y 2 >
3
–x 1 – 2x 2 <
–2
y 1 – 2y 2 >
3
x 1 ,
x 2 >
0
y 1 ,
y 2 >
0
3x 1 + 3x 2 = z [max]
y 1 – 2y 2 = z9 [min]
Onvéri fie(parexemplegra phi que ment)quel’opti mumdeΡestrejetéàl’infini.Ledual est impos sible (son polyèdre est vide) car la somme de ses deux contraintes
explicites four nit : 23y 2 > 6, soit : y 2 < 22, qui est contra dic toire avec y 2 > 0.
– Illus tra tion du cas 3
(P) d
x 1 –
x 2 <
3
(1)
(D) d
y 1 –
y 2 >
2
(19)
–x 1 +
x 2 <
– 4
(2)
– y 1 +
y 2 >
1
(29)
x 1 ,
x 2 >
0
y 1 ,
y 2 >
0
2x 1 +
x 2 = z [max]
3y 1 – 4y 2 = z9 [min]
(P) n’a pas de solu tion admis sible : (1) + (2) entraîne 0 < 21 : impos sible.
(D) non plus, car (1r) + (2r) entraîne 0 > 3 : impos sible.
346
En mul ti pliant par –1 cha cune des contraintes du « dual du dual », ainsi que sa fonc -
tion éco no mique (ce qui la ramène à une maxi mi sa tion), le lec teur reconnaî tra... le
primal (au nom près des variables : nom mées t j ici, au lieu de x j pré cé dem ment).
D’une manière géné rale, on a le théorème suivant :
Théo rème 1 : le dual du dual d’un pro gramme linéaire, coïn cide avec le primal.
2)Onmontreaussique:Théorème 2 : pour deux pro grammes linéaires en dua lité (un primal et un dual),
un et un seul des trois cas sui vants se trouve réa lisé :
• Cas1.Leprimaletledualontdessolu tionsopti malesfinies,res pec ti ve mentx* et
y*. Alors, à l’opti mum, les valeurs des fonc tions éco no miques du primal et du dual
sont égales :
z
*
= z9, soit c ∙ x* = y* ∙ b
Ce cas est, de loin, le plus fré quent dans les appli ca tions concrètes ; c’est le cas de
notre exemple, comme nous allons le voir plus loin.
• Cas2.L’undesdeuxPLn’apasdesolu tionadmis sible(c’est-
à-direqu’ilestimpos -
sible),l’autreenadmet
tantaumoinsune,maissonopti
mumestrejetéàl’infini.
• Cas3.Nileprimalniledualn’ontdesolu tionsadmis sibles.
– Illus tra tion du cas 1
Le lec teur se repor tera à notre exemple du pro blème de l’ate lier.
– Illus tra tion du cas 2
(P) d
–x 1 +
x 2 <
1
(D) d
–y 1 –
y 2 >
3
–x 1 – 2x 2 <
–2
y 1 – 2y 2 >
3
x 1 ,
x 2 >
0
y 1 ,
y 2 >
0
3x 1 + 3x 2 = z [max]
y 1 – 2y 2 = z9 [min]
Onvéri fie(parexemplegra phi que ment)quel’opti mumdeΡestrejetéàl’infini.Ledual est impos sible (son polyèdre est vide) car la somme de ses deux contraintes
explicites four nit : 23y 2 > 6, soit : y 2 < 22, qui est contra dic toire avec y 2 > 0.
– Illus tra tion du cas 3
(P) d
x 1 –
x 2 <
3
(1)
(D) d
y 1 –
y 2 >
2
(19)
–x 1 +
x 2 <
– 4
(2)
– y 1 +
y 2 >
1
(29)
x 1 ,
x 2 >
0
y 1 ,
y 2 >
0
2x 1 +
x 2 = z [max]
3y 1 – 4y 2 = z9 [min]
(P) n’a pas de solu tion admis sible : (1) + (2) entraîne 0 < 21 : impos sible.
(D) non plus, car (1r) + (2r) entraîne 0 > 3 : impos sible.