331
© Dunod – Toute reproduction non autorisée est un délit.
8.5 Démar rage de l’algo rithme du sim plexe…
Tel est le cas dans notre exemple du pro blème de l’ate lier.
Dans cha cune des m contraintes, on ajoute une variable d’écart :
a
p
j51
a ij # x j 1 x i 5 b i .
Les m variables d’écart x i forment une base de matrice iden tité I (dont les élé
ments diagonaux sont égaux à 1 et les non diagonaux égaux à 0). Les p 5 n 2 m
variables prin ci pales : x 1 , x 2 , c , x p sont hors base.
Le som met asso cié est l’ori gine Ο (dans l’espace des variables prin ci pales : R
p
).
L’expres sion des variables de base en fonc tion des variables hors base est immé
diate :
x i 5 b i – a
p
j51
a ij # x j , (i 5 1, 2, c , m).
Enfin, l’expres sion ini tiale de la fonc tion éco no mique : z 5 a
p
j51
c j # x j fait que z est
direc te ment expri mée uni que ment en fonc tion des variables hors- base :
z 5 a
p
j51
c j # x j 1 (0 # x 1 1 0 # x 2 1 c 1 0 # x m )
Le tableau asso cié à cette base ini tiale est :
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
. . .
. . .
. . .
. . .
. . .
a 11
a 21
a 12
a 2p
c p
p
z 0
a 1p
b 1
b 2
b m
a mp
a 22
a m2
a m1
c 2
c 1
m
1
1
2
1
1
0
0
0
0
0
0
0
0
0
1
1
2
2
m
i bi
(0)
i
Le lec teur se repor tera à notre exemple de l’ate lier pour l’illus tra tion de ce cas.
8.5.2 Cas où une solu tion est connue à l’avance
Il arrive fré quem ment qu’un « sys tème » dont on veut opti mi ser la marche pos sède
déjà un point de fonc tion ne ment, c’est àdire dans le cadre d’un pro gramme linéaire,
une solu tion admis sible (on rappelle qu’une telle solution vérifie les m + n contraintes
du PL). Cette solu tion ne sera uti li sable, pour la réso lu tion par l’algoritme du sim plexe,
que s’il s’agit d’une solu tion de base réa li sable, c’est- à-dire com por tant, au plus, m
variables posi tives (les autres étant nulles) et telles que les m colonnes de la matrice A
asso ciées à ces variables forment une matrice régu lière (inver sible), notée B.
Le démar rage de l’algo rithme du sim plexe néces site de connaître l’expres sion
des m variables de base et de z, en fonc tion des variables hors base.
© Dunod – Toute reproduction non autorisée est un délit.
8.5 Démar rage de l’algo rithme du sim plexe…
Tel est le cas dans notre exemple du pro blème de l’ate lier.
Dans cha cune des m contraintes, on ajoute une variable d’écart :
a
p
j51
a ij # x j 1 x i 5 b i .
Les m variables d’écart x i forment une base de matrice iden tité I (dont les élé
ments diagonaux sont égaux à 1 et les non diagonaux égaux à 0). Les p 5 n 2 m
variables prin ci pales : x 1 , x 2 , c , x p sont hors base.
Le som met asso cié est l’ori gine Ο (dans l’espace des variables prin ci pales : R
p
).
L’expres sion des variables de base en fonc tion des variables hors base est immé
diate :
x i 5 b i – a
p
j51
a ij # x j , (i 5 1, 2, c , m).
Enfin, l’expres sion ini tiale de la fonc tion éco no mique : z 5 a
p
j51
c j # x j fait que z est
direc te ment expri mée uni que ment en fonc tion des variables hors- base :
z 5 a
p
j51
c j # x j 1 (0 # x 1 1 0 # x 2 1 c 1 0 # x m )
Le tableau asso cié à cette base ini tiale est :
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
. . .
. . .
. . .
. . .
. . .
a 11
a 21
a 12
a 2p
c p
p
z 0
a 1p
b 1
b 2
b m
a mp
a 22
a m2
a m1
c 2
c 1
m
1
1
2
1
1
0
0
0
0
0
0
0
0
0
1
1
2
2
m
i bi
(0)
i
Le lec teur se repor tera à notre exemple de l’ate lier pour l’illus tra tion de ce cas.
8.5.2 Cas où une solu tion est connue à l’avance
Il arrive fré quem ment qu’un « sys tème » dont on veut opti mi ser la marche pos sède
déjà un point de fonc tion ne ment, c’est àdire dans le cadre d’un pro gramme linéaire,
une solu tion admis sible (on rappelle qu’une telle solution vérifie les m + n contraintes
du PL). Cette solu tion ne sera uti li sable, pour la réso lu tion par l’algoritme du sim plexe,
que s’il s’agit d’une solu tion de base réa li sable, c’est- à-dire com por tant, au plus, m
variables posi tives (les autres étant nulles) et telles que les m colonnes de la matrice A
asso ciées à ces variables forment une matrice régu lière (inver sible), notée B.
Le démar rage de l’algo rithme du sim plexe néces site de connaître l’expres sion
des m variables de base et de z, en fonc tion des variables hors base.