Solu tions des exer cices du cha pitre 8
533
© Dunod – Toute reproduction non autorisée est un délit.
Étant donné le tableau ci- après :
1
y 1
x 1
x 2
x 3
y 2
y 3
y 4
y 5
0
0
45
9
0
1
0
40
10
0
200
500
300
36 000
9 000
0
1
36
11
4
5


6
On écrit immé dia te ment le pro gramme dual :
d
y 1
1
45y 4 1
9y 5 > 4
y 2
1
40y 4 1
10y 5 > 5
y 3 1
36y 4 1
11y 5 > 6
3min4Zr 5 200y 1 1 500y 2 1 300y 3 1 36 000y 4 1 9 000y 5 .
Pour nous rame ner à une maxi mi sa tion, nous mul ti plions par 21 la fonc tion nelle Zr :
2Z r 5 2200y 1 2 500y 2 2 300y 3 2 36 000y 4 2 9 000y 5 .
L’intro duc tion des variables d’écart, pour rame ner les contraintes à des éga li tés, four nit :
d
y 1
1 45y 4 1 9y 5 2 y 1
5 4
y 2
1 40y 4 1 10y 5
2 y 2
5 5
y 3 1 36y 4 1 11y 5
2 y 3 5 6
2200y 1 2 500y 2 2 300y 3 2 36 000y 4 2 9 000y 5 1 0y 1 1 0y 2 1 0y 3 5 2Z r 3max4
Pour résoudre le pro gramme dual, il serait mal adroit (et long !) d’intro duire trois variables
arti fi cielles (après celle des variables d’écart).
En effet, on remarque que les trois variables y 1 , y 2 et y 3 forment une base évi dente (de
matrice B 5 I ). Pour dres ser le tableau asso cié à cette base, il suf fit d’expri mer 2Z r en fonc -
tion des variables qui sont alors hors- base, soit y 4 , y 5 , y 1 , y 2 , y 3 ; il vient :
2Z r 5 25 100 1 3 800y 4 1 1 100y 5 .
�200
�9 000
�500
�300
�200
1
s
1
1
0
0
0
0
0
0
1
�1
0
0
0
1
0
�1
0
0
�1
0
4
6
5
45
0
0
0
1
1
0
0
0
0
�1
�1
�19
�10
�
0
1
1
2
3
4
5
0
0
5
40
36
10
11
0
0
0
0
0
2
3
4
5
9
1
2
3
5
2
3
�500
�500
�300
�300
�200 �500 �300
�9 000
3 800 1 100
�36 000
2
3
1
2
3
� � j
�Z � ��5
1
9
�
10
9
10
9
10
9
�
11
9
11
9
1
9
4
9
5
9
↑
e