Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)

Es wird nun ein weiterer Simplexschritt durchgeführt. Ziel ist es, die künstliche Variable $y_1$ aus der Basis zu eliminieren. Es müssen zunächst wieder Pivotspalte, Pivotzeile und Pivotelement nach dem primalen Simplexverfahren bestimmt werden:

Es wird zunächst wieder die Pivotspalte bestimmt, indem der kleinste negative Wert ausgewählt wird. Da hier $M$ als hinreichend groß angenommen wird, bestimmt man den kleinsten negativen Wert anhand der $M$-Werte:

$-\frac{2}{3}M$ und $-\frac{1}{3}M$

Der kleinste negative Wert ist demnach $-\frac{2}{3}M$.

Die Pivotzeile wird dann bestimmt, indem die rechte Seite durch die positiven Werte der Pivotspalte geteilt werden und der kleinste Quotient ausgewählt wird. In diesem Fall ist $4:\frac{2}{3} = 6$ der kleinste Quotient. 

Das Pivotelement liegt dort, wo sich Pivotspalte und Pivotzeile schneiden. 

Es wird als nächstes das neue Tableau nach Durchführung eines weiteren Simplexschrittes aufgestellt. Dabei müssen Basisvariable und Nichtbasisvariable des Pivotelements vertauscht werden:

In der obigen Tabellen ist das neue Tableau nach einem weiteren Simplexschritt zu sehen. Die Basisvariable $y_1$ und die Nichtbasisvariable $x_2$ sind vertauscht worden. Sobald eine künstliche Variable $y_i$ die Basis verlässt und zur Nichtbasisvariable wird, kann diese im weiteren Verlauf unberücksichtigt bleiben. Dies ist anhand der $x$ angedeutet. Dies stellt auch gleichzeitig die Pivotspalte dar, welche dann für das neue Tableau nicht berechnet werden muss. Auch der Wert des alten Pivotelements muss also für das neue Tableau nicht bestimmt werden. Es müssen aber die Werte der alten Pivotzeile und die restlichen Werte bestimmt werden.

Werte der alten Pivotzeile

Der alte Wert innerhalb der Pivotzeile wird durch das Pivotelement geteilt.

Restliche Werte

Die restlichen Werte werden bestimmt indem der alte Wert abzüglich der alten Werte aus zugehöriger Pivotspalte mal Pivotzeile durch Pivotelement berechnet wird. Z.B. der Wert $-\frac{1}{2}$ in der Zielfunktionszeile unter $x_3$:

$M - [\frac{(- \frac{1}{3} - \frac{2}{3}M \cdot -1)}{\frac{2}{3}}]$

$M - [\frac{ \frac{1}{3} + \frac{2}{3}M}{\frac{2}{3}}]$

$M - \frac{1}{2} - 1M$

$-\frac{1}{2}$

Zielfunktionswert

Der Zielfunktionswert wurde ermittelt, indem die Basisvariablen mit den Werten der rechten Seite in die Zielfunktion eingesetzt werden (die Nichtbasisvariablen besitzen den Wert Null):

$z = (2 + 4M) \cdot 2 + (1 + 2M) \cdot 6 - M \cdot 0 - M \cdot 0 - 20M$

$z = (2 + 4M) \cdot 2 + (1 + 2M) \cdot 6 - 20M $

$z = 4 + 8M + 6 + 12 M - 20M = 10$.

Zulässige Lösung

Es sind alle künstlichen Variablen $y_i$ aus der Basis entfernt worden. Auch die $M$-Werte sind alle eliminiert. Es liegt demnach eine zulässige Lösung vor:

$x_1 = 2$, $x_2 = 6$, $x_5 = 2$ und $y_1 = y_2 = x_3 = x_4 = 0$ mit dem Zielfunktionswert $z = 10$.