Wir hatten in der Übung heute morgen über verschiedene Spezialfälle beim Simplexverfahren geredet, hier nochmal etwas mehr Details dazu:
Für unser Pivotelement wählen wir die Zeile gemäß der Regel \( \min_{i \in 1, \ldots, m} \left\{\frac{a_{i,s}}{b_i} : a_{i,s} \geq 0 \right\} \) aus, wobei \(s\) die Pivotspalte ist. Kann kein solches Element gefunden werden (also sind alle unsere \(a_{i,s} < 0\)), dann ist unser Polyeder nach oben unbeschränkt. Der Simplex-Algorithmus bricht ab und es kann keine Optimallösung gefunden werden.
Hinweis: die Beschränkung auf \( a_{i,s} \geq 0 \) fehlt auf den Folien.
Falls es mehrere Optimallösungen für ein Optimierungsproblem gibt, dann existiert eine nicht-Basisvariable \(x_i\) mit \(c_i = 0\) (also der Wert in der Kopfzeile ist null) in unserem fertigem Simplextableau. Diesen Fall besprechen wir nächste Woche in der Vorlesung.
In jedem Schritt des Simplex-Verfahrens haben wir eine Basis \(B\) mit der zugehörigen Basis(teil)matrix \(A_B\). Es kann hilfreich sein, sich die Basisvariablen in einer Spalte links im Tableau aufzuschreiben. Mit jeder Iteration des Verfahrens tauschen wir genau eine Basisvariable in unserer Basis aus (\(\Rightarrow\) eine Variable verlässt die Basis, eine andere kommt rein) und verbessern so unsere Lösung. Das heißt auch, dass wir in jeder Iteration eine zulässige Basis haben. Sollte dies mal nicht der Fall sein, hat sich vermutlich ein Rechenfehler eingeschlichen und ihr solltet eure Schritte nochmal überprüfen.Wer mehr Details möchte, dem kann ich das Buch "Grundlagen der Mathematischen Optimierung" von Peter Gritzmann empfehlen (ist als E-Book über die Uni Bibliothek verfügbar), welches das Simplex Verfahren sehr genau aufbaut und motiviert.