Eckpunkt
Voraussetzung: Normalform (kanonische Form)
Bei zwei Entscheidungsvariablen lässt sich ein Optimierungsproblem zeichnen. Du siehst den erlaubten Bereich und findest das Optimum mit dem Auge. Das ist die einfachste Lösungsmethode und zeigt, warum der Simplex-Algorithmus später von Ecke zu Ecke läuft. Voraussetzung sind die Zielfunktion und die kanonische Form, außerdem Geradengleichungen und Gleichungssysteme mit zwei Unbekannten.
Das graphische Verfahren hat vier Schritte:
- Ein Koordinatensystem mit den Achsen \(x_1\) und \(x_2\) zeichnen. Wegen \(x_1,x_2\ge 0\) zählt nur der erste Quadrant.
- Für jede Nebenbedingung die Grenzgerade zeichnen. Dazu wird aus \(\le\) ein \(=\). Zwei Punkte genügen, zum Beispiel die Schnittpunkte mit den Achsen. Der erlaubte Bereich liegt auf der Seite, auf der der Ursprung liegt, solange \(b\ge 0\) ist.
- Eine Höhenlinie \(Z=c\) der Zielfunktion zeichnen.
- Die Höhenlinie parallel verschieben, so weit der erlaubte Bereich reicht. Die letzte Ecke, die sie berührt, ist das Optimum.
Die Achsenabschnitte einer Grenzgeraden \(ax_1+bx_2=d\) bekommst du durch Einsetzen: Auf der \(x_1\)-Achse ist \(x_2=0\), also \(x_1=\tfrac{d}{a}\). Auf der \(x_2\)-Achse ist \(x_1=0\), also \(x_2=\tfrac{d}{b}\). Die Ecken im Inneren sind Schnittpunkte zweier Grenzgeraden. Du bekommst sie, indem du beide Gleichungen zugleich löst.
Eine lineare Zielfunktion hat ihr Maximum immer in einer Ecke des Bereichs. Ist \(c\) positiv, wächst \(Z\), wenn du die Höhenlinie vom Ursprung wegschiebst. Du schiebst so weit, bis die Linie den Bereich nur noch in einem Punkt berührt.
Wenn die Höhenlinie parallel zu einer Kante liegt
Für \(Z=2x_1+2x_2\) unter \(x_1+x_2\le 6\) und \(x_1\le 4\) liegt die Höhenlinie parallel zur Grenzgeraden \(x_1+x_2=6\). Beim Verschieben berührt sie am Ende die ganze Kante zwischen den Ecken \((0,6)\) und \((4,2)\). In beiden Ecken und an jedem Punkt dazwischen ist \(Z=12\). Es gibt also unendlich viele optimale Punkte.
Ein zweites Beispiel, ein Bereich ohne obere Grenze
Gilt nur \(x_1-x_2\le 2\) und \(x_1,x_2\ge 0\), reicht der Bereich nach oben ohne Ende. Für \(Z=x_1+x_2\) lässt sich die Höhenlinie beliebig weit schieben, \(Z\) wächst über jede Grenze. Es gibt kein Maximum, das Problem ist unbeschränkt. Solche Fälle erkennst du im Simplex-Tableau daran, dass in der Pivotspalte kein positiver Eintrag steht.