311
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
e
x 4 5 1 000 2 u
x 2 5 500
x 6 5 1 500
x 7 5 3 750 2 3u
z 5 6 000 1 4u
L’accroissement du bénéfice étant proportionnel à u, on a intérêt à prendre u le
plus grand possible.
Pour res pec ter la positivité des variables, on prend au mieux u 5 1 000: x 4 alors
s’annule et sort de la base ; l’équa tion de l’échange est x 4 5 1 000 2 x 1 ; en subs ­
ti tuant dans les autres équa tions du sys tème asso cié au som met C, à x 1 la valeur
1 000 2 x 4 , il vient, avec @ B = {x 1 , x 2 , x 6 , x 7 } :
B g
x 1
5
1 000
2
x 4
x 2
5
500
2
x 5
x 6
5
1 500
2
x 3
x 7
5
3 750
2
2x 3
2
3(1 000 2 x 4 )
1
6x 5
5
750
2
2x 3
1
3x 4
1
6x 5
(*)
z
5
6 000
1
3x 3
1
4(1 000 2 x 4 )
2
12x 5
5 10 000
1
3x 3
2
4x 4
2
12x 5
On reconnaît en effet le sys tème asso cié au som met Β : l’expres sion des variables
de base en Β : x 1 , x 2 , x 6 , x 7 , en fonc tion des variables hors base en Β : x 3 , x 4 , x 5 .
Puisque z, ainsi exprimé, com porte encore un coef fi cient posi tif : 3, sur une
variable hors base (x 3 ), on peut pra ti quer une nou velle ité ra tion ; on pose x 3 5 u
positif et crois sant, et x 4 5 x 5 5 0 ; il vient :
e
x 1 5 1 000
x 2 5 500
x 6 5 1 500 2 u
x 7 5 750 2 2u
z 5 10 000 1 3u
On prend u 5 375 : en effet la variable x 7 est la pre mière à s’annu ler quand u croît ;
x 7 est donc la variable sor tante ; l’équa tion de l’échange est :
x 7 5 750 2 2x 3 1 3x 4 1 6x 5 ;
d’où : x 3 5 375 1
3
2
x 4 1 3x 5 2
1
2
x 7 .
En subs ti tuant à x 3 cette valeur dans les autres équa tions du sys tème asso cié à B, il
vient, avec @ R = {x 1 , x 2 , x 6 , x 3 } :