ZU DEN KURSEN!

Operations Research - Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)

Kursangebot | Operations Research | Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)

Operations Research

Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)

Inhaltsverzeichnis

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

Primales Simplexverfahren Austauschritt

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:

Primales Simplexverfahren Austauschritt

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:

Primales Simplexverfahren neues Tableau

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:

Primales Simplexverfahren Optimale Lösung

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

$-\frac{3}{5} = \frac{1}{2} - \frac{-\frac{1}{4} \cdot -\frac{1}{2}}{\frac{5}{4}}$

$\frac{2}{5} = \frac{1}{4} - \frac{-\frac{1}{4} \cdot \frac{3}{4}}{\frac{5}{4}}$

$\frac{1}{5} = \frac{1}{4} - \frac{-\frac{1}{4} \cdot -\frac{1}{4}}{\frac{5}{4}}$

$4 = 2 - \frac{5 \cdot -\frac{1}{2}}{\frac{5}{4}}$

$0  = 3 - \frac{5 \cdot \frac{3}{4}}{\frac{5}{4}}$

Basislösung

Aufgrund der Durchführung eines weiteren Simplexschrittes resultiert eine neue Basislösung. Dabei besitzen die Nichtbasisvariablen immer den Wert Null $x_5 = 0$ und $x_3 = 0$ und die Basisvariablen immer den Wert der rechten Seite: $x_2 = 4$, $x_4 = 4$ und $x_1 = 0$. 

Der Zielfunktionswert ist bei dieser zweiten Basislösung:

$f(0,0) = 1 \cdot 0 + 1 \cdot 4 + 0 \cdot 0 + 0 \cdot 4 + 0 \cdot 0 = 4$


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:

$x_1 = 0$

$x_2 = 4$

$x_4 = 4$.


Das gesamte Problem sieht wie folgt aus:

$f(x_1, x_2) = x_1 + x_2 + 0x_3 + 0x_4 + 0x_5$  $ \rightarrow$   max!

u.d.N.

$x_1 + 2x_2 + x_3                      = 8$

$2x_1 + x_2         + x_4              = 8$

$4x_1 + 3x_2                + x_5    = 12$

$x_1, x_2, x_3, x_4, x_5 \ge 0$

Zusammenfassend kann gesagt werden, dass von $x_1 =0 $ Einheiten produziert/erbracht werden und von $x_2 = 4$ 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 $x_2 = 4$ vollständig ausgenutzt, deswegen ist im Ausgangstableau die Schlupfvariable $x_3 = 0$. Es ist also keine Kapazität mehr offen. Betrachtet man die zweite Restriktion, so sind beim Einsetzen von $x_2 = 4$ noch 4 Einheiten übrig. Dies zeigt auch im Endtableau die Schlupfvariable $x_4 = 4$ an. Es stehen hier also noch 4 Einheiten zur Verfügung. Die letzte Restriktion wird vollständig ausgenutzt, wenn $x_2 = 4$ produziert wird. Dies zeigt auch im Endtableau die Schlupfvariable $x_5 = 0$ an. Diese Restriktion führt auch dazu, dass $x_2 = 4$ Einheiten produziert werden und für $x_1 = 0$. Hier dürfte $x_1$ nur mit dem Wert 3 eingehen, wobei $x_2 = 0$ 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 $x_2 = 4$ und $x_1 = 0$ mit dem Zielfunktionswert 4.