8.7 Dua lité
343
© Dunod – Toute reproduction non autorisée est un délit.
Il est de la forme : A # x < b , x > 0 , c # x 5 z [max] , que l’on appelle « forme
stan dard de pas sage au dual ». Dans ce cas, les com po santes du vec teur b ne sont
pas astreintes à être posi tives, comme lors de la réso lu tion du primal.
Pardéfi ni tion,lepro grammedualdenotreexempleest:
e
y 1
+
3y 4 >
4
y 2
+
6y 4 >
12
y 3
+
2y 4 >
3
y 1
,
y 2
,
y 3
,
y 4 >
0
1 000y 1
+
500y 2
+
1 500y 3
+
6 750y 4
=
z r [min]
Ainsi le primal com porte n = 3 variables, posi tives ou nulles et m = 4 contraintes
expli cites. Dans le pro gramme dual on a nr 5 m 5 4 variables, elles aussi posi tives
ou nulles, et m r 5 n 5 3 contraintes expli cites. L’objec tif du primal est une maxi
mi sa tion, celui du dual est une minimi sa tion. Les « seconds membres » du dual ne
sont autres que les coef fi cients de la fonc tion éco no mique du primal, c’est- à-direle vec teur c (trans posé); de même, les coef fi cients de la fonc tion éco no mique dudual ne sont autres que les « seconds membres » du primal, c’est- à-dire le vec teur b
(trans posé).
Enfinlesmatricesdescoef fi cientsduprimal:A, et celle du dual : Ar, sont :
A
m 3 n
= D
1 0 0
T ;
0 1 0
0 0 1
3 6 2
Ar
n 3 m
= C
1 0 0 3
S
0 1 0 6
0 0 1 2
OnconstatequelamatriceAr du dual est la trans po sée de la matrice du primal :
Ar 5 A
T
.
Enfin,onremarquequelescontraintes,danslaformestan dardduprimal,sontdesinéga li tés de sens : < , soit : a
n
j51
a ij # x j < b i où i = 1, 2, c , m .
Celles du dual sont de sens inverse : > , soit : a
m
i51
y i # a ij > c j où j = 1, 2, c , n .
On peut résu mer matriciellement cette règle de pas sage : le primal, sans intro duc -
tion de variable d’écart et s’il ne com porte pas de contrainte en éga lité, peut s’écrire :
(P) A # x < b , x > 0 , 3max4 z 5 c # x où b i (i 5 1, 2, c , m) est ici de signe
quel conque,
les for mats étant les sui vants : pour A : m 3 n ; pour b : m 3 1 ; pour x : 1 3 n ;
pour c : 1 3 n.
343
© Dunod – Toute reproduction non autorisée est un délit.
Il est de la forme : A # x < b , x > 0 , c # x 5 z [max] , que l’on appelle « forme
stan dard de pas sage au dual ». Dans ce cas, les com po santes du vec teur b ne sont
pas astreintes à être posi tives, comme lors de la réso lu tion du primal.
Pardéfi ni tion,lepro grammedualdenotreexempleest:
e
y 1
+
3y 4 >
4
y 2
+
6y 4 >
12
y 3
+
2y 4 >
3
y 1
,
y 2
,
y 3
,
y 4 >
0
1 000y 1
+
500y 2
+
1 500y 3
+
6 750y 4
=
z r [min]
Ainsi le primal com porte n = 3 variables, posi tives ou nulles et m = 4 contraintes
expli cites. Dans le pro gramme dual on a nr 5 m 5 4 variables, elles aussi posi tives
ou nulles, et m r 5 n 5 3 contraintes expli cites. L’objec tif du primal est une maxi
mi sa tion, celui du dual est une minimi sa tion. Les « seconds membres » du dual ne
sont autres que les coef fi cients de la fonc tion éco no mique du primal, c’est- à-direle vec teur c (trans posé); de même, les coef fi cients de la fonc tion éco no mique dudual ne sont autres que les « seconds membres » du primal, c’est- à-dire le vec teur b
(trans posé).
Enfinlesmatricesdescoef fi cientsduprimal:A, et celle du dual : Ar, sont :
A
m 3 n
= D
1 0 0
T ;
0 1 0
0 0 1
3 6 2
Ar
n 3 m
= C
1 0 0 3
S
0 1 0 6
0 0 1 2
OnconstatequelamatriceAr du dual est la trans po sée de la matrice du primal :
Ar 5 A
T
.
Enfin,onremarquequelescontraintes,danslaformestan dardduprimal,sontdesinéga li tés de sens : < , soit : a
n
j51
a ij # x j < b i où i = 1, 2, c , m .
Celles du dual sont de sens inverse : > , soit : a
m
i51
y i # a ij > c j où j = 1, 2, c , n .
On peut résu mer matriciellement cette règle de pas sage : le primal, sans intro duc -
tion de variable d’écart et s’il ne com porte pas de contrainte en éga lité, peut s’écrire :
(P) A # x < b , x > 0 , 3max4 z 5 c # x où b i (i 5 1, 2, c , m) est ici de signe
quel conque,
les for mats étant les sui vants : pour A : m 3 n ; pour b : m 3 1 ; pour x : 1 3 n ;
pour c : 1 3 n.