64
Recherche opérationnelle
1
2
3
4
5
2
3
1
1/2
1
1
0
2
0
5
2
-2
0
-2
1
-1
+1
0
-2
0
Z-4
On se trouve dans le cas où l'une des variables de base
est nulle, dit cas de
dégénérescence du premier type. Pour pouvoir continuer l'algorithme du simplexe, il
convient de remplacer le zéro du second membre par un nombre
très petit, quitte à
le supprimer par la suite (ce raffinement est essentiellement destiné au calcul sur
ordinateur; il est en effet nécessaire que la machine puisse reconnaître, lors de
l'application du second critère de Dantzig, les quantités
avec
des
avec
).
On obtient le tableau optimal :
1
2
3
4
5
2
2
2
1
2
2
0
2
0
5
6
0
4
2
1
-3
0
-2
-4
0
Z-8
soit, en supprimant le , la solution optimale :
8
=
0
=
4
=
0
=
3
2
1
z
x
x
x
Les dégénérescences de ce type sont relativement importantes sur le plan théorique, dans
la mesure où elles représentent le seul cas où l'algorithme du simplexe peut ne pas
converger. Dans ce cas en effet, on montre qu'il peut y avoir cyclage, c'est-à-dire qu'au
cours de l'algorithme on rencontre un sommet déjà rencontré. Il existe des procédures
pour éviter ce type de mésaventures, par ailleurs très rares, mais dans le cadre limité de
cet exposé, nous n'en parlerons pas.
Remarque : On peut à propos des dégénérescences recenser les principaux « accidents »
pouvant survenir au cours de l'algorithme du simplexe :
1) Un (ou plusieurs) élément du second membre est nul :
Dégénérescence du premier type
Signification géométrique : le sommet correspondant, dans , est l'intersection de plus
de hyperplans.
2) Un gain marginal associé à une variable hors base est nul.
Dégénérescence du second type.