Chapitre 8 • La pro gram ma tion linéaire
338
0
0
0
0
0
0
0
0
0
0
4
3
3
2
3
1
1
1
1
1
1
1
1
1
1
2
2
1
2
2
i
z 19
j
8
On a obtenu, en une ité ra tion, lors de la phase 2, l’opti mum du PL d’ori gine :
x 1 5 4 , x 2 5 0 , x 3 5 1 et z* 5 19. (x 2 5 8 ; x 1 5 x 3 5 0).
8.5.6 Variante. Méthode du « grand M »
Nous don nons cette variante à titre d’exer cice seule ment : les logi ciels de P.L. uti
lisant la méthode des 2 phases.
On peut com bi ner les deux phases 1 et 2 en intro dui sant les variables arti fi cielles
comme ci dessus dans les contraintes, puis en les intro dui sant aussi dans la fonc tion
éco no mique d’ori gine : chaque variable arti fi cielle y sera munie d’un coef fi cient –M,
« très néga tif » : c’est àdire qu’on peut prendre la valeur M arbi trai re ment supé
rieure à tout autre coef fi cient inter ve nant dans le PL.
Ainsi, si une variable arti fi cielle n’est pas nulle, elle don nera à cette nou velle
fonc tion éco no mique une valeur numé rique très « mau vaise » car très néga tive (de
valeur abso lue très grande).
En maxi mi sant la nou velle fonc tion éco no mique, notée z , l’algorithme aura ten
dance à faire sor tir les variables arti fi cielles de la base ; si, à l’opti mum de ce PL,
toutes les variables arti fi cielles sont nulles, alors z coïn cide avec la fonc tion éco no
mique d’ori gine z. Mais si à l’opti mum du PL (avec la fonc tion éco no mique z ) une
ou plu sieurs variable(s) arti fi cielle(s) est (sont) en base et non nulles, cela signi fie
que le PL d’ori gine est impos sible.
Ainsi, pour notre exemple, [MAX] z 5 z 2 Mx ar 2 Mx as ,
soit : [MAX] z 5 4x 1 1 5x 2 1 3x 3 2 Mx ar 2 Mx as .
La base ini tiale étant asso ciée aux variables x 1 , x ar et x as , l’expres sion de z , en fonc
tion des variables hors base ini tia le ment, est :
z 5 4x 1 1 5x 2 1 3x 3 2 M(1 2 2x 1 2 x 2 2 x 3 1 x 2 ) 2 M(4 2 x 1 2 x 2 )
z 5 25M 1 (3M 1 4)x 1 1 (2M 1 5)x 2 1 (M 1 3)x 3 2 Mx 2
La valeur initiale de la fonction économique est donc : 25M : très négative.
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
338
0
0
0
0
0
0
0
0
0
0
4
3
3
2
3
1
1
1
1
1
1
1
1
1
1
2
2
1
2
2
i
z 19
j
8
On a obtenu, en une ité ra tion, lors de la phase 2, l’opti mum du PL d’ori gine :
x 1 5 4 , x 2 5 0 , x 3 5 1 et z* 5 19. (x 2 5 8 ; x 1 5 x 3 5 0).
8.5.6 Variante. Méthode du « grand M »
Nous don nons cette variante à titre d’exer cice seule ment : les logi ciels de P.L. uti
lisant la méthode des 2 phases.
On peut com bi ner les deux phases 1 et 2 en intro dui sant les variables arti fi cielles
comme ci dessus dans les contraintes, puis en les intro dui sant aussi dans la fonc tion
éco no mique d’ori gine : chaque variable arti fi cielle y sera munie d’un coef fi cient –M,
« très néga tif » : c’est àdire qu’on peut prendre la valeur M arbi trai re ment supé
rieure à tout autre coef fi cient inter ve nant dans le PL.
Ainsi, si une variable arti fi cielle n’est pas nulle, elle don nera à cette nou velle
fonc tion éco no mique une valeur numé rique très « mau vaise » car très néga tive (de
valeur abso lue très grande).
En maxi mi sant la nou velle fonc tion éco no mique, notée z , l’algorithme aura ten
dance à faire sor tir les variables arti fi cielles de la base ; si, à l’opti mum de ce PL,
toutes les variables arti fi cielles sont nulles, alors z coïn cide avec la fonc tion éco no
mique d’ori gine z. Mais si à l’opti mum du PL (avec la fonc tion éco no mique z ) une
ou plu sieurs variable(s) arti fi cielle(s) est (sont) en base et non nulles, cela signi fie
que le PL d’ori gine est impos sible.
Ainsi, pour notre exemple, [MAX] z 5 z 2 Mx ar 2 Mx as ,
soit : [MAX] z 5 4x 1 1 5x 2 1 3x 3 2 Mx ar 2 Mx as .
La base ini tiale étant asso ciée aux variables x 1 , x ar et x as , l’expres sion de z , en fonc
tion des variables hors base ini tia le ment, est :
z 5 4x 1 1 5x 2 1 3x 3 2 M(1 2 2x 1 2 x 2 2 x 3 1 x 2 ) 2 M(4 2 x 1 2 x 2 )
z 5 25M 1 (3M 1 4)x 1 1 (2M 1 5)x 2 1 (M 1 3)x 3 2 Mx 2
La valeur initiale de la fonction économique est donc : 25M : très négative.
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ