Algorithme du simplex
63
Dans le cas où une solution de base n'est pas évidente, il convient alors, on le sait, de
transformer la contrainte
)
(
=
a
b
x
a
i
j
j
i
en deux contraintes :
)
(
'
i
j
j
i
a
b
x
a
j
j
i x
a
)
"
(a
b i
- la contrainte (a') va générer une variable d'écart
- la contrainte (a'') va générer une variable d'écart et une variable artificielle.
2.4. CAS DE LA DEGENERESCENCE DU PREMIER TYPE
Prenons l'exemple :
2
2
1
3
2
1
x
x
x
4
2
4
3
2
1
x
x
x
0
,
,
3
2
1
x
x
x
Résolvons cet exemple, en introduisant les variables d'écart
et . Le premier tableau
est :
1
2
3
4
5
0
4
1
1/2
1
1
0
2
0
5
4
-1
+2
0
1
4
1
2
2
0
0
Z
Si l'on fait entrer
tout en faisant sortir
, on obtient, ce qui est
arbitraire puisque :