309
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
@ 0 = {x 4 , x 5 , x 6 , x 7 } 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 700 2 3x 1 2 6x 2 2 2x 3
z 5 0 1 4x 1 1 12x 2 1 3x 3
L’exa men de z montre que, pour aug men ter sa valeur numé rique, il faut don ner
à l’une des variables hors base, actuel le ment nulle au som met consi déré (O), une
valeur posi tive. Puisque dans z, x 2 a le coef fi cient (béné fice mar gi nal) le plus élevé,
nous choi sis sons d’accroître x 2 en posant x 2 5 u, où θ est un para mètre que nous
pre nons posi tif crois sant ; nous gar dons, pour cette ité ra tion, les autres variables hors
base nulles : x 1 5 x 3 5 0.
Le sys tème devient :
e
x 4 5 1 000
x 5 5 500 2 u
x 6 5 1 500
x 7 5 6 750 2 6u
z 5
0 1 12u
Jus qu’à quelle valeur peut- on accroître θ (c’est- à-dire x 2 ) ?
Le béné fice glo bal z est pro por tion nel à θ : l’entre prise peut- elle deve nir très riche
en don nant à θ une valeur très éle vée ? En fait non, car il ne faut pas oublier que
toutes les variables sont posi tives ou nulles, et doivent le demeu rer (« contraintes
impli cites » ) :
x 5 > 0 entraîne u < 500
x 7 > 0 entraîne u < 6 750/6 5 1 125
Ainsi, la plus grande valeur de θ qui res pecte la positivité de toutes les variables
est u 5 500 (et non pas 1 125 qui ren drait x 5 néga tif). Si l’on pose donc u 5 500,
il vient numé ri que ment :
e
x 4 5 1 000 x 1 5 0
x 5 5
0 x 2 5 500
x 6 5 1 500 x 3 5 0
x 7 5 3 750
z 5 6 000
On reconnaît alors les coor don nées du som met C : le pro gramme de pro duc tion (0,
500, 0) qui engen dre un béné fice z 5 6 000 euros.
On vient donc de trou ver un pro cédé algé brique qui nous a per mis de pas ser d’un
som met (O) d’un polyèdre à un som met « voi sin » (C), en décri vant une arête de ce
polyèdre : l’arête OC, en augmentant z.
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
@ 0 = {x 4 , x 5 , x 6 , x 7 } 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 700 2 3x 1 2 6x 2 2 2x 3
z 5 0 1 4x 1 1 12x 2 1 3x 3
L’exa men de z montre que, pour aug men ter sa valeur numé rique, il faut don ner
à l’une des variables hors base, actuel le ment nulle au som met consi déré (O), une
valeur posi tive. Puisque dans z, x 2 a le coef fi cient (béné fice mar gi nal) le plus élevé,
nous choi sis sons d’accroître x 2 en posant x 2 5 u, où θ est un para mètre que nous
pre nons posi tif crois sant ; nous gar dons, pour cette ité ra tion, les autres variables hors
base nulles : x 1 5 x 3 5 0.
Le sys tème devient :
e
x 4 5 1 000
x 5 5 500 2 u
x 6 5 1 500
x 7 5 6 750 2 6u
z 5
0 1 12u
Jus qu’à quelle valeur peut- on accroître θ (c’est- à-dire x 2 ) ?
Le béné fice glo bal z est pro por tion nel à θ : l’entre prise peut- elle deve nir très riche
en don nant à θ une valeur très éle vée ? En fait non, car il ne faut pas oublier que
toutes les variables sont posi tives ou nulles, et doivent le demeu rer (« contraintes
impli cites » ) :
x 5 > 0 entraîne u < 500
x 7 > 0 entraîne u < 6 750/6 5 1 125
Ainsi, la plus grande valeur de θ qui res pecte la positivité de toutes les variables
est u 5 500 (et non pas 1 125 qui ren drait x 5 néga tif). Si l’on pose donc u 5 500,
il vient numé ri que ment :
e
x 4 5 1 000 x 1 5 0
x 5 5
0 x 2 5 500
x 6 5 1 500 x 3 5 0
x 7 5 3 750
z 5 6 000
On reconnaît alors les coor don nées du som met C : le pro gramme de pro duc tion (0,
500, 0) qui engen dre un béné fice z 5 6 000 euros.
On vient donc de trou ver un pro cédé algé brique qui nous a per mis de pas ser d’un
som met (O) d’un polyèdre à un som met « voi sin » (C), en décri vant une arête de ce
polyèdre : l’arête OC, en augmentant z.