Chapitre 8 • La pro gram ma tion linéaire
312
R h
x 1 5 1 000 2 x 4
x 2 5
500
2 x 5
x 6 5 1 125 2
3
2
x 4 2 3x 5 1
1
2
x 7 (*)
x 3 5
375 1
3
2
x 4 1 3x 5 2
1
2
x 7
z 5 11 125 1
1
2
x 4 2 3x 5 2
3
2
x 7
On reconnaît le som met R (1 000, 500, 375) où le béné fice vaut : 11 125 euros.
Nou velle (et der nière) ité ra tion : la variable hors base x 4 ayant dans z un coef
fi cient posi tif (1/2), entre en base : on pose x 4 5 u, posi tif crois sant et on garde
x 5 5 x 7 5 0 ; il vient :
x 1 5 1 000 2 u, x 2 5 500, x 6 5 1 125 2
3
2
u, x 3 5 375 1
3
2
u, z 5 11 125 1
1
2
u.
La variable sor tante est donc x 6 (avec u 5 1 125 ^a
3
2
b 5 750).
L’équa tion de l’échange est : x 6 5 1 125 2
3
2
x 4 2 3x 5 1
1
2
x 7 ; d’où, en l’inversant :
3
2
x 4 5 1 125 2 3x 5 2 x 6 1
1
2
x 7 et donc : x 4 5 750 2 2x 5 2
2
3
x 6 1
1
3
x 7 .
En subs ti tuant à x 4 cette valeur dans les autres équa tions du sys tème asso cié à R, il
vient, avec @ Q = {x 1 , x 2 , x 3 , x 4 }.
Q h
x 1 5
250 1 2x 5 1
2
3
x 6 2
1
3
x 7
x 2 5
500 2 x 5
x 3 5 1 500
2 x 6
x 4 5
750 2 2x 5 2
2
3
x 6 1
1
3
x 7
z 5 11 500 2 4x 5 2
1
3
x 6 2
4
3
x 7
On reconnaît le som met Q : x 1 5 250, x 2 5 500, x 3 5 1 500 avec un béné fice de
z 5 11 500 euros. Le som met est opti mal : il n’est pas pos sible d’amé lio rer z par le
pro cédé ci- dessus car tous les coef fi cients des variables (hors base) figu rant dans z
sont néga tifs ; on peut alors démon trer, en uti li sant un argu ment de convexité et de
dualité que, dans ces condi tions, l’opti mum est effec ti ve ment atteint : nous y revien
drons plus loin dans le para graphe 8.7 consacré à la dua lité.
Sys té ma ti sons la pro cé dure ci dessus employée dans l’algo rithme du sim plexe.
Nous avons vu que l’algo rithme consiste à pro gres ser d’un som met ini tial vers
un som met adja cent en ayant soin de ne pas dimi nuer la valeur de la fonc tion éco
312
R h
x 1 5 1 000 2 x 4
x 2 5
500
2 x 5
x 6 5 1 125 2
3
2
x 4 2 3x 5 1
1
2
x 7 (*)
x 3 5
375 1
3
2
x 4 1 3x 5 2
1
2
x 7
z 5 11 125 1
1
2
x 4 2 3x 5 2
3
2
x 7
On reconnaît le som met R (1 000, 500, 375) où le béné fice vaut : 11 125 euros.
Nou velle (et der nière) ité ra tion : la variable hors base x 4 ayant dans z un coef
fi cient posi tif (1/2), entre en base : on pose x 4 5 u, posi tif crois sant et on garde
x 5 5 x 7 5 0 ; il vient :
x 1 5 1 000 2 u, x 2 5 500, x 6 5 1 125 2
3
2
u, x 3 5 375 1
3
2
u, z 5 11 125 1
1
2
u.
La variable sor tante est donc x 6 (avec u 5 1 125 ^a
3
2
b 5 750).
L’équa tion de l’échange est : x 6 5 1 125 2
3
2
x 4 2 3x 5 1
1
2
x 7 ; d’où, en l’inversant :
3
2
x 4 5 1 125 2 3x 5 2 x 6 1
1
2
x 7 et donc : x 4 5 750 2 2x 5 2
2
3
x 6 1
1
3
x 7 .
En subs ti tuant à x 4 cette valeur dans les autres équa tions du sys tème asso cié à R, il
vient, avec @ Q = {x 1 , x 2 , x 3 , x 4 }.
Q h
x 1 5
250 1 2x 5 1
2
3
x 6 2
1
3
x 7
x 2 5
500 2 x 5
x 3 5 1 500
2 x 6
x 4 5
750 2 2x 5 2
2
3
x 6 1
1
3
x 7
z 5 11 500 2 4x 5 2
1
3
x 6 2
4
3
x 7
On reconnaît le som met Q : x 1 5 250, x 2 5 500, x 3 5 1 500 avec un béné fice de
z 5 11 500 euros. Le som met est opti mal : il n’est pas pos sible d’amé lio rer z par le
pro cédé ci- dessus car tous les coef fi cients des variables (hors base) figu rant dans z
sont néga tifs ; on peut alors démon trer, en uti li sant un argu ment de convexité et de
dualité que, dans ces condi tions, l’opti mum est effec ti ve ment atteint : nous y revien
drons plus loin dans le para graphe 8.7 consacré à la dua lité.
Sys té ma ti sons la pro cé dure ci dessus employée dans l’algo rithme du sim plexe.
Nous avons vu que l’algo rithme consiste à pro gres ser d’un som met ini tial vers
un som met adja cent en ayant soin de ne pas dimi nuer la valeur de la fonc tion éco