Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Tableau

Aus Wikiversity



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.

Tableau[Bearbeiten]

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.


Discussion