|
|
primaler Simplexalgorithmus
I. Begriff: Iteratives Verfahren zur Bestimmung einer optimalen (Basis-)Lösung für primal zulässige kanonische lineare Optimierungssysteme (primal zulässige kanonische Form).
II. Grundgedanke: Der p. S. beruht auf der Erkenntnis, daß zu einem (kanonischen) linearen Optimierungssystem auch eine optimale Basislösung existiert, wenn es überhaupt für dieses System eine optimale Lösung gibt. Entsprechend wird bei Anwendung des p. S. zu einem Ausgangssystem, bei dem es sich um ein primal zulässiges kanonisches lineares Optimierungssystem handeln muß, eine Folge primal zulässiger kanonischer Formen dieses Systems konstruiert, wobei man i. d. R. jeweils zu einer solchen kanonischen Form fortschreitet, die eine bessere, nie jedoch eine schlechtere Basislösung ausweist (lösungsneutrale Umformungen). Der Umformungsprozeß beim Übergang von einer kanonischen Form zu einer anderen ist im wesentlichen mit einem Pivotschritt im Rahmen des modifizierten Gauss-Algorithmus identisch, den man auf das Teilsystem ((1), (2)) des betreffenden kanonischen linearen Optimierungssystem ausführt. Im Unterschied zum modifizierten Gauss-Algorithmus wird lediglich das Pivotelement nach einer bestimmten Regel (vgl. V Schritt 3) ausgewählt, die gewährleistet, daß die zu erzeugende nächste kanonische Form ebenfalls primal zulässig ist und keinesfalls eine schlechtere Basislösung ausweist. Da für ein (zulässiges) kanonisches lineares Optimierungssystem nur endlich viele (zulässige) kanonische Formen existieren, gelangt man - sofern keine primale Entartung eintritt - nach endlich vielen Schritten zu einer optimalen kanonischen Form und kann daraus eine optimale Lösung des ursprünglichen Systems ablesen bzw. man erkennt, daß eine derartige Lösung nicht existiert.
III. Bezeichnungsweisen: Das Ausführen des Bündels von lösungsneutralen Umformungen, das erforderlich ist, um von einer primal zulässigen kanonischen Form zu einer anderen überzugehen, heißt in diesem Zusammenhang primaler Simplexschritt.
IV. Sonderfälle: 1. Da das Ausgangssystem voraussetzungsgemäß bereits eine zulässige Lösung ausweist, kann das betrachtete System allenfalls dann keine optimale Lösung besitzen, wenn der Zielwert unbeschränkt ist (vgl. V Schritt 2). Bei ökonomischen Anwendungen ist dieser Fall nicht sehr realistisch; wenn er eintritt, dürfte dies auf eine fehlerhafte Modellformulierung zurückzuführen sein. - 2. Beim Auftreten einer primalen Entartung besteht zumindest theoretisch die Möglichkeit des Kreisens des Simplexalgorithmus. Reale Anwendungen, bei denen ein Kreisen auftrat, wurden bisher aber nicht bekannt. Mit Hilfe einfacher Zusatzvorschriften (vgl. V Schritt 3) auszuschließen.
V. Algorithmus:
Anwendungsvoraussetzungen: Gegeben ist ein lineares Maximierungssystem (Minimierungssystem) in primal zulässiger kanonischer Form:
Hier wegen der numerisch noch nicht spezifizierten Koeffizienten als solches nicht erkennbar.
Anfangsschritt:
(0.1) Markiere die m Basisvariablen!
Schritt 1 (Optimale Lösung)
(1.1) Gilt a0j > 0 (bzw. a0j < 0)
für alle j = 1, ... , n?
Schritt 2 (Unbeschränkter Zielwert):
(2.1) Gibt es eine Variable xq mit a0q < 0 (bzw. a0q > 0) und aiq (5.1)! NEIN: —> (3.1)!
Schritt 3 (Bestimmung des Pivotelements):
(3.1) Wähle ein q mit a0q < 0 (bzw. a0q > 0)!
(3.2) Wähle ein p mit:
Schritt 4 (Primaler Simplexschritt):
(4.1) Setze:
(4.2) Markiere die neue Basisvariable xq!
(4.3) Lösche die Markierung für die neue Nichtbasisvariable! —> (1.1)!
Endschritt:
(5.1) "Der Zielwert des Maximierungs- (bzw. Minimierungs-)Systems ist unbeschränkt." —> (5.3)!
(5.2) "Es liegt eine primal und dual zulässige kanonische Form des Maximierungs (bzw. Minimierungs-)Systems vor. Die ausgewiesene Basislösung ist eine optimale Lösung des Systems ((1), (2), (3), (4))."
(5.3) STOP!
VI. Bedeutung: Der p. S. ist ein wichtiger Baustein von Simplexmethoden zur Bestimmung optimaler Lösungen für lineare Optimierungsprobleme (lineare Optimierung).
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
