Sonderfälle

Aus Operations-Research-Wiki
Version vom 4. Juli 2007, 16:04 Uhr von Biedinger (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Wechseln zu: Navigation, Suche

m Zusammenhang mit dem Simplex-Algorithmus gibt es drei Sonderfälle:

Sonderfall 1: unbegrenzte Lösung
Sonderfall 2: primale Entartung
Sonderfall 3: duale Entartung


Sonderfall 1: unbegrenzte Lösung

Tritt ein Tableau auf, das in der Pivot-Spalte nur negative Elemente oder Nullelemente enthält, so ist es nicht möglich, für dieses eine Pivot-Zeile und somit ein Pivot-Element zu wählen. Man spricht von einer unbegrenzten Lösung.

Beispiel:


http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/SBild1.jpg
Bild 1



In diesem Beispiel ist die erste Spalte die Pivot-Spalte, da nur diese einen negativen Zielfunktionskoeffizienten enthält. Betrachtet man nun die restlichen Spaltenelemente, so stellt man fest, dass diese alle negativ oder gleich Null sind. Daraus folgt, dass die Variable x1 nicht in die Basis getauscht werden kann. Sie kann somit bis ins unendliche vergrößert werden, da dadurch keine andere Variable gleich Null wird. Für die Variable x1 liegt also keine Lösungsbegrenzung vor.

Graphische Darstellung:


http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/SBild2.jpg
Bild 2



In der Praxis tritt dieses Problem meist auf, wenn Fehler bei der Modellkonstruktion begangen wurden.


Sonderfall 2: primale Entartung

Treten bei der Rechnung mit dem Simplex-Algorithmus in einem Tableau mehrere gleich gute Pivot-Spalten oder Pivot-Zeilen auf, so spricht man von Entartung.

Bei der primalen Entartung findet man nach der Bestimmung der Pivot-Spalte mehrere Zeilen mit gleich großem, kleinsten Quotienten aus rechter Seite und Spaltenelement. In diesem Fall könnte man einfach eine der möglichen Zeilen als Pivot-Zeilen wählen, was aber unter Umständen dazu führt, dass man in einen Kreislauf gerät, der immer wieder zurück zum Ausgangstableau führt.

Beispiel:

http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/SBild3.jpg
Bild 3


Wählt man für dieses Beispiel nach Steepest-Unit-Ascent die erste Spalte als Pivot-Spalte und die erste Zeile als Pivot-Zeile, so führt dies nach 6 Iterationen wieder zum oben angegebenen Tableau.

Um solche Schleifen zu vermeiden wählt man, wenn ein Problem mit primaler Entartung auftritt, ein beliebiges Matrix-Element als Pivot-Element und rechnet dann nach den bekannten Rechenregeln für Phase 2 um, um zu einem anderen Tableau zu gelangen, bei dem die Entartung dann eventuell schon nicht mehr auftritt und man das Problem lösen kann. Tritt die Entartung weiterhin auf, wählt man wieder ein beliebiges Element und verfährt wie oben beschrieben.


Sonderfall 3: duale Entartung

Treten bei der Rechnung mit dem Simplex-Algorithmus mehrere Spalten mit gleich großem absolut größtem Zielfunktionskoeffizienten auf, so spricht man von dualer Entartung. Man hat mehrere Pivot-Spalten zur Auswahl und kann in diesem Fall eine beliebige dieser Spalten, z.B. die Erste, als Pivot-Spalte wählen und wird immer zur Lösung finden. Schleifen, wie im Fall der primalen Entartung, treten nicht auf.

Beispiel:


http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/SBild4.jpg
Bild 4


Das obige Tablau führt immer, egal ob man mit der ersten oder der zweiten Spalte beginnt, nach zwei Iterationen zum Endtableau.


http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/grafik/SBild5.jpg
Bild 5


Literatur

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