359
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
À nou veau, cette contrainte n’est pas « primal- admissible » : pour l’inté grer au primal,onyajouteunevariablearti fi cielle,notéea 1 . Elle devient :
1
12
x 3 1
2
3
s 2 2 t 1 1 a 1 5
11
12
.
et la fonc tion éco no mique est z s 5 x 1 1 x 2 2 M # a 1 (à maximiser).
Le nou veau tableau est le sui vant :
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
12
1
1
1
↑
s
↑
e
x 1
x 1
x 2
x 2
a 1
t 1
a 1
z
s 2
c i
x i
c j
j
x 3
x 4
x 4
2/ 3
2/ 3
M 1
M
M
2
1
1/ 12
1/ 12
11/12
11/12
12
23 11M
3
2M 5 M
En fai sant entrer en base x 3 ,lavariablearti fi ciellea 1 sort de la base :
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
11
1
1
1
1
1
1
1
1
1
1
1
1
x 1
x 1
x 2
x 2
t 1
a 1
z 1
s 2
c i
x i
c j
x 3
x 3
x 4
x 4
M
M
1
2
1
1 1
12 12
j
ici z s 5 z car a 1 5 0.
Puisque désor mais a 1 = 0, on peut sup pri mer la colonne a 1 .Onestalorsàl’opti mumde PLNE puisque toutes les variables sont entières :
x 1 = 0 , x 2 = 1, x 3 = 11, x 4 = 1 ; z* = 1.
8.8.2 Inter pré ta tion gra phique
On aurait pu, certes, pro fi ter du fait que le PLNE ne com porte ini tia le ment que2 variables pour le résoudre gra phi que ment. Mais notre pro pos est, ici, seule ment
d’illus trer com ment, à chaque ité ra tion, la tron ca ture éli mine du domaine admis sible
© Dunod – Toute reproduction non autorisée est un délit.
8.8 Pro gramme linéaire en nombres entiers…
À nou veau, cette contrainte n’est pas « primal- admissible » : pour l’inté grer au primal,onyajouteunevariablearti fi cielle,notéea 1 . Elle devient :
1
12
x 3 1
2
3
s 2 2 t 1 1 a 1 5
11
12
.
et la fonc tion éco no mique est z s 5 x 1 1 x 2 2 M # a 1 (à maximiser).
Le nou veau tableau est le sui vant :
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
12
1
1
1
↑
s
↑
e
x 1
x 1
x 2
x 2
a 1
t 1
a 1
z
s 2
c i
x i
c j
j
x 3
x 4
x 4
2/ 3
2/ 3
M 1
M
M
2
1
1/ 12
1/ 12
11/12
11/12
12
23 11M
3
2M 5 M
En fai sant entrer en base x 3 ,lavariablearti fi ciellea 1 sort de la base :
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
11
1
1
1
1
1
1
1
1
1
1
1
1
x 1
x 1
x 2
x 2
t 1
a 1
z 1
s 2
c i
x i
c j
x 3
x 3
x 4
x 4
M
M
1
2
1
1 1
12 12
j
ici z s 5 z car a 1 5 0.
Puisque désor mais a 1 = 0, on peut sup pri mer la colonne a 1 .Onestalorsàl’opti mumde PLNE puisque toutes les variables sont entières :
x 1 = 0 , x 2 = 1, x 3 = 11, x 4 = 1 ; z* = 1.
8.8.2 Inter pré ta tion gra phique
On aurait pu, certes, pro fi ter du fait que le PLNE ne com porte ini tia le ment que2 variables pour le résoudre gra phi que ment. Mais notre pro pos est, ici, seule ment
d’illus trer com ment, à chaque ité ra tion, la tron ca ture éli mine du domaine admis sible