Lineare Optimierung grafisch lösen
Lineare Optimierung grafisch lösen
Das geht nur bei 2 Variablen.
Ein lineares Optimierungsproblem lässt sich grafisch mit 2 Schritten lösen:
- Einzeichnen der Nebenbedingungen als Geraden; dadurch wird eine Fläche "zugeschnitten", die den zulässigen Bereich darstellt;
- eine Isogewinnlinie finden, die den zulässigen Bereich nur noch am Rande in einem Punkt berührt. Der Berührungspunkt ist der optimale Punkt, d.h. die Lösung.
Beispiel
Beispiel: Lineare Optimierung grafisch lösen
Im Beispiel zur linearen Optimierung war die erste Beschränkung:
k + t <= 3 (Die Summe der K-Becher und T-Becher darf höchstens 3 sein, es gab nur 3 Becher).
Auf der waagrechten x-Achse in einem Koordinatensystem sollen die K-Becher, auf der senkrechten y-Achse die T-Becher abgetragen werden.
Beschränkungen einzeichnen
Man könnte aus der Beschränkung eine Geradengleichung konstruieren, am einfachsten ist es aber, sich zu überlegen, was bei 0 Einheiten des einen mit dem anderen passiert. Bei 0 K-Bechern kann es 3 T-Becher geben, das gibt den Punkt (0, 3).
Bei 0 T-Bechern kann es 3 K-Becher geben, das gibt den Punkt (3, 0).
Durch diese beiden Punkte kann man eine Gerade (gestrichelte Gerade, siehe unten) ziehen, das ist die erste Beschränkung ("Grenze").
Die zweite Beschränkung war:
2k + 4t <= 8 (Ein K-Becher hatte 2 Zuckerwürfel, ein T-Becher 4 Zuckerwürfel; es gab in Summe 8 Zuckerwürfel).
Bei 0 K-Bechern kann es 2 T-Becher geben (dann wären 2 × 4 = 8 Zuckerwürfel verbraucht), das gibt den Punkt (0, 2).
Bei 0 T-Bechern kann es 4 K-Becher geben, (dann wären 4 × 2 = 8 Zuckerwürfel verbraucht), das gibt den Punkt (4, 0).
Durch diese beiden Punkte kann man wieder eine Gerade ziehen (gepunktete Gerade, siehe unten), das ist die zweite Beschränkung / Grenze.
Die Lösung des Optimierungsproblems muss dann in dem Bereich liegen, der durch die beiden Geraden / Beschränkungen begrenzt wird (diesen zulässigen Bereich könnte man schraffieren).
Dieser Bereich hat 3 Eckpunkte: (0, 2), (2, 1) und (3, 0). Wenn das lineare Programm ein Optimum hat, muss es eines der Eckpunkte des zulässigen Bereichs sein.
Man könnte jetzt hier die 3 Punkte durchrechnen, bei mehr Punkten ist das aber umständlich.
Besser: Isogewinnlinie zeichnen und verschieben.
Isogewinnlinie einzeichnen
Eine Isogewinnlinie ist eine Gerade, die Kombinationen der Variablen widerspiegelt, die denselben Gewinn haben.
Eine geht z.B. durch die Punkte (0, 2) und (3, 0), der Gewinn ist jeweils 6 €: o K-Becher, aber 2 T-Becher bringen 2 × 3 = 6 € Gewinn; 3 K-Becher, aber 0 T-Becher bringen 3 × 2 = 6 € Gewinn.
Verschiebt man diese Isogewinnlinie (durchgezogene Gerade, siehe unten) parallel nach außen / oben (Richtung höheren Gewinnen), bis sie den zulässigen Bereich nur noch in einem Punkt berührt, hat man die optimale Lösung gefunden; diese liegt hier bei dem Punkt (2, 1), also 2 K-Becher und 1 T-Becher, mit 2 × 2 + 1 × 3 = 7 € Gewinn.
Grafik
