Degeneration
Voraussetzung: Pivot und Theta
Der vierte Sonderfall des Skripts ist unscheinbar: Das Tableau sieht aus wie immer, nur steht in der Spalte der rechten Seite eine \(0\) bei einer Basisvariablen. Du lernst, was das heißt, wie es bei gleichen Quotienten entsteht und warum \(Z\) in einem Schritt mit Quotient \(0\) nicht wächst. Voraussetzung ist der Pivotschritt mit dem kleinsten Quotienten.
Eine zulässige Basislösung heißt degeneriert, wenn mindestens eine Basisvariable den Wert \(0\) hat. Du siehst es am Tableau in der Spalte der rechten Seite, bevor du pivotierst. Geometrisch gehen in dieser Ecke mehr Grenzen durch einen Punkt, als nötig sind: Bei zwei Variablen schneiden sich in der Ecke drei Geraden statt zwei.
Degeneration kann schon im Starttableau vorliegen, wenn eine rechte Seite \(0\) ist. Häufiger entsteht sie während des Verfahrens so:
- In der Pivotspalte haben zwei Zeilen denselben kleinsten Quotienten Rechte Seite durch Eintrag. Beide Grenzen werden zugleich erreicht.
- Du wählst eine der beiden Zeilen als Pivotzeile. Beide Wahlen sind erlaubt und führen zum richtigen Ergebnis.
- Die andere Zeile hat nach dem Schritt die rechte Seite \(0\). Ihre Basisvariable ist \(0\), die Basislösung ist degeneriert.
Der Grund: Der Quotient nennt, wie weit die Pivotvariable wachsen darf, bis eine Zeile knapp wird. Bei gleichen Quotienten werden zwei Zeilen im selben Moment knapp. Nur eine der beiden Basisvariablen verlässt die Basis, die andere bleibt in der Basis und ist dann \(0\).
Ein Schritt mit Quotient \(0\) ändert \(Z\) nicht. Der Zuwachs von \(Z\) ist der Betrag des negativen Eintrags in der Zeile \(Z\) mal der Quotient. Ist die rechte Seite der Pivotzeile \(0\) und der Eintrag positiv, ist der Quotient \(0\div a=0\), und \(Z\) bleibt gleich. Die Ecke wechselt im Tableau, der Punkt in der Ebene bleibt derselbe.
Die Pivotspalte ist \(x_1\) mit den Einträgen \(1\), \(1\) und \(0\) bei den rechten Seiten \(4\), \(4\) und \(3\). Die dritte Zeile hat den Eintrag \(0\), also keinen Quotienten. Die ersten beiden Zeilen haben den Quotienten \(4\div 1=4\), beide gleich. Wählst du die erste Zeile, ist \(x_1=4-x_2-S_1\). Setzt du das in die zweite Zeile \(x_1+S_2=4\) ein, steht dort \(S_2=x_2+S_1\). Mit \(x_2=0\) und \(S_1=0\) ist \(S_2=0\). Die Basisvariable \(S_2\) ist \(0\), die Basislösung \((4,0)\) ist degeneriert, mit \(Z=8\). Geometrisch gehen die drei Geraden \(x_1+x_2=4\), \(x_1=4\) und \(x_2=0\) durch den Punkt \((4,0)\).
Ein zweites Beispiel, Quotient 0
Ein Tableau hat \(Z=12\). Unter der Pivotspalte steht in der Zeile \(Z\) der Eintrag \(-3\). Die Pivotzeile hat die rechte Seite \(0\) und den Eintrag \(2\). Der Quotient ist \(0\div 2=0\), der Zuwachs \(3\cdot 0=0\). Nach dem Schritt ist \(Z\) weiter \(12\). Die Basis hat gewechselt, die Zeile \(Z\) hat sich geändert, und im nächsten Schritt kann \(Z\) wieder wachsen.
Mehr als zwei Zeilen mit gleichem Quotienten
Haben drei Zeilen denselben kleinsten Quotienten, bleiben nach dem Schritt zwei Basisvariablen mit dem Wert \(0\). Du zählst immer die Zeilen mit dem kleinsten Quotienten unter den Zeilen mit positivem Eintrag. Eine Zeile mit Eintrag \(0\) oder negativem Eintrag hat keinen Quotienten und zählt nicht.