Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Tableau

Charakterisierung von Polyederecken

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 $Ax=b,x\ge 0$ gegeben, $Rang(A)=m<n$. 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

Das Simplex-Verfahren besteht aus einer Folge von Basen bzw. Tableus. Zuerst wird die zulässige Basis $A_B$ gefunden und daraus das Starttableau konstruiert. Anschließend wir eine neue zulässige Basis $A_B$ aus $A_B$ konstruiert, so dass die zulässige Basislösung von $A_B$ besser ist, als die von $A_B$. Das Tableau wird nun aktualisiert. Wenn es keine bessere Basislösung mehr gibt, dann ist die letzte optimal. Ein Tableau entspricht dem Gleichungssystem $\left(\begin{array}{c}{c}^T\\ A\end{array}\right)x=\left(\begin{array}{c}{c}^{T}x\\ b\end{array}\right)$ mit $max{c}^{T}x,Ax=bundx\ge 0$. $T_B$ ist ein Simplextableau zur Basis $A_B$

$T_B=\left(\begin{array}{cc}{c}_N^T-C_B^T{A}_B^{-1}{A}_N& -C_B^T{A}_B^{-1}b\\ A_B^{-1}{A}_N& A_B^{-1}b\end{array}\right)$ mit $A=(A_B{A}_N),x=(x_B{x}_N),c^T=(c_N^T{c}_B^T)$

Update eines Tableau

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: $E=\{j|c_x{x}_j>0\}$. Wenn $E=\mathrm{\varnothing }$ 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: $L_j=\{i|x_j^i>0\}$. Wenn $L_i=\mathrm{\varnothing }$ für alle $i\in E$ dann ist das LP unbeschränkt, da die Zielfunktion $c^{T}x$ durch $x_i$ unbeschränkt wächst.

Optimierungsphase

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

Heuristik für die Auswahl der Tauschvektoren

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.