Simplex-Algorithmus

Der Simplex-Algorithmus berechnet eine optimale Lösung zu einem linearen Problem.

Siehe auch

Basislösung

Algorithmus

Gegeben sei ein LP in Normalform und Matrixschreibweise mit

• Insgesamt Variablen:
  • Problem- bzw. Entscheidungsvariablen
  • Nebenbedingungen / Schlupfvariablen
• Zielfunktionsvektor
• Koeffizientenmatrix
• Restriktionsvektor

Simplex-Tableau

Dann wird eine Tabelle dieser Form aufgestellt:

In die erste Spalte kommen die Basisvariablen, daneben die Entscheidungsvariablen, die Schlupfvariablen und anschließend der Restriktionsvektor. In die letzte Zeile kommt der Zielfunktionsvektor. Die Felder in der Mitte werden mit der Koeffizientenmatrix aufgefüllt.

Bestimmung des Pivot-Elements

	Primaler Schritt	Dualer Schritt
Bedingung	hat nur positive Werte	enthält mindestens einen negativen Wert
Pivot-Spalte/Zeile	Pivot-Spalte ist die mit dem kleinsten negativen Wert aus	Pivot-Zeile ist die mit dem kleinsten negativen Wert aus
Quotient-Berechnung*	Für jede Zeile wird der Wert aus durch den aus der Pivot-Spalte geteilt	Für jede Spalte wird der Wert aus durch den aus der Pivot-Zeile geteilt
Quotient-Ausnahmen	Nur positive nicht Werte sind erlaubt	Nur negative nicht 0 Werte sind erlaubt
Pivot-Spalte/Zeile	Die Zeile mit dem kleinsten Quotient ist die Pivot-Zeile	Die Spalte mit dem größten Quotient ist die Pivot-Spalte

* Bei der Quotient-Berechnung bietet sich an, sich eine Hilfsspalte bzw. -Zeile zu erstellen und die Zwischenergebnisse zu notieren

Das Element, bei dem sich Pivot-Zeile und -Spalte treffen, heißt Pivot-Element .

Tableautransformation

Tipp

Die folgenden Schritte ähneln sehr den Zeilenumformumgen in linearen Gleichungssystemen.

Die Zeile mit dem Pivot-Element wird so ungeformt, dass das Pivot-Element auf normalisiert wird. Das kann man durch Multiplikation mit dem -fachen erzielen.

Anschließend werden die anderen Zeilen so umgeformt, dass sie in der Pivot-Spalte eine stehen haben. Das kann durch geschickte Addition bzw. Subtraktion eines vielfachen der Pivotzeile erzielt werden. (Allgemein: Hat die Zeile in der Pivotspalte das -fache der Pivotspalte, dann subtrahiere das -fache der Pivotzeile von der Zeile)

Schließlich wird die Variable der Pivotzeile ersetzt durch die der Pivotspalte.

Ergebnis

Hat die -Zeile keine negativen Einträge, ist die Lösung optimal, und der Algorithmus ist beendet. Andernfalls müssen weitere Iterationen angewendet werden.

Die Lösung lässt sich wie folgt ablesen: Die Basisvariablen stehen in der ersten Spalte, ihre Werte in der Spalte von . Alle anderen Variablen sind .

Beispiel