Chapitre 8 • La programmation linéaire
358
cette­nou­ ­ velle­contrainte­une­variable­arti­ ­ fi­ ­ cielle,­notée a 2 , pour com plé ter la base
pré cé dente b 5 {x 1 , x 2 };­ en­ effet,­ nous­ avons­ désor­ ­ mais­ 3­ contraintes­ expli­ ­ cites.Comme plus haut : La nou velle contrainte devient :
1
2
x 4 2 s 2 1 a 2 5
1
2
et la
fonc tion éco no mique (cf 8.5.6) :
z r 5 x 1 1 x 2 2 M # a 2 (où M est­un­coef­ ­ fi­ ­ cient­posi­ ­ tif­très­grand);­a 2 étant une variable de base, il convient d’abord d’expri mer z r en fonc tion des variables hors- base,
soit : x 3 , x 4 et s 2 ; ce qui donne : zr 5 a
11
4
2
M
2
b 2
1
12
x 3 1 a
M
2
2
5
6
bx 4 .
0
0
0
0
0
0
0
0
0
0
0
0
0
4
2
0
0
0
1
1
1
1
1
11
1
1
↑

↑
e
x 1
x 1
x 2
x 2
a 2
a 2
z  
s 2
c i
x i
c j
x 3
x 4
5/4
1/ 3
M
M
M
M
M/ 2
1/ 12
1
1/ 12
5/ 6
1/2
3/ 2
1/ 2
1/2



En­une­ité­ ­ ra­ ­ tion,­on­fait­sor­ ­ tir­de­la­base­cou­ ­ rante­la­variable­arti­ ­ fi­ ­ cielle­a 2 et on obtient
une­base­sans­variable­arti­ ­ fi­ ­ cielle­(a 2 sera donc prise nulle ulté rieu re ment) :
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
1
1
23
1
1
1
2
1
1
1
1
1
x 1
x 1
x 2
x 2
a 2
z  
s 2
c i
x i
c j
x 3
x 4
x 4
2/ 3
M
M
1/ 12
2/ 3
5/ 3
5/ 3
1
2
1/ 12
11/ 12
(comme­la­variable­arti­ ­ fi­ ­ cielle­a 2 est nulle, on a : z coïncide désormais avec z').
Dans la suite on sup pri mera donc la colonne a 2 de ce tableau.
La variable de base x 1 vaut
11
12
; x 1 n’étant pas entière, on peut en déduire une nou -
velle tron ca ture :
1
12
x 3 1
2
3
s 2 2 t 1 5
11
12
, où t 1 est une nouvelle variable d’écart.