Simplex-Algorithmus
Du möchtest wissen, was der Simplex-Algorithmus ist? Hier erklären wir dir Schritt für Schritt, wie dieser Algorithmus funktioniert und welche der zulässigen Lösungen die Zielfunktion maximiert.
Inhaltsübersicht
Simplex-Algorithmus bzw. Primaler Simplex: Erklärung und Beispiel
Der Simplex-Algorithmus, auch als Simplexverfahren, Simplex Methode oder primaler Simplex bekannt, ist ein Optimierungsverfahren, das dir hilft die optimale zulässige Lösung eines linearen Optimierungsproblems zu finden oder dessen Unlösbarkeit festzustellen. Dabei versucht man beim Maximierungsproblem eine Lösung 
mit möglichst großem 
zu finden, beim Minimierungsproblem ist das genaue Gegenteil der Fall. Der Simplex-Algorithmus ist im Grunde also ein geschicktes Suchverfahren. Die Grundidee basiert auf den Überlegungen von Georg Dantzig. Er startet mit einer zulässigen Basislösung.
Diese ist ein Schnittpunkt zweier Nebenbedingungen, die innerhalb der zulässigen konvexen Menge liegen. Wenn sie nicht optimal ist, findet ein Übergang zu einer benachbarten Basislösung durch Austauschen einer Basisvariable statt. Bei jedem Schritt wird dadurch der Zielfunktionswert verbessert. Wenn kein besserer Zielfunktionswert mehr gefunden werden kann, wurde die optimale Lösung identifiziert.
Voraussetzungen und Simplex-Algorithmus Beispiel
Anhand dieses linearen Optimierungsproblems zeigen wir dir jetzt, wie du auf die optimale Lösung kommst. Wie du siehst, haben wir eine Zielfunktion, drei Nebenbedingungen und die beiden Nichtnegativitätsbedingungen der beiden Variablen:
Zielfunktion: 
Nebenbedingungen:
Nichtnegativitätsbedingungen: 
Voraussetzung für den Start des primalen Simplexverfahrens ist, dass das lineare Gleichungssystem in Normalform vorliegt, die rechten Seiten der Variablen nichtnegativ sind und sich eine Einheitsmatrix unter den Schlupfvariablen bildet. Du musst also das Ungleichungssystem in ein Gleichungssystem umwandeln, indem du die Hilfsvariablen 
einfügst. Die Normalform ergibt sich in diesem Fall zu:
Simplex Tableau erstellen
Diese Normalform musst du jetzt in das Simplextableau übertragen. Dieses Tableau hat Zeilen und Spalten für die Basisvariablen, kurz BV, sowie Spalten für die Nichtbasisvariablen, kurz NBV. Die Basisvariablen sind am Anfang deine Schlupfvariablen 
, 
und 
aus der Normalform des linearen Gleichungssystems. Deine Nichtbasisvariablen sind deine Entscheidungsvariablen 
und 
. Nun trägst du deine zugehörigen Werte der Variablen in das Tableau ein. Die 
-Spalte gibt einfach die Werte hinter dem Gleichheitszeichen wieder.
In die F-Zeile des Tableaus tragen wir die Faktoren der Zielfunktion ein. Die zwei letzten Spalten lassen wir für unsere weiteren Berechnungen leer. In der -Spalte der F-Zeile finden wir den Zielfunktionswert; im Moment ist dieser natürlich noch Null. Als letztes musst du nur noch jede Zeile nummerieren. Dabei bekommt die Funktionszeile die gleiche Zahl wie die vorherige Zeile, nur mit einem zusätzlichen Strich. Damit haben wir das Simplextableau gefüllt! Jetzt können wir mit dem Simplex Verfahren beginnen.
Erster Iterationsschritt: Wahl der Pivotspalte
Der Ablauf einer Iteration, also eines Durchgangs, verläuft nun nach folgendem Muster: Der erste Iterationsschritt ist die Wahl einer Pivotspalte. Daher wird der Algorithmus auch häufig als Pivotverfahren bezeichnet. Dafür schaust du dir die F-Zeile an. Gibt es dort keine negativen Werte der Variablen, ist die aktuelle Basislösung optimal und das Simplex Verfahren ist beendet. Dies ist hier nicht der Fall. Wir markieren die Variable mit dem kleinsten, also negativsten Wert, in unserem Fall Minus 80. Dies ist unsere Pivotspalte.
Zweiter Iterationsschritt: Wahl der Pivotzeile
Der zweite Iterationsschritt ist die Wahl der Pivotzeile z. Du berechnest dafür 
indem du durch das jeweilige Element 
in der Pivotspalte s dividierst.
Für Zeile 1 ist das also 16 durch 2 gleich 8. Analog machen wir das für Zeile zwei und drei. Hier markierst du nun das kleinste , also 6. Das ist unsere Pivotzeile. Das Element, das nun sowohl in der Pivotzeile, als auch in der Pivotspalte steht, bezeichnen wir als Pivotelement.
Dritter Iterationsschritt: Basisvariablen, Schlupfvariablen und Nichtbasisvariablen
Nun folgt Iterationsschritt Nr. 3, die Berechnung der neuen zulässigen Basislösung. Wir fügen wieder drei neue Zeilen hinzu und beschriften diese mit den Basisvariablen. Dabei ersetzen wir die Basisvariable in der Pivotzeile durch die Nichtbasisvariable in der Pivotspalte. Also mit . Jetzt versuchen wir in der Spalte der neuen Basisvariable einen Einheitsvektor zu erzeugen. Die 1 soll dabei an der gleichen Stelle sein wie das Pivotelement. Dazu teilen wir jedes Element der Pivotzeile durch 4. Damit erhalten wir für die Zeile fünf: 1, ½, 0, ¼, 0, 6. Die anderen Zeilen der Pivotspalte sollen eine Null bekommen. In Zeile 4 müssen dafür die Elemente der Zeile 1 Minus 0,5 Mal Zeile 2 genommen werden. Analog erhalten wir für Zeile 6.
Die F-Zeile wird natürlich auch mit transformiert. Damit hast du jetzt eine Iteration geschafft! Keine Sorge, mit der Zeit wird dir der Simplex-Algorithmus einfacher fallen.
Der nächste Iterationsschritt erfolgt wieder nach dem gleichen Schema. Zunächst ermitteln wir gemeinsam das Pivotelement. Die weiteren Schritte überspringen wir jetzt allerdings und füllen das Simplex Tableau direkt aus. Wenn du dir nun die Zeile mit der Zielfunktion anschaust, erkennst du, dass wir keine negativen Eintragungen mehr haben. Den Zielfunktionswert findest du jetzt in der Spalte der F-Zeile. In unserem Fall 540.
Simplex Algorithmus: Ergebnis kontrollieren
Zur Kontrolle des Verfahrens betrachten wir die lineare Zielfunktion ein weiteres Mal.
Setzen wir die Werte der Variablen und in die lineare Zielfunktion ein, muss genau der ermittelte Zielfunktionswert herauskommen:
Bei uns ist das der Fall und wir können damit das Verfahren beenden. Du siehst, auch wenn der Simplex-Algorithmus auf den ersten Blick sehr kompliziert erscheint – mit ein wenig Übung ist er sehr gut machbar.