Simplex-Verfahren
Simplex-Verfahren, auch Simplex-Algorithmus: Ein Verfahren der mathematischen Optimierung (siehe auch Operations-Research, lineare Optimierung) 1947 von George Dantzig entwickelt. Es löst ein lineares Optimierungsproblem nach endlich vielen Schritten exakt (oder stellt die Unlösbarkeit des Problems fest). In eher theoretischen Ausnahmefällen können Zyklen auftreten, die das Auffinden der optimalen Lösung verhindern. Zunächst die Definition eines linearen Optimierungsproblems:
Maximiere die ZielfunktionDiejenigen Punkte x, die alle Nebenbedingungen gleichzeitig erfüllen (sog. zulässige Lösungen des Problems), bilden eine polyedrale Menge (Polyeder) im n-dimensionalen Raum. Wenn es keinerlei zulässigen Punkte gibt, so ist dies ein Anzeichen für sich widersprechende Nebenbedingungen und das Optimierungsproblem ist unlösbar. Wenn die zulässige Menge dagegen nicht leer ist, so sind 2 Fälle möglich: Entweder die Zielfunktion G ist über den zulässigen Punkten x durch eine obere Schranke begrenzt oder nicht. In letzterem Fall spricht man vom optimalen Zielfunktionswert (plus) unendlich und kann logischerweise keine optimale Lösung x dazu angegeben. Im ersten Fall dagegen läßt sich zeigen, daß das Maximum der Zielfunktion von einem Punkt auf dem Rand der zulässigen Menge angenommen wird, und zwar sogar von einem Eckpunkt. Insbesondere liegt die Lösung also nicht im Inneren des Polyeders. Das Simplex-Verfahren hangelt sich ausgehend von einer zulässigen Startlösung die Ecken entlang bis zu einer optimalen Lösung bzw. stellt fest, daß eine unendlich lange Kante des Polyeders mit unbeschränkt wachsender Zielfunktion existiert.unter der Nebenbedingung ,
A: n*m -Matrix x: n-dimensionaler Vektor a: n-dimensionaler Vektor b: m-dimensionaler Vektor : skalares Produkt, lineare Funktion mit n Variablen, reeller Wert der Zielfunktion Ax : m-dimensionaler Vektor, der aus der Multiplikation der Matrix A mit dem n dimensionalen Vektor x entsteht.
Wenn keine zulässige Startlösung bekannt ist, so kann man ein leicht abgewandeltes lineares Optimierungsproblem zur Bestimmung einer Startlösung bzw. zur Feststellung der Unlösbarkeit benutzen (sog. Phase I mit sog. künstlichen Variablen).
Bei einigen Problemstellungen kommt es vor, dass die Zielfunktion G minimal werden soll. Beispielsweise sollen beim Transportproblem die Transportkosten möglichst gering bzw. die Transportwege möglichst kurz sein. In diesem Fall führt man eine neue Zielfunktion H = -G ein und maximiert diese.
Anhand eines einfachen Beispiels wird der Lösungsweg Schritt für Schritt gezeigt. Reale Probleme haben oft mehrere 10.000 Nebenbedingungen, denen man häufig die Widerspruchsfreiheit bzw. die Existenz einer zulässigen Startlösung nicht unmittelbar ansehen kann.
Eine Firma stellt 2 verschiedene Produkte her. Es stehen 3 Maschinen A, B, C zur Verfügung. Maschine A hat eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden, Maschine B von 150 Stunden und Maschine C von 180 Stunden. Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Die Fixkosten betragen 36.000 Euro pro Monat.
Angenommen der Betrieb fertigt pro Monat x1 ME von Produkt 1 und x2 ME von Produkt 2. Dann beträgt der Ertrag (Gewinn oder Verlust)
Natürlich kann man nicht beliebig grosse Mengen fertigen, da die Maschinenkapazitäten beschränkt sind. Aus den Belegungszeiten ergeben sich für x1 und x2 daher die folgenden Nebenbedingungen:
Weil es unhandlich ist, mit solchen Ungleichungen zu rechnen, führt man diese in Gleichungen über. Dazu führt man so genannte Schlupfvariablen yA, yB und yC ein, welche die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Damit führt man beispielsweise die Nebenbedingung für Maschine A über in die Gleichung
Damit lässt sich das Problem folgendermaßen formulieren:
Maximiere die Zielfunktion G unter den Nebenbedingungen
Diese Gleichungen überträgt man in ein so genanntes Simplex-Tableau:
Zunächst bestimmt man eine zulässige Lösung. Das sind Werte für x1 und x2, welche alle Nebenbedingungen erfüllen.
Man kann sofort eine triviale zulässige Lösung angeben, nämlich
Diese Ausgangslösung ist natürlich unbefriedigend: Es wird nichts produziert, der Ertrag G beträgt -36.000 Euro, bedeutet also einen Verlust.
Daher muss man versuchen, bessere zulässige Lösungen zu finden.
In einer Simplex-Iteration wird eine Basisvariable gegen eine Nichtbasisvariable ausgetauscht. Man spricht daher auch von einem Austauschschritt.
In Frage kommen Nichtbasisvariable mit negativem Zielfunktionskoeffizienten. Unter diesen sucht man diejenige Basisvariable, deren Austausch den grössten Zuwachs für die Zielfunktion bringt. Sei s die Nummer der Spalte der auszutauschenden Nichtbasisvariable und r die Nummer der Zeile der auszutauschenden Basisvariablen. Ein Austauschschritt entspricht exakt einem Schritt beim Lösen eines linearen Gleichungssystems, bei dem man die Zeile r nach der Variablen xs auflöst und dann xs in die restlichen Gleichungen einsetzt. Seien aij die (Matrix)Elemente des Simpextablaus. Dann heißt ars das Pivotelement des Simplextableaus. Die Spalte s heißt Pivotspalte, die Zeile r heißt Pivotzeile.
Bei einem Austauschschritt berechnet sich das neue Simplextableau folgendermaßen:
Pivotelement:
Spalte 1 hat den negativen Zielfunktionskoeffizienten -300, kommt also als Pivotspalte s in Frage.
Mit dem Austauschschritt wird die Basisvariabke YB mit der Nichtbasisvariablen x1 ausgetauscht.
Das Simplex-Tableau wird nach den obigen Regeln umgerechnet.
Umrechnung des Pivotelementes: a2,1 = 1 / 1 = 1
Umrechnung der Pivotzeile r = 2: Jedes Element wird durch das Pivotelement geteilt.
Spalte 1 ist Pivotelement und wurde eben bereits berechnet.
Spalte 2: a2,2 = 1 / 1 = 1
rechte Seite: b2 = 150 / 1 = 150
Umrechnung der Pivotspalte s = 1: Jedes Element wird durch das Pivotelement geteilt,
das Vorzeichen kehrt sich um.
Zielfunktion: - (-300 / 1) = 300
Zeile 1: a1,1 = - (1 / 1) = -1
Zeile 2 ist Pivotzeile und bereits berechnet
Zeile 3: a3,1 = (- (0 / 1) = 0
Umrechnung der restlichen Werte:
Zielfunktion Spalte 2: -500 - (-300 × 1) /1 = -200
Zeile 1 Spalte 2: a1,1 = 2 - 1×1 / 1 = 1
Zeile 2 Spalte 2 gehört zur Pivotzeile und ist bereits berechnet.
Zeile 3 Spalte 2: a3,1 = 3 - 0×1 / 1 = 3
Zielfunktion:
G = -36000 - (-300 × 150) / 1 = 9000
rechte Seite:
Zeile 1: b1 = 170 - 1×150 / 1 = 20
Zeile 2 gehört zur Pivotzeile und ist bereits berechnet.
Zeile 3: b3 = 180 - 0×150 / 1 = 180
Nach der Umrechnung ergibt sich ein neues Simplex-Tableau:
Diese Lösung bedeutet: Es werden 150 ME von Produkt 1 (rechte Seite der Zeile mit x1) produziert. von Produkt 2 wird nichts gefertigt (x2 ist Nichtbasisvariable). Damit erzielt die Firma einen Gewinn von 9.000 Euro. Maschine A steht 20 Stunden pro Monat still (obwohl sie 170 Stunden laufen könnte). Maschine B hat keine Leerlaufzeit. Maschine C steht 180 Stunden still, d.h. sie wird überhaupt nicht benötigt. Dies ergibt sich auch direkt aus der Aufgabenstellung: Maschine C wird nur bei der Herstellung von Produkt 2 benötigt. Da diese nicht gefertigt wird braucht man Maschine C natürlich nicht.
Da die Zielfunktion im entstandenen Simplex-Tableau noch einen negativen Koeffizienten enthält kann man die Lösung noch verbessern. Dies geschieht mittels einer weiteren Simplex-Iteration.
Bei der Auswahl des Pivotelementes kommt nur Spalte s = 2 in Frage, da nur hier der Zielfunktionskoeffizient negativ ist. Die Pivotzeile r ergibt sich aus dem Minimum der Quotienten "rechte Seite / Spalte 2", also dem Minimum aus
Mit den gleichen Umrechnungen wie oben erhält man als neues Simplex-Tableau:
Da die Zielfunktion nun keine negativen Koeffizienten mehr enthält haben wir die optimale Lösung erreicht.
Es werden 130 ME von Produkt 1 und 20 ME von Produkt 2 hergestellt. Damit erzielt die Firma einen Gewinn von 13.000 Euro. Maschine A und Maschine B sind voll ausgelastet. Maschine C läuft 120 Stunden und hat daher noch eine ungenutzte Kapazität von 60 Stunden.
Den Durchbruch für das Simplex-Verfahren schaffte George Dantzig 1947, als auch er eine Arbeit über lineare Optimierung veröffentlichte. Interesse an dieser Arbeit zeigten zunächst die amerikanischen Militärs, speziell die Air Force; man wollte die militärischen Einsätze optimieren. In den Folgejahren entwickelten John von Neumann und O. Morgenstern das Verfahren weiter.
Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnte man auch größere Probleme lösen. Man entwickelte spezielle Varianten (revidierte Simplexalgorithmen) der Simplexmethode, die auf die Eigenschaften der jeweiligen Computer zugeschnitten waren, indem sie z.B. sehr sparsam mit der Nutzung des (knappen und teuren) Hauptspeichers umgingen.
Parallel - nach 1950 - entdeckte die Wirtschaft, dass man mit dem Simplex-Verfahren auch Optimierungsprobleme aus ihrem Bereich lösen konnte. Insbesondere die Ölraffinerien nutzten das Verfahren.
1960 optimierte W.Knödel die Belieferung der Zuckerfabriken in Österreich. Damit senkte er die Transportkosten um ca. 10 Prozent.
1979 verbesserte der russische Mathematiker Khashian den Algorithmus derart, dass man mit weniger Iterationsschritten die optimale Lösung erreicht. Diese Methode entwickelte der amerikanische Mathematiker Narenda Karkarmar fort.
Ein Beispiel aus der Praxis
Aufgabenstellung in Worten
Fertigt man 1 ME von Produkt 1, dann benötigt man dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde die Maschine B. 1 ME von Produkt 2 belegt nacheinander 2 Stunden Maschine A, 1 Stunde Maschine B und 3 Stunden Maschine C.Mathematische Formulierung mit Ungleichungen
Diesen Ertrag möchte die Firma maximieren. 1·x1 + 2·x2 ≤ 170 Maschine A
1·x1 + 1·x2 ≤ 150 Maschine B
0·x1 + 3·x2 ≤ 180 Maschine C
Negative Produktionsmengen sind nicht möglich, d.h. es gelten noch die Nebenbedingungen x1 ≥ 0
x2 ≥ 0
Überführung in Gleichungen
yA + x1 + 2·x2 = 170
Offensichtlich dürfen die Schlupfvariablen nicht negativ sein. G - 300x1 - 500x2 = - 36.000
yA + x1 + 2x2 = 170
yB + x1 + x2 = 150
yC + 3x2 = 180
yA, yB, yC, x1, x2 ≥ 0
Das Simplex-Tableau
-----------------------------
| x1 x2 | rechte Seite
---------------------------------
G | -300 -500 | -36000
---------------------------------
YA | 1 2 | 170 = b1
YB | 1 1 | 150 = b2
YC | 0 3 | 180 = b3
Die Variablen in der Kopfzeile heißen Nichtbasisvariable, die Variablen in der 1.Spalte Basisvariable. Die Zahlen in der "Zeile G" - der Gleichung für die Zielfunktion - heißen Zielfunktionskoeffizienten. Die Variablen b1, b2 und b3 bezeichnen die Werte der rechten Seite.Bestimmung einer zulässigen Ausgangslösung
x1 = 0
x2 = 0
Diese Lösung wird im obigen Simplextableau dargestellt. x1 und x2 sind die Nichtbasisvariablen. Die Nichtbasisvariablen haben immer den Wert "0".Verbesserung der Lösung mittels einer Simplex-Iteration
Pivotzeile für j ungleich s:
Pivotspalte für i ungleich r:
restliche Elemente:
Auswahl des Pivotelementes
Die letzte Formel ist entscheidend für die Auswahl der Pivotzeile r und der Pivotspalte s. Man sucht sich diejenigen Werte r,s, für die der Zielfunktionskoeffizient s negativ ist und für die der Wert von G := G - a0s bj / ars
am groessten wird. Dabei ist darauf zu achten, dass nach dem Austausch die entstandene Lösung weiterhin zulässig ist, d.h. alle Nebenbedingungen müssen erfüllt bleiben. Daher bestimmt man r und s derart, dass der Quotient bj / ars mit ars <> 0
innerhalb einer Spalte minimal wird.
Berechnung der Quotienten dieser Spalte 1:
Reihe 1: 170 / 1 = 170
Reihe 2: 150 / 1 = 150
Reihe 3: a31 = 0, daher kein Quotient berechenbar.
Den minimalen Quotient 150 erhält man also in Reihe 2. Mit dem Pivotelement a2,1 berechnet sich der neue Wert der Zielfunktion zu G = -36000 - (-300)×150 / 1 = 9000
Auch Spalte 2 hat mit -500 einen negativen Zielfunktionskoeffizienten, kommt also als Pivotspalte s in Frage.
Berechnung der Quotienten dieser Spalte 2:
Reihe 1: 170 / 2 = 85
Reihe 2: 150 / 1 = 150
Reihe 3: 180 / 3 = 60
Den minimalen Quotient 60 erhält man also in Reihe 3. Mit dem Pivotelement a3,1 berechnet sich der neue Wert der Zielfunktion zu G = -36000 - (-500)×60 / 3 = -26000
Damit ist es günstiger, als Pivotelement die Zahl 1 aus Spalte s = 1 und Reihe r = 2 zu wählen, weil damit die Zielfunktion am meisten anwächst, nämlich auf 9000.Durchführung eines Austauschschrittes
Das Pivotelement ist a2,1 = 1.
Das neue Simplex-Tableau
-----------------------------
| YB x2 | rechte Seite
---------------------------------
G | 300 -200 | 9000
---------------------------------
YA | -1 1 | 20 = b1
x1 | 1 1 | 150 = b2
YC | 0 3 | 180 = b3
Die Variable x1 ist in die Basis gerückt, die Variable YB erscheint in der Kopfzeile und ist damit eine Nichtbasivariable.nochmalige Verbesserung der Lösung
20 / 1 = 20
150 / 1 = 150
180 / 3 = 60
Damit ist Zeile r = 1 Pivotzeile. Das Pivotelement ist a1,2 = 1. Es wird die Basisvariable YA gegen die Nichtbasisvariable x2 ausgetauscht. -----------------------------
| YB YA | rechte Seite
---------------------------------
G | 100 200 | 13000
---------------------------------
x2 | -1 1 | 20
x1 | 2 -1 | 130
YC | 3 -3 | 120
Die optimale Lösung
Anmerkung zur Auswahl des Pivotelementes
Im Beispiel wurde das Pivotelement so ausgewählt, dass der Wert der Zielfunktion nach dem Iterationsschritt am meisten wächst. Dies bezeichnet man als Greatest Change Methode.
Alternativ kann man auch die Spalte als Pivotspalte auswählen, für die der Zielfunktionskoeffizient negativ und betragsmäßig am größten ist. Da dieser Koeffizient eine Art Steigung darstellt spricht man von der Steepest Unit Ascent Methode.
Oft - aber nicht immer - gelangt man bei der Greatest Change Methode mit weniger Simplex-Iterationen zur optimalen Lösung.Anwendungsgebiete
Wird von einer oder mehreren Variablen Ganzzahligkeit gefordert, dann löst man das Problem mit Hilfe des Simplex-Verfahrens zunächst ohne die Ganzzahligkeits-Bedingung. Ist die erhaltene Lösung nicht ganzzahlig, dann schneidet man diese Lösung weg, indem man geeignete Nebenbedingungen hinzufügt. Danach wiederholt man das Simplex-Verfahren. Bekannt sind das Verfahren Cutting-Plane-Verfahren von Gomory und die Methode Branch and Bound.
Probleme der diskreten linearen l1-Approximation sowie Probleme der diskreten Tschbyscheff-Approximation lassen sich so umformulieren, dass man sie mit dem Simplex-Verfahren lösen kann.Historie
Erstmals behandelte der russische Mathematiker Leonid Kantorovich 1939 in seinem Buch "Mathematische Methoden in der Organisation und Planung der Produktion" die lineare Optimierung. Kurz danach präsentierte der Amerikaner F.L. Hitchcock eine Arbeit zu einem Transportproblem. Damals erkannte man noch nicht die Bedeutung dieser Arbeiten.