Simplex-Algorithmus

Der Simplex-Algorithmus ist ein populäres Verfahren zum Lösen von Aufgaben der linearen Optimierung. Die optimale Lösung wird dabei iterativ (d.h. in mehreren Schritten) ermittelt.

Es wird dringend empfohlen, sich zunächst die folgenden Kapitel durchzulesen:

Standard-Maximierungsproblem

Im Folgenden schauen wir uns ein Standard-Maximierungsproblem anhand eines Produktionsproblems an.

Aufgabenstellung
In einer Fabrik werden zwei verschiedene Sorten von Kabeln hergestellt und für 150 € (Typ A) bzw. 100 € (Typ B) pro 100 Meter verkauft. Für Kabel des Typ A benötigt man 16kg Plastik und 4kg Kupfer. Für Kabel des Typ B benötigt man 6kg Plastik und 12kg Kupfer. Der Materialvorrat beträgt derzeit nur 252kg Plastik und 168kg Kupfer.

Welche Mengen der beiden Kabelsorten maximieren unter Einhaltung der Nebenbedingungen den Umsatz der Firma?

1.) Übersichtliches Zusammenstellen der Aufgabe

\begin{array}{r|r|r|r}
& \text{Typ A} & \text{Typ B} & \text{Vorrat} \\ \hline
\text{Plastik} & 16 & 6 & 252 \\ \hline
\text{Kupfer} & 4 & 12 & 168 \\ \hline
\text{Verkaufspreis} & 150 & 100 &
\end{array}

2.) Mathematische Formulierung des Problems

Restriktionen \(\begin{align*}
16x_1 + 6x_2 &\leq 252\\
4x_1 + 12x_2 &\leq 168
\end{align*}\)
Zielfunktion \(z(x_1,x_2) = 150x_1 + 100x_2 \quad \rightarrow \quad \text{Max!}\)
Nichtnegativitätsbedingung \(x_1,~x_2 \geq 0\)

3.) Simplex-Algorithmus

3.1) Einführung von Schlupfvariablen: Umwandlung in ein Gleichungssystem

Mit Hilfe sog. "Schlupfvariablen" (Hilfsvariablen) möchte man nicht ausgenutzte Kapazitäten darstellen. Dadurch wird es möglich, dass Ungleichungssystem in ein Gleichungssystem umzuwandeln.

Vorher: Ungleichungssystem ohne Schlupfvariablen

\begin{align*}
&16x_1 + 6x_2 {\color{red}\: \leq \:} 252 \\
&4x_1 + 12x_2 {\color{red}\: \leq \:} 168 \\
\end{align*}

Nachher: Gleichungssystem mit Schlupfvariablen

\begin{align*}
&16x_1 + 6x_2 {\color{red} \: + \: y_1 = \:} 252 \\
&4x_1 + 12x_2 {\color{red} \: + \: y_2 = \:} 168 \\
\end{align*}

Ebenso wie die Entscheidungsvariablen müssen auch die Schlupfvariablen die Nichtnegativitätsbedingung erfüllen. Entsprechend gilt: \(x_1,~x_2,~y_1,~y_2 \geq 0\).

Nichtnegativitätsbedingungen verstehen

  • \(x_1 \geq 0\): Die Produktionsmenge von Kabel Typ A darf nicht kleiner als Null werden.
  • \(x_2 \geq 0\): Die Produktionsmenge von Kabel Typ B darf nicht kleiner als Null werden.
  • \(y_1 \geq 0\): Der Vorrat von Plastik darf nicht kleiner als Null werden.
  • \(y_2 \geq 0\): Der Vorrat von Kupfer darf nicht kleiner als Null werden.

Die Nichtnegativitätsbedingungen ergeben sich also aus logischen Überlegungen.

Gleichungssystem verstehen

\begin{align*}
&16x_1 + 6x_2 + y_1 = 252 \\
&4x_1 + 12x_2 + y_2 = 168 \\
\end{align*}

Wir haben ein Gleichungssystem mit \(m = 2\) Gleichungen (\(m\) ist immer die Zahl der Restriktionen) und \(m + n = 4\) Variablen (\(n\) ist immer die Raumdimension, d.h. die Zahl der ursprünglichen Variablen [hier: \(x_1\) und \(x_2\)]). Setzt man 2 der 4 Variablen zu Null, so haben wir ein quadratisches System, das (von Ausnahmen abgesehen) genau eine Lösung hat.

Wichtig:
Nur durch das Nullsetzen von 2 Variablen lässt sich eine eindeutige Lösung berechnen!

In unserem Beispiel gibt es folgende Möglichkeiten 2 der 4 Variablen gleich Null zu setzen:

  • \(x_1 = 0\) und \(x_2 = 0\)
  • \(x_1 = 0\) und \(y_1 = 0\)
  • \(x_1 = 0\) und \(y_2 = 0\)
  • \(x_2 = 0\) und \(y_1 = 0\)
  • \(x_2 = 0\) und \(y_2 = 0\)
  • \(y_1 = 0\) und \(y_2 = 0\)

Die Variablen, die wir Null setzen, heißen Nullvariablen.
Die Nicht-Nullvariablen heißen Basisvariablen.

Wir müssten jetzt 6 Gleichungssysteme lösen und danach durch Einsetzen in jede Gleichung überprüfen, ob die berechneten Lösungen alle Nichtnegativitätsbedingungen erfüllen. Danach gilt noch herauszufinden, welche der zulässigen Lösungen die Zielfunktion maximiert. Der rechnerische Aufwand für dieses Verfahren wäre extrem hoch.

Deutlich einfacher ist dagegen das Vorgehen mit dem Simplex-Algorithmus:

  1. In die Basis eintretende Variable bestimmen
  2. Aus der Basis zu eliminierende Variable bestimmen
  3. Basiswechsel

Meist muss man diese drei Schritte mehrmals hintereinander ausführen, um zur optimalen Lösungen zu gelangen. Einen Durchlauf - also das einmalige Durchführen der drei Schritte - bezeichnet man als Iterationsschritt. Das Ziel eines jeden Interationsschrittes ist der Tausch einer Nullvariablen mit einer Basisvariablen, und zwar so, dass sich der Wert der Zielfunktion (in unserem Beispiel: der Umsatzfunktion) maximal erhöht.

Zu Beginn sind die ursprünglichen Variablen (hier: \(x_1\) und \(x_2\)) gleich Null.

3.2) Gleichungssystem in Tabellenform bringen

Gegeben

\begin{align*}
&16x_1 + 6x_2 + y_1 = 252 \\
&4x_1 + 12x_2 + y_2 = 168 \\
\end{align*}

\(z(x_1,x_2) = 150x_1 + 100x_2\)

Zur übersichtlicheren Darstellung schreiben wir die Informationen in folgende Tabelle:

\(\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 & 16 & 6 & 1 & & 252 & \\ \hline
y_2 & 4 & 12 & & 1 & 168& \\ \hline
-VP & -150 & -100 & & & & \\ \hline
\end{array}\)

Aus dieser Tabelle können wir eine Vielzahl von Informationen herauslesen:

  • Die Basisvariablen (\(BV\)) sind \(y_1\) und \(y_2\). Dabei gilt:
    \(\Rightarrow y_1 = 252\)
    \(\Rightarrow y_2 = 168\)
  • Die Nullvariablen (= Nicht-Basisvariablen) sind \(x_1\) und \(x_2\).

Ökonomische Interpretation:
Da zu Beginn weder Kabel Typ A (\(x_1 = 0\)) noch Kabel Typ B (\(x_2 = 0\)) produziert wird,
sind die Vorräte von Plastik (\(y_1 = 252\)) und Kupfer (\(y_2 = 168\)) unangetastet.

\(RS\) steht die "rechte Seite" des (ursprünglichen) Gleichungssystems.

\(Q\) steht für "Quotient". Diese Spalte brauchen wir in einem der folgenden Schritte.

In der letzten Zeile tragen wir den Verkaufspreis (\(VP\)) der beiden Produkte \(x_1\) und \(x_2\) ein.
Aus rechnerischen Gründen schreiben wir diese Zeile mit negativem Vorzeichen auf.

Wir merken uns:

Eine vorliegende Lösung ist so lange nicht optimal, wie sich in der Zielfunktion (\(-VP\) Zeile) noch negative Koeffizienten befinden.

Um diesen wichtigen Merksatz zu verstehen, müssen wir uns die 2. und 3. Spalte anschauen.

Erhöhen wir die Produktion von \(x_1\) um eine Einheit, passiert Folgendes:

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

  • Die Lagermenge von \(y_1\) sinkt um \(16\) Einheiten.
  • Die Lagermenge von \(y_2\) sinkt um \(4\) Einheiten.
  • Der Umsatz erhöht sich um \(150\) Geldeinheiten.

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 & x_1 & \fcolorbox{Green}{}{\(x_2\)} & y_1 & y_2 & RS & Q \\ \hline
y_1 & 16 & \fcolorbox{Red}{}{\(6\)} & 1 & & 252 & \\ \hline
y_2 & 4 & \fcolorbox{Red}{}{\(12\)} & & 1 & 168& \\ \hline
-VP & -150 & \fcolorbox{Green}{}{\(-100\)} & & & & \\ \hline
\end{array}\)

  • Die Lagermenge von \(y_1\) sinkt um \(6\) Einheiten.
  • Die Lagermenge von \(y_2\) sinkt um \(12\) Einheiten.
  • Der Umsatz erhöht sich um \(100\) Geldeinheiten.

Solange in der letzten Zeile negative Zahlen auftauchen, die einen positiven Einfluß auf unsere zu maximierende Zielfunktion haben, lohnt es sich, einen weiteren Iterationsschritt durchzuführen.

Anmerkung:
Falls zu Beginn alle Werte in der letzten Zeile positiv sind, kann man sich das Rechnen sparen!

1. Iterationsschritt: Teilschritt 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\).

1. Iterationsschritt: Teilschritt 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 & 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.

1. Iterationsschritt: Teilschritt 3 (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\) und \(y_2\). Dabei gilt:
    \(\Rightarrow x_1 = 15,75\)
    \(\Rightarrow 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.

2. Iterationsschritt: Teilschritt 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 & 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.

2. Iterationsschritt: Teilschritt 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.

2. Iterationsschritt: Teilschritt 3 (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.

4.) Lösung ablesen

\(\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
BV & y_1 & y_2 & y_1 & y_2 & RS & Q \\ \hline
\fcolorbox{Orange}{}{\(x_1\)}& 1 & & \frac{1}{14} & -\frac{1}{28} & \fcolorbox{Orange}{}{\(12\)}& \\ \hline
\fcolorbox{Orange}{}{\(x_2\)}& & 1 & -\frac{1}{42} & \frac{2}{21} & \fcolorbox{Orange}{}{\(10\)}& \\ \hline
-VP & & & \frac{25}{3} & \frac{25}{6} & \fcolorbox{Orange}{}{\(2800\)}& \\ \hline
\end{array}\)

Die Firma optimiert ihren Umsatz, wenn sie

  • \(12\) Einheiten vom Typ A (\(x_1\)) und
  • \(10\) Einheiten vom Typ B (\(x_2\))

produziert.

Das Umsatzmaximum lässt sich unten rechts ablesen: \(2800\) Geldeinheiten.

Standard-Minimierungsproblem

Aus einer beliebigen Aufgabenstellung lesen wir die folgenden Informationen heraus:

Restriktionen \(\begin{align*}
16x_1 + 4x_2 &\geq 150\\
6x_1 + 12x_2 &\geq 100
\end{align*}\)
Zielfunktion \(z(x_1,x_2) = 252x_1 + 168x_2 \quad \rightarrow \quad \text{Min!}\)
Nichtnegativitätsbedingung \(x_1,~x_2 \geq 0\)

Im Gegensatz zur vorherigen Aufgabe muss die Zielfunktion dieses Mal minimiert werden. Da der Simplex-Algorithmus nur für die Maximierung ausgelegt ist, müssen wir dieses Standard-Minimierungsproblem auf ein Standard-Maximierungsproblem zurückführen. Dazu führen wir folgende Schritte aus:

a) Ungleichungssystem als Matrix aufschreiben

\(A = \begin{pmatrix}{\color{red}16}&{\color{red}4}&{\color{red}150}\\ 6 & 12 & 100 \\ 252 & 168 & 0 \end{pmatrix}\)

b) Matrix transponieren

Eine Matrix wird transponiert, indem man aus den Zeilen Spalten macht.

\(A^{T} = \begin{pmatrix}{\color{red}16}& 6 & 252 \\{\color{red}4}& 12 & 168 \\{\color{red}150}& 100 & 0 \end{pmatrix}\)

c) Aus der Matrix das (neue) Ungleichungssystem herauslesen

Zu beachten sind die umgedrehten Ungleichheitszeichen bei den Restriktionen.

Restriktionen \(\begin{align*}
16x_1 + 6x_2 &\leq 252\\
4x_1 + 12x_2 &\leq 168
\end{align*}\)
Zielfunktion \(z(x_1,x_2) = 150x_1 + 100x_2 \quad \rightarrow \quad \text{Max!}\)
Nichtnegativitätsbedingung \(x_1,~x_2 \geq 0\)

Jetzt haben wir wieder ein Standard-Maximierungsproblem vor uns.
Wie man das berechnet, haben wir bereits gelernt!

Simplex-Algorithmus: Zusammenfassung

1.1) Von der Aufgabenstellung zum Ausgangstableau

  1. Übersichtliches Zusammenstellen der Aufgabe
  2. Mathematische Formulierung des Problems
  3. Einführung von Schlupfvariablen: Umwandlung in ein Gleichungssystem
  4. Gleichungssystem in Tabellenform ("Ausgangstableau") bringen

1.2) Von dem Ausgangstableau zum Optimaltableau (= Simplex-Algorithmus)

  1. In die Basis eintretende Variable bestimmen ("Pivotspalte")
  2. Aus der Basis zu eliminierende Variable bestimmen ("Pivotzeile")
  3. Basiswechsel

2.) Vom Minimierungs- zum Maximierungsproblem

  1. Ungleichungssystem als Matrix aufschreiben
  2. Matrix transponieren
  3. Aus der Matrix das (neue) Ungleichungssystem herauslesen
Andreas Schneider

Hat dir meine Erklärung geholfen?
Facebook Like Button
Für Lob, Kritik und Anregungen habe ich immer ein offenes Ohr.

Weiterhin viel Erfolg beim Lernen!

Andreas Schneider

PS: Ich freue mich, wenn du mir mal schreibst!