Chapitre 8 • La pro gram ma tion linéaire
310
Pour pou voir encore pro gres ser il convient d’expri mer les variables de base en C,
c’est àdire celles qui sont posi tives en C, en fonc tion des variables hors base en C.
Or, désor mais, x 2 est deve nue posi tive et x 5 s’est annu lée : on va donc fal loir pro cé der
à un échange : la variable x 2 entrant dans la base et la variable x 5 sor tant de la base.
Repar tons du sys tème asso cié au som met Ο et transformons le pour obte nir celui
asso cié au som met C :
O e
x 4 5 1 000 2 x 1
x 5 5 500
2 x 2
(*)
x 6 5 1 500
2 x 3
x 7 5 6 750 2 3x 1 2 6x 2 2 2x 3
z 5
0 1 4x 1 1 12x 2 1 3x 3
Nous allons expri mer les variables de bases en C (celles posi tives en ce som met)
en fonc tion des variables hors base (celles nulles en C). On com mence, à par tir de
l’équa tion de l’échange, qui est la rela tion qui a fixé la valeur maximale à don ner à
la variable entrante (ici x 2 ), à expri mer la variable entrante en fonc tion de la variable
sor tante (ici x 5 ) (et, éven tuel le ment, des autres variables hors base) ; il vient :
x 2 5 500 2 x 5 .
Puis cha cune des autres variables qui restent en base : x 4 , x 6 , x 7 , de même que z
doit être expri mée en fonc tion des variables hors base en C, c’est àdire : x 1 , x 5 et x 3 .
Pour ce faire, il suf fit dans l’expres sion de cha cune des autres variables de base en O
de subs ti tuer à la variable x 2 (la variable entrante) son expres sion issue de l’équa tion
de l’échange (ici x 2 5 500 2 x 5 ). Ici seules x 7 et z sont concernées (x 2 étant absente
de l’expression de x 4 et x 6 cidessus). Il vient donc :
@ c = {x 4 , x 2 , x 6 , x 7 } C g
x 4 5 1 000 2 x 1
(*)
x 2 5
500
2
x 5
x 6 5 1 500
2 x 3
x 7 5 6 750 2 3x 1 2 2x 3 2 6(500 2 x 5 )
5 3 750 2 3x 1 2 2x 3 1
6x 5
z 5
0 1 4x 1 1 3x 3 1 12(500 2 x 5 )
5 6 000 1 4x 1 1 3x 3 2
12x 5
On peut alors, par tant du sommet C (où le béné fice est de 6 000 euros), pra ti quer une
nou velle ité ra tion afin d’accroître ce béné fice. La variable entrante est la variable
hors base qui a le plus grand coef fi cient posi tif
1
dans l’expres sion de z en fonc tion
des variables hors base ; soit ici x 1 . On pose donc x 1 5 u où θ est posi tif crois sant, en
gar dant x 3 5 x 5 5 0 (x 3 et x 5 étant nulles en C). Il vient :
1. On pour rait se contenter de choi sir comme variable entrante, une variable hors base ayant un
coef fi cient posi tif dans l’expres sion de z en fonc tion des variables hors base.
310
Pour pou voir encore pro gres ser il convient d’expri mer les variables de base en C,
c’est àdire celles qui sont posi tives en C, en fonc tion des variables hors base en C.
Or, désor mais, x 2 est deve nue posi tive et x 5 s’est annu lée : on va donc fal loir pro cé der
à un échange : la variable x 2 entrant dans la base et la variable x 5 sor tant de la base.
Repar tons du sys tème asso cié au som met Ο et transformons le pour obte nir celui
asso cié au som met C :
O e
x 4 5 1 000 2 x 1
x 5 5 500
2 x 2
(*)
x 6 5 1 500
2 x 3
x 7 5 6 750 2 3x 1 2 6x 2 2 2x 3
z 5
0 1 4x 1 1 12x 2 1 3x 3
Nous allons expri mer les variables de bases en C (celles posi tives en ce som met)
en fonc tion des variables hors base (celles nulles en C). On com mence, à par tir de
l’équa tion de l’échange, qui est la rela tion qui a fixé la valeur maximale à don ner à
la variable entrante (ici x 2 ), à expri mer la variable entrante en fonc tion de la variable
sor tante (ici x 5 ) (et, éven tuel le ment, des autres variables hors base) ; il vient :
x 2 5 500 2 x 5 .
Puis cha cune des autres variables qui restent en base : x 4 , x 6 , x 7 , de même que z
doit être expri mée en fonc tion des variables hors base en C, c’est àdire : x 1 , x 5 et x 3 .
Pour ce faire, il suf fit dans l’expres sion de cha cune des autres variables de base en O
de subs ti tuer à la variable x 2 (la variable entrante) son expres sion issue de l’équa tion
de l’échange (ici x 2 5 500 2 x 5 ). Ici seules x 7 et z sont concernées (x 2 étant absente
de l’expression de x 4 et x 6 cidessus). Il vient donc :
@ c = {x 4 , x 2 , x 6 , x 7 } C g
x 4 5 1 000 2 x 1
(*)
x 2 5
500
2
x 5
x 6 5 1 500
2 x 3
x 7 5 6 750 2 3x 1 2 2x 3 2 6(500 2 x 5 )
5 3 750 2 3x 1 2 2x 3 1
6x 5
z 5
0 1 4x 1 1 3x 3 1 12(500 2 x 5 )
5 6 000 1 4x 1 1 3x 3 2
12x 5
On peut alors, par tant du sommet C (où le béné fice est de 6 000 euros), pra ti quer une
nou velle ité ra tion afin d’accroître ce béné fice. La variable entrante est la variable
hors base qui a le plus grand coef fi cient posi tif
1
dans l’expres sion de z en fonc tion
des variables hors base ; soit ici x 1 . On pose donc x 1 5 u où θ est posi tif crois sant, en
gar dant x 3 5 x 5 5 0 (x 3 et x 5 étant nulles en C). Il vient :
1. On pour rait se contenter de choi sir comme variable entrante, une variable hors base ayant un
coef fi cient posi tif dans l’expres sion de z en fonc tion des variables hors base.