Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)

Das primale Simplexverfahren ist dann abgeschlossenen, wenn keine negativen Werte mehr in der Zielfunktionsleiste stehen:

Da in diesem Beispiel aber noch negative Werte (hier -1/4) vorhanden sind, wird ein weiterer Simplexschritt durchgeführt, da der Zielfunktionswert noch weiter verbessert werden kann. Es wird zunächst wieder die Pivotspalte (kleinstes negatives Element) und die Pivotzeile (kleinster positiver Quotient) ausgewählt. Dort wo sich Pivotspalte und Pivotzeile schneiden liegt das Pivotelement:

Da beide Quotienten der rechten Seite den gleichen Wert aufweisen, wird die Pivotzeile beliebig gewählt.

Als nächstes werden nacheinander die Rechenschritte -siehe vorherigen Abschnitt- durchgeführt um die neuen Elemente zu bestimmen. Nicht vergessen: Dort wo sich das Pivotelement befindet müssen die Basisvariable und die Nichtbasisvariable vertauscht werden:

In dem obigen Tableau sind zunächst alle neuen Elemente der Pivotspalte und Pivotzeile eingetragen. Das Pivotelement geht in seinen reziproken Wert über (1/Pivotelement). Die Werte der Pivotspalte werden bestimmt, indem der alte Wert durch das Pivotelement dividiert wird und mit -1 multipliziert. Die Werte der Pivotzeile, indem der alte durch das Pivotelement dividiert wird. Die restlichen Werte des neuen Tableaus ergeben sich wie folgt:

Für diese restlichen Werte wird die Berechnung nochmals separat aufgeführt:

Basislösung

Aufgrund der Durchführung eines weiteren Simplexschrittes resultiert eine neue Basislösung. Dabei besitzen die Nichtbasisvariablen immer den Wert Null und und die Basisvariablen immer den Wert der rechten Seite: , und . 

Der Zielfunktionswert ist bei dieser zweiten Basislösung:

Der Zielfunktionswert hat sich demnach verbessert und liegt bei 4. 

Da keine weiteren negativen Werte in der Zilefunktionszeile mehr gegeben sind, ist das Verfahren abgeschlossen.

Interpretation

Es kann nun begonnen werden die optimale Basislösung zu interpretieren. Die Basisvariablen besitzen die Werte der rechten Seite, also:

.

Das gesamte Problem sieht wie folgt aus:

    max!

u.d.N.

Zusammenfassend kann gesagt werden, dass von Einheiten produziert/erbracht werden und von Einheiten. Dies stellt die optimale Kombination dar, um unter den gegebenen Nebenbedingungen den größten Zielfunktionswert (hier: 4) zu erreichen. Die erste Restriktion wird beim Einsetzen von vollständig ausgenutzt, deswegen ist im Ausgangstableau die Schlupfvariable . Es ist also keine Kapazität mehr offen. Betrachtet man die zweite Restriktion, so sind beim Einsetzen von noch 4 Einheiten übrig. Dies zeigt auch im Endtableau die Schlupfvariable an. Es stehen hier also noch 4 Einheiten zur Verfügung. Die letzte Restriktion wird vollständig ausgenutzt, wenn produziert wird. Dies zeigt auch im Endtableau die Schlupfvariable an. Diese Restriktion führt auch dazu, dass Einheiten produziert werden und für . Hier dürfte nur mit dem Wert 3 eingehen, wobei gesetzt werden müsste, damit diese Restriktion nicht überschritten wird. Dies würde aber einen Zielfunktionswert von 3 zur Folge habe. Demnach ergibt sich am Ende und mit dem Zielfunktionswert 4.