Beispiel: Maximierungsproblem / grafische Lösung

In diesem Abschnitt soll ein gegebenes Maximierungsproblem zunächst grafisch gelöst werden. Im folgenden Abschnitt wird dasselbe Problem dann mittels Simplexverfahren gelöst.

Beispiel: Produktionsprogrammplanung

Ein Unternehmen produziert zwei Produkte und mit einem Gewinn von und . Zur Produktion der beiden Produkte stehen zwei Maschinen zur Verfügung: und . Einige Montagearbeiter sind dafür zuständig die Teile am Ende so zusammenzusetzen, dass die beiden Produkte entstehen. In der folgenden Tabelle sind die dazugeghörigen Daten aufgelistet:

Im mittleren Bereich der Tabelle stehen die Stundenzahlen, die für die Produktion eines Produktes benötigt werden. So werden zum Beispiel zur Produktion von Produkt 1 4 Stunden auf Maschine A, 2 Stunden auf Maschine B und 4 Stunden zur Montage benötigt.

Ziel des Unternehmens ist es, seinen Gewinn zu maximieren. Es handelt sich in diesem Fall also um ein Maximierungsproblem mit der Form:

      max!

u.d.N.

Die Nichtnegativitätsbedingung muss hier eingeführt werden, da keine negativen Produkte hergestellt werden können. Das Maximierungsproblem wird zunächst grafisch gelöst.

grafische Lösung

Um die Restriktionen einzeichnen zu können, müssen die Schnittpunkte der einzelnen Gleichungen mit den Koordinatenachsen bestimmt werden. Die Koordinatenachsen spiegeln die zwei Produkte wieder. Für die Gleichung 

ergibt sich der Schnittpunkt mit der -Achse durch Nullsetzen von und der Schnittpunkt mit der -Achse durch Nullsetzen von :

.

Werden keine Einheiten von produziert, so können 6 Einheiten von produziert werden. Werden keine Einheiten von produziert, so können 8 Einheiten von produziert werden.

Die beiden Punkte und werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Produkte hinsichtlich der Maschinenrestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einem Produkt produziert wird, desto weniger Kapazität bleibt für das andere Produkt übrig.

Entsprechend wird auch mit den anderen beiden Restriktionen verfahren:

In der obigen Grafik ist das Koordinatensystem mit den eingezeichneten Restriktionen zu sehen. Dabei nennt man den Bereich, der von den Restriktionen eingeschlossen wird zulässigen Bereich. Alle Lösungen innerhalb dieses Bereichs sind zulässig. Es soll aber die optimale Lösung unter den zulässigen Lösungen gefunden werden.

In dem nächsten Schritt wird nun die Zielfunktion benötigt. Für diese wird auf der rechten Seite ein fiktiver Gesamtgewinn angesetzt, so dass die Neigung der Gewinnfunktion in die Grafik eingezeichnet werden kann.

Sinnvoll ist es einen Wert zu wählen, so dass die Division mit den beiden Werten und ganze Zahlen bzw. Zahlen mit nur einer Nachkommastelle ergeben (umso genauer kann die Zielfunktionsgerade eingezeichnet werden). Außerdem sollte die Zielfunktionsgerade noch im zulässigen Bereich liegen. Wir wählen hier also nun einen bliebigen Gesamtgewinn aus:

Der Schnittpunkt mit der -Achse ergibt sich durch Nullsetzen von und der Schnittpunkt mit der -Achse durch Nullsetzen von :

.

Die gestrichelte Linie stellt die Zielfunktionsgerade dar. Diese muss nun solange parallel zu sich selbst verschoben werden (Geodreieck verwenden), bis diese gerade noch den zulässigen Bereich berührt. Der letzte Berührungspunkt der Zielfunktionsgeraden mit dem zulässigen Bereich stellt die optimale Lösung dar.

In der obigen Grafik wurde die Zielfunktionsgerade nun solange verschoben (parallel zu sich selbst), bis sie gerade noch im zulässigen Bereich liegt. Der Punkt (grau) ist dabei der Punkt, der gerade noch im zulässigen Bereich liegt und damit die optimale Lösung:

und 

.

Das bedeutet also, dass von Menge produziert und von Mengen produziert werden, damit der Gewinn für das Unternehmen am Größten ausfällt unter Berücksichtigung der gegebenen Kapazitäten. Da nur ganze Produkte hergestellt werden können, muss in jedem Fall immer abgerundet werden.

Der Gewinn des Unternehmens beträgt dann:

.