Lineare Optimierung
Dieses Kapitel versteht sich als Einführung in das Thema der linearen Optimierung (LOP). Der Einfachheit halber beschränken wir uns im Folgenden auf eine lineare Optimierung mit zwei Variablen.
Einordnung
Die lineare Optimierung kann als (praktische) Anwendung linearer Ungleichungssysteme verstanden werden. Das letzte Kapitel 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
$$ z = z(x,y) = dx + dy $$
Die zu maximierende (minimierende) lineare Funktion heißt Zielfunktion. Die in der Zielfunktion auftretenden Variablen ($x$, $y$) heißen Entscheidungsvariablen.
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)
$$ x \geq 0 $$
$$ y \geq 0 $$
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.
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.
Produktionsproblem
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. Die produzierte Menge von B darf nicht größer sein als die doppelte Menge von A. Außerdem beträgt der Materialvorrat 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
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 $$
Lösungsmenge graphisch bestimmen
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.
$$ \Rightarrow y \leq 2x $$
Die farbige Fläche gibt den Bereich an, der die 3. Nebenbedingung erfüllt.
Die Lösungsmenge des linearen Ungleichungssystems
$$ \begin{align*} 16x + 6y &\leq 252 \\ 4x + 12y &\leq 168 \\ y &\leq 2x \end{align*} $$
ist in der Abbildung farblich hervorgehoben.
Optimale Lösung bestimmen
a) 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\ \textrm{€} $$
$$ z(6;12) = 150 \cdot 6 + 100 \cdot 12 = 2.100\ \textrm{€} $$
$$ z(12;10) = 150 \cdot 12 + 100 \cdot 10 = 2.800\ \textrm{€} \qquad \rightarrow \quad \text{Maximum!} $$
$$ z(15{,}75;0) = 150 \cdot 15{,}75 + 100 \cdot 0 = 2.362{,}50\ \textrm{€} $$
Die Fabrik maximiert ihren Umsatz unter Einhaltung der Nebenbedingungen, wenn sie $12$ mal $100\ \textrm{m}$ Kabel vom Typ A und $10$ mal $100\ \textrm{m}$ Kabel vom Typ B produziert.
b) Graphisch
Graphisch finden wir das Maximum, indem wir die Zielfunktion einzeichnen und anschließend solange parallel verschieben, 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 Abbildung durch einen roten Punkt dargestellt.
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\ \textrm{€}$ und kann $200$ Personen sowie $6$ Tonnen Ladung transportieren. Typ B kostet pro Flug $1.000\ \textrm{€}$ 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?
Daten in einer Tabelle zusammenstellen
$$ \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} $$
Problem mathematisch formulieren
Zielfunktion
$$ z(x,y) = 4000x + 1000y \quad \rightarrow \quad \text{Min!} $$
Nebenbedingungen
$$ \begin{align*} 200x + 100y &\geq 1600 \\ 6x + 15y &\geq 96 \end{align*} $$
Zusätzlich gilt:
$$ x \leq 11 $$
$$ y \leq 8 $$
Nichtnegativitätsbedingung
$$ x \geq 0 $$
$$ y \geq 0 $$
Lösungsmenge graphisch bestimmen
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
$$ \begin{align*} 200x + 100y &\geq 1600 \\ 6x + 15y &\geq 96 \\ x &\leq 11 \\ y &\leq 8 \end{align*} $$
ist in der Abbildung farblich hervorgehoben.
Optimale Lösung bestimmen
a) 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\ \textrm{€} $$
$$ z(4;8) = 4.000 \cdot 4 + 1.000 \cdot 8 = 24.000\ \textrm{€} \qquad \rightarrow \quad \text{Minimum!} $$
$$ z(11;8) = 4.000 \cdot 11 + 1.000 \cdot 8 = 52.000\ \textrm{€} $$
$$ z(11;2) = 4.000 \cdot 11 + 1.000 \cdot 2 = 46.000\ \textrm{€} $$
Die Fluggesellschaft minimiert ihre Kosten unter Einhaltung der Nebenbedingungen, wenn sie $4$ Flugzeuge des Typ A und $8$ Flugzeuge des Typ B einsetzt.
b) Graphisch
Graphisch finden wir das Minimum, indem wir die Zielfunktion einzeichnen und anschließend solange parallel verschieben, 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 Abbildung 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.
Zusammenfassung
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. Mithilfe 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 mithilfe des sog. Simplex-Algorithmus.
