62
Recherche opérationnelle
On obtient :
1
2
3
4
5
6
0
4
1
1
1
1
0
0
4
-M
6
2
1
-1
0
-1
+1
2
1+2M 1+M
1-M
0
-M
0
Z+2M
Faisons entrer dans la base; les règles de l'algorithme du simplexe donnent :
1
2
3
4
5
6
0
4
1
1/2
3/2
1
1/2
0
4
-M
6
2
1/2 -1/2 0
-1/2
1/2
2
0
1/2
3/2
0
1/2
-M-1/2
Z-1
On peut alors éliminer , dont on n'a plus besoin. Le tableau suivant est alors :
1
2
3
4
5
1
3
1
1/3
1
2/3
1/3
2
1
1
1
2/3
0
1/3
-1/3
2
0
0
0
-1
0
Z-4
On atteint une solution optimale
3
Remarque 1 : Lorsque l'on est amené à introduire plusieurs variables artificielles, on
peut les faire intervenir dans la fonction économique avec le même poids
(avec
très grand). Là aussi, si à la fin de l'algorithme du simplexe, une ou plusieurs
variables artificielles restent dans la base, c'est que le système des contraintes du P.L est
incompatible.
Remarque 2 : Il se peut également que l'on ait certaines contraintes qui soient des
égalités (et non des inégalités
).
3 La présence de gains marginaux pour des variables hors base montre qu’il existe des solutions
équivalentes (par exemple
On a donc affaire à une
dégénérescence du second type. C’est-à-dire à une infinité de solutions optimales.