|
|
dualer Simplexalgorithmus
I. Charakterisierung: Iteratives Verfahren zur Bestimmung einer optimalen (Basis-)Lösung für dual zulässige kanonische lineare Optimierungssysteme (dual zulässige kanonische Form). - Grundgedanke: Analog zum primalen Simplexalgorithmus wird zu dem betrachteten System, bei dem es sich um ein dual zulässiges, aber primal unzulässiges kanonisches lineares Optimierungssystem handeln muß, eine Folge dual zulässiger kanonischer Formen konstruiert, bis eine auch primal zulässige kanonische Form gefunden ist oder man erkennt, daß keine optimale Lösung existiert. Mit dem Fortschreiten des Verfahrens weisen die kanonischen Formen Basislösungen aus, deren Zielwerte (sofern keine duale Entartung auftritt) immer näher beim Zielwert der gesuchten optimalen Lösung liegen (sofern eine solche Lösung existiert). Allerdings sind sämtliche Basislösungen (mit Ausnahme der optimalen) unzulässig. - Das betrachtete System besitzt überhaupt keine zulässige Lösung, wenn im Laufe der Anwendung des Verfahrens eine Gleichung Gi der Form
und aij > 0 für j = 1, 2,... , n auftritt (vgl. II. Schritt 2).
II. Algorithmus:
Anwendungsvoraussetzungen: Gegeben ist ein dual zulässiges kanonisches Maximierungssystem (Minimierungssystem) der Form:
(Die kanonische Form ist hier wegen der numerisch noch nicht spezifizierten Koeffizienten als solche nicht erkennbar.)
Anwendungsschritte:
(0.1) Markiere die Basisvariablen!
Schritt 1 (optimale Lösung):
(1.1) Gilt bj > 0 für alle i = 1, 2,... ,m?
JA: –> (5.2)!
NEIN: –> (2.1)!
Schritt 2 (keine zulässige Lösung):
(2.1) Gibt es eine Gleichung mit Index i mit bi < 0 und aij > 0 für alle j = 1, 2,... , n?
JA: –> (5.1)!
NEIN: –> (3.1)!
Schritt 3 (Bestimmung des Pivotelementes):
(3.1) Wähle ein p mit bp < 0!
(3.2)
Schritt 4 (dualer Simplexschritt):
(4.1) Setze
(4.2) Markiere die neue Basisvariable!
(4.3) Lösche die Markierung der neuen Nichtbasisvariablen! –> (1.1)!
Endschritt:
(5.1) "Es existiert keine zulässige Lösung." –> (5.3)!
(5.2) "Es liegt eine primal und dual zulässige kanonische Form des betrachteten Optimierungssystems vor. Die ausgewiesene Basislösung ist eine optimale Lösung des Systems ((1), (2), (3), (4))."
(5.3) STOP!
III. Bedeutung: Dual, aber nicht primal zulässige kanonische Optimierungssysteme ergeben sich v. a. im Zusammenhang mit postoptimalen Rechnungen, Sensitivitätsanalysen, parametrischer linearer Optimierung sowie bei der Lösung ganzzahliger Optimierungsprobleme.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
