ZU DEN KURSEN!

Operations Research 1 - Grafische Lösung eines Maximierungsproblems

Kursangebot | Operations Research 1 | Grafische Lösung eines Maximierungsproblems

Operations Research 1

Grafische Lösung eines Maximierungsproblems

In diesem Abschnitt soll aufgezeigt werden, wie man ein lineares Optimierungsproblem grafisch löst. Dazu muss die Standardform

Methode

Hier klicken zum Ausklappen

         maximiere $f(x) = c^Tx$

u.d.N.

                      $Ax \le b$

                      $x \ge 0$

gegeben sein. Die grafische Lösung ist für Optimierungsprobleme mit zwei Entscheidungsvariablen geeignet. Es wird das folgende -aus dem vorherigen Abschnitt entnommene - Maximierungsproblem betrachtet:


$f(x_1, x_2) = 30 x_1 + 40 x_2$    $\rightarrow$   max!

u.d.N.

$x_1 + x_2 \le 15 $        Maschinenrestriktion

$x_1 + 2 x_2 \le 27$     Energierestriktion

$x_1 \le 8$                   Absatzrestriktion 1

$x_2 \le 10$                 Absatzrestriktion 2


$x_1, x_2 \ge 0$


Es soll nun für dieses Optimierungsproblem die optimale Kombination aus $x_1$ und $x_2$ zur Maximierung des Deckungsbeitrages unter Berücksichtigung der Restriktionen bestimmt werden. Dabei stellen $x_1$ und $x_2$ die stündlich zu produzierende Menge in Kilogramm dar.

Für die grafische Lösung geht man nun wie folgt vor:

Methode

Hier klicken zum Ausklappen

1. Einzeichnung aller Restriktionen (Nebenbedingungen).

2. Einzeichnung der Zielfunktion.

3. Verschiebung der Zielfunktion (parallel zu sich selbst) bis diese gerade noch innerhalb des zulässigen Bereichs liegt.

1. Einzeichnen der Restriktionen

Die Nebenbedingungen werden nacheinander in ein Koordinatensystem eingezeichnet. Die Maschinenrestriktion (in rot eingezeichnet) hat die Form:

$x_1 + x_2 \le 15 $  

Um $x_1$ einzuzeichnen, wird $x_2 = 0$ gesetzt und dann nach $x_1$ aufgelöst:

$ x_1 = 15$

Um $x_2$ einzuzeichnen wird $x_1 = 0$ gesetzt und dann nach $x_2$ aufgelöst:

$x_2 = 15$

Merke

Hier klicken zum Ausklappen

Werden keine Einheiten von $x_2$ produziert, so können 15 Einheiten von $x_1$ produziert werden und umgekehrt.

Die beiden Punkte $x_1(15; 0)$ und $x_2(0; 15)$ werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Eissroten hinsichtlich der Maschinenrestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einer Eissorte produziert wird, desto weniger Kapazität bleibt für die andere Eissorte übrig.


Die Energierestriktion (in grün) hat die Form:

$x_1 + 2 x_2 \le 27$ 


Umstellen nach $x_1$ und $x_2$ ergibt dann jeweils (wobei die andere Variable null wird):

$x_1 = 27$

$x_2 = \frac{27}{2} = 13,5$

Werden keine Einheiten von $x_2$ produziert, so können 27 Einheiten von $x_1$ produziert werden. Werden keine Einheiten von $x_1$ produziert, so können 13,5 Einheiten von $x_2$ produziert werden.

Die beiden Punkte $x_1(27; 0)$ und $x_2(0; 13,5)$ werden dann in das Koordinatensystem eingezeichnet und miteinander verbunden. Dies liegt daran, dass die beiden Eissroten hinsichtlich der Energierestriktionen voneinander abhängig sind bzw. sich begrenzen. Je mehr von einer Eissorte produziert wird, desto weniger Kapazität bleibt für die andere Eissorte übrig.


Die Absatzrestriktionen (in blau) haben die Form:

$x_1 \le 8$

$x_2 \le 10$

Diese beiden Punkte hingegen werden nicht miteinander verbunden, sondern stellen Geraden dar. Dies liegt daran, dass die Absatzrestriktionen der beiden Torten nicht voneinander abhängig sind und sich gegenseitig nicht begrenzen.

In der nachfolgenden Grafik sind alle Restriktionen eingezeichnet:

Grafische Lösung LP - Restriktionen


Der zulässige Bereich wird durch diese eingezeichneten Restriktionen ermittelt. In diesem Beispiel ist dieser gegeben durch die Maschinenrestriktion (rot) und durch die Absatzrestriktionen (blau). Der zulässige Bereich ist in der nachfolgenden Grafik durch die schwarzen Linien gekennzeichnet:

Grafische Lösung LP - zulässiger Bereich

Die Nichtnegativitätsbedingungen geht dadurch ein, dass der Bereich oberhalb der Abzisse ($x_1$-Achse) und rechts von der Ordinate ($x_2$-Achse) betrachtet wird. Der zulässige Bereich stellt ein Vieleck (=Simplex) dar.

2. Einzeichnung der Zielfunktion

Um nun das optimale Produktionsprogramm zu ermitteln, also die optimale Kombination aus $x_1$ und $x_2$ zur Maximierung des Gesamtdeckungsbeitrages, wird die Zielfunktion benötigt. Diese hat die Form:

$f(x_1, x_2) = 30 x_1 + 40 x_2$ 

Hierbei ist es egal, welchen Höchstwert (rechte Seite) man ansetzt. Es ist wichtig, dass der gewählte Wert so hoch ist, dass sich die Zielfunktion in die Grafik einzeichnen lässt und noch innerhalb des zulässigen Bereiches liegt. Außerdem sollten dabei einigermaßen gerade Werte für $x_1$ und $x_2$ resutieren. Umso genauer wird am Ende das Ergebnis. In diesem Beispiel haben wir den Höchstwert $180$ gewählt:

$30x_1 + 40 x_2 \le 180$

mit

$x_1 = 6$

$x_2 = 4,5$

3. Verschiebung der Zielfunktion

Grafisches Verfahren Maximierungsproblem optimale Lösung
Bestimmung der optimalen Lösung

Diese beiden Punkte zeichnet man nun in die Grafik ein und verbindet sie miteinander (gelbe Linie). Als nächstes nimmt man sich ein Geodreieck in die Hand und verschiebt die Gerade solange (parallel zu sich selbst) nach oben bis zu dem Punkt, welcher sich gerade noch innerhalb des zulässigen Bereiches befindet. In der Grafik ist dies der gelb eingezeichnete Punkt. 

Es werden also von $x_1 = 5 kg/std$ und von $x_2 = 10 kg/std$ produziert. Dies ergibt einen Gesamtdeckungsbeitrag in Höhe von:

$f(5, 10) = 30 \cdot 5 + 40 \cdot 10 = 550 €$

Für die Gesamtproduktionsmenge von 15 kg pro Stunde erhält das Unternehmen einen Deckungsbeitrag von 550 € pro Stunde.

Zusammenfassung

Die Maschinenrestriktion (rot) begrenzt die Produktion der Eissorten. Es können also nicht beide Eissorten bis zu ihrem Absatzmaximum ($x_1 = 8$, $x_2 = 10$) produziert werden. Es stellt sich also die Frage, welche Sorte einen besseren Beitrag für den Deckungsbeitrag leistet. Es ist ersichtlich, dass die Schokoladensorte ($x_2$) bis zu ihrem Absatzmaximum in Höhe von 10 kg/std produziert wird. Die Vanillesorte hingegen ($x_1$) wird nicht bis zu ihrem Absatzmaximum in Höhe von 5 kg/std produziert. Der Grund dafür liegt darin, dass die Schokoladensorte einen höheren Deckungsbeitrag aufweist (40 €) und zur Maximierung des Gesamtdeckungsbeitrages einen höheren Beitrag leistet als die Vanillesorte. Die Energierestiktion ist in diesem Beispiel unerheblich, da die Maschinenrestriktion die Produktion so stark begrenzt, dass die Energiekapazität nicht ausgeschöpft wird.