Pivot und Theta sagt, wie weit eine Nichtbasisvariable steigen darf, bevor eine Basisvariable 0 wird. In der Rechnung 220/11 ist das 20, also verlässt S2 die Basis. Dazu: Pivot und Theta
Voraussetzung: Schlupfvariable
Der Simplex-Algorithmus wandert von Ecke zu Ecke und wird dabei in jedem Schritt besser. Jeder Schritt tauscht eine Variable in der Basis. Welche Variable hereinkommt und welche hinausgeht, entscheiden zwei Regeln: die Wahl der Pivotspalte und die Wahl der Pivotzeile mit dem Quotienten \(\Theta\). Diese Karte übt genau diese Wahl. Voraussetzung ist das Starttableau mit Schlupfvariablen.
Im Tableau steht unter den Variablen die Zeile \(Z\) mit den Einträgen \(-c_1,\dots,-c_n,0,\dots,0\). Ein negativer Eintrag bedeutet, dass die Zielfunktion noch wachsen kann, wenn diese Variable in die Basis kommt. Hat die Zeile \(Z\) keinen negativen Eintrag mehr, ist das Tableau fertig.
- Pivotspalte: die Spalte mit dem kleinsten Eintrag der Zeile \(Z\).
- \(\Theta\): Für jede Zeile, in der der Eintrag der Pivotspalte positiv ist, teilst du die rechte Seite \(b\) durch diesen Eintrag.
- Pivotzeile: die Zeile mit dem kleinsten \(\Theta\). Der Eintrag in Pivotzeile und Pivotspalte heißt Das Pivotelement ist der positive Eintrag, durch den die Pivotzeile geteilt wird. Dazu: Pivot und Theta.
Warum der kleinste \(\Theta\)-Wert? Die neue Basisvariable darf nur so weit wachsen, bis die erste Nebenbedingung ausgeschöpft ist. Genau das berechnet \(\Theta\): Es ist der größte Wert der Variablen, den die Zeile erlaubt. Der kleinste dieser Werte ist die erste Grenze. Bei einem Eintrag \(\le 0\) wächst die linke Seite nie bis zur Kapazität, die Zeile begrenzt nichts und bekommt kein \(\Theta\).
Eine Zeile mit negativem Eintrag
In der Pivotspalte stehen die Einträge \(4\), \(-2\) und \(3\) mit den rechten Seiten \(40\), \(30\) und \(36\). Für die Zeile mit \(-2\) gibt es kein \(\Theta\). Die übrigen sind \(\frac{40}{4}=10\) und \(\frac{36}{3}=12\), die Pivotzeile ist also die erste. Die Zeile mit \(-2\) wird im nächsten Schritt durch das Nullen nur verändert und bleibt zulässig.
Ein zweites Beispiel, nur eine Zeile kommt in Frage
Sind in der Pivotspalte alle Einträge positiv bis auf einen, bleibt unter Umständen nur eine Zeile mit einem \(\Theta\) übrig. Sie ist dann die Pivotzeile, ganz gleich wie groß ihr \(\Theta\) ist. Gibt es gar keinen positiven Eintrag in der Pivotspalte, ist das Problem unbeschränkt, denn die Variable kann beliebig wachsen, ohne eine Kapazität zu verletzen.
reduzierten Kosten
Der Eintrag in der Zielfunktionszeile zeigt, ob Z in dieser Spalte noch wachsen kann.