8.7 Dua lité
351
© Dunod – Toute reproduction non autorisée est un délit.
Les rela tions d’exclu sion per mettent :
• de trou ver aisément l’opti mum de dual, si l’on connaît l’opti mum du primal etréci pro que ment (on sup pose évi dem ment ici que l’on ne connaît pas le tableau opti -
mal, sinon on appli que rait la règle de cor res pon dance du para graphe pré cé dent!),
comme suit :
Repre nons le sous- problème de notre exemple de l’ate lier à n = 2 variables :
(P) 3x 1 < 1 000 ; x 2 < 500 ; x 1 1 2x 2 < 1 750 ; x 1 , x 2 > 0 ; max z 5 4x 1 1 12x 2 4
il a pour dual :
(D)3y 1 1 y 3 > 4 ; y 2 1 2y 3 > 12 ; y 1 , y 2 . y 3 > 0 ; min zr 5 1 000y 1 1 500y 2 1 1750y 3 4.
Les rela tions d’exclu sion s’écrivent :
b
y 1 ? (1 000 2 x 1 ) 5 0 ; y 2 ? (500 2 x 2 ) 5 0 ; y 3 ? (1 750 2 x 1 2 2x 2 ) 5 0
(1)
(y 1 1 y 3 2 4) ? x 1 5 0 ; (y 2 1 2y 3 2 12 ) ? x 2 5 0
(2)
Onarésolu(gra phi que ment)(P) : x 1
* 5 750 , x 2
* 5 500 , z
* 5 9 000
Repor tons ces valeurs dans les rela tions d’exclu sion ; il vient le sys tème linéaire :
b
y 1 ? (1 000 2 750) 5 0 ; y 2 ? (500 2 500) 5 0 ; y 3 ? (1 750 2 1 750) 5 0
(1)
(y 1 1 y 3 2 4) ? 750 5 0 ; (y 2 1 2y 3 2 12 ) ? 500 5 0
(2)
Ontrouveaisé ment:y 1 = 0 et, en repor tant dans (2) : y 3 = 4, y 2 =4.Onsaitenoutrequ’àl’opti mum z r = z, d’où z r=9000.L’optimumde(D)adoncétéfacilementobtenu.
• Lesrela tionsd’exclu sionper mettentaussidetestersiunesolu tionadmis sibleduprimal(ou du dual) estopti male ou pas. Il suf fit alors derepor terlesvaleurs desvariables du primal (resp. du dual) dans le sys tème des rela tions d’exclu sion, puis de
déter mi ner si l’on obtient une solu tion admis sible du dual (resp. du primal) : si oui,
la solu tion tes tée du primal est opti male, sinon elle ne l’est pas. Ainsi, sur le même
exemple, tes tons si la solu tion admis sible x 1 = 850 ; x 2 = 450 est opti male (certes,
nous connais sons d’avance le résul tat, puisque la solu tion opti male du pro blème de
l’ate lier est unique, mais omet tons le pro vi soi re ment). Il vient :
y 1 ∙(10002 850) = 0 ; y 2 ∙(5002 450) = 0 ; y 3 ∙(17502 1 750) = 0 , d’où
y 1 = y 2 = 0. Puis : (y 3 24)∙850=0et(2y 3 212)∙450=0.Ilyacontra dic tion:y 3
ne sau rait être égal à la fois à 4 et à... 6.
La solution admissible de (P) : x 1 5 850 et x 2 5 450 n’est donc pas optimale.
Pour ter mi ner sou li gnons que les rela tions d’exclu sion s’appliquent à des solu tions
admis sibles de (P) et (D), mais pas néces sai re ment de base (comme dans notre cal -
cul ci- dessus). Ainsi pour l’exemple du 8.3.1, pour lequel tous les points du segment
[B,C]sontoptimaux,lelecteurpourravérifierainsiquelasolutionx 1 = 2,2 ; x 2 = 4,7 ;
x 1 5 1,2 (qui n’est pas de base) est optimale : le point (2,2 ; 4,7) étant sur [B, C].
351
© Dunod – Toute reproduction non autorisée est un délit.
Les rela tions d’exclu sion per mettent :
• de trou ver aisément l’opti mum de dual, si l’on connaît l’opti mum du primal etréci pro que ment (on sup pose évi dem ment ici que l’on ne connaît pas le tableau opti -
mal, sinon on appli que rait la règle de cor res pon dance du para graphe pré cé dent!),
comme suit :
Repre nons le sous- problème de notre exemple de l’ate lier à n = 2 variables :
(P) 3x 1 < 1 000 ; x 2 < 500 ; x 1 1 2x 2 < 1 750 ; x 1 , x 2 > 0 ; max z 5 4x 1 1 12x 2 4
il a pour dual :
(D)3y 1 1 y 3 > 4 ; y 2 1 2y 3 > 12 ; y 1 , y 2 . y 3 > 0 ; min zr 5 1 000y 1 1 500y 2 1 1750y 3 4.
Les rela tions d’exclu sion s’écrivent :
b
y 1 ? (1 000 2 x 1 ) 5 0 ; y 2 ? (500 2 x 2 ) 5 0 ; y 3 ? (1 750 2 x 1 2 2x 2 ) 5 0
(1)
(y 1 1 y 3 2 4) ? x 1 5 0 ; (y 2 1 2y 3 2 12 ) ? x 2 5 0
(2)
Onarésolu(gra phi que ment)(P) : x 1
* 5 750 , x 2
* 5 500 , z
* 5 9 000
Repor tons ces valeurs dans les rela tions d’exclu sion ; il vient le sys tème linéaire :
b
y 1 ? (1 000 2 750) 5 0 ; y 2 ? (500 2 500) 5 0 ; y 3 ? (1 750 2 1 750) 5 0
(1)
(y 1 1 y 3 2 4) ? 750 5 0 ; (y 2 1 2y 3 2 12 ) ? 500 5 0
(2)
Ontrouveaisé ment:y 1 = 0 et, en repor tant dans (2) : y 3 = 4, y 2 =4.Onsaitenoutrequ’àl’opti mum z r = z, d’où z r=9000.L’optimumde(D)adoncétéfacilementobtenu.
• Lesrela tionsd’exclu sionper mettentaussidetestersiunesolu tionadmis sibleduprimal(ou du dual) estopti male ou pas. Il suf fit alors derepor terlesvaleurs desvariables du primal (resp. du dual) dans le sys tème des rela tions d’exclu sion, puis de
déter mi ner si l’on obtient une solu tion admis sible du dual (resp. du primal) : si oui,
la solu tion tes tée du primal est opti male, sinon elle ne l’est pas. Ainsi, sur le même
exemple, tes tons si la solu tion admis sible x 1 = 850 ; x 2 = 450 est opti male (certes,
nous connais sons d’avance le résul tat, puisque la solu tion opti male du pro blème de
l’ate lier est unique, mais omet tons le pro vi soi re ment). Il vient :
y 1 ∙(10002 850) = 0 ; y 2 ∙(5002 450) = 0 ; y 3 ∙(17502 1 750) = 0 , d’où
y 1 = y 2 = 0. Puis : (y 3 24)∙850=0et(2y 3 212)∙450=0.Ilyacontra dic tion:y 3
ne sau rait être égal à la fois à 4 et à... 6.
La solution admissible de (P) : x 1 5 850 et x 2 5 450 n’est donc pas optimale.
Pour ter mi ner sou li gnons que les rela tions d’exclu sion s’appliquent à des solu tions
admis sibles de (P) et (D), mais pas néces sai re ment de base (comme dans notre cal -
cul ci- dessus). Ainsi pour l’exemple du 8.3.1, pour lequel tous les points du segment
[B,C]sontoptimaux,lelecteurpourravérifierainsiquelasolutionx 1 = 2,2 ; x 2 = 4,7 ;
x 1 5 1,2 (qui n’est pas de base) est optimale : le point (2,2 ; 4,7) étant sur [B, C].