Chapitre 8 • La pro gram ma tion linéaire
314
• nou velles valeurs des variables de base (l’élément de la ligne k dans le vec teur
second membre b est la valeur de x k ) :
br k 5 b k 2 a ke
b s
a se
(k 2 s) et br s 5
b s
a se
(valeur de la variable entrante x e )
b k (resp. b s ) étant l’ancienne valeur ;
• nou velle valeur de l’élé ment de la ligne k et de la colonne A (k 2 s):
ar k, 5 a k, 2 a ke
a s,
a se
,
a k étant l’ancienne valeur ;
• nou velle valeur de l’élé ment de la ligne s de la colonne A :
ar s, 5
a s,
a se ,
a s étant l’ancienne valeur : on divise la ligne s, celle du pivot, par le pivot : a se qui
est nécessairement positif, cf le second critère de Dantzig.
Dans ces condi tions, comme à chaque pas on désire que zr soit supérieur (ou égal)
à z, il fau dra prendre Δ e posi tif (
b s
a se sera posi tif, car b s . 0 est posi tif ou – excep
tion nel le ment – nul et le pivot a se sera pris posi tif). Heuristiquement, on a inté rêt à
prendre D e . 0 le plus élevé pos sible. C’est pour quoi le pre mier cri tère de Dantzig
s’énonce ainsi :
« Pour déter mi ner la colonne A
e
qui doit entrer dans la base, on choi sit celle qui
com porte le D j posi tif le plus grand ». Si tous les D j sont néga tifs ou nuls: fin, l’opti
mum est atteint (prop riété admise ici).
Le pre mier cri tère de Dantzig vise à minimi ser le nombre d’ité ra tions effec tuées au
cours du dérou le ment de l’algo rithme. Mais ceci n’est pas tou jours le cas, il existe
même des exemples, certes rares, pour les quels l’uti li sation de ce cri tère peut être
par ti cu liè re ment désas treuse et l’algo rithme ne jamais se ter mi ner. C’est pour quoi
d’autres cri tères ont été don nés évi tant ceci. Citons le cri tère de Bland : pour déter
mi ner la colonne A
e
, qui doit entrer dans la base, on choi sit celle pour laquelle
l’indice j est le plus petit, parmi celles pour les quelles D j . 0. Bland a mon tré que
l’uti li sation de ce cri tère assu rait la ter mi nai son de l’algo rithme. En pra tique, des
stra té gies mixtes com bi nant les deux cri tères de Bland et Dantzig, ou bien encore
d’autres stra té gies basées sur des tirages aléa toires peuvent être uti li sées.
On veut encore que, pour tout k, br k soit non négatif :
br k 5 b k 2 a ke #
b s
a se > 0. Cela s’écrit aussi : b k > a ke #
b s
a se .
314
• nou velles valeurs des variables de base (l’élément de la ligne k dans le vec teur
second membre b est la valeur de x k ) :
br k 5 b k 2 a ke
b s
a se
(k 2 s) et br s 5
b s
a se
(valeur de la variable entrante x e )
b k (resp. b s ) étant l’ancienne valeur ;
• nou velle valeur de l’élé ment de la ligne k et de la colonne A (k 2 s):
ar k, 5 a k, 2 a ke
a s,
a se
,
a k étant l’ancienne valeur ;
• nou velle valeur de l’élé ment de la ligne s de la colonne A :
ar s, 5
a s,
a se ,
a s étant l’ancienne valeur : on divise la ligne s, celle du pivot, par le pivot : a se qui
est nécessairement positif, cf le second critère de Dantzig.
Dans ces condi tions, comme à chaque pas on désire que zr soit supérieur (ou égal)
à z, il fau dra prendre Δ e posi tif (
b s
a se sera posi tif, car b s . 0 est posi tif ou – excep
tion nel le ment – nul et le pivot a se sera pris posi tif). Heuristiquement, on a inté rêt à
prendre D e . 0 le plus élevé pos sible. C’est pour quoi le pre mier cri tère de Dantzig
s’énonce ainsi :
« Pour déter mi ner la colonne A
e
qui doit entrer dans la base, on choi sit celle qui
com porte le D j posi tif le plus grand ». Si tous les D j sont néga tifs ou nuls: fin, l’opti
mum est atteint (prop riété admise ici).
Le pre mier cri tère de Dantzig vise à minimi ser le nombre d’ité ra tions effec tuées au
cours du dérou le ment de l’algo rithme. Mais ceci n’est pas tou jours le cas, il existe
même des exemples, certes rares, pour les quels l’uti li sation de ce cri tère peut être
par ti cu liè re ment désas treuse et l’algo rithme ne jamais se ter mi ner. C’est pour quoi
d’autres cri tères ont été don nés évi tant ceci. Citons le cri tère de Bland : pour déter
mi ner la colonne A
e
, qui doit entrer dans la base, on choi sit celle pour laquelle
l’indice j est le plus petit, parmi celles pour les quelles D j . 0. Bland a mon tré que
l’uti li sation de ce cri tère assu rait la ter mi nai son de l’algo rithme. En pra tique, des
stra té gies mixtes com bi nant les deux cri tères de Bland et Dantzig, ou bien encore
d’autres stra té gies basées sur des tirages aléa toires peuvent être uti li sées.
On veut encore que, pour tout k, br k soit non négatif :
br k 5 b k 2 a ke #
b s
a se > 0. Cela s’écrit aussi : b k > a ke #
b s
a se .