Solu tions des exer cices du cha pitre 8
545
© Dunod – Toute reproduction non autorisée est un délit.
Le dual se pré sen te rait alors sous la forme suivante (on sup prime la contrainte (1) du
primal, ou bien 2 ce qui est équi va lent 2 on pose y 1 5 0 dans le dual ci- dessus) :
3y 2 1 2y 3 > 5 (1)
2y 2 1 y 3 > 4 (2)
3y 2 1 y 3 > 3 (3)
y 2 1 4y 3 > 1 (4)
y 2 , y 3 > 0
5y 2 1 7y 3 5 z r 3min4
NB ce dual comportant seulement 2 variables, on peut le résoudre graphiquement
De plus, l’in équa tion la plus contrai gnante du dual est la contrainte (2) ; on a en effet :
5 3 (2)    1 310y 2 1 5y 3 > 204 (2 r) 1 312y 2 1 8y 3 > 204 (1r)
où (1r) 5 4 3 (1); on a donc (2) 1 (1) puisque 12y 2 1 8y 3 > 10y 2 1 5y 3 > 20.
33y 2 1 y 3 > 3 4 (3) 1 33y 2 1 12y 3 > 3 4 (4r), où (4r) 5 3 3 (4).
Donc (3) 1 (4)
3 3 (2)    1 36y 2 1 3y 3 > 13 4 (2 r) 1 312y 2 1 4y 3 > 12 4 (3 r);
où (3 r) 5 4 3 (3). Donc (2) 1 (3)
On a donc : (2) 1 (1) et, par transitivité, (2) 1 (3) et (2) 1 (4). Ainsi les contraintes (1),
(3) et (4) sont redondantes.
La solution (y 1 5 0 ; y 2 5 2 ; y 3 5 0), pour minimiser : Zr 5 12y 1 1 5y 2 1 7y 3 est alors
évidente au sommet A, où Z' = 10.
y 3
y 2
B
Z� � 28
Z� � 21
4
3
2,5
2
2
1
A
(4)
(3)
(1)
1
(2)
1/4
5/3
0
Z� � 14
Z� � 10
� dual
Z'