Operations Research

Simplex-Algorithmus

Inhaltsübersicht

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.

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 x\ \in\ \mathrm{\Omega} mit möglichst großem f(x) 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.

Simplex-Verfahren, Simplex-Algortihmus
Simplex-Verfahren

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: 80x_1+60x_2

Nebenbedingungen:

2x_1+2x_2\le16\ (1)

4x_1+2x_2\le24\ (2)

4x_1+6x_2\le36\ (3)

Nichtnegativitätsbedingungen: x1,x2\ge 0

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 x_3,\ x_4\ und\ x_5 einfügst. Die Normalform ergibt sich in diesem Fall zu:

Simplex-Algorithmus
Normalform und Matrix der Schlupfvariablen

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 x_3, x_4 und x_5 aus der Normalform des linearen Gleichungssystems. Deine Nichtbasisvariablen sind deine Entscheidungsvariablen x_1 und x_2. Nun trägst du deine zugehörigen Werte der Variablen in das Tableau ein. Die b_i-Spalte gibt einfach die Werte hinter dem Gleichheitszeichen wieder.

Simplex Tableau ausgefüllt
Simplex Tableau ausgefüllt

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 b_i-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 \frac{b_i}{a_{is}} indem du b_i durch das jeweilige Element a_is in der Pivotspalte s dividierst.

Simplex-Algorithmus
Wahl der Pivotzeile und -spalte

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 \frac{b_i}{a_{is}}, 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 x_4 mit x_1. 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.

Simplex Tableau
Simplextableau

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 b_iSpalte der F-Zeile. In unserem Fall 540.

Zielfunktion ermitteln
Zielfunktion ermitteln

Simplex Algorithmus: Ergebnis kontrollieren

Zur Kontrolle des Verfahrens betrachten wir die lineare Zielfunktion ein weiteres Mal.

F\left(x\right)=80x_1+60x_2=540

Setzen wir die Werte der Variablen x_1 und x_2 in die lineare Zielfunktion ein, muss genau der ermittelte Zielfunktionswert herauskommen:

F(x)=80\ast\frac{9}{2}+60\ast3=540

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.


Andere Nutzer halten diese Inhalte aus dem Bereich „Operations Research“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.