Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Tableau



Charakterisierung von Polyederecken

Bearbeiten

Auf dieser Seite werden die Tableaus des Simplex Verfahrens behandelt Warum schauen wir uns Basen und Basislösungen an? Wir waren doch an Ecken des Polyeders interessiert...

Sei das System   gegeben,  . Dann sind äquivalent:

  1. x ist eine Ecke des zugehörigen Polyeders
  2. x ist eine zulässige Basislösung von Ax=b

Wir wissen, dass die optimale Lösung in einem Eckpunkt liegen muss, falls sie existiert. D.h. wir müssen nur über die Basen von A optimieren (diese bestimmen ja die zulässigen Basislösungen von Ax=b). Dies erfolgt mit sogenannten Tableaus.

Das Simplex-Verfahren besteht aus einer Folge von Basen bzw. Tableus. Zuerst wird die zulässige Basis   gefunden und daraus das Starttableau konstruiert. Anschließend wir eine neue zulässige Basis   aus   konstruiert, so dass die zulässige Basislösung von   besser ist, als die von  . Das Tableau wird nun aktualisiert. Wenn es keine bessere Basislösung mehr gibt, dann ist die letzte optimal. Ein Tableau entspricht dem Gleichungssystem   mit  .   ist ein Simplextableau zur Basis  


  mit  

Update eines Tableau

Bearbeiten

Für das Update eines Tableau wird eine neue zulässige Basis bestimmt, indem ein Basisvektor durch einen Nichtbasisvektor ausgetauscht wird. Die Menge der Nichtbasisvektoren, die getauscht werden können, ist über die positiven Koeffienten c der Zielfunktion definiert als:  . Wenn   dann breche ab und gehe zu x zurück. Die Menge der Basisvektoren, die getauscht werden können, ist über ihre j-te Komponente bestimmt:  . Wenn   für alle   dann ist das LP unbeschränkt, da die Zielfunktion   durch   unbeschränkt wächst.

Optimierungsphase

Bearbeiten

Berechne für eine zulässige Basis, das zugehörige Tableau. Nun wird E bestimmt. Wenn   dann wird abgebrochen und x zurückgegeben. Ansonsten wird   durch eine geeignete Pivotregel gewählt. Als nächstes wird L bestimmt. Wenn   dann wird zurückgegeben, dass LP unbeschränkt ist. Ansonsten wird   durch eine geeignete Pivotregel gewählt. Führe nun einen Basiswechsel durch und starte wieder oben.

Heuristik für die Auswahl der Tauschvektoren

Bearbeiten

Als erstes werden die größten Koeffizienten in der Zielfunktion gewählt (Dantzig). Eine andere Möglichkeit ist das steepest-edge pricing, welches die Kombination aus Spalten- und Zeilenvektor wählt, die den größten Zuwachs für die Zielfunktion bringt. Oder der kleinste Index wird gewählt. Die letzte Möglichkeit ist eine zufällige Auswahl.