Lineare Optimierung

Planungspolygone

Unter Optimierung versteht man die Festlegung eines bestimmten Programms, mit dessen Hilfe der günstigste Wert für ein vorgegebenes Ziel erreicht wird. Dabei spielen Restriktionen (Nebenbedingungen), die sich oft durch Ungleichungen ausdrücken lassen, eine wichtige Rolle.

Wir betrachten hier verhältnismässig einfache Probleme, die sich mit graphischen Methoden lösen lassen: Von einer Funktion $Z$ (genannt Zielfunktion) werden extremale Werte bestimmt, wobei die Nebenbedingungen (lineare Ungleichungen) zu beachten sind. Diese Bedingungen ergeben, graphisch in einem Koordinatensystem dargestellt, das sogenannte Planungspolygon.

Example 1

Eine Fabrik stellt die beiden Modelle "analog" und "digital" eines Taschenradios her. Jedes Radio der Analogausführung bringt einen Gewinn von Fr.15.-, das der Digitalausführung Fr.45.-. Die Tagesproduktion der Firma unterliegt den folgenden Einschränkungen: Von der Analogausführung können höchstens $1200$ , von der Digitalausführung höchstens $700$ , von beiden zusammen höchstens $1400$ Stück hergestellt werden. In der Analogausführung wird eine Verstärkerstufe, in der Digitalausführung werden zwei Verstärkerstufen eingebaut. Pro Tag stehen aber höchstens $1800$ Verstärkerstufen zur Verfügung.

Wie viele Analog- bzw. Digitalradios soll die Firma pro Tag herstellen, wenn ihr Gewinn möglichst gross sein soll? Werden die Anzahl der pro Tag hergestellten Analoggeräte mit $x$ und die Anzahl der Digitalgeräte mit $y$ bezeichnet, so können die erwähnten Nebenbedingungen (Restriktionen) als ein Ungleichungssystem formuliert werden:

\begin{align} x&\leq1200\\ y&\leq700\\ x+y&\leq1400\\ x+2y&\leq1800 \end{align}

Ausserdem gelten noch die Bedingungen

\begin{align*} x\geq0\\ y\geq0 \end{align*}

da ja die Anzahlen $x$ und $y$ nicht negativ sein können.

Zunächst wird das Planungspolygon, die Lösungsmenge des Ungleichungssystems, erstellt:

Für den Gewinn der Firma in Abhängigkeit von $x$ und $y$ hat man den Funktionsterm

G(x,y)=15x+45y.

$G$ heisst Zielfunktion und ist eine affine Funktion mit 2 Variablen. Alle Paare $(x\mid y)$ , die die obigen Bedingungen erfüllen, stellen zulässige Lösungen des Problems dar. Gesucht wird aber dasjenige Paar $(x\mid y)$ ( $x,y$ sind natürliche Zahlen), für das der Gewinn $G(x,y)$ maximal wird. Durch Umformen des Zielfunktionsterms erhält man

y=-\frac{1}{3}x+\frac{G}{45}

eine affine Funktionsschar. Die entsprechende Graphen sind parallele Geraden mit den $y$ -Achsenabschnitten $\frac{G}{45}$ . Gesucht ist ein Punktepaar $(x\mid y)$ , das einerseits das Ungleichungssystem erfüllt, und für das andererseits der $y$ -Achsenabschnitt $\frac{G}{45}$ und damit auch $G$ möglichst gross wird. Man erhält die Lösung $(x\mid y)$ , indem man eine Gerade der Geradenschar, etwa die durch die Punkte $(0\mid 100)$ und $(300\mid 0)$ , $m=-\frac{1}{3}$ , auswählt, und sie solange längs der $y$ -Achse nach oben verschiebt, bis sie mit der Begrenzungslinie des Planungspolygons nur noch einen Punkt oder eine Strecke gemeinsam hat.

Wie aus der Zeichnung abzulesen ist, entpuppt sich das Paar $(400\mid 700)$ als optimale Lösung des Problems. Die Firma erzielt einen maximalen Gewinn, wenn sie pro Tag $400$ Analogradios und $700$ Digitalradios herstellt. Den entsprechenden Gewinn berechnet man mit Hilfe der Zielfunktion:

G(400,700) = 15\cdot400\,\mathrm{Fr.} + 45\cdot700\,\mathrm{Fr.} = 37\,500\,\mathrm{Fr.}

Die optimale Lösung kann auch rechnerisch ermittelt werden, indem man den Schnittpunkt der beiden entsprechenden Geraden berechnet (Lösen eines Gleichungssystems mit $2$ Unbekannten).

Exercise 1: Maximiere die Zielfunktion

Maximiere die Zielfunktion

Z = 3x + 2y

unter den Nebenbedingungen

\begin{align} x + 2y &\leq 8 \\ 2x + y &\leq 6 \\ x &\geq 0 \\ y &\geq 0 \end{align}

Solution

Zeichne die Einschränkungen in einem Koordinatensystem und bestimme die zulässige Region (Planungspolygon).

Bestimme die Eckpunkte der zulässigen Region: $(0,0)$ , $(6,0)$ , $(2,3)$ .

Berechne den Wert der Zielfunktion $Z = 3x + 2y$ an jedem Eckpunkt:

Für $(0,0)$ : $Z = 3(0) + 2(0) = 0$
Für $(6,0)$ : $Z = 3(6) + 2(0) = 18$
Für $(2,3)$ : $Z = 3(2) + 2(3) = 12$

Der maximale Wert der Zielfunktion tritt bei $(6,0)$ auf. Damit ist die Lösung: Maximale Zielfunktion: $Z = 18$ , optimaler Punkt: $(x, y) = (6, 0)$ .

Exercise 2: Weidebetrieb

Ein landwirtschaftlicher Weidebetrieb hat sich auf die Haltung von Kühen und Jungvieh spezialisiert. In den Ställen des Betriebs können höchstens $70$ Kühe und $500$ Stück Jungvieh gehalten werden. Für die Ernährung einer Kuh sind $0.25\,\text{ha}$ , für ein Jungvieh $0.10\,\text{ha}$ Weideland nötig. Insgesamt hat der Betrieb $50\,\text{ha}$ Weideland. Für die Pflege der Kühe und des Jungviehs stehen drei Arbeiter zur Verfügung, die insgesamt $8000$ Arbeitsstunden im Jahr leisten. Für eine Kuh sind $100$ Arbeitsstunden, für ein Stück Jungvieh $10\,\text{Arbeitsstunden}$ je Jahr notwendig. Der Gewinn bei einer Kuh beträgt $400\,\mathrm{Franken}$ , bei einem Jungvieh $50\,\mathrm{Franken}$ im Jahr.

Wie viele Kühe und wie viel Stück Jungvieh muss der Betrieb halten, damit der Gesamtgewinn möglichst gross wird?

Solution

Die Zielfunktion ist $z(x,y)=400x+50y\Leftrightarrow y_z=-8x+\frac{z}{50}$ und die Bedingungen

\begin{align} 0.25x+0.1y\leq50 &\Leftrightarrow y_1\leq -2.5x+500\\ 100x+10y\leq8000 &\Leftrightarrow y_2\leq -10x+800 \end{align}

Das Planungspolygon sieht so aus:

$z$ soll möglichst gross werden. Der Punkt, der noch im Planungspolygon liegt und $z$ maximiert muss der Schnittpunkt der Geraden $y_1$ und $y_2$ sein, da die Steigung $-8$ zwischen den Steigungen $-2.5$ und $-10$ liegt. Aus $y_1=y_2$ folgt $x=40$ und damit $y=400$ . Also resultiert optimaler Gewinn, wenn man $40$ Kühe und $400$ Rinder hält.