Sonderfälle: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][gesichtete Version]
K (Oua poganiuc verschob Seite Sonderfälle nach Sonderfälle)
 
(2 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
m Zusammenhang mit dem Simplex-Algorithmus gibt es drei Sonderfälle:
+
===Zusammenfassung===
 +
Im Zusammenhang mit dem Simplex-Algorithmus gibt es drei Sonderfälle:
  
 
:Sonderfall 1: unbegrenzte Lösung
 
:Sonderfall 1: unbegrenzte Lösung
Zeile 20: Zeile 21:
  
  
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 x<sub>1</sub> 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 x<sub>1</sub> liegt also keine Lösungsbegrenzung vor.  
+
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 x<sub>1</sub> 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 x<sub>1</sub> liegt also keine Lösungsbegrenzung vor.  
  
 
Graphische Darstellung:
 
Graphische Darstellung:
Zeile 33: Zeile 34:
  
 
In der Praxis tritt dieses Problem meist auf, wenn Fehler bei der Modellkonstruktion begangen wurden.
 
In der Praxis tritt dieses Problem meist auf, wenn Fehler bei der Modellkonstruktion begangen wurden.
 
  
 
===Sonderfall 2: primale Entartung===
 
===Sonderfall 2: primale Entartung===

Aktuelle Version vom 22. Mai 2013, 11:50 Uhr

Zusammenfassung

Im 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:


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Abb. 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:


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Abb. 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:


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Abb. 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:


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Abb. 4


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


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Abb. 5


Literatur

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