Chapitre 8 • La programmation linéaire
340
Remarque. L’éva lua tiondesΔ j dans la variante « méthode du grand M » est
faci li tée par l’appli ca tion de la for mule que nous avons prou vée plus haut
(cf. para graphe 8.4) :
D j 5 c j 2 a c i # a ij (pour x j hors- base),
oùlasom ma tionestéten dueauxindicesdesvariablesdebase;lesα ij étant les
coef fi cientsdutableaucou rant;c i désigneicilecoef fi cient(initial)delai
ième
variable de base.
Ainsi après une ité ra tion, on a :
D 2 5 c 2 2 (c 1 # a 12 1 c 1 # a 22 1 c as # a 32 )
5 5 2 30, 4, 2 M 4 # C
3/2
1/2
1/2
S 5 M/2 1 3
Pour appli quer plus faci le ment cette for mule on a indi qué immé dia te ment à
gauche de chaque variable de base x i soncoef fi cientini tialdansz , soit c i , et
l’on a inter calé entre le tableauprin ci palet la ligne desΔ ˆ j , les valeurs des
coef fi cientsini tiauxc j de z .
En pra tique, les logi ciels de pro gram ma tion linéaire implé men tant l’algo -
rithme du sim plexe uti lisent la méthode en deux phases. En effet, lors de la
phase1,enminimi santlasommedesvariablesarti fi cielles,lavarianteditedu« grand M » conduit à uti li ser des nombres dont les ordres de gran deur sont
trèsdif fé rents,cequiestsourcededif fi cul tésnumé riques.
8.6 NotioNs sur la méthode révi sée du sim plexe
La méthode révi sée du sim plexe est une amé lio ra tion de l’algo rithme du sim plexe
visant, d’une part, à réduire la masse de cal culs et, d’autre part, à amé lio rer la pré ci -
sion des résul tats.
1
Consi dé rons une base admis sible du pro gramme linéaire (PL)
[A # x 5 b ; x > 0 ; max z 5 c # x], de matrice B.
Le sys tème des contraintes A # x 5 b s’écrit alors : B # x B 1 N # x N 5 b.
Pour obte nir la valeur numé rique de la solu tion (som met) asso ciée à cette base, on
annule les variables hors- base : x N 5 0 ; il reste donc à résoudre un pre mier sys tème
linéaire B # x B 5 b, sys tème de Cra mer (c’est- à-dire à déter mi nant non nul) de m
équa tions à m inconnues. En par ti cu lier si l’on connaît l’inverse de la matrice B, soit
B
21
, on obtient direc te ment : x B 5 B
2 1 # b.
1. enta chés par des erreurs dues à l’uti li sation de l’arith mé tique flot tante en infor ma tique.
ˆ
ˆ
340
Remarque. L’éva lua tiondesΔ j dans la variante « méthode du grand M » est
faci li tée par l’appli ca tion de la for mule que nous avons prou vée plus haut
(cf. para graphe 8.4) :
D j 5 c j 2 a c i # a ij (pour x j hors- base),
oùlasom ma tionestéten dueauxindicesdesvariablesdebase;lesα ij étant les
coef fi cientsdutableaucou rant;c i désigneicilecoef fi cient(initial)delai
ième
variable de base.
Ainsi après une ité ra tion, on a :
D 2 5 c 2 2 (c 1 # a 12 1 c 1 # a 22 1 c as # a 32 )
5 5 2 30, 4, 2 M 4 # C
3/2
1/2
1/2
S 5 M/2 1 3
Pour appli quer plus faci le ment cette for mule on a indi qué immé dia te ment à
gauche de chaque variable de base x i soncoef fi cientini tialdansz , soit c i , et
l’on a inter calé entre le tableauprin ci palet la ligne desΔ ˆ j , les valeurs des
coef fi cientsini tiauxc j de z .
En pra tique, les logi ciels de pro gram ma tion linéaire implé men tant l’algo -
rithme du sim plexe uti lisent la méthode en deux phases. En effet, lors de la
phase1,enminimi santlasommedesvariablesarti fi cielles,lavarianteditedu« grand M » conduit à uti li ser des nombres dont les ordres de gran deur sont
trèsdif fé rents,cequiestsourcededif fi cul tésnumé riques.
8.6 NotioNs sur la méthode révi sée du sim plexe
La méthode révi sée du sim plexe est une amé lio ra tion de l’algo rithme du sim plexe
visant, d’une part, à réduire la masse de cal culs et, d’autre part, à amé lio rer la pré ci -
sion des résul tats.
1
Consi dé rons une base admis sible du pro gramme linéaire (PL)
[A # x 5 b ; x > 0 ; max z 5 c # x], de matrice B.
Le sys tème des contraintes A # x 5 b s’écrit alors : B # x B 1 N # x N 5 b.
Pour obte nir la valeur numé rique de la solu tion (som met) asso ciée à cette base, on
annule les variables hors- base : x N 5 0 ; il reste donc à résoudre un pre mier sys tème
linéaire B # x B 5 b, sys tème de Cra mer (c’est- à-dire à déter mi nant non nul) de m
équa tions à m inconnues. En par ti cu lier si l’on connaît l’inverse de la matrice B, soit
B
21
, on obtient direc te ment : x B 5 B
2 1 # b.
1. enta chés par des erreurs dues à l’uti li sation de l’arith mé tique flot tante en infor ma tique.
ˆ
ˆ