8.7 Dua lité
347
© Dunod – Toute reproduction non autorisée est un délit.
8.7.3 Cri tère d’optimalité
Sup po sons que le primal et le dual aient des solu tions admis sibles (cas 1).
Soit x une solu tion admis sible du primal et y une solu tion admis sible du dual (ces
solu tionsn’étantpasnéces sai re mentdessolu tionsdebase).Onmontreaisément
(1)
que la valeur de la fonc tion éco no mique du primal pour tout x est majo rée par celle
du dual pour tout y :
z (x) < z r(y) soit : c # x < y # b.
Onendéduitaisé ment(parl’absurde)ques’ilexisteunesolu tionadmis sible x
,
du
primal et une solu tion admis sible du dual y
,
telles que :
z ( x
,
) 5 z r( y
,
) soit : c # x
, 5 y
, # b,
alors x
,
est une solu tion opti male du primal et y
,
, une solu tion opti male du dual.
8.7.4 Cor res pon dance entre l’opti mum du primal
et l’opti mum du dual (cas 1)
Nous allons tout d’abord résoudre le pro gramme dual du pro blème de l’ate lier. Le
lec teurobser veraquelesvariablesd’écartdoiventpré sen teruncoef fi cient–1,enrai son du sens des inéga li tés au dual : > ; on rap pelle que les variables d’écart
doivent être non néga tives. Il se pose le pro blème de la solu tion de départ (de la
base ini tiale). Dans la réso lu tion du primal nous avions annulé les variables x 1 , x 2
et x 3 (variables hors- base) et obtenu x 4 = 1 000, x 5 = 500, x 6 = 1 500 et x 7 = 6 750,
c’est- à-dire que la base ini tiale était for mée des m = 4 variables d’écart ; de plus
les colonnes A 4 , A 5 , A 6 et Α 7 étaient uni taires (et jux ta po sées, consti tuant une matrice iden tité 4 3 4). Mais, au dual, si l’on pra ti quait de même, on aurait y 5 = – 4,
y 6 = –12 et y 7 = –3 : non admis sible. Cepen dant, pour la réso lu tion du dual, nous
avons une base ini tiale admissible évi dente puisque les colonnes 1, 2 et 3 du dual
sont uni taires : les variables y 1 , y 2 et y 3 forment cette base et la matrice de base est :
B 5 I.
Il convient alors d’expri mer z r uni que ment en fonc tion des variables hors- base,
c’est- à-dire y 4 , y 5 , y 6 et y 7 :
z r 5 1 000y 1 1 500y 2 1 1 500y 3 1 6 750y 4
zr 5 1 000 # (4 2 3y 4 1 y 5 ) 1 500 # (12 2 6y 4 1 y 6 ) 1 1 500 # (3 2 2y 4 1 y 7 ) 1 6 750y 4
z r 5 14 500 2 2 250y 4 1 1 000y 5 1 500y 6 1 1 500y 7
Enfinaulieudeminimi serz r, nous maxi mi se rons son opposé (ce qui est équi va lent) :
z s 5 2z r 5 214 500 1 2 250y 4 2 1 000y 5 2 500y 6 2 1 500y 7 .
1. En effet : 3A # x < b et y > 04 entraîne : y # (A # x) < y # b (5 z r(y)) et
3y # A > c et x > 04 entraîne : (y # A) # x > c # x (5 z (x)), d’où : z (x) < y # A # x < z r(y).
(1)
347
© Dunod – Toute reproduction non autorisée est un délit.
8.7.3 Cri tère d’optimalité
Sup po sons que le primal et le dual aient des solu tions admis sibles (cas 1).
Soit x une solu tion admis sible du primal et y une solu tion admis sible du dual (ces
solu tionsn’étantpasnéces sai re mentdessolu tionsdebase).Onmontreaisément
(1)
que la valeur de la fonc tion éco no mique du primal pour tout x est majo rée par celle
du dual pour tout y :
z (x) < z r(y) soit : c # x < y # b.
Onendéduitaisé ment(parl’absurde)ques’ilexisteunesolu tionadmis sible x
,
du
primal et une solu tion admis sible du dual y
,
telles que :
z ( x
,
) 5 z r( y
,
) soit : c # x
, 5 y
, # b,
alors x
,
est une solu tion opti male du primal et y
,
, une solu tion opti male du dual.
8.7.4 Cor res pon dance entre l’opti mum du primal
et l’opti mum du dual (cas 1)
Nous allons tout d’abord résoudre le pro gramme dual du pro blème de l’ate lier. Le
lec teurobser veraquelesvariablesd’écartdoiventpré sen teruncoef fi cient–1,enrai son du sens des inéga li tés au dual : > ; on rap pelle que les variables d’écart
doivent être non néga tives. Il se pose le pro blème de la solu tion de départ (de la
base ini tiale). Dans la réso lu tion du primal nous avions annulé les variables x 1 , x 2
et x 3 (variables hors- base) et obtenu x 4 = 1 000, x 5 = 500, x 6 = 1 500 et x 7 = 6 750,
c’est- à-dire que la base ini tiale était for mée des m = 4 variables d’écart ; de plus
les colonnes A 4 , A 5 , A 6 et Α 7 étaient uni taires (et jux ta po sées, consti tuant une matrice iden tité 4 3 4). Mais, au dual, si l’on pra ti quait de même, on aurait y 5 = – 4,
y 6 = –12 et y 7 = –3 : non admis sible. Cepen dant, pour la réso lu tion du dual, nous
avons une base ini tiale admissible évi dente puisque les colonnes 1, 2 et 3 du dual
sont uni taires : les variables y 1 , y 2 et y 3 forment cette base et la matrice de base est :
B 5 I.
Il convient alors d’expri mer z r uni que ment en fonc tion des variables hors- base,
c’est- à-dire y 4 , y 5 , y 6 et y 7 :
z r 5 1 000y 1 1 500y 2 1 1 500y 3 1 6 750y 4
zr 5 1 000 # (4 2 3y 4 1 y 5 ) 1 500 # (12 2 6y 4 1 y 6 ) 1 1 500 # (3 2 2y 4 1 y 7 ) 1 6 750y 4
z r 5 14 500 2 2 250y 4 1 1 000y 5 1 500y 6 1 1 500y 7
Enfinaulieudeminimi serz r, nous maxi mi se rons son opposé (ce qui est équi va lent) :
z s 5 2z r 5 214 500 1 2 250y 4 2 1 000y 5 2 500y 6 2 1 500y 7 .
1. En effet : 3A # x < b et y > 04 entraîne : y # (A # x) < y # b (5 z r(y)) et
3y # A > c et x > 04 entraîne : (y # A) # x > c # x (5 z (x)), d’où : z (x) < y # A # x < z r(y).
(1)