315
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Si l’on prend
b s
a se posi tif, alors β k , qui est posi tif, est sûre ment plus grand que a ke #
b s
a se
lorsque a ke est néga tif. Au contraire, lorsque a ke est posi tif, on peut divi ser les deux
membres de l’inéga lité par a ke et l’on a :
b s
a se
<
b k
a ke
.
La condi tion sera donc réa li sée si l’on a soin de prendre, parmi les quo tients
b k
a ke
obte
nus pour toutes les valeurs k, le plus petit posi tif d’entre eux (obtenu pour k 5 s).
D’où le deuxième cri tère de Dantzig :
« Pour déter mi ner la colonne A
s
qui doit sor tir de la base, on choi sit celle d’indice
s tel que
b k
a ke
soit le plus petit posi tif (l’indice e ayant été déter miné par l’appli ca tion
du pre mier cri tère) ».
N.B. Si tous ces rapports sont négatifs, alors l’optimum est rejeté à l’infini : fin. Ce
cas ne se présente pas dans les PL ayant un contexte économique.
Tels sont les deux cri tères sur les quels est fondé l’algo rithme de Dantzig.
L’opti mum sera atteint dès que le pre mier cri tère ne sera plus appli cable, c’est àdire
lorsque tous les D j rela tifs aux variables hors base seront néga tifs ou nuls, ceux rela
tifs aux variables de base étant nécessairement nuls.
Remarque. Le pre mier cri tère est heu ris tique (on tente loca le ment de s’appro
cher au plus vite de l’opti mum, c’est une démarche « gour mande » : ce cri tère
est donc facul ta tif. Le second, en revanche, est obli ga toire pour aller de solu
tion réa li sable en solu tion réa li sable, (c’est àdire pour pré ser ver la positivité
des variables de base).
8.2.2 Règle pra tique (maxi mi sa tion) : méthode des tableaux
Pour rendre pra tique l’appli ca tion manuelle des cri tères de Dantzig, per fec tion nons le
tableau ini tial en lui ajou tant une colonne à gauche où seront indi qués les c i (coef fi cients
de la fonc tion éco no mique sous sa forme ini tiale, pour chaque valeur i des indices de
ligne figu rant dans le tableau, c-à-d pour toute variable de base x i ) et une ligne sous le
tableau principal où seront notés les c j (coef fi cients de la fonc tion éco no mique sous sa
forme ini tiale, cor res pon dant cette fois aux indices j immuables, des colonnes). Dans le
tableau de droite, la colonne b, on indique les valeurs des variables de la base cou rante.
(Pour la base ini tiale asso ciée au som met O, rap pe lons que l’on a : b 5 b.)
Lors de toute itération le repé rage de la colonne e qui doit entrer dans la base est
simple : il suf fit de lire la ligne des Δ j et de sélec tion ner celui des Δ j qui est le plus
grand et posi tif, si l’on applique le pre mier cri tère de Dantzig.
Ici, c’est D 2 5 12, dans la colonne 2 ; on a donc : e 5 2 et c’est x 2 qui est associé à la
deuxième colonne, qui entrera dans la base.
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Si l’on prend
b s
a se posi tif, alors β k , qui est posi tif, est sûre ment plus grand que a ke #
b s
a se
lorsque a ke est néga tif. Au contraire, lorsque a ke est posi tif, on peut divi ser les deux
membres de l’inéga lité par a ke et l’on a :
b s
a se
<
b k
a ke
.
La condi tion sera donc réa li sée si l’on a soin de prendre, parmi les quo tients
b k
a ke
obte
nus pour toutes les valeurs k, le plus petit posi tif d’entre eux (obtenu pour k 5 s).
D’où le deuxième cri tère de Dantzig :
« Pour déter mi ner la colonne A
s
qui doit sor tir de la base, on choi sit celle d’indice
s tel que
b k
a ke
soit le plus petit posi tif (l’indice e ayant été déter miné par l’appli ca tion
du pre mier cri tère) ».
N.B. Si tous ces rapports sont négatifs, alors l’optimum est rejeté à l’infini : fin. Ce
cas ne se présente pas dans les PL ayant un contexte économique.
Tels sont les deux cri tères sur les quels est fondé l’algo rithme de Dantzig.
L’opti mum sera atteint dès que le pre mier cri tère ne sera plus appli cable, c’est àdire
lorsque tous les D j rela tifs aux variables hors base seront néga tifs ou nuls, ceux rela
tifs aux variables de base étant nécessairement nuls.
Remarque. Le pre mier cri tère est heu ris tique (on tente loca le ment de s’appro
cher au plus vite de l’opti mum, c’est une démarche « gour mande » : ce cri tère
est donc facul ta tif. Le second, en revanche, est obli ga toire pour aller de solu
tion réa li sable en solu tion réa li sable, (c’est àdire pour pré ser ver la positivité
des variables de base).
8.2.2 Règle pra tique (maxi mi sa tion) : méthode des tableaux
Pour rendre pra tique l’appli ca tion manuelle des cri tères de Dantzig, per fec tion nons le
tableau ini tial en lui ajou tant une colonne à gauche où seront indi qués les c i (coef fi cients
de la fonc tion éco no mique sous sa forme ini tiale, pour chaque valeur i des indices de
ligne figu rant dans le tableau, c-à-d pour toute variable de base x i ) et une ligne sous le
tableau principal où seront notés les c j (coef fi cients de la fonc tion éco no mique sous sa
forme ini tiale, cor res pon dant cette fois aux indices j immuables, des colonnes). Dans le
tableau de droite, la colonne b, on indique les valeurs des variables de la base cou rante.
(Pour la base ini tiale asso ciée au som met O, rap pe lons que l’on a : b 5 b.)
Lors de toute itération le repé rage de la colonne e qui doit entrer dans la base est
simple : il suf fit de lire la ligne des Δ j et de sélec tion ner celui des Δ j qui est le plus
grand et posi tif, si l’on applique le pre mier cri tère de Dantzig.
Ici, c’est D 2 5 12, dans la colonne 2 ; on a donc : e 5 2 et c’est x 2 qui est associé à la
deuxième colonne, qui entrera dans la base.