Graphisches Lösen

Das gegebene Problem ist dergestalt, dass wir es graphisch in der Ebene lösen können. Dazu werden zuerst kalkülmäßig die Zielfunktion und die Nebenbedingungen formuliert. Die Nebenbedingungen sind Ungleichungen. Die graphische Veranschaulichung der Nebenbedingungen ergibt Schnitte von Halbebenen, deren Ergebnis im vorliegenden Fall ein begrenztes Gebiet ist, der sogenannte zulässige Bereich (Abbildung 2). Der zulässige Bereich enthält alle Punkte der Ebene, deren Koordinaten die Nebenbedingungen erfüllen. Als Repräsentation der Zielfunktion wird eine Optimierungsgerade eingeführt. Diese wird so lange parallel in Optimierungsrichtung verschoben (der Absolutwert der verschobenen Gerade muss kleiner werden, weil die Zielfunktion minimiert werden soll), bis die Optimierungsgerade eben noch den zulässigen Bereich tangiert. Dieser "letzte" Berührungspunkt der Optimierungsgerade mit dem zulässigen Bereich ist der optimale Punkt, seine Koordinaten sind die gesuchten Werte $x$ und $y$.

Lineare Funktionen besitzen die Eigenschaft der Konvexität. Daher können wir den Sachverhalt nutzen, dass der "letzte" gemeinsame Punkt der Optimierungsgerade mit dem zulässigen Bereich ein Eckpunkt ist. Es reicht demzufolge aus, die Gerade in alle Eckpunkte parallel zu verschieben und dabei den Absolutwert der Gerade, die Ordinate des Schnittpunktes mit der Ordinatenachse, zu betrachten (Abbildung 2).

Es bezeichne $x$ die Anzahl der einzukaufenden Platten des Typs $\mathrm{I}$,
es bezeichne $y$ die Anzahl der einzukaufenden Platten des Typs $\mathrm{II}$.

Modellieren wir die im Aufgabentext angegebenen Aussagen in Formeln, entsteht das folgende Optimierungsproblem. Die zugehörige Zielfunktion lautet:

$G=300\cdot x+200\cdot y=\text{Min!}$

(1)

Als Nebenbedingungen ergeben sich die Ungleichungen (die Bezeichnung entspricht den Bedingungen, die an die einzelnen Plattentypen gestellt werden):

(A) $2x$ $+$ $y$ $$ $\ge$ $10$ (B) $x$ $+$ $2y$ $\ge$ $12$ (C) $x$ $+$ $y$ $\ge$ $8$ (D) $2y$ $\ge$ $4$ (D') $2y$ $\le$ $16$ (E) $x$ $\le$ $5$ (N) $x$, $y$ $\ge$ $0$    ($x$, $y$ ganzzahlig)

(2)

Zur besseren graphischen Darstellbarkeit wird (1) und (2) umgeformt, es entsteht als Zielfunktion:

$$y=-\frac{3}{2}x+G^{\mathrm{*}}$$

,  wobei gilt

$$G^{\mathrm{*}}=\frac{G}{200}=\mathrm{Min!}$$

(3)

Als Nebenbedingungen entstehen die folgenden Ungleichungen für ganze $x$ und $y$:

(A) $y$ $$ $\ge$ $-2x$ $+$ $10$ (B) $y$ $$ $\ge$ $$-\frac{1}{2}x$$ $+$ $6$ (C) $y$ $\ge$ $-x$ $+$ $8$ (D) $y$ $$ $\ge$ $2$ (D') $y$ $$ $\le$ $8$ (E) $0$ $\le$ $-x$ $+$ $5$ (N) $x$, $y$ $\ge$ $0$ .

(4)

Durch den Eintrag in ein Koordinatensystem in der Ebene gelangen wir nun zum zulässigen Bereich durch den Schnitt der Halbebenen, die in (4) definiert sind (Abbildung 2).

Als Eckpunkte des zulässigen Bereiches ergeben sich die Koordinatentupel $P_1\left(5|8\right)$, $P_2\left(5|\mathrm{3,5}\right)$, $P_3\left(1|8\right)$, $P_4\left(2|6\right)$ und $P_5\left(4|4\right)$. Da an eine Lösung des Optimierungsproblems die Forderung der Ganzzahligkeit gestellt wird, werden die Eckpunkte mit nichtganzzahligen Koordinaten (im Beispiel $P_2$) nicht weiter berücksichtigt.

Zeichnen wir im Koordinatensystem eine Schar von Parallelen, die verschiedenen $G^{*}$ entsprechen, so dass jeweils die (ganzzahligen!) Eckpunkte des zulässigen Bereichs auf den Geraden liegen (Abbildung 3), ergeben sich die Absolutwerte der Geraden mit ${G_1}^{*}=\mathrm{15,5}$; ${G_3}^{*}=\mathrm{9,5}$; ${G_4}^{*}=9$ und ${G_5}^{*}=10$;

Betrachten wir aufgrund der Minimierung von $G^{*}$ die Optimierungsrichtung in Richtung der negativen $y$-Achse, erkennen wir, dass $G^{*}$ den Minimalwert annimmt und gerade noch den zulässigen Bereich in dem Eckpunkt $\left(x|y\right)=\left(2|6\right)$ tangiert, wenn $G^{*}={G_4}^{*}=9$ gilt.

Also besitzt das lineare Optimierungsproblem folgende Lösung: Es sind genau 2 Platten des Typs $\mathrm{I}$ und 6 Platten des Typs $\mathrm{II}$ einzukaufen, der Einkaufswert beträgt $G=1800\text{ Euro}$.

Graphische Lösungen bieten sich bei zweidimensionalen Problemen aber auch an, wenn nur die Nebenbedingungen linear sind und die Zielfunktion beispielsweise quadratisch auftritt. Nicht unerwähnt bleiben soll das graphische Lösen dreidimensionaler linearer Optimierungsprobleme. Einfache räumliche Aufgaben unterstreichen die Komplexität der mathematischen Optimierung, schulen das Vorstellungsvermögen und sind in komplizierterer Form ein hervorragender Einstieg in vieldimensionale Problematiken, hinarbeitend auf die Simplexmethode.