ZU DEN KURSEN!

Operations Research - Beispiel: Maximierungsproblem / grafische Lösung

Kursangebot | Operations Research | Beispiel: Maximierungsproblem / grafische Lösung

Operations Research

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 $x_1$ und $x_2$ mit einem Gewinn von $g_1 = 250 €$ und $g_2 = 450 €$. Zur Produktion der beiden Produkte stehen zwei Maschinen zur Verfügung: $A$ und $B$. Einige Montagearbeiter $M$ 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:

  Artikel Kapazität pro Tag
  1 2
Maschine A 4 3 24 h
Maschine B 2 4 24 h
Montagearbeiter M 4 5 32 h
Gewinn pro Stück       250    450       

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:

$f(x_1, x_2) = z = 250x_1 + 450 x_2$    $ \rightarrow$   max!

u.d.N.

$4x_1 + 3x_2                      \le 24$

$2x_1 + 4x_2                      \le 24$

$4x_1 + 5x_2                      \le 32$

$x_1, x_2  \ge 0$

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 

$4x_1 + 3x_2                      \le 24$

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

$x_1 = \frac{24}{4} = 6$

$x_2 = \frac{24}{3} = 8$.

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

Die beiden Punkte $P_1(6; 0)$ und $P_2(0; 8)$ 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:

Beispiel Maximierungsproblem grafische Lösung

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.

Beispiel Maximierungsproblem grafische Lösung zulässiger Bereich

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.

$z = 250x_1 + 450 x_2 $

Sinnvoll ist es einen Wert zu wählen, so dass die Division mit den beiden Werten $250$ und $450$ 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:

$z = 250 x_1 + 450 x_2  = 900$

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

$x_1 = 3,6$

$x_2 = 2$.

Beispiel Maximierungsproblem grafische Lösung

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.

Beispiel Maximierungsproblem grafische Lösung

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:

$x_1 = 1,3$ und 

$x_2 = 5,3$.

Das bedeutet also, dass von $x_1 = 1$ Menge produziert und von $x_2 = 5$ 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:

$z = 250 \cdot 1 + 450 \cdot 5  = 2.500 €$.