Simplex-Algorithmus

Iterationsschritt 1: In die Basis eintretende Variable bestimmen

Wähle aus der letzten Zeile die kleinste negative Zahl aus.

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV &\colorbox{Red}{${\color{white}x_1}$} & x_2 & y_1 & y_2 & RS & Q \\ \hline y_1 & 16 & 6 & 1 & & 252 & \\ \hline y_2 & 4 & 12 & & 1 & 168 & \\ \hline -VP &\fcolorbox{Red}{}{$-150$} & -100 & & & & \\ \hline \end{array} $$

$$ \min\{-150;-100\} = -150 $$

$\Rightarrow x_1$ tritt in diesem Iterationsschritt in die Basis ein.

Ökonomische Interpretation:
Im 1. Teilschritt überlegen wir, welches der beide Produkte ($x_1$ oder $x_2$) für einen größeren Zuwachs unserer zu maximierenden Funktion $z(x_1,x_2) = 150x_1 + 100x_2$ sorgt. Es ist leicht zu erkennen, dass $x_1$ einen größeren Einfluß auf die Zielfunktion hat als $x_2$.

Iterationsschritt 1: Aus der Basis zu eliminierende Variable bestimmen

Teile die Werte, die in der Spalte $RS$ stehen, durch die Koeffizienten aus der im vorherigen Schritt bestimmten Spalte und wähle hieraus die kleinste positive Zahl aus.

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & x_1 & x_2 & y_1 & y_2 & RS & Q \\ \hline \colorbox{Green}{${\color{white}y_1}$} & 16 & 6 & 1 & & 252 &\frac{252}{16} =\fcolorbox{Green}{}{$15{,}75$} \\ \hline y_2 & 4 & 12 & & 1 & 168 & \frac{168}{4} = 42 \\ \hline -VP &-150 & -100 & & & & \\ \hline \end{array} $$

$$ \min\{15{,}75;42\} = 15{,}75 $$

$\Rightarrow y_1$ wird aus der Basis eliminiert.

Ökonomische Interpretation:
Im 1. Teilschritt haben wir uns dazu entschlossen, ausschließlich $x_1$ zu produzieren. Die Frage ist nun, wie viele Einheiten von Kabel Typ A ($x_1$) produziert werden können, ohne eine Restriktion zu verletzen. Um diese Frage zu beantworten, dividieren wir in der Spalte $Q$ die vorhandenen Kapazitäten von $y_1$ ($252$) und $y_2$ ($168$) durch die jeweils benötigten Mengen. Zur Erinnerung: Zur Produktion von Kabel Typ A brauchen wir $16$ Einheiten Plastik und $4$ Einheiten Kupfer. Das Ergebnis der Divisionen zeigt an, wie viele Einheiten von $x_1$ sich maximal produzieren lassen, ohne die Kapazitätsschranken (Restriktionen) zu überschreiten. Relevant ist lediglich der kleinere der beiden Werte ($\min\{15{,}75;42\} = 15{,}75$). Der kleinere Wert zeigt nämlich an, welche Restriktion zuerst greift. Fazit: Wir können maximal $15{,}75$ Einheiten von $x_1$ produzieren. Die Produktion jeder weiteren Einheit von $x_1$ würde für eine Verletzung der Nichtnegativitätsbedingung $y_1 \geq 0$ sorgen.

Iterationsschritt 1: Basiswechsel

Im letzten Schritt des 1. Iterationsschritts müssen wir in der Spalte der zur Basisvariable werdenden Variable (hier: $x_1$) einen Einheitsvektor erzeugen.

• $1$ berechnen: $y_1$-Zeile geteilt durch 16

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & x_1 & x_2 & y_1 & y_2 & RS & Q \\ \hline y_1 &\fcolorbox{RoyalBlue}{}{$1$} & 0{,}375 & 0{,}0625 & & 15{,}75 & \\ \hline y_2 & 4 & 12 & & 1 & 168 & \\ \hline -VP & -150 & -100 & & & & \\ \hline \end{array} $$

• $0$ berechnen: $y_2$-Zeile - 4 $\cdot$ $y_1$-Zeile
• $0$ berechnen: $-VP$-Zeile + 150 $\cdot$ $y_1$-Zeile

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV &\colorbox{RoyalBlue}{${\color{white}y_1}$} & x_2 & y_1 & y_2 & RS & Q \\ \hline \colorbox{RoyalBlue}{${\color{white}x_1}$} & 1 & 0{,}375 & 0{,}0625 & & 15{,}75 & \\ \hline y_2 & & 10{,}5 & -0{,}25 & 1 & 105 & \\ \hline -VP & & -43{,}75 & 9{,}375 & & 2362{,}5 & \\ \hline \end{array} $$

Der Einheitsvektor wird erzeugt, damit ein Austausch der Variablen möglich wird.

Aus der neuen Tabelle können wir wieder eine Vielzahl von Informationen herauslesen:

• Die Basisvariablen ($BV$) sind $x_1$ ($= 15{,}75$) und $y_2$ ($= 105$).
• Die Nullvariablen (Nicht-Basisvariablen) sind $x_2$ und $y_1$.

Ökonomische Interpretation:
Produzieren wir von $x_1$ genau $15{,}75$ Einheiten, ist das ganze Plastik aufgebraucht ($y_1 = 0$). Aus diesem Grund ist eine Produktion von $x_2$ nicht möglich ($x_2 = 0$). Im Lager befinden sich aber noch $105$ Einheiten Kupfer. Unser Produktionsprogramm ($x_1 = 15{,}75$ und $x_2 = 0$) erwirtschaftet einen Umsatz von $2362{,}5$ Geldeinheiten (vgl. unten rechts in der Tabelle).

Ob dieser Betrag stimmt, lässt sich leicht überprüfen:

$$ z(15{,}75; 0) = 150 \cdot 15{,}75 + 100 \cdot 0 = 2362{,}5 $$

Handelt es sich bei $2362{,}5$ schon um die optimale Lösung?

Offenbar nicht, denn in der Zielfunktion ($-VP$ Zeile) befinden sich noch negative Koeffizienten. Die $-43{,}75$ in der letzten Zeile bedeuten nämlich, dass sich der Umsatz für jede (weitere) Einheit von $x_2$ um jeweils $43{,}75$ Geldeinheiten erhöhen lässt. Aus diesem Grund müssen wir einen weiteren Interationsschritt durchführen.

Im Folgenden werden wir die Tabelle noch einmal kurz interpretieren.

Erhöhen wir die Produktion von $x_2$ um eine Einheit, passiert Folgendes:

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 & \fcolorbox{Green}{}{$x_2$} & y_1 & y_2 & RS & Q \\ \hline x_1 & 1 & \fcolorbox{Red}{}{$0{,}375$} & 0{,}0625 & & 15{,}75 & \\ \hline y_2 & & \fcolorbox{Red}{}{$10{,}5$} & -0{,}25 & 1 & 105 & \\ \hline -VP & & \fcolorbox{Green}{}{$-43{,}75$} & 9{,}375 & & 2362{,}5 & \\ \hline \end{array} $$

• Wir müssen die Produktion von $x_1$ um $0{,}375$ Einheiten reduzieren.
• Die Lagermenge von $y_2$ sinkt um $10{,}5$ Einheiten.
• Der Umsatz erhöht sich um $43{,}75$ Geldeinheiten.

Steht von $y_1$ eine Einheit weniger zur Verfügung, passiert Folgendes:

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 & x_2 & \fcolorbox{Red}{}{$y_1$} & y_2 & RS & Q \\ \hline x_1 & 1 & 0{,}375 & \fcolorbox{Red}{}{$0{,}0625$} & & 15{,}75 & \\ \hline y_2 & & 10{,}5 & \fcolorbox{Green}{}{$-0{,}25$} & 1 & 105 & \\ \hline -VP & & -43{,}75 & \fcolorbox{Red}{}{$9{,}375$} & & 2362{,}5 & \\ \hline \end{array} $$

• Wir müssen die Produktion von $x_1$ um $0{,}0625$ Einheiten reduzieren. Dadurch erhöht sich der Lagerbestand von $y_2$ um $0{,}25$ Einheiten.
• Der Umsatz verringert sich um $9{,}375$ Geldeinheiten.

Iterationsschritt 2: In die Basis eintretende Variable bestimmen

Wähle aus der letzten Zeile die kleinste negative Zahl aus.

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 &\colorbox{Red}{${\color{white}x_2}$} & y_1 & y_2 & RS & Q \\ \hline x_1 & 1 & 0{,}375 & 0{,}0625 & & 15{,}75 & \\ \hline y_2 & & 10{,}5 & -0{,}25 & 1 & 105 & \\ \hline -VP & & \fcolorbox{Red}{}{$-43{,}75$} & 9{,}375 & & 2362{,}5 & \\ \hline \end{array} $$

$$ \min\{-43{,}75\} = -43{,}75 $$

$\Rightarrow x_2$ tritt in diesem Iterationsschritt in die Basis ein.

Ökonomische Interpretation:
Eine Erhöhung der Produktion von $x_2$ um eine Einheit, erhöht den Umsatz um $43{,}75$ GE.

Iterationsschritt 2: Aus der Basis zu eliminierende Variable bestimmen

Teile die Werte, die in der Spalte $RS$ stehen, durch die Koeffizienten aus der im vorherigen Schritt bestimmten Spalte und wähle hieraus die kleinste positive Zahl aus.

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 & x_2 & y_1 & y_2 & RS & Q \\ \hline x_1 & 1 & 0{,}375 & 0{,}0625 & & 15{,}75 & \frac{15{,}75}{0{,}375} = 42 \\ \hline \colorbox{Green}{${\color{white}y_2}$} & & 10{,}5 & -0{,}25 & 1 & 105 & \frac{105}{10{,}5} =\fcolorbox{Green}{}{$10$} \\ \hline -VP & & -43{,}75 & 9{,}375 & & 2362{,}5 & \\ \hline \end{array} $$

$$ \min\{42;10\} = 10 $$

$\Rightarrow y_2$ wird aus der Basis eliminiert.

Ökonomische Interpretation:
Im 1. Teilschritt haben wir uns dazu entschlossen, die Produktion von $x_2$ anzukurbeln. Die Frage ist nun, wie viele Einheiten von Kabel Typ B ($x_2$) produziert werden können, ohne eine Restriktion zu verletzen. Um diese Frage zu beantworten, dividieren wir in der Spalte $Q$ die bisherige Produktionsmenge von $x_1$ ($15{,}75$) durch $0{,}375$ – das ist der Wert, der angibt, wie weit man die Produktion von $x_1$ einschränken muss, wenn man die Produktion von $x_2$ um eine Einheit erhöht. Wir könnten also $42$ Einheiten von $x_2$ produzieren, bevor die Restriktion $x_1 \geq 0$ verletzt wird. Außerdem dividieren wir die vorhandene Kapizität von $y_2$ ($105$) durch den Bedarf pro Einheit von $x_2$ ($10{,}5$). Wir könnten also $10$ Einheiten von $x_2$ produzieren, bevor die Restriktion $y_1 \geq 0$ verletzt wird. Relevant ist lediglich der kleinere der beiden Werte ($\min\{42;10\} = 10$). Der kleinere Wert zeigt auch hier an, welche Restriktion zuerst greift.

Iterationsschritt 2: Basiswechsel

Im letzten Schritt des 2. Iterationsschritts müssen wir in der Spalte der zur Basisvariable werdenden Variable (hier: $x_2$) einen Einheitsvektor erzeugen.

• $1$ berechnen: $y_2$-Zeile geteilt durch 10,5

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 & x_2 & y_1 & y_2 & RS & Q \\ \hline x_1 & 1 & 0{,}375 & 0{,}0625 & & 15{,}75 & \\ \hline y_2 & &\fcolorbox{RoyalBlue}{}{$1$} & -\frac{1}{42} & \frac{2}{21} & 10 & \\ \hline -VP & & -43{,}75 & 9{,}375 & & 2362{,}5 & \\ \hline \end{array} $$

• $0$ berechnen: $x_1$-Zeile - 0,375 $\cdot$ $y_2$-Zeile
• $0$ berechnen: $-VP$-Zeile + 43,75 $\cdot$ $y_2$-Zeile

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline BV & y_1 &\colorbox{RoyalBlue}{${\color{white}y_2}$} & y_1 & y_2 & RS & Q \\ \hline x_1 & 1 & & \frac{1}{14} & -\frac{1}{28} & 12 & \\ \hline \colorbox{RoyalBlue}{${\color{white}x_2}$} & & 1 & -\frac{1}{42} & \frac{2}{21} & 10 & \\ \hline -VP & & & \frac{25}{3} & \frac{25}{6} & 2800 & \\ \hline \end{array} $$

Der Einheitsvektor wird erzeugt, damit ein Austausch der Variablen möglich wird.

Da sich in der Zielfunktion ($-VP$-Zeile) keine negative Koeffizienten mehr befinden, ist die optimale Lösung gefunden. Der Simplex-Algorithmus ist an dieser Stelle beendet.