Äquivalenz von Problemen < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:52 Do 03.05.2012 | | Autor: | math1987 |
| Aufgabe | Es sei M ⊂ [mm] R^n [/mm] × [mm] R^m. [/mm] Dann heißt die Menge
pr_xM [mm] ={x∈R^n |∃y∈R^m :(x,y)∈M}
[/mm]
(orthogonale) Projektion von M (auf den ”x-Raum“ [mm] R^n). [/mm] (Beispiel:Für [mm] M={(x,y)∈R^2 |x^2+y^2 ≤9}gilt [/mm] pr_xM=[−3,3].)
Weiter seien die Probleme
P1 : min f(x) s.t. (x,y) ∈ M
und
P2 : min f(x) s.t. x ∈ pr_xM [mm] x∈R^n [/mm] gegeben.
Zeigen Sie, dass die Probleme P1 und P2 im folgenden Sinne äquivalent sind: (a) Für jeden optimalen Punkt (x∗,y∗) von P1 ist x∗ optimaler Punkt von P2.
(b) Für jeden optimalen Punkt x∗ von P2 existiert ein y∗ ∈ [mm] R^m, [/mm] so dass (x∗, y∗) optimaler Punkt von P1 ist.
(c) Die Optimalwerte von P1 und P2 stimmen überein.
Bemerkung: Sie können davon ausgehen, dass die auftretenden Optimalpunkte und -werte
existieren. |
Hallo zusammen,
da mir dieses Forum schon häufig gute Denkanstöße geleifert hat, möchte ich es nun selbst mal mit einer Frage versuchen. Folgende Aufgabe muss ich heute Mittag abgeben und ich steh dabei leider etwas auf dem Schlauch.
Für P1:
Mein Ansatz wäre, dass M eine kompakte Menge ist.
Mit dem Satz von Weierstraß kann man zeigen, dass M globalen Minimal bzw. Maximalpunkt besitzt. Jetzt weiß ich allerdings nicht wie ich daraus schließen kann, dass dieser Punkt auch optimal für P2 ist.
Über eine Hilfe wäre ich sehr dankbar.
Viele Grüße,
Sebastian
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:21 Do 03.05.2012 | | Autor: | Stoecki |
> Es sei M ⊂ [mm]R^n[/mm] × [mm]R^m.[/mm] Dann heißt die Menge
> pr_xM [mm]={x∈R^n |∃y∈R^m :(x,y)∈M}[/mm]
> (orthogonale)
> Projektion von M (auf den ”x-Raum“ [mm]R^n).[/mm] (Beispiel:Für
> [mm]M={(x,y)∈R^2 |x^2+y^2 ≤9}gilt[/mm] pr_xM=[−3,3].)
> Weiter seien die Probleme
> P1 : min f(x) s.t. (x,y) ∈ M
> und
> P2 : min f(x) s.t. x ∈ pr_xM [mm]x∈R^n[/mm] gegeben.
>
> Zeigen Sie, dass die Probleme P1 und P2 im folgenden Sinne
> äquivalent sind: (a) Für jeden optimalen Punkt
> (x∗,y∗) von P1 ist x∗ optimaler Punkt von P2.
> (b) Für jeden optimalen Punkt x∗ von P2 existiert ein
> y∗ ∈ [mm]R^m,[/mm] so dass (x∗, y∗) optimaler Punkt von P1
> ist.
> (c) Die Optimalwerte von P1 und P2 stimmen überein.
> Bemerkung: Sie können davon ausgehen, dass die
> auftretenden Optimalpunkte und -werte
> existieren.
> Hallo zusammen,
>
> da mir dieses Forum schon häufig gute Denkanstöße
> geleifert hat, möchte ich es nun selbst mal mit einer
> Frage versuchen. Folgende Aufgabe muss ich heute Mittag
> abgeben und ich steh dabei leider etwas auf dem Schlauch.
>
> Für P1:
>
> Mein Ansatz wäre, dass M eine kompakte Menge ist.
> Mit dem Satz von Weierstraß kann man zeigen, dass M
> globalen Minimal bzw. Maximalpunkt besitzt. Jetzt weiß ich
> allerdings nicht wie ich daraus schließen kann, dass
> dieser Punkt auch optimal für P2 ist.
>
> Über eine Hilfe wäre ich sehr dankbar.
>
> Viele Grüße,
> Sebastian
>
>
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
zu a) da in M mehr zulässige lösungen existieren als in [mm] pr_x(M) [/mm] ist der zielfuntionswert von P1 kleiner oder gleich dem von P2. Zu zeigen ist also, dass er nicht echt kleiner sein kann. tipp: f hängt nur von x ab. das bedeutet was?
zu b): in der a) wurde implizit die Gleichheit der zielfunktionswerte gezeigt... naja, warum das y existiert sollte schon relativ klar sein (bemerkung: immerhin hängt f ja nur von x ab)
die c) ist im prinzip oben bereits erschlagen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:34 Do 03.05.2012 | | Autor: | math1987 |
Super, damit komm ich weiter. Vielen Dank für die schnelle Hilfe!
|
|
|
|
