Lineare Optimierung

Das Problem

Bei der linearen Optimierung handelt es sich um ein Verfahren zur Bestimmung des Minimums oder Maximums einer linearen Zielfunktion, wobei zudem einschränkende Bedingungen (so genannte Randbedingungen in Form linearer (Un-)gleichungen) erfüllt sein müssen. Das Verfahren zur Lösung solcher Fragestellungen soll im Folgenden nur anhand von Beispielen erklärt werden, da eine strikte mathematische Verallgemeinerung hier zu weit führen würde. Wen es dennoch interessiert, findet weiter unten einige Links.

Lösungsweg anhand eines Beispiels

Ein Bäcker stellt unter anderem Haselnusskuchen und Zitronenkuchen her. Neben Mehl, Zucker und Milch benötigt er für den Haselnusskuchen noch Nüsse und für den Zitronenkuchen eine Mischung, die einen Zitronengeschmack hat. Dabei hat er von jeder Zutat nur eine bestimmte Menge zur Verfügung: Mehl 30 kg, Zucker 25 kg, Milch 100 l, Haselnüsse 10 kg und Zitronenmischung 20 kg. Des Weiteren sei erwähnt, dass der Haselnussteig zu 40 Prozent aus Mehl, zu 20 Prozent aus Zucker, zu 25 Prozent aus Milch und 15 Prozent Haselnüssen besteht. Bei dem Zitronenkuchenteig hingegen beträgt die Zusammensetzung: 25 Prozent Mehl, 30 Prozent Zucker, 15 Prozent Milch und 30 Prozent Zitronenmischung. Ferner wiegen beide Kuchen je ein Kilogramm. Wenn der Bäcker den Haselnusskuchen verkauft, erhält er sieben Euro, für den Zitronenkuchen drei Euro. Jetzt stellt sich die Frage, wieviele Haselnuss- bzw. Zitronenkuchen er herstellen muss, so dass er mit den vorhandenen Zutaten auskommt und er zudem seinen Gewinn maximiert.
Zunächst können wir die in obiger Beschreibung gegebenen Daten der Übersichtlichkeit halber in einer Tabelle zusammentragen:

Nun wollen wir aus dieser Tabelle ein Ungleichungssystem ableiten. Dazu bezeichnen wir die Anzahl der hergestellten Haselnusskuchen mit x und die Anzahl der Zitronenkuchen mit y. Wir betrachten zunächst das Mehl und stellen fest, dass wir 0.4x + 0.25y Kilogramm Mehl verbrauchen, da beide Kuchen je ein Kilogramm wiegen und der Haselnusskuchen zu vier Zehnteln (das sind 40%) sowie der Zitronenkuchen zu einem Viertel aus Mehl besteht. Die verbrauchte Menge Mehl darf nun aber unseren Vorrat von 30 kg nicht übersteigen, wir erhalten also als erste Ungleichung (die wir, wie oben gesagt, eine Randbedingung nennen):

Als Nächstes betrachten wir den Zucker: Ein Nusskuchen braucht 0.2 kg Zucker, ein Zitronenkuchen 0.3 kg, also verbrauchen wir 0.2x + 0.3y Kilogramm, wir haben 25 kg im Lager, also lautet die zweite Randbedingung

Nun zur Milch, ein Nusskuchen braucht 0.25 l, ein Zitronenkuchen 0.15 l, d.h. wir brauchen 0.25x + 0.15y Liter Milch, uns stehen 100 l zur Verfügung, d.h. wir haben die Randbedingung

Nun brauchen wir für einen Nusskuchen genau 0.15 kg Haselnüsse, wovon uns 10 kg zur Verfügung stehen, die nächste Bedingung lautet also

Genauso brauchen wir für den Zitronenkuchen noch Zitronenmischung und zwar für jeden 0.3 kg. Da unser Lager 20 kg enthält, lautet die letzte Randbedingung

Aber wir müssen zusätzlich noch beachten, dass wir keine negative Anzahl Kuchen herstellen können, also erhalten wir noch die zusätzlichen Randbedingungen, dass x und y positiv sein müssen, also

Unser Gewinn - die Größe, die wir maximieren wollen - beträgt 7x + 3y. Da es unser Ziel ist, den Gewinn zu maximieren, nennen wir 7x + 3y auch die Zielfunktion, die wir mit Z bezeichnen wollen.
Nun können wir unser Problem noch einmal in Form eines linearen Ungleichungssystems notieren:

Alle Werte x und y, die gemeinsam alle Randbedingungen erfüllen, heißen zulässige Lösungen. Die Menge der zulässigen Lösungen ist der ausgefüllte Teil in folgender Zeichnung.

Zur Erklärung sei noch gesagt, dass die Geraden, die dieses Gebiet begrenzen, genau diejenigen sind, bei denen in den Ungleichungen R₁-R₇ Gleichheit vorliegt.
Die Geraden 7x + 3y = c sind für verschiedene c gestrichelt eingezeichnet. Die Zahl c soll so gewählt werden, dass sie erstens maximal ist und dass zweitens die Gerade den zulässigen Bereich noch schneidet. Parallelverschiebung dieser Geraden entspricht verschiedenen Werten von c. Größeren Werten der Zielfunktion entsprechen hier "weiter rechts" liegende Geraden. Wir können nun die Zielfunktion maximieren, indem wir unsere Garaden parallel soweit es geht innerhalb der zulässigen Lösungen verschieben. Man kann erkennen, dass sie im Punkt c = (x₀,y₀) einen maximalen Wert annimmt, der der Schnittpunkt der Geraden ist, die durch die Gleichungen R₁ und R₄ beschrieben sind. D.h. man kann somit den Punkt c = (x₀,y₀) genau bestimmen, indem man das lineare Gleichungssystem

löst.
Dazu wenden wir den Algorithmus von Gauß an. Wir haben, um uns das Rechnen zu vereinfachen, zunächst die Dezimalbrüche in Brüche umgewandelt:

D.h. wir erhalten als einzige Lösung c = (66 2/3,13 1/3). Dies können wir nun in die Zielfunktion einsetzen und erhalten

d.h. der Bäcker kann mit diesen Zutaten einen maximalen Gewinn von ungefähr 506,66 Euro erzielen.
Manchmal ist anhand der Zeichnung nicht zu erkennen, wo die Zielfunktion ihren maximalen Wert annimmt, dann muss man alle Ecken des Vielecks, welches die zulässigen Lösungen begrenzt, einsetzen. Der maximale Wert ist dann die Lösung, da man zeigen kann, dass das Maximum stets auf einer solchen Ecke liegen muss.

Beispiele

Als weiteres Beispiel wollen wir Folgendes betrachten: Auf einem Landgut sollen die Weine W₁ und W₂ mit den Substanzen S₁, S₂ und S₃ gemischt werden, so dass die Mischung möglichst preisgünstig wird. Die relevanten Angaben sind hier schon direkt in folgender Tabelle zusammengefasst:

Dies können wir nun wieder zu einem Ungleichungssystem umformen, wobei auch hier wieder darauf zu achten ist, dass man nur dann eine sinnvolle Lösung erhält, wenn x und y nichtnegativ sind.

Erneut können wir dieses Ungleichungssystem zeichnerisch darstellen:

Die zulässigen Lösungen befinden sich in dem schraffierten Teil des Bildes und die Zielfunktion ist durch eine parallele Geradenschar gegeben.
Der Zeichnung entnehmen wir, dass der Schnittpunkt c = (x₀, y₀) der Geraden, die durch R₁ und R₃ gegeben sind, die minimale Lösung ist. Wie schon oben berechnen wir den Punkt mit Hilfe des Gaußschen Algorithmus.

Unsere Lösung ist also c = (3,7). Damit ist der minimale Wert der Zielfunktion

Als drittes Beispiel wollen wir nun einmal ein Minimumproblem mit drei Unbekannten betrachten: Eine Geschirrfabrik beliefert drei Großmärkte unter anderem mit Tassen, großen Tellern und kleinen Tellern. Markt 1 verkauft die Tassen und großen Teller jeweils für vier Euro und die kleinen Teller für drei Euro. Insgesamt will er mindestens 70 Euro daran verdienen. Markt 2 verkauft die Tassen immer für zwei Euro und die großen Teller für einen, er bietet gar keine kleinen Teller an und will mindestens 20 Euro an den beiden Artikeln verdienen. Markt 3 bietet die Tassen für vier Euro an und die großen und kleinen Teller jeweils für zwei Euro. Er will mindestens 60 Euro an den Geschirrstücken verdienen. Die Produktion einer Tasse kostet die Fabrik einen Euro, die Produktion eines großen Tellers zwei Euro und eines kleinen Tellers einen Euro. Sie will natürlich den Bedarf der Märkte decken, so dass diese jeweils ihre geplanten Einnahmen haben, andererseits will sie ihre eigenen Kosten so gering wie möglich halten. Zur Übersicht stellen wir wieder folgende Tabelle auf:

Das heißt, wir haben folgendes lineares Ungleichungssystem zu betrachten:

Wir können nun wieder versuchen, die Menge der Lösungen zu skizzieren. Hierbei ist darauf zu achten, dass wir keine Geradenungleichungen, sondern Ebenenungleichungen vorliegen haben und auch die Zielfunktion durch eine Ebene repräsentiert wird, die wir parallel nach unten verschieben müssen, um ihren Wert zu minimieren.

Hier ist der Zeichnung nicht direkt zu entnehmen, an welcher Ecke das Minimum angenommen wird, daher setzen wir die Ecken unseres Vielflächners nun nacheinander in die Zielfunktion ein. Dazu müssen wir diese Ecken zunächst berechnen. Dies tun wir, indem wir die Schnittpunkte der Ebenen miteinander und mit den Koordinatenebenen berechnen.
Als Beispiel sei hier der Schnittpunkt der drei durch die ersten Ungleichungen gegebenen Ebenen miteinander berechnet, dieser ergibt sich als Lösung des Gleichungssystem

Dazu lösen wir das lineare Gleichungssystem:

Der Schnittpunkt der drei ersten Ebenen ist also (10,0,10), insgesamt erhalten wir als Ecken des Vielflächners:

Setzen wir nun in die Zielfunktion ein, so erhalten wir (diese Werte haben wir oben in die Zeichnung in hellgrau eingetragen):

Das lineare Optimierungsproblem besitzt somit die optimale Lösung c = p₂ und der Wert der Zielfunktion beträgt