Äquivalenz zweier Aussagen < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:22 Do 21.07.2011 | | Autor: | delm |
| Aufgabe | Sei gegeben:
(LP) min [mm] c^{T}x
[/mm]
s.t. Ax [mm] \geq [/mm] b
[mm] x\geq [/mm] 0
und das duale Problem
(DP) max [mm] b^{T}y
[/mm]
s.t. [mm] A^{T}y \leq [/mm] c
[mm] y\geq [/mm] 0
[mm] \overline{x} [/mm] sei eine zulässige Lösung für (LP) und [mm] \overline{y} [/mm] eine zulässige Lösung für (DP).
Beweisen Sie die Äquivalenz der 2 Aussagen:
1) [mm] \overline{x} [/mm] ist optimal für (LP) und [mm] \overline{y} [/mm] ist optimal für (DP)
2) [mm] \overline{x}^{T}(c-A^{T}\overline{y}) [/mm] = 0 und [mm] \overline{y}^{T}(b-A\overline{x}) [/mm] = 0 |
Komme bei der Aufgabe leider nicht weiter... Habe versucht, die Äquivalenz mit der starken Dualität zu beweisen. Finde aber keinen Weg um auf die beiden Gleichungen zu gelangen... Hat einer von euch eine passende Idee?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Das ist der Satz vom komplementären Schlupf:
https://www.fbi.h-da.de/fileadmin/personal/h.meyer/skripte/or/or_teil4.pdf
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:42 Fr 22.07.2011 | | Autor: | delm |
Super! Scheint genau das zu sein, was ich gesucht habe.
Danke dafür :)
|
|
|
|
