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, das heißt die Lösung.

Beispiel

Beispiel: Lineare Optimierung grafisch lösen

Wir greifen hier das Beispiel zur linearen Optimierung auf (und kennen von dort schon die Lösung zum Vergleich):

Ein Kiosk verkauft zwei Produkte:

  • den K-Becher: ein Becher mit Zucker (1 Becher, 2 Zuckerwürfel) für Kaffeetrinker und
  • den T-Becher: ein Becher mit mehr Zucker (1 Becher, 4 Zuckerwürfel) für Teetrinker.

Kaffee oder Tee müssen die Kunden selbst mitbringen. Der Gewinn je K-Becher sei 2 € und je T-Becher 3 €. Der Absatz sei unbeschränkt (große Nachfrage).

k sei die verkaufte Menge K-Becher, t die verkaufte Menge T-Becher.

Die (lineare) Zielfunktion ist:

Z(k, t) = k × 2 € + t × 3 €.

und diese soll maximiert werden.

Die Beschränkungen werden als Nebenbedingungen mit Ungleichungen erfasst:

k × 1 + t × 1 <= 3 (es gibt nur 3 Becher)

k × 2 + t × 4 <= 8 (es gibt nur 8 Zuckerwürfel).

Zudem müssen k und t >= 0 sein.

Grafische Lösung

Im obigen Beispiel 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 zum Beispiel 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

Lineare Optimierung grafisch lösen