Dualität, komplementärer Schlupf Flashcards
Definition: Duales Problem
vgl. Folie 186
Satz: Einschließungssatz/Schwache Dualität
Sei A ein Maximierungsproblem mit der zulässigen Lösung (x1, …, xn) und sei B das duale (Minimierungs-) Problem von A mit der zulässigen Lösung (u1, …, un) dann gilt:
z(x1, …, xn) <= zd(u1, …, un)
(Beweis auf Folie 187)
Satz: Starke Dualität
Hat das primale Problem P eine optimale Lösung x, so besitzt das zugehörige duale Problem D eine optimale Lösung u und es gilt zp(x) = zd(u).
(Die optimale Lösung des dualen Problems kann in der ZF-Zeile des primalen Problems abgelesen werden.)
Wahr oder falsch?
Ist das primale Problem unbeschränkt, so besitzt das duale Problem keine zulässige Lösung.
Wahr!
Achtung! Umkehrsatz ist notwendig aber nicht hinreichend
Komplementärer Schlumpf
Welcher Zusammenhang besteht zwischen primalem und dualen Problem im Hinblick auf Variablen und Schlupf?
Variable –> Schlupf
Primal: j-te Variable pos.
–> Dual: Schlupf der j-ten NB ist gleich 0
Dual: i-te Variable pos.
–> Primal: Schlupf der i-ten NB ist gleich 0
Schlupf –> Variable
Primal: Schlupf der i-ten NB pos.
–> Dual: i-te Variable ist gleich 0
Dual: Schlupf der j-ten NB ist pos.
–> Primal: j-te Variable ist gleich 0
Welche Zusammenhänge zwischen primalem und dualem Problem sind möglich?
Primal: unbeschränkt und Dual: unbeschränkt
Primal: unbeschränkt und Dual: keine Lösung
Primal: keine Lösung und Dual: keine Lösung
Primal: keine Lösung und Dual: unbeschränkt
Primal: unbeschränkt und Dual: unbeschränkt (unmöglich)
Primal: unbeschränkt und Dual: keine Lösung (möglich)
Primal: keine Lösung und Dual: keine Lösung (möglich)
Primal: keine Lösung und Dual: unbeschränkt (möglich)
Gib alle wichtigen Aspekte der Transformation von primalem zu dualem Problem wieder.
vgl. Folie 194
Wie ändert sich der ZF-Wert, wenn man eine NB des Dualproblems um eine Einheit lockert?
Es ändert sich der ZF-Wert des primalen Problems. Außerdem ändert sich die Steigung der ZF. Dies kann zwei mögliche Folgen haben:
1) Die optimale Lösung ändert sich nicht
- -> Optimale Lösung in neue ZF einsetzen und neuen ZF-Wert erhalten
2) Die optimale Lösung ändert sich
- -> Primales Problem erneut lösen
(Anmerkung: Um heraus zu finden, in welchem der beiden Fälle man sich befindet, muss man eine Sensitivitätsanalyse durchführen.)
Stelle die Beziehungen zwischen primalen und dualem Problem dar.
optimale Lösung, Unbeschränktheit, Keine Zulässige Lösung etc.
Primales Problem besitzt eine optimale Lösung & Duales Problem besitzt eine optimale Lösung (Äquivalenzbeziehung)
Primales Problem ist unbeschränkt
–> Duales Problem hat keine zulässige Lösung
Duales Problem ist unbeschränkt
–> Primales Problem hat keine zulässige Lösung
Primales Problem hat keine zulässige Lösung
–> Duales Problem ist unbeschränkt oder hat keine zulässige Lösung
Duales Problem hat keine zulässige Lösung
–> Primales Problem ist unbeschränkt oder hat keine zulässige Lösung
Wo kann die Lösung des dualen Problems am Optimaltableau des primalen Problems abgelesen werden?
In der ZF-Zeile
Beachte Zusammengehörigkeit primaler und dualer Variablen!
Wo kann die Lösung des primalen Problems am Optimaltableau des dualen Problems abgelesen werden?
In der bi-Zeile
Beachte Zusammengehörigkeit primaler und dualer Variablen!
Beschreibe die Zusammengehörigkeit von primaler und dualer Variable.
i-te Variable und Schlupf der i-ten NB
Alternativ: i-te Schlupfvariable und i-te Variable
Wahr oder falsch?
Die Schlupfvariablen des Dualproblems geben Auskunft darüber, ob die zugehörigen Primalvariablen größer als 0 oder gleich 0 sind.
Falsch!
us > 0 –> x = 0
us = 0 –> x >= 0 (Achtung! Hier kann x = 0 oder x > 0 sein)
(Merksatz: Beim komplementären Schlupf kann man von der einen Variable nie darauf schließen, dass die andere gleich 0 ist! Man kann immer nur darauf schließen, dass eine Variable gleich 0 ist!)
Wahr oder falsch?
Ein primales und das dazugehörige duale Problem können beide unbeschränkt sein.
Falsch!
vgl. Folie 208
