Simplex-Verfahren/ Simplex-Algorithmus
Inhaltsübersicht
Der Simplex-Algorithmus dient in der Mathematik dazu, lineare Optimierungsprobleme bzw. sogenannte Lineare Programme zu lösen. Im wirtschaftlichen Kontext wird das Simplex-Verfahren beispielsweise eingesetzt, um eine Kostenminimierung oder eine Gewinnmaximierung unter Einhaltung von bestimmten Beschränkungen zu errechnen.
Da es sich um ein iteratives Verfahren handelt, erfolgt das Finden der optimalen Lösung in mehreren Schritten. Dabei wird zunächst mit einer zulässigen Basislösung begonnen, diese wird dann auf ihre Optimalität geprüft. Ist die Basislösung nicht optimal, wird eine neue verbesserte Lösung gesucht, welche dann wiederum darauf geprüft wird, ob Optimalität vorliegt. Das Verfahren kommt zum Ende sobald eine optimale Lösung gefunden wurde.
Im einfachsten Fall liegt das Problem bereits als Standardproblem der Linearen Programmierung, also als allgemeines Maximierungsproblem mit - Nebenbedingungen, vor. Ist dies nicht der Fall, kann das Problem mittels einfacher Rechenoperationen in ein solches transformiert werden.
Transformationen
Beispiel:
Ein Unternehmen produziert mit Hilfe von zwei vorhandenen Maschinen die Güter 1 und 2. Maschine 1 weist eine Kapazität von 1.000 Minuten und Maschine 2 eine Kapazität von 10.000 Minuten auf. Gut 1 beansprucht eine Minute Laufzeit auf Maschine 1 und 25 Minuten auf Maschine 2. Die Bearbeitung von Gut 2 hingegen benötigt 2 Minuten auf Maschine 1 aber lediglich 10 Minuten auf Maschine 2. Da der Markt relativ klein ist, können nicht mehr als 700 Stück von Gut 1 und 500 Stück von Gut 2 abgesetzt werden. Die Gewinnfunktion des Unternehmens lautet: G = 300x1 + 200x2 – 50000.
Wieviel sollte das Unternehmen von den jeweiligen Gütern herstellen, wenn ein maximaler Gewinn unter Beachtung aller Beschränkungen erzielt werden soll?
Für die Anwendung des Simplex-Algorithmus müssen die Ungleichungen der Nebenbedingungen in ein Gleichungssystem überführt werden. Dies wird mit Hilfe von sogenannten Schlupfvariablen gemacht, sie stellen im Gleichungssystem unausgelastete Kapazitäten dar. Zudem muss die Zielfunktion, in die Form „ … = Konstante“ gebracht werden, ohne den Zielfunktionswert zu negativieren.
Liegen die Nebenbedingungen in Gleichungsform vor, können alle Koeffizienten des Problems in ein sogenanntes Simplex-Tableau übertragen werden. Jede Variable erhält eine eigene Spalte und jede Nebenbedingung eine eigene Zeile. Die Zielfunktion wird in die unterste Zeile eingetragen.
Aus dem ersten Simplex-Tableau kann dann auch die erste Basislösung abgelesen werden. Dazu wird jeder Variable die einen Einheitsvektor unter sich stehen hat derjenige Wert aus der letzten Spalte zugeordnet der auf gleicher Höhe mit der „1“ aus dem Einheitsvektor steht. Hat eine Variable keinen Einheitsvektor unter sich stehen, so wird der Variable der Wert 0 zugeordnet.
Die Lösung ist so lange nicht optimal, solange sich in der Zielfunktionszeile (=letzte Spalte des Tableaus) ein negativer Wert befindet. Dazu muss durch Zeilenoperationen ein Einheitsvektor in derjenigen Spalte erzeugt werden, in der der Wert der Zielfunktionszeile am kleinsten ist. Die Spalte mit dem kleinsten Wert wird dann als Pivotspalte bezeichnet.
Um herauszufinden an welcher Stelle die „1“ des Einheitsvektors steht, muss zunächst die sogenannte Pivotzeile gefunden werden. Diese befindet sich an derjenigen Stelle, an der der Quotient aus dem jeweiligen Element der Pivotspalte und der letzten Spalte des Tableaus am kleinsten ist. Negative sowie nichtbestimmbare (z.B. 120 ) Quotienten werden dabei nicht berücksichtigt. Dasjenige Element, das sich sowohl in der Pivotspalte als auch in der Pivotzeile befindet wird als sogenanntes Pivotelement bezeichnet, an dieser Stelle soll dann die „1“ des Einheitsvektors erzeugt werden.
Das Pivotelement kann sich weder in der untersten Zeile noch in der letzten Spalte befinden.
Merke:
Die Lösung ist nicht optimal, solange sich in der Zielfunktionszeile ein negativer Wert befindet! Der Algorithmus endet erst, wenn die optimale Lösung gefunden wurde.
Damit eine bessere Lösung gefunden werden kann, wird mittels Zeilenoperationen versucht, das Pivotelement zu einer „1“ zu machen und die restlichen Elemente der Spalte jeweils zu „0“-ern. Dazu kann man zur besseren Übersicht zunächst ein Zwischentableau erstellen, welches sich vom vorhergehendem Simplex-Tableau in der Hinsicht unterscheidet, dass bereits eine erste Zeilenoperation in der Pivotzeile stattgefunden hat. Mit dieser veränderten Zeile werden dann die restlichen Zeilen so angepasst, dass in der Pivotspalte ein Einheitsvektor erzeugt wird. Wurde dieser erzeugt, liegt das zweite Simplex-Tableau vor, aus diesem kann dann die verbesserte Lösung abgelesen werden.
Fortsetzung Beispiel:
Das Pivotelement in diesem Beispiel war das Element „25“, dieses soll nun zur „1“ des Einheitsvektors werden. Dazu wird die gesamte zweite Zeile mit 125 multipliziert, die neue zweite Zeile wird dann als (II)‘ bezeichnet.
Verbesserte Basislösung: x1= 400; x2=600; y2= 0; ys= 300; y4= 500; G=70000
→ Vorliegende Lösung noch nicht optimal, Algorithmus weiterführen!
→ Optimales Tableau = Ende des Simplex-Algorithmus
Optimale Lösung : x1* = 250; x2* = 375; y1* = 0; y2* = 0; y3* = 450; y4* = 125 ; G* = 100000
Interpretation: Das Unternehmen erzielt den maximalen Gewinn von 100000, wenn es 250 Mengeneinheiten von Gut 1 und 375 Mengeneinheiten von Gut 2 produziert. Sowohl Maschine 1 als auch Maschine 2 werden voll ausgelastet. Es liegt ein nicht ausgenutztes Absatzpotential von 450 Mengeneinheiten von Gut 1 sowie von 125 Mengeneinheiten von Gut 2 vor.
Du suchst hilfreiche Dokumente zum Thema?
Auf Studydrive findest du jede Menge Lernmaterialien, die dir bei der Kurs- oder Prüfungsvorbereitung helfen werden. Hier findest du Zusammenfassungen und Notizen, Lösungen zu vergangenen Prüfungen und Arbeitsblätter.
Übungen & Klausuraufgaben
Finde alle passenden Kurse auf Studydrive
Melde dich jetzt bei Studydrive an und erhalte kostenlos Zugang zu allen Kursen, die zu deinem Thema passen. Tausche dich außerdem mit anderen Studierenden aus und bekomme hilfreiche Antworten auf all deine Fragen!