Lineare Optimierung grafisch – wie komme ich vom Aufgabentext zum zulässigen Bereich, und warum liegt das Optimum immer in einer Ecke?

Schöne Fragen, die gehen alle auf denselben Kern zurück. Erst das Rezept, dann die Begründung.

Vom Text zum Modell in fünf Schritten:

1. Variablen definieren – mit Einheit. „x₁ = produzierte Menge von Produkt A in Stück pro Woche“. Ohne Einheit passieren später Bezugsfehler.
2. Zielfunktion aufstellen. Maximiere Z = db₁·x₁ + db₂·x₂. Verwende den Deckungsbeitrag pro Stück, nicht den Stückgewinn: Fixkosten fallen ohnehin an, sie verschieben nur den Zielfunktionswert, nicht die optimale Lösung.
3. Für jeden Engpass eine Ungleichung. Koeffizient = Verbrauch pro Stück, rechte Seite = verfügbare Kapazität. Faustregel: Jede Zahl im Text, die eine Obergrenze beschreibt, wird zu einer Zeile.
4. Nichtnegativität nicht vergessen: x₁ ≥ 0, x₂ ≥ 0. Das ist kein Formalismus – ohne diese beiden Bedingungen ist der Bereich ein anderer.
5. Zeichnen: Jede Ungleichung als Gleichung auffassen und über die beiden Achsenschnittpunkte (einmal x₁ = 0, einmal x₂ = 0) als Gerade einzeichnen. Welche Halbebene gilt, prüfst du mit einem Testpunkt – meist dem Ursprung (0|0). Die Schnittmenge aller Halbebenen ist der zulässige Bereich.

Warum eine Ecke? Der zulässige Bereich entsteht als Durchschnitt endlich vieler Halbebenen und ist deshalb konvex – ein Vieleck ohne Dellen. Die Zielfunktion ist linear, ihre Höhenlinien (die Isogewinngeraden Z = const.) sind also parallele Geraden mit der festen Steigung −db₁/db₂. Verschiebst du diese Schar in Richtung wachsender Zielwerte, verlässt sie den Bereich irgendwann; der letzte Berührpunkt ist die Lösung. Ein solcher Berührpunkt eines konvexen Vielecks mit einer Geraden ist entweder ein Eckpunkt oder eine ganze Kante – innen liegen kann er nie, weil man von jedem inneren Punkt aus noch in Richtung höherer Zielwerte weitergehen könnte. Genau das besagt der Hauptsatz der linearen Optimierung.

Damit ist auch die dritte Frage beantwortet: Ablesen ist nur zum Finden da, nicht zum Rechnen. Du erkennst in der Zeichnung, welche zwei Restriktionsgeraden sich in der optimalen Ecke schneiden, und berechnest den Schnittpunkt danach exakt über das lineare Gleichungssystem der beiden zugehörigen Gleichungen. Dann Zielfunktionswert einsetzen – fertig.

Drei Sonderfälle, die gern als Teilaufgabe kommen: Ist die Isogewinngerade parallel zu einer bindenden Restriktion, ist die gesamte Kante optimal (unendlich viele Lösungen bei gleichem Zielwert). Ist der zulässige Bereich leer, widersprechen sich die Bedingungen. Ist er unbeschränkt in Richtung der Zielfunktion, existiert kein endliches Maximum – bei Kapazitätsaufgaben ein sicheres Zeichen, dass eine Restriktion vergessen wurde.

Ergänzend der Teil nach der Rechnung, denn in Klausuren hängen an der Lösung fast immer noch Interpretationsfragen – und die geben oft mehr Punkte als das Zeichnen selbst.

Setz deine optimale Lösung in jede Restriktion ein und schau, ob sie mit Gleichheit erfüllt ist:

• Mit Gleichheit erfüllt = bindend. Die Ressource ist vollständig verbraucht, das ist ein echter Engpass.
• Mit Ungleichheit erfüllt = nicht bindend. Die Differenz ist die Schlupfvariable und beziffert die ungenutzte Kapazität. Genau danach wird oft gefragt („Wie viele Maschinenstunden bleiben ungenutzt?“).

Der zweite Standardteil ist der Schattenpreis (Dualwert): Um wie viel steigt der optimale Zielfunktionswert, wenn von der knappen Ressource eine Einheit mehr zur Verfügung steht? Grafisch verschiebst du die bindende Gerade um eine Einheit nach außen, berechnest die neue Ecke und bildest die Differenz der Zielwerte. Zwei Dinge dazu:

1. Für eine nicht bindende Restriktion ist der Schattenpreis null – mehr von etwas, das ohnehin übrig ist, bringt nichts.
2. Der Wert gilt nur in einem Gültigkeitsbereich. Erweiterst du zu stark, wird eine andere Restriktion bindend, und der Schattenpreis ändert sich sprunghaft. Deshalb ist die Antwort auf „Was dürfte eine zusätzliche Maschinenstunde kosten?“ immer der Schattenpreis innerhalb dieses Bereichs – das sind Opportunitätskosten, kein Marktpreis.

Und noch die Verbindung zur Kostenrechnung, weil beides oft im selben Modul geprüft wird: Die einfache Regel „nach Deckungsbeitrag je Engpasseinheit sortieren und der Reihe nach auffüllen“ funktioniert nur bei genau einem Engpass. Sobald zwei Restriktionen gleichzeitig binden können, liefert diese Rangfolge falsche Programme – und genau dafür gibt es die lineare Optimierung. Wenn du in einer Aufgabe begründen sollst, warum hier nicht mit der einfachen Rangfolge gearbeitet wird, ist das die Antwort.

Für das Üben zu Hause noch die Werkzeugseite – zum Kontrollieren, nicht zum Ersetzen der Handrechnung.

Tabellenkalkulation (Solver): Variablen in zwei Zellen, Zielfunktion und jede Restriktion als SUMMENPRODUKT aus Koeffizientenzeile und Variablenzellen. Im Solver dann Zielzelle auf Maximum, veränderbare Zellen und die Nebenbedingungen eintragen, Verfahren „Simplex-LP“. Wichtig: Die Option „ganzzahlig“ nur setzen, wenn die Aufgabe wirklich unteilbare Stücke verlangt – damit wird aus dem LP ein ganzzahliges Problem, und der Sensitivitätsbericht mit den Schattenpreisen ist dann nicht mehr aussagekräftig. Ohne Ganzzahligkeit liefert genau dieser Bericht dir Lisas Dualwerte frei Haus.

Python: scipy.optimize.linprog. Zwei Stolpersteine, an denen praktisch jeder einmal hängen bleibt:

• Die Funktion minimiert grundsätzlich. Für eine Maximierung übergibst du die Zielfunktion mit umgekehrtem Vorzeichen und drehst das Ergebnis am Ende zurück.
• Alle Ungleichungen müssen in der Form „≤“ vorliegen. Eine Mindestmengenbedingung (≥) multiplizierst du dafür mit −1, wodurch sich das Ungleichheitszeichen umdreht.

Der eigentliche Nutzen fürs Lernen: Du rechnest die Aufgabe von Hand, tippst sie ein und vergleichst. Weichen die Ergebnisse ab, liegt der Fehler fast immer beim Aufstellen – vertauschte Koeffizienten oder eine vergessene Restriktion –, nicht beim Rechnen. Das trainiert genau den Schritt, der in der Klausur die Punkte bringt.

Und zur Einordnung: Grafisch geht es nur mit zwei Variablen, weil man drei Dimensionen nicht mehr sinnvoll zeichnen kann. Deshalb bleiben Prüfungsaufgaben bei zwei Produkten – nicht weil die Realität so aussieht, sondern weil man daran die Logik sichtbar machen kann, die der Simplex-Algorithmus später rechnerisch abarbeitet: Er wandert von Ecke zu Ecke, solange sich der Zielwert verbessert 🙂

Später Nachtrag, aber der Punkt fehlt mir hier noch – nämlich die Verbindung zur Engpassplanung aus der Kostenrechnung. Die beantwortet nebenbei die Frage, wann man das Zeichnen überhaupt braucht.

Bei genau einem Engpass brauchst du keine lineare Optimierung. Dann reicht der relative Deckungsbeitrag: Du rechnest für jedes Produkt den Deckungsbeitrag pro Stück und teilst ihn durch den Verbrauch der knappen Ressource pro Stück – also DB je Maschinenstunde statt DB je Stück. Danach sortierst du absteigend und füllst den Engpass von oben auf, bis er voll ist. Klingt simpel, ist aber genau die Aufgabe, an der viele scheitern, weil sie nach dem absoluten Deckungsbeitrag sortieren. Das Produkt mit dem höchsten Stück-DB kann das schlechteste sein, wenn es die knappe Maschine dreimal so lange belegt.

Erst ab zwei knappen Ressourcen versagt diese Sortierung, weil zwei Rangfolgen entstehen, die sich widersprechen können. Genau da beginnt die lineare Optimierung – grafisch bei zwei Produkten, mit dem Simplex-Verfahren darüber hinaus. Wenn in einer Aufgabe also nur eine Restriktion knapp ist, ist der Rechenweg über den relativen Deckungsbeitrag der schnellere und meist auch der erwartete.

Zwei Dinge, die in Klausuren gern als Zusatzfrage kommen:

• Fixkosten gehören nicht in die Zielfunktion. Man maximiert den Deckungsbeitrag, nicht den Gewinn – die Fixkosten sind für die Programmentscheidung irrelevant, weil sie unabhängig von der Menge anfallen. Den Gewinn bildet man erst am Schluss, indem man sie vom optimalen Gesamt-DB abzieht.
• Der Schattenpreis (Dualwert) einer Restriktion sagt dir, um wie viel der Zielwert steigt, wenn du von dieser Ressource eine Einheit mehr hättest. Das ist die betriebswirtschaftlich spannendste Zahl der ganzen Rechnung: Sie ist die Obergrenze dafür, was eine zusätzliche Maschinenstunde – etwa als Überstunde oder Fremdvergabe – kosten darf. Bei einer Restriktion, die im Optimum nicht voll ausgelastet ist, ist der Schattenpreis null.

Und zur Sorge mit dem Millimeterpapier: In der Praxis nimmt man den Solver in Excel oder LibreOffice, gibt Zielzelle, veränderbare Zellen und Nebenbedingungen ein und lässt rechnen. Zum Üben ist das trotzdem gut, weil man die eigene Zeichnung damit gegenprüfen kann – und der Solver liefert die Schattenpreise gleich mit.