Interaktive Mathe- und Wissenschafts-Lektionen

Lineare Optimierung (2D)

LP mit 2 Variablen: zulässiger Bereich, Eckpunktoptimierung

Interaktive Simulation wird geladen...

Ein zulässiger Bereich ist keine Garantie für eine Lösung 🖖

Die Eckenregel hat eine leicht übersehene Voraussetzung: Ein Optimum muss überhaupt existieren. Lade die Voreinstellung „unbeschränkt“ – maximiere 2x + y unter x ≥ 0, y ≥ 0, x + y ≥ 2 – und der zulässige Bereich ist völlig nichtleer, doch keine Ecke ist die beste, denn du kannst ewig nach Nordosten laufen und dich weiter verbessern. Dieses Werkzeug liefert daher nicht ein, sondern eines von drei Urteilen: optimal, unzulässig oder unbeschränkt. Das dritte erkennt es, indem es auf eine verbessernde Rezessionsrichtung prüft, nicht daran, dass es keine Ecke findet. Stelle dieselbe Voreinstellung auf Minimieren, und sofort erscheint eine endliche Lösung bei (0, 2). Zulässigkeit und Lösbarkeit sind zwei verschiedene Fragen.

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.

LINEARE OPTIMIERUNG — WARUM MAN IMMER NUR DIE ECKEN PRÜFT

In welchem Fall der linearen Optimierung bist du?

Jedes lineare Programm stellt dieselbe Frage: Wie weit lässt sich eine geradlinige Zielfunktion über ein Gebiet schieben, das von geradlinigen Nebenbedingungen eingezäunt wird? Weil beides gerade ist, kann der beste Punkt nur eine Ecke sein — deshalb besteht das Verfahren darin, die Ecken aufzulisten und zu vergleichen. Welcher Fall vorliegt, hängt davon ab, ob das Gebiet die Zielfunktion überhaupt einsperrt und ob die gelieferte Ecke eine brauchbare Zahl ist.

Beschränktes Gebiet — das Optimum liegt auf einer Ecke z = 10 → (2, 2)
Die beste Ecke ist gebrochen — und das ist ein anderes Problem z = 24 → (8/3, 8/3)
Unbeschränktes Gebiet mit beschränkter Antwort min z = 13
Kein endliches Optimum — und die Ecken verraten es nicht z → ∞

01

Beschränktes Gebiet — das Optimum liegt auf einer Ecke

Was du weißt: Eine zu maximierende Zielfunktion und genug ≤-Bedingungen, um das Gebiet zu schließen. Die zulässige Menge ist ein Vieleck.

Was zu prüfen ist: z = 10 → (2, 2)

Rechenbeispiel: Maximiere 3x + 2y unter x + y ≤ 4, x ≤ 2, y ≤ 3. Die Ecken sind (0,0), (2,0), (2,2), (1,3), (0,3), und z = 10 in (2,2) schlägt sie alle.

Diesen Fall öffnen: Diätproblem
Beschränktes Gebiet — das Optimum liegt auf einer Ecke. Die Ziellinie wandert nach rechts oben, bis sie das Vieleck nur noch in einer einzigen Ecke berührt. Eine zu maximierende Zielfunktion und genug ≤-Bedingungen, um das Gebiet zu schließen. Die zulässige Menge ist ein Vieleck.
Die Ziellinie wandert nach rechts oben, bis sie das Vieleck nur noch in einer einzigen Ecke berührt.

02

Die beste Ecke ist gebrochen — und das ist ein anderes Problem

Was du weißt: Wieder ein beschränktes Gebiet, aber die von der Zielfunktion gewählte Ecke liegt nicht auf ganzen Zahlen.

Was zu prüfen ist: z = 24 → (8/3, 8/3)

Rechenbeispiel: Maximiere 5x + 4y unter 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. Das Optimum ist z = 24 in (8/3, 8/3), also etwa (2,67, 2,67).

Diesen Fall öffnen: Fabrikausstoß
Die beste Ecke ist gebrochen — und das ist ein anderes Problem. Die beiden bindenden Bedingungen kreuzen sich abseits der Gitterlinien, also hat die beste Ecke gebrochene Koordinaten. Wieder ein beschränktes Gebiet, aber die von der Zielfunktion gewählte Ecke liegt nicht auf ganzen Zahlen.
Die beiden bindenden Bedingungen kreuzen sich abseits der Gitterlinien, also hat die beste Ecke gebrochene Koordinaten.

03

Unbeschränktes Gebiet mit beschränkter Antwort

Was du weißt: Minimierung unter ≥-Bedingungen. Das zulässige Gebiet läuft ins Unendliche, die Zielfunktion hat trotzdem einen Boden.

Was zu prüfen ist: min z = 13

Rechenbeispiel: Minimiere 2x + 3y unter x + y ≥ 6, x ≥ 2, y ≥ 1. Das Gebiet ist unendlich, das Minimum liegt dennoch bei z = 13 in (5,1).

Diesen Fall öffnen: Min. Kosten
Unbeschränktes Gebiet mit beschränkter Antwort. Das Gebiet erstreckt sich unbegrenzt vom Ursprung weg, das Minimum liegt aber auf einer Ecke in dessen Nähe. Minimierung unter ≥-Bedingungen. Das zulässige Gebiet läuft ins Unendliche, die Zielfunktion hat trotzdem einen Boden.
Das Gebiet erstreckt sich unbegrenzt vom Ursprung weg, das Minimum liegt aber auf einer Ecke in dessen Nähe.

04

Kein endliches Optimum — und die Ecken verraten es nicht

Was du weißt: Die Zielfunktion verbessert sich in einer Richtung, die keine Bedingung blockiert. Es gibt keinen besten Punkt.

Was zu prüfen ist: z → ∞

Rechenbeispiel: Maximiere 2x + y unter x + y ≥ 2, x ≥ 0, y ≥ 0. Läuft man entlang wachsendem x immer weiter, wächst die Zielfunktion immer weiter; das Ergebnis ist unbeschränkt.

Diesen Fall öffnen: Unbeschränkt
Kein endliches Optimum — und die Ecken verraten es nicht. Das schattierte Gebiet ist nach rechts oben offen, und die Zielfunktion verbessert sich dort endlos weiter. Die Zielfunktion verbessert sich in einer Richtung, die keine Bedingung blockiert. Es gibt keinen besten Punkt.
Das schattierte Gebiet ist nach rechts oben offen, und die Zielfunktion verbessert sich dort endlos weiter.
Quellen (3)
  • The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
  • Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
  • Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Aufgabe vollständig gelöst

  1. Das Diät-Problem zur Maximierung von Z = 3x + 2y 5 Schritte

    Welche Ecke gewinnt, und wie viel ist die benachbarte Ecke wert? Das ist das Diätproblem: Maximieren Sie Z = 3x + 2y unter den Nebenbedingungen x + y ≤ 4, x ≤ 2 und y ≤ 3, wobei x und y beide mindestens 0 sind.

    1. Nehmen Sie zwei beliebige zulässige Punkte und betrachten Sie die gerade Strecke zwischen ihnen. Eine lineare Zielfunktion entlang dieser Strecke ist ein gewichtetes Mittel ihrer beiden Endwerte, und ein gewichtetes Mittel ist nie größer als der größere der beiden Endwerte. Kein Punkt, der strikt zwischen zwei anderen liegt, kann also das eindeutige Optimum sein; wendet man dies nacheinander in jede Richtung an, bleibt das Optimum an einer Ecke hängen.

    2. Eine Ecke ist der Schnittpunkt zweier Begrenzungslinien, sodass sich die Kandidaten aus der paarweisen Kombination der fünf Linien ergeben. Zehn Paare, davon zwei parallel, und nur fünf der verbleibenden acht erfüllen die Nebenbedingungen, aus denen sie nicht gebildet wurden — x + y = 4 schneidet x = 0 bei (0, 4), was y ≤ 3 verletzt.

    3. Fünf arithmetische Auswertungen und ein Vergleich, und die Suche ist abgeschlossen. Es bleibt kein Inneres mehr zu testen und keine Kante mehr abzulaufen.

    4. An der gewinnenden Ecke sind x + y = 4 und x = 2 beide bindend, während y = 2 eine ganze Einheit unter ihrer Obergrenze von 3 liegt. Eine Nebenbedingung mit Spielraum schränkt nichts ein, sodass ihre Lockerung nichts ändert; bei den anderen beiden lohnt es sich, mit jeweils einer Einheit mehr neu zu lösen.

    5. Gewichten Sie jeden dieser drei Preise mit der Menge der jeweiligen Ressource, die im Problem vorgegeben war.

    Antwort

    Das Werkzeug gibt x* = 2, y* = 2 und Z* = 10 aus, den dritten der fünf Eckenwerte. Die Zahlen aus Schritt 4 — 2, 1 und 0 — sind die Schattenpreise, und sie beantworten eine Frage, die das Diagramm nicht beantworten kann: Eine weitere Einheit des x + y-Budgets ist doppelt so viel wert wie eine weitere Einheit von x, und eine weitere Einheit von y ist überhaupt nichts wert. Schritt 5 ist die starke Dualität, und sie ist kein Zufall dieser Zahlen; die mit den Kapazitäten gewichteten Preise ergeben stets wieder das Optimum, was sie überhaupt erst zu Preisen macht. Ein Schattenpreis hat jedoch auch ein Ablaufdatum. Das x + y-Budget bringt 2 pro Einheit nur bis 5, wo die Ecke (2, 3) erreicht, die anderen beiden Nebenbedingungen bindend werden und Z bei 12 verharrt — darüber hinaus liegt der Preis bei 0 und jede zusätzlich gekaufte Einheit ist verschwendet.

· Aktualisiert

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Statistik & Finanzen →

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.