Über 80 € Preisvorteil gegenüber Einzelkauf!
Mathe-eBooks im Sparpaket
Von Schülern, Studenten, Eltern und
Lehrern mit 4,86/5 Sternen bewertet.
47 PDF-Dateien mit über 5000 Seiten
inkl. 1 Jahr Updates für nur 29,99 €.
Ab dem 2. Jahr nur 14,99 €/Jahr.
Kündigung jederzeit mit wenigen Klicks.
Jetzt Mathebibel herunterladen

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.

Standard-Maximierungsproblem 

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

Beispiel 1 

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

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

Daten in einer Tabelle zusammenstellen

$$ \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} $$

Problem mathematisch formulieren

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 $$

Schlupfvariablen einführen

Mithilfe 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$]).

Wenn wir 2 der 4 Variablen gleich Null setzen, haben wir ein quadratisches System vor uns, das (von Ausnahmen abgesehen) genau eine Lösung hat.

Wichtig: Nur durch das Nullsetzen von 2 Variablen lässt sich in diesem Fall 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 müssten wir noch herausfinden, 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 Nullvariable mit einer Basisvariable, 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.

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$ ($= 252$) und $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!

Simplex-Algorithmus anwenden

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.

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 

Beispiel 2 

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:

Ungleichungssystem als Matrix aufschreiben

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

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} $$

Aus der Matrix das (neue) Ungleichungssystem herauslesen

Beachte 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!

Noch Fragen? Logo von Easy-Tutor hilft!

Probestunde sichern