317
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Plu tôt que d’appli quer, élé ment par élé ment, les for mules ci dessus, on emploie les
règles pra tiques de trans for ma tion du tableau très simples (qui leur sont équi va
lentes) sui vantes :
1) on repère le pivot a se qui est à l’inter sec tion de la ligne s et de la colonne e. C’est
l’indice de ligne cor res pon dant à l’indice de la colonne (associée à x s ) qui sort de la
base et de la colonne e : indice de la colonne (associée à x e ) qui entre dans la base ;
2) on divise les élé ments de la ligne s par le pivot a se c’estàdire dans le tableau
cen tral et la colonne de droite, donc pour j 5 1, 2, c , 7 et on rem place l’indice du
tableau de gauche, 2
e
colonne, par l’indice e de la colonne qui entre dans la base ; on
rem place le coef fi cient c s du tableau de gauche, l
ère
colonne, par la valeur c e du coef
fi cient de la fonc tion éco no mique ;
3) parmi les autres lignes du tableau, celles qui com portent un 0 dans la colonne
e qui entre dans la base (a ke 5 0, où k 2 s), ne sont pas modi fiées : la variable
entrante x e est absente dans l’expression de la variable de l’ancienne base x k (qui reste
dans la nouvelle base).
4) les élé ments des autres lignes du tableau qui com portent un élé ment dif fé rent de
0 dans la colonne qui entre dans la base (a ke 2 0, où k 2 s), sont modi fiés comme
suit :
– on mul ti plie les élé ments de la nou velle ligne du pivot (désor mais ligne e) par cet
élé ment a ke (non nul) et on sous trait les résul tats aux élé ments cor res pon dants de
la ligne à modi fier ;
– ce trai te ment est appli cable aux élé ments du vec teur des seconds membres
(« colonne b ») ;
– il s’applique éga le ment aux élé ments de la ligne z de la fonc tion éco no mique ; en
par ti cu lier pour le second membre de la ligne z, on ins crit z 2
b s
a se
# D e .
Par exemple, reve nant au tableau pré cé dent (cf p. 313), on aura :
1) l’élé ment dis tin gué (pivot) est le 1 de ligne 5 et de la colonne 2 ;
2) la ligne 5, divi sée par le pivot égal à 1 reste donc la même ; on rem place, dans le
tableau de gauche, 5 par 2 (c’est àdire 5 par e) et immé dia te ment à gauche 0 par 12
(c’est àdire c 5 par c 2 ) ;
3) les lignes 4 et 6 ne subissent pas de modi fi ca tion (car elles com portent un 0 dans
la colonne entrante, c’est àdire la colonne 2) ;
4) la ligne 7 est modi fiée comme suit :
3000
6 750
3750
1
1
0
0
0
0
0
0
0
0
0
0
0
2
2
6
6
6
6
3
3
↑
anciens éléments de la ligne 7
les éléments de la ligne 5
multipliée par 6
nouvelle ligne 7 : (7) (7) 6 (5)
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
Plu tôt que d’appli quer, élé ment par élé ment, les for mules ci dessus, on emploie les
règles pra tiques de trans for ma tion du tableau très simples (qui leur sont équi va
lentes) sui vantes :
1) on repère le pivot a se qui est à l’inter sec tion de la ligne s et de la colonne e. C’est
l’indice de ligne cor res pon dant à l’indice de la colonne (associée à x s ) qui sort de la
base et de la colonne e : indice de la colonne (associée à x e ) qui entre dans la base ;
2) on divise les élé ments de la ligne s par le pivot a se c’estàdire dans le tableau
cen tral et la colonne de droite, donc pour j 5 1, 2, c , 7 et on rem place l’indice du
tableau de gauche, 2
e
colonne, par l’indice e de la colonne qui entre dans la base ; on
rem place le coef fi cient c s du tableau de gauche, l
ère
colonne, par la valeur c e du coef
fi cient de la fonc tion éco no mique ;
3) parmi les autres lignes du tableau, celles qui com portent un 0 dans la colonne
e qui entre dans la base (a ke 5 0, où k 2 s), ne sont pas modi fiées : la variable
entrante x e est absente dans l’expression de la variable de l’ancienne base x k (qui reste
dans la nouvelle base).
4) les élé ments des autres lignes du tableau qui com portent un élé ment dif fé rent de
0 dans la colonne qui entre dans la base (a ke 2 0, où k 2 s), sont modi fiés comme
suit :
– on mul ti plie les élé ments de la nou velle ligne du pivot (désor mais ligne e) par cet
élé ment a ke (non nul) et on sous trait les résul tats aux élé ments cor res pon dants de
la ligne à modi fier ;
– ce trai te ment est appli cable aux élé ments du vec teur des seconds membres
(« colonne b ») ;
– il s’applique éga le ment aux élé ments de la ligne z de la fonc tion éco no mique ; en
par ti cu lier pour le second membre de la ligne z, on ins crit z 2
b s
a se
# D e .
Par exemple, reve nant au tableau pré cé dent (cf p. 313), on aura :
1) l’élé ment dis tin gué (pivot) est le 1 de ligne 5 et de la colonne 2 ;
2) la ligne 5, divi sée par le pivot égal à 1 reste donc la même ; on rem place, dans le
tableau de gauche, 5 par 2 (c’est àdire 5 par e) et immé dia te ment à gauche 0 par 12
(c’est àdire c 5 par c 2 ) ;
3) les lignes 4 et 6 ne subissent pas de modi fi ca tion (car elles com portent un 0 dans
la colonne entrante, c’est àdire la colonne 2) ;
4) la ligne 7 est modi fiée comme suit :
3000
6 750
3750
1
1
0
0
0
0
0
0
0
0
0
0
0
2
2
6
6
6
6
3
3
↑
anciens éléments de la ligne 7
les éléments de la ligne 5
multipliée par 6
nouvelle ligne 7 : (7) (7) 6 (5)