Grafisches Verfahren

Das im ersten Kapitel Wiederholung OR 1 eingeführte lineare Programm und die dort vorgestellte grafische Lösung des Maximierungsproblems hatte eine ganzzahlige Lösung zum Ergebnis. 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:

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 (=ganzzahligen) 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.