Das Phänomen der Degeneration tritt auf, wenn im Verlauf des Simplexalgorithmus gleiche charakteristische Koeffizienten auftreten, so dass eine Auswahlmöglichkeit für die Pivotzeile entsteht.
Dadurch entsteht im nächsten Tableau mindestens eine Basisvariable, die den Wert Null erhält.
Eine Basislösung heißt degeneriert, wenn mindestens eine Basisvariable Null ist.
Anschaulich tritt die Degeneration in einem Problem mit n Kontrollvariablen immer dann ein, wenn sich in einer Ecke des zulässigen Bereiches mehr als n Hyperebenen schneiden.
Starttableau:
Erstes verbessertes Tableau:
Lösung mit a12 als Pivotelement:
Optimale Basislösung: (x1,x2,y1,y2,y3) = (4,8,0,0,0) ; G* =2240,
mit den Basisvariablen x1,x2,y3 und den Nichtbasisvariablen y1,y2.
Lösung mit a32 als Pivotelement::
Optimale Basislösung: (x1,x2,y1,y2,y3) = (4,8,0,0,0) ; G* =2240,
mit den Basisvariablen x1,x2,y1 und den Nichtbasisvariablen y2,y3.
Im bisher geschilderten Verfahren ist garantiert dass der Wert der Zielfunktion (bei der Maximierung) nicht kleiner wird. Sind degenerierte Basislösungen vorhanden, dann ist es theoretisch nicht ausgeschlossen, dass das Verfahren über mehrere Basislösungen (Tableaus) führt, ohne die Zielfunktion zu verbessern, um schließlich wieder auf eine zuvor berechnete Basislösung zu gelangen. Auf diese Weise können Zyklen entstehen, die verhindern, dass das Verfahren zum Optimum gelangt. Der Algorithmus gelangt in eine "Endlosschleife".
In solchen Fällen muss der Zyklus erkannt werden; der Algorithmus wird dann durch Wahl einer anderen Pivotzeile und damit eines anderen Pivotelementes fortgesetzt. Er verlässt damit den Zyklus und arbeitet mit einer anderen Ecke weiter.
Es existiert eine zusätzliche Pivotauswahlregel, die sicherstellt, dass bei jedem Schritt eine neue Basislösung berechnet wird und damit Zyklen verhindert. In der Praxis hat sich jedoch eine geringe Relevanz dieses Problems herausgestellt. So zeigt es sich, dass die bei der numerischen Berechnung innerhalb eines Computers unvermeidlichen Rundungsfehler dazu führen, dass sich im Verfahren, nach dem Durchlaufen hinreichend vieler Zyklen, ein Wert in den Nachkommastellen so weit verändert hat, dass der Simplexalgorithmus ein anderes Pivotelement auswählt und den Zyklus verlässt.
Daher wird hier lediglich das Problem als solches dargestellt und auf die Behandlung der zusätzlichen Pivotauswahlregel verzichtet.
