Chapitre 8 • La programmation linéaire
348
Pour la formulation de ce dual, le lecteur se reportera au paragraphe 8.7.1.
Le tableau ini tial pour ce dual est le sui vant :
3/ 2
4/ 3*
12/ 6
500
0
0
0
0
0
0
0
0
0
0
6
0
0
0
12
4
3
0
0
2
1
1
1
1
1
1
1000
1500
2250
3
↑
s
↑
e
y 1
y 1
y 2
y 2
y 3
y 3
y 4
y 5
y 6
y 7
z   14 500
i
 





(1)
La­fonc­ ­ tion­éco­ ­ no­ ­ mique­du­dual­com­ ­ porte­un­seul­coef­ ­ fi­ ­ cient­posi­ ­ tif­:­Δ 4 = 2250 :
y 4 entre en base ; puis on déter mine la variable sor tante : y 1 .­ On­obtient­ alors­ unenou velle base, dont voici le tableau :
4/ 3
1/ 3
1/ 3
2/ 3
2/ 3
750
500
0
0
0
0
0
0
2
0
0
0
4
0
0
0
0
1/ 3
1
1
2
1
1
1500
250
1
y 4
y 2
y 1
y 1
y 2
y 3
y 3
y 4
y 5
y 6
y 7
i


y 2
y 3
z   11 500

(2)
On­a­atteint­l’opti­ ­ mum­:
y 1 = 0 , y 2 = 4 , y 3 = 1/3 , y 4 = 4/3 , y 1 5 0, y 2 5 0, y 3 5 0 ; zs 5 211 500 .
Puisque z s 5 211 500, on a z r 5 11 500.
Rap pe lons le tableau opti mal du primal :
1/ 3
2/ 3
4/ 3
1/ 3
1/ 3
2/ 3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
2
2
1
1
1
1
1
1
1500
750
250
500
x 1
x 2
x 1
x 3
x 1
x 2
x 3
x 4
x 5
x 6
x 7
j
x 1
x 2
x 3
x 4
z  11 500
