Eckpunktberechnungsmethode
Definition
Die Eckpunktberechnungsmethode basiert auf der mathematischen Erkenntnis, dass die optimale Lösung eines linearen Optimierungsproblems immer in einem Eckpunkt des zulässigen Bereichs (Planungspolyeder) liegt.
Dieses Verfahren ist besonders effizient bei zwei oder drei Entscheidungsvariablen, wenn die grafische Genauigkeit nicht ausreicht.
Vorgehensweise
Die Ermittlung der optimalen Lösung erfolgt in vier Schritten:
- Bestimmung des zulässigen Bereichs: Aufstellen der Nebenbedingungen und der Nichtnegativitätsbedingungen.
- Identifikation der Eckpunkte: Die Eckpunkte entstehen durch die Schnittpunkte der begrenzenden Geraden.
- Berechnung der Koordinaten: Die Koordinaten der Eckpunkte werden durch das Lösen von linearen Gleichungssystemen ermittelt (z. B. mit dem Gaußsches Eliminationsverfahren).
- Prüfung der Zielfunktion: Alle berechneten Eckpunkte werden in die Zielfunktion eingesetzt. Der Punkt mit dem höchsten Wert (Maximierung) bzw. niedrigsten Wert (Minimierung) ist die optimale Lösung.
Beispiel
Betrachtet man das Beispiel der Modellwerk Ruhr GmbH, ergeben sich folgende Begrenzungslinien:
- \(L_1: 2x_1 + x_2 = 100\)
- \(L_2: x_1 + 2x_2 = 80\)
Der relevante Eckpunkt \(C\) im Inneren entsteht durch den Schnittpunkt von \(L_1\) und \(L_2\): \[ \begin{vmatrix} (I) & 2x_1 + x_2 = 100 \\ (II) & x_1 + 2x_2 = 80 \end{vmatrix} \] Lösung mittels Gaußsches Eliminationsverfahren: \(x_1 = 40, x_2 = 20\).
Vergleich der Eckpunkte:
- \(A(0|0) \Rightarrow z = 0\)
- \(B(50|0) \Rightarrow z = 2000\)
- \(C(40|20) \Rightarrow z = 2600\) (Optimum)
- \(D(0|40) \Rightarrow z = 2000\)
Zusammenhang mit anderen Themen
Die Eckpunktberechnung ist eng verknüpft mit dem Thema Matrizenrechnung, da Bedingungssysteme auch in Matrixform geschrieben werden können. Im Vergleich zum Simplexalgorithmus ist sie anschaulicher, bei vielen Variablen jedoch deutlich aufwendiger.