ZU DEN KURSEN!

Operations Research 2 - Grafisches Verfahren

Kursangebot | Operations Research 2 | Grafisches Verfahren

Operations Research 2

Grafisches Verfahren

Das im ersten Kapitel Wiederholung OR 1 eingeführte lineare Programm und die dort vorgestellte grafische Lösung des Maximierungsproblems hatte zum Ergebnis eine ganzzahlige Lösung. Dies ist allerdings nicht immer gegeben, denn häufig werden bei linearen Programme nicht ganzzahlige Lösungen ermittelt. In diesem Abschnitt soll die grafische Lösung eines Maximierungsproblems im Hinblick auf die Ganzzahligkeitsbedingung aufgezeigt werden.

Die grafischen Lösung von linearen Optimierungsproblemen kann nur auf Probleme mit $n \le 3$ Variablen angewandt werden. Bereits bei $n = 3$ Variablen ist es allerdings schwierig, das Problem grafisch zu lösen. Im Folgenden wird ein lineares Maximierungsproblem mit $n = 2$ Variablen betrachtet. Die grafische Lösung erfolgt analog zu der im Abschnitt Grafische Lösung des Maximierungsproblems allerdings dürfen hier nur die ganzzahligen Punkte innerhalb des zulässigen Bereichs betrachtet werden.

Zur Veranschaulichung wird das folgenden Maximierungsproblem betrachtet:

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

u.d.N.

(1) $3x_1 + 2x_2 \le 6 $   

(2) $5x_1 + 2 x_2 \le 8$    


$x_1, x_2 \ge 0$    und ganzzahlig


Als Bedingung soll neben der Nichtnegativitätsbedingung $x \ge 0$ zusätzlich die Ganzzahligkeit für die Entscheidungsvariablen $x_1$ und $x_2$ gegeben sein.

Die grafische Lösung ergibt sich dann wie folgt:

Ganzzahlige Optimierung grafische Lösung

In der obigen Grafik sind die beiden Restriktionen eingezeichnet. Die grüne Linien spiegelt die Restrtiktion (1) wieder und die blaue Linie die Restriktion (2). Die gestrichelte Linie ist die Zielfunktion, welche bei der grafischen Lösung solange parallel zu sich selbst verschoben wird, bis diese den Rand des zulässigen Bereiches erreicht. Dort befindet sich bei der linearen Programmierung dann die optimale Lösung, also bei $x = (1, 1,5)$ (roter Punkt). Allerdings stellt dies keine ganzzahlige Lösung dar. Da aber in der obigen Formulierung des Modells eine ganzzahlige Lösung gefordert wird, ist die ermittelte Lösung unzulässig. Es werden nun alle zulässigen Lösungen innerhalb des obigen Bereichs markiert (siehe schwarze Punkte) und dann der Punkt gewählt, welcher die Zielfunktion maximiert. Dies erreicht man durch Parallelverschiebung der Zielfunktion bis zum letztmöglichen Punkt. In diesem Beispiel kommen dafür zwei Punkte in Frage, zum einen der Punkt $(0,3)$ und zum anderen der Punkt $(1,1)$. Für beide wird der Zielfunktionswert:

$f(x_1, x_2) = 3$ 

erzielt. Alle anderen Punkte führen zu einem kleineren Zielfunktionswert. Die optimale Lösung liegt also bei diesen beiden Punkten für das gegebene Problem aufgrund der Ganzzahligkeitsbedingung der Entscheidungsvariablen.