Lineare Optimierung graphisch lösen – wie finde ich den optimalen Punkt im Polygon?

TimDual

Ich sitze gerade an einer Übungsaufgabe zur linearen Optimierung (Maximierungsproblem, zwei Variablen, drei Nebenbedingungen plus Nichtnegativitätsbedingungen). Den zulässigen Bereich habe ich gezeichnet, das Polygon mit den Eckpunkten sehe ich auch, aber ich bin mir unsicher, wie ich von da aus auf den optimalen Punkt komme.

Was ich bisher verstanden habe:

Das Optimum liegt bei linearer Optimierung immer in einem Eckpunkt (oder auf einer ganzen Kante, wenn die Zielfunktion parallel zu einer Nebenbedingung verläuft).
Ich könnte also einfach alle Eckpunkte ablesen und in die Zielfunktion einsetzen.

Mir kommt das aber bei mehr als 4-5 Ecken ziemlich mühsam vor. In der Vorlesung wurde kurz was von einer „Isogewinngeraden“ erwähnt, die man parallel verschiebt, aber ich habe nicht ganz kapiert, wie man das sauber zeichnerisch umsetzt bzw. woran man erkennt, wann man den letzten Punkt vor dem Verlassen des zulässigen Bereichs erreicht hat. Geht ihr da anders ran, oder bleibt bei zwei Variablen wirklich nur das Einsetzen aller Eckpunkte als zuverlässige Methode?

Mathe_Marco

Hi TimDual, beide Methoden führen zum Ziel, aber die Isogewinngerade ist bei größeren Polygonen wirklich der elegantere Weg, wenn man den Dreh erstmal raus hat. 😄

So gehe ich vor:

Zielfunktion z = c1*x1 + c2*x2 nach x2 auflösen, also x2 = -(c1/c2)*x1 + z/c2. Das ist eine Gerade mit fester Steigung -(c1/c2), nur der Achsenabschnitt z/c2 hängt vom Zielfunktionswert ab.
Du zeichnest diese Gerade für irgendeinen beliebigen Wert von z (z.B. z=0 oder einen schönen runden Wert, der durchs Polygon läuft) als Hilfslinie ein.
Jetzt verschiebst du diese Gerade parallel (Steigung bleibt immer gleich!) in Richtung wachsendem z – bei Maximierung und positivem c2 heißt das meistens „nach oben rechts“, das kannst du dir aber auch über den Gradienten-Vektor (c1, c2) klarmachen, der zeigt immer in Richtung wachsender Zielfunktion.
Du schiebst so lange, bis die Gerade den zulässigen Bereich gerade noch berührt. Der letzte Berührpunkt ist dein Optimum. Wichtig: Sobald du weiterschieben würdest, verlässt die Gerade komplett das Polygon – das erkennst du daran, dass keine Schnittpunkte mit dem zulässigen Bereich mehr existieren.

Der Vorteil: Du musst nicht rechnen, nur die Richtung sauber einschätzen. Typischer Fehler dabei ist, die Steigung beim Verschieben zu verändern – das darf nicht passieren, sonst verschiebst du keine Isogewinngerade mehr sondern irgendeine andere Gerade. Merksatz: „Steigung fix, nur der Achsenabschnitt wandert.“ Bei mehreren möglichen Berührpunkten (Kante statt Ecke) hast du dann unendlich viele Optimallösungen – auch das erkennst du sofort zeichnerisch, wenn die Isogewinngerade genau auf einer Kante des Polygons liegt.

RobertM

Marco hat das mit der Isogewinngeraden schon super erklärt, das ist auch bei uns im WI-Studium genau so dran gekommen. Ich ergänze mal den Schritt davor, weil ich da anfangs selbst gestolpert bin: das saubere Zeichnen des zulässigen Bereichs.

Was mir geholfen hat:

Jede Nebenbedingung erst als Gleichung behandeln (also „=“ statt „≤“ oder „≥“) und als Gerade einzeichnen. Dafür einfach x1=0 setzen (ergibt x2-Achsenabschnitt) und x2=0 setzen (ergibt x1-Achsenabschnitt), dann die beiden Punkte verbinden.
Danach für jede Gerade mit dem Nullpunkt (0,0) testen, ob er die Ungleichung erfüllt – wenn ja, zeigt die zulässige Halbebene in Richtung Ursprung, wenn nein, in die andere Richtung. Das ist der Punkt, an dem ich am Anfang am häufigsten Fehler gemacht habe, gerade wenn eine Nebenbedingung nicht durch den Ursprung läuft oder der Ursprung selbst nicht zulässig ist (z.B. bei Mindestproduktionsmengen).
Den zulässigen Bereich dann als Schnittmenge aller Halbebenen plus Nichtnegativität (erstes Quadranten) markieren, am besten mit Schraffur oder Farbe, sonst verliert man bei drei-vier Nebenbedingungen schnell den Überblick, welche Fläche jetzt eigentlich gemeint ist.

Typischer Fehler, den ich auch in Klausuren bei Kommilitonen gesehen habe: Die Richtung der Ungleichung wird vertauscht, weil man nicht mit einem Testpunkt prüft, sondern „nach Gefühl“ schraffiert. Lieber einmal mehr den Nullpunkt-Test machen, das kostet zwei Sekunden und erspart ein völlig falsches Polygon.

Lineare Optimierung graphisch lösen – wie finde ich den optimalen Punkt im Polygon?

Jetzt mitmachen!

Letzte Beiträge

Konfidenzintervall berechnen – wie wähle ich den richtigen z- oder t-Wert? 1

Determinante einer 3x3-Matrix – welche Regel ist am schnellsten? 3

Lineare Optimierung graphisch lösen – wie finde ich den optimalen Punkt im Polygon? 2

Bayes-Theorem in der Klausur – wie erkenne ich, wann ich es anwenden muss? 2

Multikollinearität in der Regression – woran erkenne ich sie, und was mache ich dagegen? 12

Grundlagen der Wahrscheinlichkeitsrechnung im Studium 3

Skalarprodukt vs. Kreuzprodukt – wann brauche ich welches eigentlich? 3

Exponentielles Wachstum berechnen – wie bestimme ich die Verdopplungszeit? 2

Simplex-Methode bei mehr als zwei Variablen – wie fange ich systematisch an? 3

Bestimmtheitsmaß R² bei linearer Regression – wie interpretiere ich den Wert richtig? 3

Konfidenzintervall berechnen – wie wähle ich den richtigen z- oder t-Wert?

Determinante einer 3x3-Matrix – welche Regel ist am schnellsten?

Lineare Optimierung graphisch lösen – wie finde ich den optimalen Punkt im Polygon?

Bayes-Theorem in der Klausur – wie erkenne ich, wann ich es anwenden muss?

Multikollinearität in der Regression – woran erkenne ich sie, und was mache ich dagegen?

Über Study-Board.de