Lineare Optimierung
Wie viel von welchem Produkt soll ein Betrieb herstellen, damit der Gewinn möglichst groß wird – wenn Maschinenzeit, Material und Absatz begrenzt sind? Solche Fragen löst die lineare Optimierung: Eine lineare Zielfunktion wird unter linearen Nebenbedingungen maximiert oder minimiert. Mit zwei Variablen geht das grafisch, mit mehr Variablen hilft das Simplex-Verfahren.
Das Modell aufstellen
Beispiel: eine Möbelwerkstatt
Eine Werkstatt baut Regale und Schränke. Für ein Regal fallen 3 Stunden Zuschnitt und 1 Stunde Montage an, für einen Schrank je 2 Stunden Zuschnitt und Montage. In der Woche hat die Werkstatt 120 Stunden für den Zuschnitt und 80 Stunden für die Montage. Mehr als 30 Regale kann die Lackiererei nicht fertig machen. Jedes Regal bringt 50 € Deckungsbeitrag, jeder Schrank 60 €.
- Entscheidungsvariablen: $x$ = Anzahl Regale, $y$ = Anzahl Schränke pro Woche.
- Zielfunktion: $z = 50x + 60y \rightarrow \max$.
- Nebenbedingungen: (1) $3x + 2y \le 120$ (Zuschnitt), (2) $x + 2y \le 80$ (Montage), (3) $x \le 30$ (Lackierung).
- Nichtnegativität: $x \ge 0,\ y \ge 0$ – negative Stückzahlen gibt es nicht.
Jede Nebenbedingung beschreibt eine Halbebene; ihre Randgerade erhält man, wenn man „$\le$“ durch „$=$“ ersetzt. Alle Punkte, die sämtliche Bedingungen erfüllen, bilden den zulässigen Bereich – bei Ungleichungen mit zwei Variablen ein Vieleck, das Planungsvieleck (auch Planungspolygon).
Grafische Lösung
- Randgeraden zeichnen, am einfachsten über die Achsenabschnitte: $3x + 2y = 120$ geht durch $(40\,|\,0)$ und $(0\,|\,60)$.
- Die richtige Seite bestimmen: Ein Testpunkt wie $(0\,|\,0)$ zeigt, ob die Halbebene zum Ursprung hin oder von ihm weg liegt.
- Den Bereich markieren, den alle Halbebenen gemeinsam haben – das Planungsvieleck.
- Die Zielgerade $50x + 60y = z$ für einen beliebigen Wert $z$ zeichnen. Alle Zielgeraden sind parallel (Steigung $-\frac{50}{60} = -\frac{5}{6}$).
- Die Zielgerade parallel verschieben, bis sie das Vieleck gerade noch berührt – beim Maximum möglichst weit vom Ursprung weg.
Getönt: zulässiger Bereich. Gestrichelt: Zielgerade $z = 50x + 60y$ durch die optimale Ecke. Mit dem Regler kannst Du sie parallel verschieben.
Zieh den Regler (oder tippe ins Bild): Solange die gestrichelte Gerade das getönte Vieleck schneidet, gibt es Produktionspläne mit diesem Deckungsbeitrag. Bei $z = 2800$ berührt sie es nur noch in der Ecke $(20\,|\,30)$.
Merke: Das Optimum liegt in einer Ecke
Hat ein lineares Optimierungsproblem überhaupt eine Lösung, dann wird sie in einer Ecke des Planungsvielecks angenommen. Man kann deshalb auch alle Ecken berechnen (Schnittpunkte zweier Randgeraden, die alle anderen Bedingungen erfüllen) und in die Zielfunktion einsetzen.
| Ecke | Schnitt von | $z = 50x + 60y$ |
|---|---|---|
| $(0\,|\,0)$ | $x = 0$, $y = 0$ | $0$ |
| $(30\,|\,0)$ | (3) und $y = 0$ | $1500$ |
| $(30\,|\,15)$ | (1) und (3) | $2400$ |
| $(20\,|\,30)$ | (1) und (2): $3x + 2y = 120$, $x + 2y = 80 \Rightarrow 2x = 40,\ x = 20$ | $\mathbf{2800}$ |
| $(0\,|\,40)$ | (2) und $x = 0$ | $2400$ |
Am meisten bringt also der Plan mit 20 Regalen und 30 Schränken: 2.800 € Deckungsbeitrag. Zuschnitt ($60 + 60 = 120$ Stunden) und Montage ($20 + 60 = 80$ Stunden) sind dann voll ausgelastet, in der Lackierung bleibt Platz für 10 weitere Regale. Die Schnittpunkte bestimmt man mit den Verfahren aus linearen Gleichungssystemen.
Sonderfälle
- Mehrdeutige Lösung: Ist die Zielgerade parallel zu einer Randgeraden, kann sie eine ganze Kante berühren. Dann sind beide Ecken und alle Punkte dazwischen optimal.
- Unbeschränkt: Ist das Vieleck nach außen offen und wächst $z$ in diese Richtung, gibt es kein Maximum. Meist fehlt dann eine Bedingung im Modell.
- Unzulässig: Widersprechen sich Bedingungen (z. B. $x + y \le 10$ und $x + y \ge 20$), ist der zulässige Bereich leer.
- Ganze Zahlen: Stückzahlen müssen oft ganzzahlig sein. Liegt die optimale Ecke nicht auf ganzen Zahlen, untersucht man die ganzzahligen Punkte in ihrer Nähe.
Minimum mit ≥-Bedingungen
Beispiel: Dünger mischen
Eine Gärtnerei mischt $x$ Säcke Dünger A (12 € je Sack) und $y$ Säcke Dünger B (7 € je Sack). Gebraucht werden mindestens 14 Einheiten Stickstoff und 37 Einheiten Phosphat; ein Sack A enthält 2 bzw. 5 Einheiten, ein Sack B 1 bzw. 3 Einheiten.
Kosten $z = 12x + 7y \rightarrow \min$ unter $2x + y \ge 14$ und $5x + 3y \ge 37$, $x, y \ge 0$.
Der zulässige Bereich liegt jetzt oberhalb der Geraden und ist nach außen offen – ein Minimum gibt es trotzdem, denn die Kosten wachsen nach außen. Ecken: $(0\,|\,14)$ mit $z = 98$, $(5\,|\,4)$ mit $z = 88$ und $(7{,}4\,|\,0)$ mit $z = 88{,}8$. Am günstigsten sind 5 Säcke A und 4 Säcke B für 88 €.
Getönt: zulässiger Bereich. Gestrichelt: Zielgerade $z = 12x + 7y$ durch die optimale Ecke. Mit dem Regler kannst Du sie parallel verschieben.
Simplex-Verfahren
Ab drei Variablen lässt sich nicht mehr zeichnen. Das Simplex-Verfahren wandert rechnerisch von Ecke zu Ecke, und zwar immer zu einer besseren, bis keine Verbesserung mehr möglich ist. Für ein Standard-Maximierungsproblem (alle Bedingungen „$\le$ Zahl“ mit Zahl $\ge 0$) läuft es so:
- Jede Bedingung bekommt eine Schlupfvariable $u_i \ge 0$ für die ungenutzte Kapazität: $3x_1 + 2x_2 + u_1 = 120$.
- Im Starttableau stehen die Koeffizienten, rechts die Kapazitäten $b$, unten die Zielzeile mit den negativen Zielkoeffizienten. Start ist die Ecke $x_1 = x_2 = 0$.
- Pivotspalte: die Spalte mit dem kleinsten (negativsten) Eintrag in der Zielzeile.
- Pivotzeile: der kleinste Quotient $b_i : a_i$ mit positivem $a_i$ in dieser Spalte (Engpass).
- Pivotzeile durch das Pivotelement teilen und die Spalte in allen anderen Zeilen zu 0 machen (wie beim Gauß-Verfahren).
- Wiederholen, bis die Zielzeile keine negativen Einträge mehr hat. Dann steht rechts unten das Optimum.
Das Möbel-Beispiel mit dem Simplex-Verfahren
Schlupfvariablen einführen
Jede ≤-Bedingung wird mit einer Schlupfvariablen $u_i \ge 0$ (ungenutzte Kapazität) zur Gleichung. Im Starttableau ist $x_1 = x_2 = 0$, die Schlupfvariablen bilden die Basis.
Starttableau
Pivotspalte: $x_2$ (negativster Eintrag $-60$ in der Zielzeile). Pivotzeile: kleinster Quotient $b_i : a_{i}$ mit positivem Nenner ($40$ in der Zeile von $u_2$). $x_2$ kommt in die Basis, $u_2$ geht hinaus.
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | \(b\) | Quotient |
|---|---|---|---|---|---|---|---|
| \(u_1\) | \(3\) | \(2\) | \(1\) | \(0\) | \(0\) | \(120\) | \(60\) |
| \(u_2\) | \(1\) | \(2\) | \(0\) | \(1\) | \(0\) | \(80\) | \(40\) |
| \(u_3\) | \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(30\) | |
| \(z\) | \(-50\) | \(-60\) | \(0\) | \(0\) | \(0\) | \(0\) |
Tableau nach Schritt 1
Pivotspalte: $x_1$ (negativster Eintrag $-20$ in der Zielzeile). Pivotzeile: kleinster Quotient $b_i : a_{i}$ mit positivem Nenner ($20$ in der Zeile von $u_1$). $x_1$ kommt in die Basis, $u_1$ geht hinaus.
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | \(b\) | Quotient |
|---|---|---|---|---|---|---|---|
| \(u_1\) | \(2\) | \(0\) | \(1\) | \(-1\) | \(0\) | \(40\) | \(20\) |
| \(x_2\) | \(0{,}5\) | \(1\) | \(0\) | \(0{,}5\) | \(0\) | \(40\) | \(80\) |
| \(u_3\) | \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(30\) | \(30\) |
| \(z\) | \(-20\) | \(0\) | \(0\) | \(30\) | \(0\) | \(2400\) |
Endtableau
In der Zielzeile steht kein negativer Eintrag mehr: Das Tableau ist optimal.
| Basis | \(x_1\) | \(x_2\) | \(u_1\) | \(u_2\) | \(u_3\) | \(b\) |
|---|---|---|---|---|---|---|
| \(x_1\) | \(1\) | \(0\) | \(0{,}5\) | \(-0{,}5\) | \(0\) | \(20\) |
| \(x_2\) | \(0\) | \(1\) | \(-0{,}25\) | \(0{,}75\) | \(0\) | \(30\) |
| \(u_3\) | \(0\) | \(0\) | \(-0{,}5\) | \(0{,}5\) | \(1\) | \(10\) |
| \(z\) | \(0\) | \(0\) | \(10\) | \(20\) | \(0\) | \(2800\) |
Ergebnis ablesen
Basisvariablen haben den Wert in der Spalte $b$, alle anderen sind 0. Rechts unten steht der optimale Zielwert.
Das Ergebnis stimmt mit der grafischen Lösung überein: $x_1 = 20$, $x_2 = 30$, $z = 2800$; die Schlupfvariable der Lackierung hat den Wert 10 – dort bleiben 10 Regale Kapazität frei. Ein Problem ist unbeschränkt, wenn eine Pivotspalte keinen positiven Eintrag hat.
Typische Fehler
- Die Nichtnegativität $x, y \ge 0$ vergessen – dann fehlen Ecken auf den Achsen.
- Schnittpunkte zweier Geraden als Ecke nehmen, ohne die übrigen Bedingungen zu prüfen.
- Beim Minimum mit „≥“ die falsche Seite der Geraden schraffieren.
- Im Simplex-Tableau den Quotienten auch bei negativen oder Null-Einträgen bilden.
Online üben
Gib die Lösung als x; y; z ein, z. B. 20; 30; 2800.
Stufe 1: Maximum, zwei Bedingungen
-
Aufgabe 1
Maximiere \(z = 6x + 7y\ \text{unter}\ 2x + 2y\) \(\le 180,\) \(4x + 5y \le 420,\) \(x, y \ge 0\)\(x; y; z\)\(\text{Ecken } (0\,|\,0): 0;\) \((90\,|\,0): 540;\) \((30\,|\,60): 600;\) \((0\,|\,84): 588\) \(\Rightarrow x = 30,\) \(y = 60,\) \(z_{\max} = 600\)
-
Aufgabe 2
Maximiere \(z = 5x + 19y\ \text{unter}\ x + 2y\) \(\le 90,\) \(x + 5y \le 135,\) \(x, y \ge 0\)\(x; y; z\)\(\text{Ecken } (0\,|\,0): 0;\) \((90\,|\,0): 450;\) \((60\,|\,15): 585;\) \((0\,|\,27): 513\) \(\Rightarrow x = 60,\) \(y = 15,\) \(z_{\max} = 585\)
-
Aufgabe 3
Maximiere \(z = 16x + 17y\ \text{unter}\ 4x + 3y\) \(\le 350,\) \(2x + 4y \le 300,\) \(x, y \ge 0\)\(x; y; z\)\(\text{Ecken } (0\,|\,0): 0;\) \((87{,}5\,|\,0): 1400;\) \((50\,|\,50): 1650;\) \((0\,|\,75): 1275\) \(\Rightarrow x = 50,\) \(y = 50,\) \(z_{\max} = 1650\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Lineare Optimierung – grafisch mit Ecken
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Was eine zusätzliche Stunde an einer voll ausgelasteten Maschine wert ist, beantworten die Schattenpreise – siehe Dualität und Schattenpreise.
Eigene Aufgaben – grafisch oder mit dem Simplex-Verfahren und vollständigem Rechenweg – löst der Rechner für lineare Optimierung. Ungleichungen mit einer Variablen findest Du unter Ungleichungen, das Rechnen mit Matrizen unter Matrizen.
Weiterlesen: Lineare Optimierung, Simplex-Verfahren bei Wikipedia