Lineare Optimierung

Lineare Optimierung (auch lineare Programmierung genannt) ist ein Verfahren, um den besten Wert einer Größe zu finden, zum Beispiel den größten Gewinn oder die geringsten Kosten, wenn die Mittel begrenzt sind. „Linear“ heißt: Die Größe, die du verbessern willst, und alle Beschränkungen sind einfache Terme wie $40x+50y$ oder $2x+y\le 100$, ohne Quadrate und ohne Produkte von Unbekannten.

Ein Betrieb kennt solche Aufgaben aus dem Alltag: Maschinen laufen nur eine bestimmte Zeit, Material ist knapp, und die Kundschaft nimmt nur eine begrenzte Menge ab. Mit zwei Unbekannten löst du die Aufgabe zeichnerisch, du brauchst dafür nur Geraden und Halbebenen. Für große Aufgaben mit tausenden Unbekannten gibt es das Simplex-Verfahren, das auf derselben Idee beruht.

Ein Beispiel: Regale und Tische

Eine kleine Schreinerei baut Regale und Tische. Für ein Regal braucht sie 2 Stunden am Zuschnitt und 1 Stunde am Schleifplatz, für einen Tisch 1 Stunde Zuschnitt und 2 Stunden Schleifen. Pro Woche stehen 100 Zuschnittstunden und 80 Schleifstunden zur Verfügung. Mehr als 45 Regale pro Woche lassen sich nicht verkaufen. Ein Regal bringt 40 € Gewinn, ein Tisch 50 €. Es ist ein vereinfachtes Zahlenbeispiel zum Üben.

Wie viele Regale und Tische soll die Schreinerei pro Woche bauen, damit der Gewinn möglichst groß wird?

Schritt 1: Das Modell aufstellen

Zuerst übersetzt du die Aufgabe in Mathematik. Wähle Variablen: $x$ ist die Zahl der Regale pro Woche, $y$ die Zahl der Tische. Dann gilt:

• Zuschnitt: $2x+y\le 100$ (Bedingung 1)
• Schleifen: $x+2y\le 80$ (Bedingung 2)
• Absatz: $x\le 45$ (Bedingung 3)
• Negative Stückzahlen gibt es nicht: $x\ge 0$ und $y\ge 0$.
• Gewinn: $Z(x,y)=40x+50y$. Dieser Wert soll möglichst groß werden.

Schritt 2: Den zulässigen Bereich zeichnen

Jede Ungleichung wie $2x+y\le 100$ teilt die Ebene in zwei Halbebenen. Du zeichnest zuerst die Randgerade und bestimmst dann die richtige Seite:

1. Setze das Gleichheitszeichen ein: $2x+y=100$. Die Achsenabschnitte sind $(50|0)$ und $(0|100)$. Ziehe die Gerade durch beide Punkte.
2. Mache die Probe mit einem Testpunkt, der nicht auf der Geraden liegt, am besten dem Ursprung: $2·0+0=0\le 100$ ist wahr. Also gehört die Seite mit dem Ursprung zum Bereich.
3. Wiederhole das für alle Bedingungen. Bedingung 2 liefert die Gerade durch $(80|0)$ und $(0|40)$, Bedingung 3 die senkrechte Gerade $x=45$.

Der zulässige Bereich ist der Durchschnitt aller Halbebenen, also die Fläche, die alle Bedingungen gleichzeitig erfüllt. Mehr zu Systemen von Ungleichungen findest du bei den Ungleichungen.

Die schrägen Geraden für $Z$ im Bild brauchst du erst im nächsten Schritt. Der Bereich ist ein Fünfeck. Seine Ecken sind die Schnittpunkte benachbarter Randgeraden. Du berechnest sie als Gleichungssystem:

• $(0|0)$: der Ursprung.
• $(45|0)$: die Gerade $x=45$ trifft die $x$-Achse.
• $(45|10)$: $x=45$ in $2x+y=100$ einsetzen, das gibt $90+y=100$, also $y=10$.
• $(40|20)$: aus $x+2y=80$ folgt $x=80-2y$. Eingesetzt in $2x+y=100$ ergibt sich $160-4y+y=100$, also $y=20$ und $x=40$.
• $(0|40)$: die Gerade $x+2y=80$ trifft die $y$-Achse.

Nicht jeder Schnittpunkt zweier Randgeraden ist eine Ecke. So schneidet $2x+y=100$ die $x$-Achse bei $(50|0)$. Dieser Punkt verletzt aber $x\le 45$ und liegt deshalb außerhalb des Bereichs.

Schritt 3: Die Zielfunktion als Schar von Geraden

Wie findest du unter den unendlich vielen Punkten des Bereichs den mit dem größten Gewinn? Lege zuerst einen Gewinn fest, etwa $Z=1000$. Alle Punkte mit $40x+50y=1000$ liegen auf einer Geraden, der Niveaulinie (der Linie gleichen Wertes). Nach $y$ aufgelöst lautet sie

Alle Niveaulinien haben dieselbe Steigung $-\mathrm{0,8}$ und sind damit parallel. Nur der Achsenabschnitt $\frac{Z}{50}$ wächst mit dem Gewinn: Für $Z=1000$ ist er 20, für $Z=2000$ ist er 40. Je größer der Gewinn, desto weiter rechts oben liegt die Gerade.

Schiebe die Gerade also so weit nach rechts oben, wie sie noch einen Punkt des Bereichs berührt. Der letzte Berührpunkt ist die Ecke $(40|20)$. Die zugehörige Gerade hat den Achsenabschnitt $\frac{Z}{50}=52$, also ist $Z=2600$.

Schritt 4: Das Eckenprinzip

Warum reichen die Ecken? Eine lineare Funktion hat überall dieselbe Steigung. Steht ein Punkt im Inneren des Bereichs, kannst du in Richtung wachsender Werte weitergehen, bis du den Rand erreichst. Entlang einer Kante ändert sich die Zielfunktion gleichmäßig, also ist sie am Ende der Kante, in einer Ecke, mindestens so groß wie davor.

Der Unterschied zu Extremwertaufgaben

Bei Extremwertaufgaben hängt die Zielgröße meist krumm von den Unbekannten ab, etwa die Fläche $x·(20-x)$. Das Maximum liegt dort, wo die Ableitung null ist, oft im Inneren. Eine lineare Funktion hat nirgends eine waagerechte Tangente. Du kannst sie immer weiter verbessern, bis eine Grenze im Weg steht. Deshalb sitzt das Optimum am Rand, genauer in einer Ecke, und du kommst ohne Ableitung aus.

Minimieren: die Futtermischung

Manchmal sollen die Kosten möglichst klein werden. Ein Beispiel: Ein Landwirt mischt zwei Futtersorten. Sorte 1 kostet 3 € pro kg und enthält pro kg 2 Einheiten Eiweiß und 1 Einheit Mineralstoffe. Sorte 2 kostet 2 € pro kg und enthält pro kg 1 Einheit Eiweiß und 2 Einheiten Mineralstoffe. Ein Tier braucht pro Tag mindestens 12 Einheiten Eiweiß und 9 Einheiten Mineralstoffe.

Mit $x$ kg Sorte 1 und $y$ kg Sorte 2 lautet das Modell:

• Eiweiß: $2x+y\ge 12$
• Mineralstoffe: $x+2y\ge 9$
• $x\ge 0$, $y\ge 0$
• Kosten: $K(x,y)=3x+2y$ soll möglichst klein werden.

Hier gelten Mindestmengen ($ge$), deshalb ist der Bereich nach oben offen. Die Ecken sind $(0|12)$, $(5|2)$ und $(9|0)$. Die Ecke $(5|2)$ entsteht aus $2x+y=12$ und $x+2y=9$. Die Kosten betragen dort $3·5+2·2=19$ €, bei $(0|12)$ sind es 24 € und bei $(9|0)$ sind es 27 €.

Beim Minimieren schiebst du die Niveaulinie vom Ursprung weg, bis sie den Bereich zum ersten Mal berührt. Das Ergebnis: Die günstigste Mischung hat 5 kg Sorte 1 und 2 kg Sorte 2 und kostet 19 €. Proben: Eiweiß $10+2=12$, Mineralstoffe $5+4=9$. Beide Mindestmengen werden genau erreicht.

Obwohl der Bereich nach oben offen ist, gibt es ein Minimum, denn die Kosten wachsen in diese Richtung nur. Ein Maximum der Kosten gäbe es nicht, mehr dazu bei den Sonderfällen.

Sonderfälle

Nicht jede Aufgabe hat genau eine beste Lösung. Es gibt drei Ausnahmen:

• Mehrere Optima: Bringt ein Regal nur 20 € und ein Tisch 40 €, ist $Z=20x+40y$. Die Niveaulinien haben die Steigung $-\mathrm{0,5}$, genau wie die Randgerade $x+2y=80$. In den Ecken $(0|40)$ und $(40|20)$ ist $Z=1600$. Dann ist jeder Punkt der Strecke dazwischen optimal, zum Beispiel $(20|30)$ mit $20·20+40·30=1600$.
• Unbeschränkte Aufgabe: Ist der Bereich offen und wächst $Z$ in diese Richtung, gibt es keinen größten Wert. Beispiel: Maximiere $Z=x+y$ unter $x-y\le 2$, $x\ge 0$, $y\ge 0$. Die Punkte $(2+t|t)$ sind zulässig, dort ist $Z=2+2t$. Du kannst $t$ beliebig groß wählen. In der Praxis fehlt dem Modell eine Grenze.
• Leerer Bereich: Widersprechen sich die Bedingungen, etwa $x+y\le 3$ und $x+y\ge 5$, gibt es keinen zulässigen Punkt und damit keine Lösung.

Das Simplex-Verfahren in Worten

Mit drei Unbekannten liegt der Bereich im Raum und ist ein Vielflach mit Ecken, Kanten und Flächen. Bei vier oder mehr Unbekannten kannst du ihn nicht mehr zeichnen. Echte Aufgaben haben tausende oder Millionen Unbekannte. Trotzdem gilt das Eckenprinzip weiter, und darauf baut das Simplex-Verfahren auf. Es läuft von Ecke zu Ecke:

1. Starte in einer Ecke, zum Beispiel im Ursprung.
2. Prüfe die benachbarten Ecken, die über eine Kante erreichbar sind. Gibt es eine, in der die Zielfunktion größer ist, gehe dorthin.
3. Wiederhole Schritt 2. Gibt es keine bessere Nachbarecke, bist du fertig. Weil der Bereich keine „Dellen“ hat (er ist konvex: Die Verbindungsstrecke zweier Punkte des Bereichs bleibt im Bereich), ist diese Ecke schon das Optimum.

Das Verfahren wählt dabei oft die Kante mit dem größten Zuwachs je Einheit. Im Beispiel ist das die $y$-Richtung mit 50 € je Tisch statt 40 € je Regal.

Rechnerisch wandelt man jede Ungleichung durch eine Reservevariable (Schlupfvariable) in eine Gleichung um, zum Beispiel $2x+y+s=100$ mit $s\ge 0$. Ein Schritt von Ecke zu Ecke entspricht dann einem Schritt wie beim Gauß-Verfahren für Gleichungssysteme.

In der Praxis ist das Simplex-Verfahren meist schnell. Es gibt aber von Klee und Minty konstruierte Beispiele, bei denen die Zahl der Schritte exponentiell wächst. Dafür wurden andere Verfahren entwickelt: 1979 zeigte Leonid Khachiyan mit der Ellipsoidmethode, dass sich lineare Programme theoretisch in vertretbarer (polynomialer) Zeit lösen lassen, und 1984 stellte Narendra Karmarkar ein Innere-Punkte-Verfahren vor, das auch praktisch gut funktioniert.

Verlangt die Aufgabe ganze Zahlen, etwa ganze Regale, wird es schwieriger. Unser Ergebnis $(40|20)$ war zufällig ganzzahlig. Im Allgemeinen liefert das Verfahren Brüche, und Runden kann das Optimum verfehlen oder die Bedingungen verletzen. Dafür gibt es die ganzzahlige Optimierung.

Dualität und Schattenpreise

Zu jeder Maximierungsaufgabe gibt es eine Zwillingsaufgabe, die duale Aufgabe. Sie fragt aus Sicht des Betriebs: Was ist eine Stunde Zuschnitt, eine Stunde Schleifen und ein Absatzplatz mindestens wert, damit die Ressourcen nicht billiger sind als der Gewinn, den sie bringen?

Seien $u$, $v$ und $w$ diese Werte pro Einheit von Bedingung 1, 2 und 3. Ein Regal verbraucht 2 Zuschnittstunden, 1 Schleifstunde und 1 Absatzplatz. Ihr Wert muss also mindestens den Gewinn von 40 € erreichen. Für den Tisch gilt Entsprechendes:

Die Lösung ist $u=10$, $v=20$ und $w=0$. Probe: Es gilt $2·10+20+0=40$ und $10+2·20=50$. Der Zielwert ist $100·10+80·20=2600$. Das ist genau der Höchstgewinn der Schreinerei.

Bei uns bringt eine zusätzliche Zuschnittstunde 10 € und eine zusätzliche Schleifstunde 20 €. Ein zusätzlicher Absatzplatz bringt nichts (0 €), denn die Grenze von 45 wird gar nicht erreicht. Zum Nachrechnen: Mit 101 Zuschnittstunden schneiden sich die Geraden bei $x=\frac{122}{3}$ und $y=\frac{59}{3}$, und der Gewinn steigt auf 2610 €. Das gilt, solange sich die Ecke nicht ändert, also für kleine Änderungen.

Anwendungen

• Produktionsplanung: Welche Mengen sollen mit knappen Maschinen und Material gefertigt werden, damit der Gewinn am größten wird?
• Mischungsaufgaben: Futter, Dünger, Legierungen oder Diäten: möglichst günstig, aber mit genügend Nährstoffen. Das Diät-Problem ist ein klassisches Beispiel.
• Transport: Güter sollen von Lagern zu Läden fließen, sodass die Fahrtkosten minimal sind. Schon Gaspard Monge betrachtete im 18. Jahrhundert, wie Erde möglichst günstig vom Aushub zur Aufschüttung wandert.
• Netze: Leitungen und Verkehrswege in der Telekommunikation und im Verkehr werden mit solchen Modellen geplant.
• Pläne: Fluggesellschaften planen den Einsatz ihrer Besatzungen mit ganzzahligen linearen Modellen. Auch Schichtpläne lassen sich so beschreiben.
• Spiele: Die beste Strategie bei Zweipersonen-Nullsummenspielen ist ein lineares Programm. Mehr dazu bei John von Neumann.

Typische Fehler

Übungen

Zum Üben mit einzelnen Ungleichungen hilft der Ungleichungsrechner.

Geschichte: von Fourier bis Karmarkar

Die Wurzeln reichen weit zurück: Schon 1827 veröffentlichte Joseph Fourier ein Verfahren, Systeme linearer Ungleichungen zu lösen. Man nennt es heute Fourier-Motzkin-Elimination, denn Theodore Motzkin entdeckte es 1936 erneut.

1939 entwickelte der sowjetische Mathematiker Leonid Kantorowitsch, der die Produktion in der Sperrholzindustrie verbessern sollte, die Technik, die wir heute lineare Optimierung nennen. Kurz danach veröffentlichte Frank Hitchcock eine Arbeit zu einem Transportproblem. Aus Planungsaufgaben der US-Luftwaffe entstand das Simplex-Verfahren, das George Dantzig 1947 veröffentlichte. Im selben Jahr erkannte John von Neumann, dass diese Aufgaben mit seiner Spieltheorie zusammenhängen. Daraus entwickelte sich die Dualitätstheorie.

Ab Mitte der 1950er Jahre lösten Computer immer größere Aufgaben, und in der Wirtschaft verbreitete sich die Methode, vor allem in Ölraffinerien. 1975 erhielten Kantorowitsch und der Ökonom Tjalling Koopmans den Wirtschaftsnobelpreis für Beiträge zur Theorie der optimalen Verteilung knapper Mittel. Nach den Verfahren von Khachiyan (1979) und Karmarkar (1984) ist lineare Optimierung heute ein Standardwerkzeug. Einen Überblick über die Mathematik dieser Zeit gibt der Beitrag zur Mathematik des 20. Jahrhunderts.

Häufige Fragen

Muss das Optimum immer in einer Ecke liegen?

Mindestens eine Ecke ist immer optimal, wenn der Bereich Ecken hat und ein Optimum existiert. Bei mehreren Optima gehört auch die ganze Kante dazwischen dazu, wie im Sonderfall oben.

Was tun, wenn es mehr als zwei Unbekannte gibt?

Dann nutzt du das Simplex-Verfahren oder ein anderes Verfahren und lässt einen Rechner arbeiten. Tabellenkalkulationen und Optimierungsprogramme haben dafür einen Solver.

Darf das Ergebnis ein Bruch sein?

Rechnerisch ja. Bei Stückzahlen musst du aber ganze Zahlen verlangen. Das ist die ganzzahlige Optimierung, die deutlich schwieriger ist.

Quellen und weiterführende Literatur

• Wikipedia: Lineare Optimierung
• Wikipedia: Simplex-Verfahren
• Wikipedia: George Dantzig
• Wikipedia: Leonid Witaljewitsch Kantorowitsch
• Wikipedia: Fourier-Motzkin-Elimination
• Wikipedia: Linear programming (englisch, Abschnitt History)
• George B. Dantzig: Linear Programming and Extensions, Princeton University Press, 1963.
• Jiří Matoušek, Bernd Gärtner: Understanding and Using Linear Programming, Springer, 2007.