Aufgabe 5.3Duale Simplexverfahren
Knut Krause Thomas Siwczyk Stefan Tittel
Technische Universität Dortmund
Fakultät für Informatik
Algorithmen und Datenstrukturen15. Januar 2009
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Aufgabenstellung
Erläutern Sie das duale Simplexverfahren (Tableau-Methode undrevidierte Simplex-Methode) und veranschaulichen Sie dasVerfahren anhand eines Beispiels.
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Motivation
Lösung eines LPs, welches weder in kanonischer Form vorliegt,noch leicht in diese transformiert werden kann
Beispiel
max F(x1, x2) = 2x1 + x2
s. t. x1 + x2 ≥ 83x1 + x2 ≥ 12x1 + x2 ≤ 10x1, x2 ≥ 0
Erweiterung eines LPs, zu dem eine optimale Lösung besteht,die nach der Erweiterung des LPs keine Lösung mehr ist
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Überblick
finde zulässige (nicht notwendigerweise optimale) Basislösungfür das Problem
übergib diese Basislösung an primalen Simplex
falls Start mit dual zulässiger1 Lösung, so ist erste primalzulässige Basislösung zugleich optimal
Schritt 1 und 2 (Wahl von Pivotzeile und Pivotspalte) andersals beim primalen Algorithmus
Schritt 3 (Tableautransformation/Matrizenrechnung) identischzum primalen Algorithmus
1alle Eintragungen in der F-Zeile ≥ 0
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Umwandlung des Ausgangsproblems
Umformung des Ausgangsproblems in kanonische Form mitSchlupfvariablen, aber negative bi zulässig
Beispiel – der kanonischen Form zugrundeliegendes LGS
F = 2x1 + x2
x3 = x1 + x2 − 8x4 = 3x1 + x2 − 12x5 = −x1 − x2 + 10
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Start-Tableau/-Matrix
für Tableau-Methode:
x1 x2 x3 x4 x5 bi
x3 −1 −1 1 −8x4 −3 −1 1 −12x5 1 1 1 10
F −2 −1 0 0 0 0
für revidierte Simplex-Methode:
−1 −1 1 0 0 0 −8−3 −1 0 1 0 0 −121 1 0 0 1 0 10−2 −1 0 0 0 1 0
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Wahl der Pivotzeile
Voraussetzung
Basislösung eines LPs (muss nicht zulässig sein); aktuelleEintragungen im Simplextableau seien mit a′ij , b
′
i , c′
j bezeichnet
1 gibt es kein b′i < 0: zulässige Basislösung liegt vor ⇒ Abbruch
2 sonst: wähle Zeile s mit kleinstem b′s als Pivotzeile (beimehreren mit gleichem kleinsten Wert wähle beliebige)
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Wahl der Pivotspalte
1 gibt es kein a′sj < 0 in Pivotzeile s: Problem hat keinezulässige Basislösung ⇒ Abbruch des gesamten Verfahrens
2 ansonsten wähle Spalte t mit
c ′ta′st
= max{ c ′j
a′sj
∣
∣
∣ j = 1, . . . , n mit a′st < 0}
als Pivotspalte
Anmerkung
Beim primalen Simplex wird zuerst die Pivotspalte, dann diePivotzeile ausgewählt, beim dualen ist es andersherum.
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Beispiel – Tableau 1
x1 x2 x3 x4 x5 bi
x3 −1 − 1 1 −8x4 − 3 − 1 1 − 12x5 1 1 1 10
F −2 − 1 0 0 0 0
1 Test: Basis-Lösung zulässig? Nein: x3 = −8 und x4 = −12!
2 bi = −12 ist minimal, Zeile 2 wird Pivotzeile
3c′
1
a′21
= −2−3
= 23
undc′
2
a′22
= −1−1
= 1⇒ Spalte 2 wird Pivotspalte
4 a′22 wird Pivotelement
Jetzt: Transformation (wie beim primalen Simplex)!
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Beispiel – Tableau 2
x1 x2 x3 x4 x5 bi
x3 2 1 −1 4x2 3 1 −1 12x5 − 2 − 1 1 − 2
F 1 0 0 −1 0 12
1 Test: Basis-Lösung zulässig? Nein: x5 = −2!
2 bi = −2 ist minimal, Zeile 3 wird Pivotzeile
3 a′31 ist einzige Auswahlmöglichkeit, Spalte 1 wird Pivotspalte
4 a′31 wird Pivotelement
Jetzt: Transformation (wie beim primalen Simplex)!
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Beispiel – Tableau 3
x1 x2 x3 x4 x5 bi
x3 1 1 2
x2 1 12
32
9
x1 1 −12−
12
1
F 0 0 0 −12
12
11
1 Test: Basis-Lösung zulässig? Ja! Nun primaler Simplex:
x1 x2 x3 x4 x5 bi
x3 1 1 2x4 2 1 3 18x1 1 1 1 10
F 0 1 0 0 2 20
Optimal: x1 = 10, x3 = 2, x4 = 18, x2 = x5 = 0,F = 20
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Gliederung
1 Aufgabenstellung und Motivation
2 Erläuterung und BeispielAllgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
A1
−1 −1 1 0 0 0 −8
−3 −1 0 1 0 0 −12
1 1 0 0 1 0 10
−2 −1 0 0 0 1 0
x1 x2 x3 x4 x5 F bi
B1
−1 1 0 0
−1 0 0 0
1 0 1 0
−1 0 0 1
x2 x3 x5 F
x2
x3
x5
F
B−11
0 −1 0 0
1 −1 0 0
0 1 1 0
0 −1 0 1
x2 x3 x5 F
x2
x3
x5
F
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
A1 · B−11
3 1 0 −1 0 0 12
2 0 1 −1 0 0 4
−2 0 0 1 1 0 −2
1 0 0 −1 0 1 12
x1 x2 x3 x4 x5 F bi
B2
3 1 0 0
2 0 1 0
−2 0 0 0
1 0 0 1
x1 x2 x3 F
x1
x2
x3
F
B−12
0 0 − 12
0
1 0 32
0
0 1 1 0
0 0 12
1
x1 x2 x3 F
x1
x2
x3
F
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren
Aufgabenstellung und MotivationErläuterung und Beispiel
Allgemeines VorgehenTableau-MethodeRevidierte Simplex-Methode
A2 · B−12
1 0 0 − 12− 1
20 1
0 1 0 12
32
0 9
0 0 1 1 1 0 2
0 0 0 − 12
12
1 11
x1 x2 x3 x4 x5 F bi
Lösung ist gültige primale Basislösung
Algorithmusstop
Knut Krause, Thomas Siwczyk, Stefan Tittel Duale Simplexverfahren