Der primale Simplex-Algorithmus (pSA) ist ein Verfahren zur Lösung von LP-Modellen. Er nutzt die Tatsache aus, dass der Lösungsraum durch eine endliche Anzahl von Eckpunkten (Basislösungen) aufgespannt wird, es handelt sich um ein konvexes, für die im Folgenden verwendeten Begriffe s. LP-Modell). In jedem Eckpunkt liegt eine zulässige Basislösung (BL) vor. Der pSA startet mit einer zulässigen BL und geht in jeder Iteration zu einer benachbarten BL über, falls diese einen höheren Zielfunktionswert aufweist. Gibt es einen solchen benachbarten Eckpunkt nicht, so ist eine optimale Lösung erreicht. Der Übergang von einer BL zu einer benachbarten erfolgt durch Austausch einer Basisvariablen (BV) gegen eine Nichtbasisvariable (NBV), d.h. durch eine entsprechende Transformation des Gleichungssystems, so dass der Zielfunktionswert möglichst stark ansteigt. Bei Handrechnungen wird der pSA mit Hilfe eines Tableaus durchgeführt, das neben dem Gleichungssystem in kanonischer Form auch eine Variable F für den Zielfunktionswert und eine Gleichung für die Zielfunktion (aufgelöst nach F) enthält. In moderner Optimierungssoftware wird der so genannte revidierte pSA eingesetzt, bei dem lediglich ein Teil des Tableaus gespeichert und transformiert werden muss. Die Vorgehensweise des pSA sei an einer Modellinstanz skizzenhaft erläutert (für die Daten s. LP-Modell). Das Starttableau enthält die Daten der kanonischen Form, die BV sind als Zeilenköpfe vermerkt. Die letzte Zeile enthält die Zielfunktion, in der die Zielfunktionskoeffizienten cj der Variablen xj mit negativem Vorzeichen eingetragen werden. In der ersten Iteration wird x2 als neue BV ausgewählt, da ihre Aufnahme in die Basis eine Steigerung des Zielfunktionswertes um c2 = 2 pro Einheit des neuen Wertes von x2 ermöglicht, die höher ist als die (Einheits-) Steigerung für x1 um c1 = 1. Somit wird als so genannte Pivotspalte t = 2 gewählt. Wegen des Steigerungspotenzials soll der Wert von x2 möglichst groß sein. Dabei darf jedoch keine bisherige BV negativ werden. Um dies zu gewährleisten, berechnet man die Quotienten qi = bi/ait für alle Zeilen i = 1,...,m. Der kleinste dieser Werte ist der maximal zulässige Wert für x2. Die in der Pivotzeile s = 3 befindliche BV x5 verlässt die Basis, da sie durch die Erhöhung von x2 zu 0 wird. Nun wird das Tableau durch lineare Transformationen so umgeformt, dass es nach der aktuellen Basis aufgelöst ist. Dazu muss unter der neuen BV x2 ein Einheitsvektor entstehen mit der 1 an der Stelle des Pivotelements (s,t), das im Starttableau mit eckigen Klammern markiert ist. Um dies zu erreichen, wird die Pivotzeile durch das Pivotelement geteilt. Von der ersten Zeile wird die Pivotzeile subtrahiert, von der zweiten wird das 9fache der Pivotzeile subtrahiert, und zur F-Zeile wird das 2-fache der Pivotzeile addiert. Tab. 3 zeigt das entstehende sowie ein weiteres Tableau. Die im Endtableau ablesbare Basislösung x =(30,60,10,0,0) mit F(x) = 150 ist optimal, da die F-Zeile keine negative Eintragung mehr enthält, also kein Basistausch eine weitere Verbesserung verspricht.
Vorhergehender Fachbegriff: Simplex-Algorithmus, dualer | Nächster Fachbegriff: Simplex-Methode
Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken
|
|
