Grafische Lösung von linearen Optimierungsproblemen

Lineare Optimierungsprobleme lassen sich auch ohne Probleme grafisch lösen, vorausgesetzt man hat nur zwei Entscheidungsvariablen. Lediglich zwei Entscheidungsvariablen deshalb, da wir so das lineare Optimierungsproblem in der Ebene lösen können.

Das nachfolgende Beispiel wurde aus der deutschen Wikipedia übernommen und soll verdeutlichen, wie man das folgende lineare Optimierungsproblem grafisch lösen kann. Konkret geht es um die Fertigung von zwei Produkten (x1 und x2)

Der Gesamtdeckungsbeitrag ist in diesem Beispiel die Zielfunktion, diese soll natürlich maximiert werden. Die Zielfunktion lautet:
f(x) = 300x1 + 500x2

Nun gibt es auch in diesem Beispiel Nebenbedingung in Forme von Machinenkapazitäten. Insgesamt muss man auf drei Maschinen Rücksicht nehmen. Dementsprechend lauten die Nebenbedingungen in diesem Beispiel:
x1+2x2 ≤ 170 (Maschine A, schwarz eingezeichnet)
x1+x2 ≤ 150 (Maschine B, türkis eingezeichnet)
3x2 ≤180 (Maschine C, violett eingezeichnet)
Mit der Nichtnegativitätsbedingung x1, x2 ≥ 0

Um das lineare Optimierungsproblem lösen zu können, müssen die Zielfunktion und die Nebenbedingungen erst einmal eingezeichnet werden. Für das Beispiel ergibt sich folgendes Bild:

Grafische Lösung lineares Optimierungsproblem

Erst einmal ist festzustellen, dass durch die Nichtnegativitätsbedingung man sich immer im ersten Quadranten befindet. Der für das Problem relevante Teil sind alle Punkte im blau umrandeten Polyeder. Darin befindet sich nämlich nun alle zulässigen Punkte. Eingegrenzt werden sie durch die unterschiedlichen Nebenbedingungen. Die rotgestrichelte Linie ist nun die Gewinnfunktion. Nun kann man sich vorstellen, dass es viele, parallel liegende Linien gibt, die ebenfalls die Gewinnfunktion darstellen. Da der Gewinn maximiert werden soll, ist nun aber nur die äußerste rechte parallele Linie interessant, die gerade noch so das Polyeder berührt. Man verschiebt die Linie also nach rechts oben bis zum äußersten Punkt, in diesem Fall der Punkt (130, 20). Würde man das Optimierungsproblem minimieren wollen, würde man die Zielfunktion nach links unten verschieben. Setzt man nun den optimalen Punkt in die Zielfunktion bekommt man den optimale Zielfunktionswert von 49.000 Euro.

Zu beachten ist einmal, dass die Menge aller optimalen Punkte auch leer sein könnte. In diesem Fall ist das Problem unlösbar! Genauso kann es aber auch sein, dass optimale Punkte nicht wie im Beispiel, immer eindeutig sind.