Lineare Optimierung (2D)
LP mit 2 Variablen: zulässiger Bereich, Eckpunktoptimierung
Konvexe Optimierungsgrenzen in begrenzten Räumen 🖖
Lineare Optimierung optimiert eine lineare Zielfunktion unter linearen Nebenbedingungen. Die zulässige Menge bildet ein konvexes Polyeder. Der Hauptsatz der linearen Optimierung besagt, dass die optimale Lösung an einer der Ecken dieses Polyeders liegen muss, was effizient durch den Simplex-Algorithmus gelöst wird.
Die besten Lösungen sitzen in den Ecken 🖖
Vereinfacht gesagt jonglierst du mit begrenzten Ressourcen unter mehreren Regeln gleichzeitig, und jede Ungleichung schneidet einen Teil der Ebene ab. Wo sich alle Regeln überschneiden, liegt der zulässige Bereich, und jeder Punkt darin ist ein gültiger Plan. Weil eine lineare Zielfunktion in eine Richtung immer weiter wächst, landet die beste Lösung in einer Ecke, wo Nebenbedingungen zusammentreffen. Fazit: Zum Optimieren prüfst du nie jeden Punkt, sondern nur die wenigen Ecken.
Wie ein Diätproblem den Simplex vorwegnahm 🖖
1945 untersuchte der Ökonom George Stigler die billigste Ernährung, die alle Nährstoffbedarfe deckt — ein lineares Programm mit 77 Lebensmitteln. Ohne passenden Algorithmus schätzte er geschickt und kam auf rund $39.93 pro Jahr (Preise von 1939). Als Dantzigs Simplex-Verfahren es 1947 exakt löste, betrug das wahre Minimum $39.69 — Stiglers Handschätzung lag nur etwa 24 Cent pro Jahr daneben. Aus trockener Ökonomie wurde so eine der Gründungsfallstudien der linearen Optimierung.
Beispielaufgaben
- Diätproblem - Klassische beschränkte Maximierung: Das Optimum liegt an einer zulässigen Ecke.
- Fabrikausstoß - Sich schneidende Kapazitätsgrenzen erzeugen einen polygonalen zulässigen Bereich.
- Min. Kosten - Bei der Minimierung unter unteren Schranken wird die dem Ursprung nächstgelegene zulässige Ecke in Richtung der Zielfunktion gewählt.
- Unbeschränkt - Der zulässige Bereich kann unbeschränkt sein, sodass die Zielfunktion kein endliches Optimum besitzt.