335
© Dunod – Toute reproduction non autorisée est un délit.
8.5 Démar rage de l’algo rithme du sim plexe…
8.5.4 Cas géné ral : emploi de variables arti fi cielles
Un pro gramme linéaire peut com por ter 3 types de contraintes (Ρ), (Q) et (R) :
les contraintes du types (P) sont de la forme : a
p
j51
a ij x j < b i où b i est posi tif
(ou nul) ; après intro duc tion d’une variable d’écart x i , il vient : a
p
j51
a ij # x j 1 x i 5 b i ,
les contraintes du type Q sont de la forme : a
p
j51
a kj # x j > b k (où b k est posi tif ou nul) ;
après intro duc tion d’une variable d’écart x k , il vient : a
p
j51
a ij # x j 2 x k 5 b k .
Enfin les contraintes de type (R) sont celles qui, à l’ori gine, sont en équa tion :
a
p
j51
a ij # x j 5 b l (b l > 0), donc dans les quelles on n’intro duit pas de variable d’écart.
Voici un exemple avec m 5 3 contraintes expli cites : la pre mière de type (P) ; la
deuxième, de type (Q) ; la troi sième de type (R).
e
x 1 1 2x 2 1 x 3 < 5 (P)
2x 1 1 x 2 1 x 3 > 1 (Q)
x 1 1 x 2
5 4 (R)
x 1 , x 2 , x 3 > 0
4x 1 1 5x 2 1 3x 3 5 z 3max4
soit :
e
x 1 1 2x 2 1 x 3 1 x 1
5 5
2x 1 1 x 2 1 x 3
2 x 2 5 1
x 1 1 x 2
5 4
x 1 , x 2 , x 3 , x 1 , x 2 > 0
4x 1 1 5x 2 1 3x 3 1 0x 1 1 0x 2 5 z 3max4
Si toutes les contraintes étaient de type (P), on serait dans le cas « favo rable », traité
plus haut au 8.5.1.
Nous allons consti tuer une base ini tiale de matrice B 5 I ; on peut inclure dans
cette base les variables d’écart ajou tées dans les contraintes de type (P) ; en effet la
colonne asso ciée à cha cune de ces variables d’écart est uni taire ; ainsi dans l’exemple
ci­ dessus la colonne asso ciée à x 1 est : C
1
0
0
S .