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)

Siehe
>>> Simplex-Methode.

auch Simplex-Algorithmus, mathematisches Lösungsverfahren von Problemen der linearen Programmierung. Dabei geht man von der Zielfunktion aus, unter der Annahme, daß die Restriktionen nicht von einander abhängig sind und sich nicht widersprechen. Weiterhin kann vorausgesetzt werden, daß die Zahl der Restriktionen kleiner ist als die Zahl der Variablen. Der Wert der Zielfunktion ist zu maximieren bzw. zu minimieren.

Das Universalverfahren der linearen Programmierung ist die von Dantzig entwickelte Simplexmethode. Die Simplexmethode verdankt ihren Namen dem Aussehen des Polyeders, der die optimale Lösung enthält. Das Simplexverfahren ist dadurch gekennzeichnet, daß es die optimale Lösung schrittweise, also in Iterationen, sucht, indem es, ausgehend von der Nullösung, am Rand des Polyeders von Eckpunkt zu Eckpunkt fortschreitet, bis die beste Lösung gefunden ist. Die Simplexmethode baut auf Verfahren zur Lösung linearer Gleichungssysteme auf, die in Matrizenform dargestellt und durch Simplexregeln umgeformt werden.

Die Simplexmethode dient in ihrer ursprünglichen Form (reguläre Simplexmethode) als Verfahren zur Lösung von linearen Optimierungsmodellen, die aus einer zu maximierenden linearen Zielfunktion und einem Block linearer Nebenbedingungen (estriktionen) sowie Nichtnegativitätsbedingungen für die Problemvariablen (x) bestehen (vgl. beispielsweise die Problemstellung der Produktionsprogrammplanung; Operations Research). Das System der Nebenbedingungen (Gleichungssystem mit sog. Schlupfvariablen) wird ebenso wie die Zielfunktion in ein Simplextableau überführt, in dessen Randspalte sich der aktuelle Lösungswert der am Kopf der Zeile stehenden Basisvariablen sowie in der letzten Zeile der Zielfunktionswert ablesen lassen. Innerhalb des Tableaus sind die Restriktionskoeffizienten (a,) der jeweils am Kopf der Spalte stehenden Variablen abzulesen, und die letzte Zeile (Zielzeile) enthält die jeweiligen Zielfunktionskoeffizienten (c). Nachfolgend ist die Struktur eines solchen Ausgangstableaus dargestellt:

Mit Hilfe sog. Basistransformationen werden beginnend mit dem oben aufgeführten Ausgangstableau im Laufe des Verfahrens verschiedene Lösungen erzeugt, die dadurch gekennzeichnet sind, dass sie aus J Basisvariablen bestehen und sich ihr Zielfunktionswert im Laufe der Iterationen nicht verschlechtert. Lässt sich keine Lösung mehr finden, die einen besseren Ziel funktionswert aufweist, so ist die Optimallösung erreicht, und das Verfahren ist beendet. Im Optimaltableau enthält die Zielzeile, in der negative Elemente auf eine Möglichkeit der Verbesserung hindeuten, nur Werte größer oder gleich null, und der Zielfunktionswert ist maximal. Veranschaulicht man sich die Vorgehensweise anhand einer Graphik, so werden im Rahmen der Simplexmethode ausgehend vom Ursprung des Koordinatenkreuzes Eckpunkte des Beschränkungspolyeders, der durch die Restriktionen festgelegt wird, auf ihre Optimalität untersucht, und nach jeder neuen Tableautransformation ist ein besserer Eckpunkt erreicht. Für mögliche Sonderfälle, wie Degeneration, Mehrdeutigkeit, Unzulässigkeit des Nullpunktes, Ganzzahligkeit der Problemvariablen u. Ä., sind Vorgehensweisen im Rahmen der Simplexmethode, Modifikationen des Verfahrens (z. B. Zwei Phasen implexmethode) oder sogar neue Verfahren, die die Simplexmethode als Ausgangspunkt verwenden (Verfahren von Dakin oder Gomory), entwickelt worden, so dass dieses Verfahren der linearen Optimierung einen zentralen Lösungsansatz darstellt. Darüber hinaus lässt sich bei weiter gehenden Fragestellungen wie denen von Sensitivitätsanalysen auf den Ergebnissen der Simplexmethode aufbauen.

Vorhergehender Fachbegriff: Simplex-Algorithmus, primaler | Nächster Fachbegriff: Simplex-Verfahren

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Zinseszinsrechnung | Fixkostenverrechnungsdifferenzen | Verkaufsorgane

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer