duales Optimierungsproblem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Welche Beziehung herrscht bzgl. der schwachen Dualität zwischen einem primalen und dem dazugehörigen dualen Optimierungsproblem? |
Hallo zusammen,
ich beschäftige mich gerade mit der Dualität von Optimierungsproblemen. Meine Frage steht ja bereits oben beschrieben.
Ich denke ich schreibe am besten kurz auf was ich unter einem primalen sowie einem dualen Optimierungsproblem und der schwachen Dualität verstehe.
sei max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b ein lineares Optimierungsproblem, wobei c,x [mm] \in \IR^{n}, [/mm] b [mm] \in \IR^{m} [/mm] und A [mm] \in \IR^{mxn}
[/mm]
Dann ist dieses Problem äquivalent zu dem linearen Optimierungsproblem min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm] und y [mm] \ge [/mm] 0
Es gilt also:
max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b [mm] \gdw [/mm] min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm]
Bzgl. der schwachen Dualität folgt letztlich:
[mm] c^{T}x \le b^{T}y
[/mm]
Nun existieren bzgl. des primalen Problems doch 3 Fälle bzgl. der Lösbarkeit, welche man aus der Darstellung der Lösungsmenge anhand einer Summe mit den Summanden der konvexen Hülle einer Menge und der konischen Hülle einer anderen Menge herleiten kann.
Ich denke anhand dieser Fälle und der schwachen Dualität müssten nun doch ebenfalls 3 Fälle für das duale Problem folgen.
Meinen Überlegungen nach sähen diese wie folgt aus:
1. max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b besitzt keine Lösung [mm] \Rightarrow [/mm] min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm] besitzt keine Lösung. Das ist trivial, da primales und duales Problem äquivalent sind, oder?
2. max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b ist nach oben unbeschränkt [mm] \Rightarrow [/mm] min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm] ist nach oben unbeschränkt, da [mm] c^{T}x \le b^{T}y [/mm]
3. [mm] c^{T}x=b^{T}y \Rightarrow [/mm] x und y sind primal bzw. dual optimal, da [mm] c^{T}x \le b^{T}y
[/mm]
Diese Möglichkeiten erscheinen mir logisch. Nun hab ich bzgl. 1. und 2. aber folgende Formulierungen gelesen:
1. max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b besitzt keine Lösung [mm] \Rightarrow [/mm] min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm] besitzt keine Lösung oder ist nach unten unbeschränkt .
2. max [mm] c^{T}x [/mm] s.d. Ax [mm] \le [/mm] b ist nach oben unbeschränkt [mm] \Rightarrow [/mm] min [mm] b^{T}y [/mm] s.d. [mm] y^{T}A=c [/mm] hat keine zulässige Lösung
Stimmt das und falls ja, wie wird das hergeleitet? Außerdem bin ich für Korrekturen meiner Überlegungen dankbar.
VViele Grüße,
Patrick
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 So 06.06.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
