307
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Consi dé rons d’abord (figure 8.5) une mon tagne
en forme de pain de sucre. Par tant d’un point
quel conque C, on peut tou jours atteindre le som
met S, pourvu qu’on monte tou jours (les iti né
raires com por tant des paliers hori zon taux limi tés
sont auto ri sés). Ce n’est pas vrai pour une mon
tagne qui pré sen te rait un som met « para site » S r,
auquel on ris que rait de par ve nir en appli quant la
méthode pré cé dente (figure 8.6).
Cela s’explique par le fait que la pre mière
mon tagne est convexe (si l’on joint deux
points quel conques de l’inté rieur ou de la sur
face, le segment de droite qui les joint est tout
entier conte nu dans le volume), tan dis que la
seconde ne l’est pas. Or, tout polyèdre (non
vide) engen dré par des contraintes linéaires
est nécessairement convexe et l’on peut trou
ver au moins un che min (figure 8.7) qui, à
par tir de n’importe quel som met, conduise
(de som met en som met adja cent) au som met
don nant la valeur maximale à la fonc tion éco
no mique (autre ment dit : il existe tou jours au
moins un som met adja cent, situé, par rap port
à l’ori gine au delà du plan (ou sur le plan) de
la fonc tion éco no mique cor res pon dant à un som met quel conque, à moins que ce der
nier ne soit l’opti mum). Ici c’est le che min CGHS.
En bref, l’algo rithme du sim plexe a un fon de ment pure ment géo mé trique : il consiste, en
dis po sant d’un point de départ, qui est un som met du polyèdre, sup posé connu, de pas ser
lors de toute ité ra tion d’un som met M à un som met voi sin M r – c’est àdire à décrire une
arête du polyèdre – en lequel la valeur de la fonc tion éco no mique, est meilleure (ou au
moins aussi bonne) qu’en M. Lors qu’on atteint un som met Q pour lequel aucun som met
voi sin n’est meilleur, alors l’algo rithme s’arête : le som met Q est opti mal.
8.2 aLgo rithme du sim pLexe : méthode aLgé brique,
méthode des tabLeaux
8.2.1 Méthode algé brique du sim plexe
On com mence par rame ner le pro gramme linéaire (PL) à une forme « stan dard » pour
laquelle toutes les contraintes sont en éga li tés et les seconds membres sont posi tifs
(ceci moyen nant l’intro duc tion de nou velles variables, dites « variables d’écart »).
Toutes les variables sont posi tives ou nulles. La fonc tion éco no mique est à maxi mi
ser (ce qui n’est pas restrictif car minimi ser une fonc tion équi vaut à maxi mi ser son
oppo sée). Reportons nous au PL for mulé au 8.1.2.
Figure 8.5
Figure 8.6
Figure 8.7
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Consi dé rons d’abord (figure 8.5) une mon tagne
en forme de pain de sucre. Par tant d’un point
quel conque C, on peut tou jours atteindre le som
met S, pourvu qu’on monte tou jours (les iti né
raires com por tant des paliers hori zon taux limi tés
sont auto ri sés). Ce n’est pas vrai pour une mon
tagne qui pré sen te rait un som met « para site » S r,
auquel on ris que rait de par ve nir en appli quant la
méthode pré cé dente (figure 8.6).
Cela s’explique par le fait que la pre mière
mon tagne est convexe (si l’on joint deux
points quel conques de l’inté rieur ou de la sur
face, le segment de droite qui les joint est tout
entier conte nu dans le volume), tan dis que la
seconde ne l’est pas. Or, tout polyèdre (non
vide) engen dré par des contraintes linéaires
est nécessairement convexe et l’on peut trou
ver au moins un che min (figure 8.7) qui, à
par tir de n’importe quel som met, conduise
(de som met en som met adja cent) au som met
don nant la valeur maximale à la fonc tion éco
no mique (autre ment dit : il existe tou jours au
moins un som met adja cent, situé, par rap port
à l’ori gine au delà du plan (ou sur le plan) de
la fonc tion éco no mique cor res pon dant à un som met quel conque, à moins que ce der
nier ne soit l’opti mum). Ici c’est le che min CGHS.
En bref, l’algo rithme du sim plexe a un fon de ment pure ment géo mé trique : il consiste, en
dis po sant d’un point de départ, qui est un som met du polyèdre, sup posé connu, de pas ser
lors de toute ité ra tion d’un som met M à un som met voi sin M r – c’est àdire à décrire une
arête du polyèdre – en lequel la valeur de la fonc tion éco no mique, est meilleure (ou au
moins aussi bonne) qu’en M. Lors qu’on atteint un som met Q pour lequel aucun som met
voi sin n’est meilleur, alors l’algo rithme s’arête : le som met Q est opti mal.
8.2 aLgo rithme du sim pLexe : méthode aLgé brique,
méthode des tabLeaux
8.2.1 Méthode algé brique du sim plexe
On com mence par rame ner le pro gramme linéaire (PL) à une forme « stan dard » pour
laquelle toutes les contraintes sont en éga li tés et les seconds membres sont posi tifs
(ceci moyen nant l’intro duc tion de nou velles variables, dites « variables d’écart »).
Toutes les variables sont posi tives ou nulles. La fonc tion éco no mique est à maxi mi
ser (ce qui n’est pas restrictif car minimi ser une fonc tion équi vaut à maxi mi ser son
oppo sée). Reportons nous au PL for mulé au 8.1.2.
Figure 8.5
Figure 8.6
Figure 8.7