8.6 Notions sur la méthode révi sée du sim plexe
341
© Dunod – Toute reproduction non autorisée est un délit.
Dans la méthode des tableaux, on repré sente en fait le sys tème B # x B 1 N # x N 5 b
sous la forme : I # x B 1 B
2 1 # N # x N 5 B
2 1 # b (où I est la matrice iden tité m × m), ce
qui revient à mul ti plier chaque membre du sys tème, à gauche, par B
21
. Mais, en fait,
une seule colonne hors- base (l’une des colonnes de B
21 # N) est utile lors de l’ité -
ra tion : c’est la « colonne entrante » qui per met ensuite de déter mi ner, à l’aide du
second cri tère de Dantzig, la variable sor tante. Aussi, le cal cul de la valeur cou rante
des autres colonnes hors- base (celles de B
21 # N), qui sont au nombre de n 2 m, est- il
inutile pour pra ti quer l’ité ra tion. Dans la méthode révi sée du sim plexe, on évite ces
cal culsinutiles:oncal culeseule mentlescoef fi cientsdelacolonneentrante,c’est-
à-dire du vecteur- colonne B
21 # N
e 5 y
e
, où N
e
est la colonne d’indice e de la matrice Ν (sous- matrice de A). Ceci revient à résoudre un second sys tème linéaire :
B # y
e 5 N
e
(si l’on ne connaît pas B
21
, ou bien si l’on ne sou haite pas cal cu ler expli -
ci te ment cet inverse). Ainsi on résout un nouveau sys tème linéaire, mais de même
matrice B que le pre mier sys tème, celui qui nous a per mis de cal cu ler la solu tion de
base x B .
Les mcoef fi cientsdey
e
sont notés : α i1,e , α i2,e , c , α im,e , sachant que la base est com -
po sée des colonnes A
i1
, A
i2
, c , A
im
(extraites de A). Il est alors aisé, connais sant y
e
,
de déter mi ner, à l’aide du second cri tère de Dantzig, la variable sor tante x s .
Pour déter mi ner la variable entrante x e , on peut préa la ble ment appli quer, par exemple,lepre miercri tèredeDantzig,cequisup poselaconnais sancedescoef fi cientsD j
(c’est- à-dire de l’expres sion de z en fonc tion des variables hors- base). Nous allons
mon trer que les D j peuvent être obte nus par la réso lu tion d’un troi sième système
linéaire, à nou veau de matrice B.
Nous avons vu que z 5 z
,
B 1 D N # x N où z
,
B 5 c B # B
2 1
et D N 5 c N 2 c B # B
2 1 # N.
Posons p 5 c B # B
21
: ce vec teur ligne 1 3 m est nommé vec teur des « mul ti pli ca
teurs du sim plexe ».
Le cal cul de p revient à résoudre le sys tème linéaire p # B 5 c B Remar quons que, s’il
a la même matrice Β que les deux sys tèmes pré cé dents, il fait inter ve nir un vecteurligne d’inconnues : p 5 [p ι , p 2 , c , p m ] mul ti pliant à gauche la matrice B, alors
que, dans les deux sys tèmes pré cé dents, on avait un vecteur- colonne m 3 1 mul ti -
pliant à droite la matrice B.
Une fois cal culé p, le cal cul de D N est tri vial : D N 5 c N 2 p # N et l’on peut alors
déter mi ner la variable entrante.
Ainsi dans la méthode révi sée du sim plexe, chaque ité ra tion se résume à résoudre
trois sys tèmes linéaires, de même matrice B, régu lière. La réso lu tion numé rique de
tels sys tèmes est du domaine de l’ana lyse numé rique ; elle a été très investiguée et
béné fi ciedemul tiplesvariantesderéso lu tioneffi cacesetpré cises.Ilexistedoncdenom breuses variantes de la méthode révi sée du sim plexe.
Une voie pos sible est de cal cu ler B
21
. Dans la variante EFI (forme expli cite de
l’inverse), on cal cule expli ci te ment B
21
à par tir de l’inverse de la matrice de la base
de l’ité ra tion pré cé dente, B
21
étant repré sen tée en mémoire cen trale. Cette variante
est adap tée aux pro grammes linéaires de taille modé rée.
341
© Dunod – Toute reproduction non autorisée est un délit.
Dans la méthode des tableaux, on repré sente en fait le sys tème B # x B 1 N # x N 5 b
sous la forme : I # x B 1 B
2 1 # N # x N 5 B
2 1 # b (où I est la matrice iden tité m × m), ce
qui revient à mul ti plier chaque membre du sys tème, à gauche, par B
21
. Mais, en fait,
une seule colonne hors- base (l’une des colonnes de B
21 # N) est utile lors de l’ité -
ra tion : c’est la « colonne entrante » qui per met ensuite de déter mi ner, à l’aide du
second cri tère de Dantzig, la variable sor tante. Aussi, le cal cul de la valeur cou rante
des autres colonnes hors- base (celles de B
21 # N), qui sont au nombre de n 2 m, est- il
inutile pour pra ti quer l’ité ra tion. Dans la méthode révi sée du sim plexe, on évite ces
cal culsinutiles:oncal culeseule mentlescoef fi cientsdelacolonneentrante,c’est-
à-dire du vecteur- colonne B
21 # N
e 5 y
e
, où N
e
est la colonne d’indice e de la matrice Ν (sous- matrice de A). Ceci revient à résoudre un second sys tème linéaire :
B # y
e 5 N
e
(si l’on ne connaît pas B
21
, ou bien si l’on ne sou haite pas cal cu ler expli -
ci te ment cet inverse). Ainsi on résout un nouveau sys tème linéaire, mais de même
matrice B que le pre mier sys tème, celui qui nous a per mis de cal cu ler la solu tion de
base x B .
Les mcoef fi cientsdey
e
sont notés : α i1,e , α i2,e , c , α im,e , sachant que la base est com -
po sée des colonnes A
i1
, A
i2
, c , A
im
(extraites de A). Il est alors aisé, connais sant y
e
,
de déter mi ner, à l’aide du second cri tère de Dantzig, la variable sor tante x s .
Pour déter mi ner la variable entrante x e , on peut préa la ble ment appli quer, par exemple,lepre miercri tèredeDantzig,cequisup poselaconnais sancedescoef fi cientsD j
(c’est- à-dire de l’expres sion de z en fonc tion des variables hors- base). Nous allons
mon trer que les D j peuvent être obte nus par la réso lu tion d’un troi sième système
linéaire, à nou veau de matrice B.
Nous avons vu que z 5 z
,
B 1 D N # x N où z
,
B 5 c B # B
2 1
et D N 5 c N 2 c B # B
2 1 # N.
Posons p 5 c B # B
21
: ce vec teur ligne 1 3 m est nommé vec teur des « mul ti pli ca
teurs du sim plexe ».
Le cal cul de p revient à résoudre le sys tème linéaire p # B 5 c B Remar quons que, s’il
a la même matrice Β que les deux sys tèmes pré cé dents, il fait inter ve nir un vecteurligne d’inconnues : p 5 [p ι , p 2 , c , p m ] mul ti pliant à gauche la matrice B, alors
que, dans les deux sys tèmes pré cé dents, on avait un vecteur- colonne m 3 1 mul ti -
pliant à droite la matrice B.
Une fois cal culé p, le cal cul de D N est tri vial : D N 5 c N 2 p # N et l’on peut alors
déter mi ner la variable entrante.
Ainsi dans la méthode révi sée du sim plexe, chaque ité ra tion se résume à résoudre
trois sys tèmes linéaires, de même matrice B, régu lière. La réso lu tion numé rique de
tels sys tèmes est du domaine de l’ana lyse numé rique ; elle a été très investiguée et
béné fi ciedemul tiplesvariantesderéso lu tioneffi cacesetpré cises.Ilexistedoncdenom breuses variantes de la méthode révi sée du sim plexe.
Une voie pos sible est de cal cu ler B
21
. Dans la variante EFI (forme expli cite de
l’inverse), on cal cule expli ci te ment B
21
à par tir de l’inverse de la matrice de la base
de l’ité ra tion pré cé dente, B
21
étant repré sen tée en mémoire cen trale. Cette variante
est adap tée aux pro grammes linéaires de taille modé rée.