Simplex-Methode

Die von dem Amerikaner George B. Dantzig 1946 vorgestellte Simplex-Methode (S.-M.) gehört zu den wichtigsten Lösungsverfahren der linearen Programmierung (LP). Sie stellt die Gleichungen in der Matrix (Simplex-Tableau) zusammen und wandelt diese nach bestimmten Regeln so lange in neue Matrizen (Tableaus) um, bis die optimale Lösung gefunden ist. Die Simplex-Methode als numerisch-iteratives Rechenverfahren (Iteration) eignet sich besonders gut für EDV-Lösungen. Standardprogramme für diese Methode liegen heute in allen bekannten Programmiersprachen vor.

Rechenregeln der S.-M.:
Die Regeln dieser Methode lassen sich für den Fall der Gewinnmaximierung in acht Punkte fassen:

(1) Formulierung des mathematischen Ansatzes mit Zielfunktion, Nebenbedingungen und Nichtnegativitätsbedingungen.

(2) Umformung der Nebenbedingungen in Gleichungen.

(3) Herstellung eines ersten Simplex-Tableaus

.

(4) Festlegung der Pivotspalte, das ist die Spalte mit dem größten positiven Koeffizienten in der Zielfunktionszeile.

(5) Festlegung der Pivotzeile, das ist die Zeile mit positivem Koeffizienten in der Pivotspalte, für die sich bei Division der rechten Seite durch das betreffende Element der Pivotspalte der kleinste Zahlenwert ergibt (= engste Restriktion).

(6) Tableau-Umformung mittels
? Division der Pivotzeile durch das Pivotelement zur Herstellung der neuen Basiseins.
? Herstellen von Nullen ober- und unterhalb der neuen Basiseins durch Addition oder Subtraktion geeigneter Vielfacher der Pivotzeile zu bzw. von den anderen Zeilen.

(7) Wiederholung der Schritte (4) bis (6), bis die Zielfunktionszeile keine positiven Koeffizienten mehr enthält; dann ist das Optimum erreicht.

(8) Ablesen der optimalen Lösung aus dem Endtableau.

Lineare Programmierung (LP)

<< vorhergehender Begriff

nächster Begriff >>

Simplex-Algorithmus, primaler

Simplexkriterium