L1 Lineare Optimierungsprobleme
Inhaltliche Einführung der Linearen Optimierung
Bis jetzt wirkt vielleicht alles ein bisschen theoretisch, aber es gibt in fast allen Bereichen der Ökonomie und in anderen Wissenschaften Probleme, die Lineare Optimierungsprobleme, kurz LPs, sind. Die Probleme sind oft sehr groß, das bedeutet, dass es viele Variablen und Nebenbedingungen gibt. Komplizierte fachliche Zusammenhänge lassen sich durch LPs abbilden. Für den Anfang ein sehr einfaches Modell:
Müslimischen
Ein nebenberuflicher Lebensmittelhersteller mischt aus regionalen Zutaten leckere Müslis, die er anschließend auf einem lokalen Wochenmarkt verkauft. Er bietet die beiden Sorten Standardmüsli und Superfruchtmüsli an, die aus den Zutaten Haferflocken, Trockenobst und Nüssen hergestellt werden.
Die Rezepturen sind wie folgt (pro kg Müsli):
| Standardmüsli | Superfruchtmüsli | |
| Haferflocken | 0,8 kg | 0,8 kg |
| Trockenobst | 0,1 kg | 0,2 kg |
| Nüsse | 0,1 kg | --- |
Das Standardmüsli kann er für 6 € pro kg verkaufen, das Superfruchtmüsli für 8 € pro kg.
Zur Mischung der Müslis für den nächsten Markttag stehen 80 kg Haferflocken, 16 kg Trockenobst und 7 kg Nüsse zur Verfügung, mehr Zutaten die seinen Qualitätsansprüchen genügen waren einfach nicht beschaffbar.
Ziel ist, am nächsten Markttag möglichst viel Geld zu erlösen. Welche Mengen der beiden Sorten sollen jeweils hergestellt werden? Getreu dem Motto „Nur Bares ist Wahres“ spielt bei der Entscheidung keine Rolle, dass die Zutaten Geld gekostet haben und es möglicherweise zu einem späteren Zeitpunkt eine andere Verwendung geben könnte. Aus Erfahrung weiß der Lebensmittelhersteller, dass seine Müslis so beliebt sind, dass er eigentlich jede Menge verkaufen kann.
Aus diesen Informationen wird nun das Lineare Optimierungsproblem aufgestellt.
Die Variablen sind:
x1: Herzustellende Menge Standardmüsli in kg
x2: Herzustellende Menge Superfruchtmüsli in kg
Die Zielfunktion lautet:
| max | z= 6·x1+ 8·x2 | (Verkaufspreis der Müslis mal produzierter Menge) |
Formulierung der Nebenbedingungen
Für die Herstellung sind die zur Verfügung stehenden Zutaten einschränkend. Für jede Zutat kann nun eine Ungleichung aufgestellt werden. Die Summe der Verbräuche einer Zutat muss geringer sein, als die zur Verfügung stehende Menge.
| u.d.N. | 0,8·x1 | + 0,8·x2 | ≤80 | (Haferflocken-Nebenbedingung) |
| 0,1·x1 | + 0,2·x2 | ≤16 | (Trockenobst-Nebenbedingung) | |
| 0,1·x1 | ≤ 7 | (Nuss-Nebenbedingung) |
Nichtnegativitätsbedingungen
x1≥0; x2≥0;
In diesem Beispiel ist es nicht nur aus algorithmischen Gründen notwendig, die Nichtnegativitätsbedingungen einzuführen, sondern auch weil negative Mengen keinen Sinn machen.
