313
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
no mique ; d’autre part, nous savons aussi que toutes les variables (prin ci pales ou
d’écart) doivent demeu rer non négatives. Nous repar tons ci dessous du som met ini
tial O, et présentons sous forme de tableaux le système associé à O.
A
1
A
3
A
2
A
4
A
5
A
6
A
7
i
j
∆ j
z 0
1
1
1
1
1
1 000
1 500
6 750
500
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
6
6
3
3
5
4
Sommet
O
7
4
12
Repre nons, dans ces condi tions, la repré sen ta tion matricielle ini tiale et notons les
colonnes par un indice j 5 1, 2, c , 7 , de manière que les vecteurs colonnes
puissent être dénom més A 1 , A 2 , c , A 7 : notons aussi b le vec teur second membre.
Ins cri vons main te nant, à gauche et face à la valeur qu’elle a dans la solu tion (base)
ini tiale, l’indice i de la variable x i (ici, au départ : x 4 5 1 000, x 5 5 500, x 6 5 1 500,
x 7 5 6 750 ; les indices i sont donc : 4, 5, 6 et 7) ; ces indices i ser vi ront à dési gner les
lignes de la matrice ; ils sont asso ciés aux variables de base : la colonne tout à gauche
est donc un descriptif de la base.
Lors de toute ité ra tion, l’élé ment de la matrice situé à l’inter sec tion d’une ligne i et
d’une colonne j sera dési gné par a ij ; l’élé ment de la colonne b situé sur la ligne i sera
sim ple ment dési gné par b i . Ini tia le ment, la colonne b coïn cide avec la colonne des
seconds membres des contraintes, notée tra di tion nel le ment b comme ci dessus.
Enfin, écrivons séparément la ligne de la fonc tion éco no mique : z 5 4x 1 1 12x 2 1 3x 3 ,
dont les coef fi cients seront écrits dans la ligne du bas ; le coefficient en colonne A j
sera noté dans la suite : D j . Lors de toute itération, z sera exprimé uniquement en
fonction des variables hors base ; par suite D j = 0 si x j est une variable de base
NB. Sur la ligne des D j dans les colonnes Α
4
, Α
5
, Α
6
, Α
7
, on a écrit des 0, car la fonc
tion éco no mique peut s’écrire :
4x 1 1 12x 2 1 3x 3 1 0x 4 1 0x 5 1 0x 6 1 0x 7 5 z 2 0,
car les variables d’écart sont de pro fit nul. De plus, ini tia le ment, z 5 0.
Les for mules du chan ge ment
(1)
de coor don nées, réa lisé par la sor tie d’un vec teur
A
s
de la base et l’entrée d’un vec teur A
e
sont les sui vantes (autrement dit : x s est la
variable sortante et x e , la variable entrante) :
• nou velle valeur de la fonc tion éco no mique : zr 5 z 1
b s
a se
# D e , z étant l’ancienne
valeur ;
le coefficient a se est nommé « pivot ».
(1) Le lecteur pourra préférer les règles pratiques de transformation : p. 317.
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
no mique ; d’autre part, nous savons aussi que toutes les variables (prin ci pales ou
d’écart) doivent demeu rer non négatives. Nous repar tons ci dessous du som met ini
tial O, et présentons sous forme de tableaux le système associé à O.
A
1
A
3
A
2
A
4
A
5
A
6
A
7
i
j
∆ j
z 0
1
1
1
1
1
1 000
1 500
6 750
500
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
6
6
3
3
5
4
Sommet
O
7
4
12
Repre nons, dans ces condi tions, la repré sen ta tion matricielle ini tiale et notons les
colonnes par un indice j 5 1, 2, c , 7 , de manière que les vecteurs colonnes
puissent être dénom més A 1 , A 2 , c , A 7 : notons aussi b le vec teur second membre.
Ins cri vons main te nant, à gauche et face à la valeur qu’elle a dans la solu tion (base)
ini tiale, l’indice i de la variable x i (ici, au départ : x 4 5 1 000, x 5 5 500, x 6 5 1 500,
x 7 5 6 750 ; les indices i sont donc : 4, 5, 6 et 7) ; ces indices i ser vi ront à dési gner les
lignes de la matrice ; ils sont asso ciés aux variables de base : la colonne tout à gauche
est donc un descriptif de la base.
Lors de toute ité ra tion, l’élé ment de la matrice situé à l’inter sec tion d’une ligne i et
d’une colonne j sera dési gné par a ij ; l’élé ment de la colonne b situé sur la ligne i sera
sim ple ment dési gné par b i . Ini tia le ment, la colonne b coïn cide avec la colonne des
seconds membres des contraintes, notée tra di tion nel le ment b comme ci dessus.
Enfin, écrivons séparément la ligne de la fonc tion éco no mique : z 5 4x 1 1 12x 2 1 3x 3 ,
dont les coef fi cients seront écrits dans la ligne du bas ; le coefficient en colonne A j
sera noté dans la suite : D j . Lors de toute itération, z sera exprimé uniquement en
fonction des variables hors base ; par suite D j = 0 si x j est une variable de base
NB. Sur la ligne des D j dans les colonnes Α
4
, Α
5
, Α
6
, Α
7
, on a écrit des 0, car la fonc
tion éco no mique peut s’écrire :
4x 1 1 12x 2 1 3x 3 1 0x 4 1 0x 5 1 0x 6 1 0x 7 5 z 2 0,
car les variables d’écart sont de pro fit nul. De plus, ini tia le ment, z 5 0.
Les for mules du chan ge ment
(1)
de coor don nées, réa lisé par la sor tie d’un vec teur
A
s
de la base et l’entrée d’un vec teur A
e
sont les sui vantes (autrement dit : x s est la
variable sortante et x e , la variable entrante) :
• nou velle valeur de la fonc tion éco no mique : zr 5 z 1
b s
a se
# D e , z étant l’ancienne
valeur ;
le coefficient a se est nommé « pivot ».
(1) Le lecteur pourra préférer les règles pratiques de transformation : p. 317.