Phasen des Simplex-Algorithmus

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

Der Simplex-Algorithmus gliedert sich in 4 Phasen:

Phase 0: gesperrte Variablen
Phase 0´: freie Variablen
Phase 1: unzulässige Ausgangslösung
Phase 2: Optimierung


Phase 0: gesperrte Variablen

Beim Simplex-Algorithmus werden Schlupfvariablen yi eingeführt, um Ungleichungen in Gleichungen zu überführen. Sie haben die Aufgabe in der Ausgangslösung, in der alle Strukturvariablen xj gleich Null sind, den Wert der rechten Seite anzunehmen, um die Gleichung zu erfüllen.

In einigen Fällen können aber Gleichungen als Restriktionen auftreten. In diesen Fällen nimmt die Strukturvariable den Wert Null an, um die Gleichung zu erfüllen. Sie wird deshalb als gesperrte Variable gekennzeichnet, die nicht in der Basis stehen darf und muss diese somit verlassen.

Um dies zu erreichen werden, solange sich gesperrte Variablen in der Basis befinden, diese Zeilen als Pivot-Zeilen gewählt. Als Pivot-Spalte kann jede Spalte gewählt werden, die keine gesperrte Variable als Nichtbasisvariable hat und in der Pivot-Zeile ein Nichtnullelement enthält. Im folgenden wird das Tableau nach den Rechenregeln für Phase 2 umgerechnet.


Phase 0`: freie Variablen

In einigen Fällen kann es sein, dass für einzelne Variablen die Nichtnegativitätsbedingungen nicht gelten. Diese Variablen werden dann als freie Variablen bezeichnet und müssen in die Basis.

Um dies zu erreichen werden, solange sich freie Variablen in der Nichtbasis befinden, diese Spalten als Pivot-Spalten gewählt. Als Pivot-Zeile kann jede Zeile gewählt werden, die keine freie Variable als Basisvariable hat und in der Pivot-Spalte ein Nichtnullelement enthält. Im folgenden wird das Tableau nach den Rechenregeln für Phase 2 umgerechnet.

Befindet sich eine freie Variable einmal in der Basis, so darf diese Zeile nie mehr als Pivot-Zeile gewählt werden, da sie die Basis sonst wieder verlässt.


Phase 1: unzulässige Ausgangslösung

In einigen Fällen kann es sein, dass Restriktionen in der Ausgangslösung eine negative rechte Seite aufweisen und somit die Nichtnegativitätsbedingungen verletzt werden, da in der Ausgangslösung wie schon erwähnt die Strukturvariablen xj den Wert Null annehmen. Dadurch nehmen die Schlupfvariable yi die negativen Wert der rechten Seite an. Tableaus dieser Art werden als unzulässige Ausgangslösungen bezeichnet.

Um eine zulässige Ausgangslösung zu erhalten werden Pivot-Zeile und Pivot-Spalte so gewählt, dass bei einer Umrechnung die Werte der rechten Seite positive Werte annehmen. Als Pivot-Zeile wird die Zeile mit negativer rechter Seite gewählt, als Pivot-Spalte eine Spalte mit negativem Wert in der Pivot-Zeile. Bei der Umrechnung nach den Rechenregeln für Phase 2 wird dann das negative Element der rechten Seite durch das negative Pivot-Element geteilt, wodurch das neue Element der rechten Seite einen positiven Wert annimmt. Dieses Vorgehen setzt man solange fort, bis alle Werte der rechten Seite positiv sind und man somit eine zulässige Ausgangslösung gefunden hat. Gibt es noch Zeilen mit negativer rechter Seite, aber keine negativen Spaltenelemente in diesen Zeilen, so kann man keine Umrechnung mehr durchführen und somit ist es unmöglich, eine zulässige Ausgangslösung zu finden.


Phase 2: Optimierung

Literatur

Müller-Merbach (1973): Operations Research, Kapitel 4.2.9 - 4.2.11


Vorlesung/Lecture

Sie können sich zu diesem Themengebiet eine Vorlesung ansehen:


Phasen des Simplex-Algorithmus (English)