Lineare Optimierung

Dieses Kapitel versteht sich als Einführung in das komplexe Thema der linearen Optimierung (LOP). In diesem Zusammenhang treten einige Fragen auf, die wir nach und nach klären wollen.

  1. Was versteht man unter dem Begriff "Lineare Optimierung"?
  2. Wie lässt sich die Problemstellung mathematisch formulieren?
  3. Was sind bekannte Anwendungsfälle der linearen Optimierung?
  4. Welche Lösungsverfahren gibt es?
  5. Welche Lösungen sind möglich?

Unsere Ausführungen beschränken sich in diesem Kapitel auf eine lineare Optimierung mit zwei Variablen.

Was ist lineare Optimierung?

Die lineare Optimierung kann als (praktische) Anwendung linearer Ungleichungssysteme verstanden werden. Der vorhergehende Artikel "Lineare Ungleichungssysteme mit zwei Variablen" ist dementsprechend die Grundlage für dieses Kapitel.

Die lineare Optimierung beschäftigt sich mit jenen mathematischen Verfahren, die den größten oder kleinsten Wert einer linearen Funktion ermitteln. Dabei werden diese meist durch zusätzliche Bedingungen eingeschränkt.

Kurz gesagt:

Die lineare Optimierung beschäftigt sich mit der Maximierung oder Minimierung einer linearen Funktion unter Nebenbedingungen.

Mathematische Formulierung

Ein sog. "lineares Programm" (LP) besteht aus folgenden Bestandteilen

Zielfunktion

Die zu maximierende (minimierende) lineare Funktion heißt Zielfunktion.Die in der Zielfunktion auftretenden Variablen (\(x\), \(y\)) nennt man Entscheidungsvariablen.

\(z = z(x,y) = dx + dy\)

Nebenbedingungen (Restriktionen)

\(\begin{align*}a_1x +b_1y &\leq c_1\\a_2x + b_2y &\leq c_2\\\qquad \vdots \qquad\vdots\\a_nx + b_ny &\leq c_n\end{align*}\)

(Nichtnegativitätsbedingung)

Bei den meisten Aufgaben aus der Praxis gibt es eine Beschränkung der Entscheidungsvariablen auf Werte größer/gleich Null. Grund dafür ist, dass diese in der Regel keine negativen Werte annehmen können. So kann zum Beispiel ein Unternehmen keine "negative Anzahl" an Produkten produzieren. 

\(x \geq 0\)
\(y \geq 0\)

Exkurs: Was bedeutet die Nichtnegativitätsbedingung graphisch?

\(x \geq 0\) bedeutet graphisch, dass nur der Bereich rechts der y-Achse für die Betrachtung relevant ist.

\(y \geq 0\) bedeutet graphisch, dass nur der Bereich oberhalb der x-Achse für die Betrachtung relevant ist.

Beachtet man sowohl \(x \geq 0\) als auch \(y \geq 0\), so stellt man fest, dass nur der 1. Quadrant des Koordinatensystems für die Betrachtung relevant ist.

Die farblich hervorgehobene Fläche ist demzufolge der Bereich, der die Nichtnegativitätsbedingung erfüllt.

Anwendungen

In der Praxis gibt es eine Vielzahl von Anwendungsfällen der linearen Optimierung. Einige davon sollen anhand von Beispielen näher erläutert werden.

Da bei den folgenden Beispielen die Nichtnegativitätsbedingung erfüllt werden muss, beschränkt sich die graphische Betrachtung auf den 1. Quadranten des Koordinatensystems.

Es wird an dieser Stelle dringend empfohlen, sich noch einmal mit dem Kapitel "Lineare Ungleichungssysteme mit zwei Variablen" auseinanderzusetzen.

a) Produktionsproblem

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. Die produzierte Menge von B darf nicht größer sein als die doppelte Menge von A. Außerdem beträgt der Materialvorrat 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

Zielfunktion \(z(x,y) = 150x + 100y \quad \rightarrow \quad \text{Max!}\)
Nebenbedingungen \(\begin{align*}
16x + 6y &\leq 252\\
4x + 12y &\leq 168
\end{align*}\)
...und wegen \(y \leq 2x\) gilt: \(2x - y \geq 0\)
Nichtnegativitätsbedingung \(x \geq 0\)
\(y \geq 0\)

3.) Graphische Betrachtung

Möchte man die 1. Nebenbedingung
\(16x + 6y \leq 252\)
in ein Koordinatensystem einzeichnen, muss man die Ungleichung nach \(y\) auflösen \(6y \leq - 16x + 252\)
\(y \leq - \frac{8}{3}x + 42\)
und anschließend die Ungleichung als Geradengleichung interpretieren
\(y = - \frac{8}{3}x + 42\)

Die farbige Fläche gibt den Bereich an, der die 1. Nebenbedingung erfüllt.

Möchte man die 2. Nebenbedingung
\(4x + 12y \leq 168\)
in ein Koordinatensystem einzeichnen, muss man die Ungleichung nach \(y\) auflösen \(12y \leq - 4x + 168\)
\(y \leq - \frac{1}{3}x + 14\)
und anschließend die Ungleichung als Geradengleichung interpretieren
\(y = - \frac{1}{3}x + 14\)

Die farbige Fläche gibt den Bereich an, der die 2. Nebenbedingung erfüllt.

Die 3. Nebenbedingung lautet:
"Die produzierte Menge von B darf nicht größer sein als die doppelte Menge von A."
...oder mathematisch formuliert: \(y \leq 2x\)

Die farbige Fläche gibt den Bereich an, der die 3. Nebenbedingung erfüllt.

Die Lösungsmenge des linearen Ungleichungssystems..
\(16x + 6y \leq 252\)
\(4x + 12y \leq 168\)
\(y \leq 2x\)
..ist in der nebenstehenden Graphik farblich hervorgehoben.

Jetzt wissen wir, wie die zulässige Lösungsmenge graphisch aussieht. Im nächsten Schritt machen wir uns auf die Suche nach der optimalen Lösung. Diese können wir entweder graphisch oder rechnerisch ermitteln.

4.1) Optimale Lösung bestimmen (Rechnerisch)

Da das Optimum einem Eckpunkt des Lösungsbereichs entspricht, lesen wir diese zunächst ab: \(P_1 (0,0)\); \(P_2 (6,12)\); \(P_3 (12,10)\); \(P_4 (15,75;0)\);

Jetzt setzen wir die Punkte in die Zielfunktion ein und bestimmen das Maximum.

\(z(x,y) = 150x + 100y\)

\(z(0,0) = 150 \cdot 0 + 100 \cdot 0 = 0 €\)

\(z(6,12) = 150 \cdot 6 + 100 \cdot 12 = 2.100 €\)

\(z(12,10) = 150 \cdot 12 + 100 \cdot 10 = 2.800 € \qquad \rightarrow \quad \text{Maximum!}\)

\(z(15,75;0) = 150 \cdot 15,75 + 100 \cdot 0 = 2.362,50 €\)

Antwort:
Die Fabrik maximiert ihren Umsatz unter Einhaltung der Nebenbedingungen, wenn sie 12 mal 100m Kabel vom Typ A und 10 mal 100m Kabel vom Typ B produziert.

4.2) Optimale Lösung bestimmen (Graphisch)

Graphisch findet man das Maximum, indem man die Zielfunktion einzeichnet und anschließend solange parallel verschiebt, bis die Gerade den letzten Eckpunkt des Lösungsbereichs berührt. Der letzte Eckpunkt entspricht dann der optimalen Lösung.

Wir lösen die Zielfunktion zunächst nach \(y\) auf..
\(z(x,y) = 150x + 100y = 0\)
\(100y = -150x\)
\(y = -1,5x\)
..um diese in das Koordinatensystem zu zeichnen. Danach verschieben wir die Gerade solange parallel, bis wir den letzten Eckpunkt des Lösungsbereichs erreichen.

Das Optimum (hier: Maximum) ist in der Graphik durch einen roten Punkt dargestellt.

b) Transportproblem

Eine Fluggesellschaft möchte eine Flugverbindung zwischen zwei Städten einrichten. Ziel ist es in einem bestimmten Zeitraum, 1600 Personen und 96 Tonnen Ladung zu transportieren. Derzeit sind zwei Flugzeugetypen verfügbar: 11 Flugzeuge des Typs A und 8 Flugzeuge des Typs B. Typ A kostet pro Flug 4.000 € und kann 200 Personen sowie 6 Tonnen Ladung transportieren. Typ B kostet pro Flug 1.000 € und kann 100 Personen und 15 Tonnen Ladung transportieren.

Wie viele Flugzeuge von jedem Typen wird die Fluggesellschaft unter Einhaltung der Nebenbedingungen einsetzen, um ihre Kosten zu minimieren?

1.) Übersichtliches Zusammenstellen der Aufgabe

\begin{array}{r|r|r|r}
& \text{Typ A} & \text{Typ B} & \text{Gesamt} \\ \hline
\text{Personen} & 200 & 100 & 1600 \\ \hline
\text{Ladung} & 6 & 15 & 96 \\ \hline
\text{Kosten} & 4.000 & 1.000 &
\end{array}

2.) Mathematische Formulierung des Problems

Zielfunktion \(z(x,y) = 4000x + 1000y \quad \rightarrow \quad \text{Min!}\)
Nebenbedingungen \(\begin{align*}
200x + 100y &\geq 1600\\
6x + 15y &\geq 96
\end{align*}\)
...außerdem gilt: \(x \leq 11\)
\(y \leq 8\)
Nichtnegativitätsbedingung \(x \geq 0\)
\(y \geq 0\)

3.) Graphische Betrachtung

Möchte man die 1. Nebenbedingung
\(200x + 100y \geq 1600\)
in ein Koordinatensystem einzeichnen, muss man die Ungleichung nach \(y\) auflösen \(100y \geq -200x + 1600\)
\(y \geq -2x + 16\)
und anschließend die Ungleichung als Geradengleichung interpretieren
\(y = -2x + 16\)

Die farbige Fläche gibt den Bereich an, der die 1. Nebenbedingung erfüllt.

Möchte man die 2. Nebenbedingung
\(6x + 15y \geq 96\)
in ein Koordinatensystem einzeichnen, muss man die Ungleichung nach \(y\) auflösen \(15y \geq - 6x + 96\)
\(y \geq - 0,4x + 6,4\)
und anschließend die Ungleichung als Geradengleichung interpretieren
\(y = - 0,4x + 6,4\)

Die farbige Fläche gibt den Bereich an, der die 2. Nebenbedingung erfüllt.

Die 3. Nebenbedingung
\(x \leq 11\)
ist eine Parallele zur y-Achse mit dem Achsenschnittpunkt \(x = 11\).

Die farbige Fläche gibt den Bereich an, der die 3. Nebenbedingung erfüllt.

Die 4. Nebenbedingung
\(y \leq 8\)
ist eine Parallele zur x-Achse mit dem Achsenschnittpunkt \(y = 8\).

Die farbige Fläche gibt den Bereich an, der die 4. Nebenbedingung erfüllt.

Die Lösungsmenge des linearen Ungleichungssystems..
\(200x + 100y \geq 1600\)
\(6x + 15y \geq 96\)
\(x \leq 11\)
\(y \leq 8\)
..ist in der nebenstehenden Graphik farblich hervorgehoben.

Jetzt wissen wir, wie die zulässige Lösungsmenge graphisch aussieht. Im nächsten Schritt machen wir uns auf die Suche nach der optimalen Lösung. Diese können wir entweder graphisch oder rechnerisch ermitteln.

4.1) Optimale Lösung bestimmen (Rechnerisch)

Da das Optimum einem Eckpunkt des Lösungsbereichs entspricht, lesen wir diese zunächst ab: \(P_1 (6,4)\); \(P_2 (4,8)\); \(P_3 (11,8)\); \(P_4 (11,2)\);

Jetzt setzen wir die Punkte in die Zielfunktion ein und bestimmen das Minimum.

\(z(x,y) = 4.000x + 1.000y\)

\(z(6,4) = 4.000 \cdot 6 + 1.000 \cdot 4 = 28.000 €\)

\(z(4,8) = 4.000 \cdot 4 + 1.000 \cdot 8 = 24.000 € \qquad \rightarrow \quad \text{Minimum!}\)

\(z(11,8) = 4.000 \cdot 11 + 1.000 \cdot 8 = 52.000 €\)

\(z(11,2) = 4.000 \cdot 11 + 1.000 \cdot 2 = 46.000 €\)

Antwort:
Die Fluggesellschaft minimiert ihre Kosten unter Einhaltung der Nebenbedingungen, wenn sie 4 Flugzeuge des Typ A und 8 Flugzeuge des Typ B einsetzt.

4.2) Optimale Lösung bestimmen (Graphisch)

Graphisch findet man das Minimum, indem man die Zielfunktion einzeichnet und anschließend solange parallel verschiebt, bis die Gerade den ersten Eckpunkt des Lösungsbereichs berührt. Der erste Eckpunkt entspricht dann der optimalen Lösung.

Wir lösen die Zielfunktion zunächst nach \(y\) auf..
\(z(x,y) = 4000x + 1000y = 0\)
\(1000y = -4000x\)
\(y = -4x\)
..um diese in das Koordinatensystem zu zeichnen. Danach verschieben wir die Gerade solange parallel, bis wir den ersten Eckpunkt des Lösungsbereichs erreichen.

Das Optimum (hier: Minimum) ist in der Graphik durch einen roten Punkt dargestellt.

Mögliche Lösungen

In den obigen Beispielen haben wir bereits gesehen, dass eine Optimierungsaufgabe eine eindeutige Lösung besitzen kann. Daneben ist es auch möglich, dass mehrere Lösungen oder gar keine Lösung existiert.

Im Folgenden findest du zu jedem Lösungsfall ein graphisches Beispiel. Dabei geht es jeweils darum, ein Minimum zu finden.

Eindeutige optimale Lösung

...dazu haben wir bereits weiter oben zwei Beispiele ausführlich betrachtet.

Unendlich viele optimale Lösungen

Ist die Zielfunktion parallel zu einer Restriktion, gibt es mehrere Lösungen. Graphisch bedeutet das, dass bei der Parallelverschiebung die Zielfunktion mit dieser Restriktionsgeraden zusammenfällt.

Keine optimale Lösung

Es gibt Fälle, in denen keine optimale Lösung existiert.

Fazit

Bei dem Thema "lineare Optimierung" hat man es oftmals mit Textaufgaben zu tun. Es ist wichtig, dass man das Wesentliche aus der Aufgabe herauslesen und in einer Tabelle zusammenfassen kann. Mit Hilfe dieser übersichtlichen Darstellung wird die anschließende mathematische Formulierung enorm vereinfacht.

Besitzt das lineare Programm lediglich zwei Variablen eignet sich zur Lösung der Optimierungsaufgabe eine graphische Analyse.

  • Das Maximum findet man graphisch, indem die Zielfunktion einzeichnet und solange parallel verschiebt, bis sie den letzten Eckpunkt des Lösungsbereichs berührt.
  • Das Minimum findet man graphisch, indem die Zielfunktion einzeichnet und solange parallel verschiebt, bis sie den ersten Eckpunkt des Lösungsbereichs berührt.

Grundsätzlich kann es bei Aufgaben der linearen Optimierung eine eindeutige, unendlich viele oder keine (optimale) Lösung geben.

Für lineare Programme mit mehr als zwei Variablen ist eine graphische Betrachtung (meist) nicht möglich. In der Praxis berechnet man in diesem Fall das Optimum mit Hilfe des sog. Simplex-Algorithmus.

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!