Chapitre 8 • La programmation linéaire
344
Le pro gramme dual, en notant y le vec teur-ligne 1 3 m des variables duales, est par
défi ni tion:
(D) y # A > c , y > 0 , 3min4 zr 5 y # b .
Pour notre exemple, il vient pour le primal :
D
1 0 0
T ? B
x 1
x 2
x 3
R < C
1 000
500
1 500
6 750
S ; B
x 1
x 2
x 3
R > 0 ; [max] z = [4, 12, 3] ? B
x 1
x 2
x 3
R
0 1 0
0 0 1
3 6 2
et pour le dual :
3y 1 , y 2 , y 3 , y 4 4 # D
1 0 0
0 1 0
0 0 1
3 6 2
T > 34, 12, 34 ,
3y 1 , y 2 , y 3 , y 4 4 > 0 ;
i
min z r 5 3y 1 , y 2 , y 3 , y 4 4 # C
1 000
500
1 500
6 750
S .
En déve lop pant, on retrouve l’expres sion du dual don née plus haut. ❑
À titre d’exer cice, indi quons com ment pas ser au dual pour le PL sui vant :
e
2x 1
1
x 2
2
4x 3
< 10
x 1
2
5x 2
1
6x 3
>
2
3x 1
2
2x 2
1
7x 3
5
5
x 1
,
x 2
,
x 3
>
0
3min 4
2 2x 1
1
3x 2
1
4x 3
5
z
Il convient de rame ner chaque contrainte, si néces saire, à la forme :
ax 1 1 bx 2 1 gx 3 < d (où δ, ici, peut être néga tif), de s’assu rer de ce que touteslesvariablesduprimalsontposi tivesounulles,et-enfin-derame nerlafonc tionéco no mique, si néces saire, à une maxi mi sa tion. En par ti cu lier ici on rem pla cera la
contrainte en éga lité : 3x 1 – 2x 2 + 7x 3 = 5, par deux in équa tions de sens contraires :
3x 1 2 2x 2 1 7x 3 < 5 et 3x 1 2 2x 2 1 7x 3 > 5
cette der nière in équa tion (de même que : x 1 2 5x 2 1 6x 3 > 2) doit être mul ti pliée
par –1 pour obte nir une inéga lité de la forme ax 1 1 bx 2 1 gx 3 < d ; de même on
ramène la fonc tion éco no mique à une maxi mi sa tion en la mul ti pliant par –1. Ainsi le
primal devient, sous forme standard de passage au dual :
344
Le pro gramme dual, en notant y le vec teur-ligne 1 3 m des variables duales, est par
défi ni tion:
(D) y # A > c , y > 0 , 3min4 zr 5 y # b .
Pour notre exemple, il vient pour le primal :
D
1 0 0
T ? B
x 1
x 2
x 3
R < C
1 000
500
1 500
6 750
S ; B
x 1
x 2
x 3
R > 0 ; [max] z = [4, 12, 3] ? B
x 1
x 2
x 3
R
0 1 0
0 0 1
3 6 2
et pour le dual :
3y 1 , y 2 , y 3 , y 4 4 # D
1 0 0
0 1 0
0 0 1
3 6 2
T > 34, 12, 34 ,
3y 1 , y 2 , y 3 , y 4 4 > 0 ;
i
min z r 5 3y 1 , y 2 , y 3 , y 4 4 # C
1 000
500
1 500
6 750
S .
En déve lop pant, on retrouve l’expres sion du dual don née plus haut. ❑
À titre d’exer cice, indi quons com ment pas ser au dual pour le PL sui vant :
e
2x 1
1
x 2
2
4x 3
< 10
x 1
2
5x 2
1
6x 3
>
2
3x 1
2
2x 2
1
7x 3
5
5
x 1
,
x 2
,
x 3
>
0
3min 4
2 2x 1
1
3x 2
1
4x 3
5
z
Il convient de rame ner chaque contrainte, si néces saire, à la forme :
ax 1 1 bx 2 1 gx 3 < d (où δ, ici, peut être néga tif), de s’assu rer de ce que touteslesvariablesduprimalsontposi tivesounulles,et-enfin-derame nerlafonc tionéco no mique, si néces saire, à une maxi mi sa tion. En par ti cu lier ici on rem pla cera la
contrainte en éga lité : 3x 1 – 2x 2 + 7x 3 = 5, par deux in équa tions de sens contraires :
3x 1 2 2x 2 1 7x 3 < 5 et 3x 1 2 2x 2 1 7x 3 > 5
cette der nière in équa tion (de même que : x 1 2 5x 2 1 6x 3 > 2) doit être mul ti pliée
par –1 pour obte nir une inéga lité de la forme ax 1 1 bx 2 1 gx 3 < d ; de même on
ramène la fonc tion éco no mique à une maxi mi sa tion en la mul ti pliant par –1. Ainsi le
primal devient, sous forme standard de passage au dual :