Konvexität lin. Programme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:09 Mi 18.07.2007 | | Autor: | TBS |
| Aufgabe | Zeigen Sie, dass die optimale Lösungsmenge X* eines linearen Programms
Z(x) -> max
u.d.N. A * x = b
x >= 0
konvex ist.
|
Hallo,
könnte mir dabei jemand helfen? Ich versteh nicht wie ich es formal, d.h. für alle Programme zeigen kann! Wäre über einen Lösungsweg sehr dankbar!
Gruß
Julian
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi, es geht so in der Richtung:
zuerst sind alle optimalen Lösungen $x^*$ auch zulässige Lösungen: d.h. sie
lösen Ax=b und x>=0. Weiterhin es kann eine oder mehere optimale Lösungen
geben. Bei nur einer Lösung ist schon alles bewiesen. Bei mehreren Lösungen
bilden sie eine Mannigfaltigkeit im [mm] $R^n$. [/mm] Das sieht man so ein:
nehme x^* und y^* zwei optimle Lösungen. Bilde nun die Gerade:
x^* [mm] +\alpha(y^*-x^*) [/mm] uind [mm] 0=<\alpha<=1. [/mm] Hiermit ergibt sich für deine Zielfunktion, die ja linear ist:
$f(x^* [mm] +\alpha(y^*-x^*))=f(x^*)+\alpha(f(y^*)-f(x^*))$. [/mm] Nun weil
f(x^*)=f(y^*) ergibt das: [mm] f(x^*)+\alpha(f(y^*)-f(x^*))=f(x^*). [/mm] Also sind alle Lösungen auf der Geraden optimal und somit bildet die Lösungsmenge eine konvexe Menge.
bis dann
|
|
|
| |
|
| Status: |
(Korrektur) oberflächlich richtig  | | Datum: | 12:28 Mi 18.07.2007 | | Autor: | TBS |
Danke für die schnelle Antwort! Das reicht also schon für den kompletten Beweis aus? Oder fehlt noch was?
Gruß
Julian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:37 Mi 18.07.2007 | | Autor: | viktory_hh |
Also, ich bin ja auch keine Mathematiker. Meiner Ansicht nach es reicht schon so, aber 100% weiß ich nicht.
|
|
|
| |
|
Hm,
X*=KH [mm] (\{x_{1}, ... , x_{n}\}) [/mm] + KK [mm] (\{k_{1}, ... , k_{n}\})
[/mm]
Wenn du sagst X* ist eine Gerade würde sich das ja aufs zweidimensionale beschränken? Oder bin ich grade auf dem Holzweg?
Und der konvexe Kegel müsste doch auch beachtet werden?
Muss man die Konvexität für das gesamte X* beweisen oder ich langt es dies für KH bzw. KK zu tun?
Gruß
|
|
|
| |
|
Hi, bin neu, sorry. Merk grad ich hätte das ganze besser als Frage deklariert...
|
|
|
| |
|
Hi, meines Wissens ist jede Menge (egal welche Dimension) dann Konvex, wenn die Verbindungsstrecke zw. zwei Punkten der Menge in der Menge liegt. Das habe ich oben gezeigt. Also wars das? oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:58 Fr 20.07.2007 | | Autor: | dormant |
Hi!
Nur eine kleine Anmerkung. Du hast gezeigt, dass auf dem Weg zwischen Optima auf jeden Fall Punkte liegen, die bzgl. der Zielfunktion einen optimalen Wert haben. Was du aber nicht zeigst, und was auch wesentlich ist, ist dass jeder Punkt auf diesem auch tatsächlich zulässig, also Ax=b genügt.
Wie man leicht nachrechnen kann gilt [mm] A(x+\lambda*(y-x))=b, [/mm] falls y, x zulässig und optimal.
Gruß,
dormant
|
|
|
| |
|
| Aufgabe | | Hi, darf ich nicht davon ausgehen, dass das LP (lin. Prog) konvexes Problem ist, und deswegen alle zul"assigen Punkte eine konvexe Menge bilden? Dann muss ich das was du sagst nicht nochmal beweisen oder? |
bis dann
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:45 Fr 20.07.2007 | | Autor: | dormant |
Hi!
Ich verstehe die Frage so: stimmt es automatisch, dass die Menge opt. Lösungen konvex ist, wenn die zulässige Menge konvex ist. Die Antwort ist natürlich - nein, stimmt nicht, da die Lösungsmenge eine Teilmenge der zulässigen ist, und die könnte nicht-konvex sein.
Sollte was anderes gemeint sein, dann bitte um genauere Fragestellung.
Gruß,
dormant
|
|
|
| |
|
| Aufgabe | Hi, ich glaube du verstehst da was falsch. Ich habe oben gezeigt, die optimale Lösungsmenge ist konvex. Was du dort zeigst, ist die Konvexität der Menge der zulässigen Punkte. Die nehme ich schon vorausgesetzt als konvex an  |
Sag, kannst Du mir auch bei dieser Frage helfen:
https://matheraum.de/read?t=284182
Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:09 Fr 20.07.2007 | | Autor: | dormant |
Hi!
> Hi, ich glaube du verstehst da was falsch. Ich habe oben
> gezeigt, die optimale Lösungsmenge ist konvex. Was du dort
> zeigst, ist die Konvexität der Menge der zulässigen Punkte.
Nein, ich zeige die Zulässigkeit der optimalen Lösungsmenge.
> Die nehme ich schon vorausgesetzt als konvex an
Das ist auch i.O., es kann aber trotzdem sein, dass auf dem Weg zwischen zwei optimalen, unzulässige Punkte lauern :)
> Sag, kannst Du mir auch bei dieser Frage helfen:
> https://matheraum.de/read?t=284182
Wenn ich wüsste was [mm] R(A^{t}A) [/mm] bezeichnet, könnte ich das vielleicht.
Gruß,
dormant
|
|
|
| |
|
| Aufgabe | Hi, ich gehe davon aus, dass zwei optimale Lösungen auch zulässig sind!
Da zulässige Menge konvex, sind auch alle auf der Strecke zwischen zulässig!
[mm] \mathcal{R}(A^TA)=\{A^TAx | x\in \mathbb{R}^n\}
[/mm]
Danke |
Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:24 Fr 20.07.2007 | | Autor: | dormant |
Hi!
> Hi, ich gehe davon aus, dass zwei optimale Lösungen auch
> zulässig sind!
> Da zulässige Menge konvex, sind auch alle auf der Strecke
> zwischen zulässig!
Jetzt versteh ich's. Jep, gutes Argument :)
> [mm]\mathcal{R}(A^TA)=\{A^TAx | x\in \mathbb{R}^n\}[/mm]
EDIT:https://matheraum.de/read?t=284182
Das stimmt nicht:
Na dann ist [mm] b\in\mathcal{R} [/mm] mit x=1.
END
Viel mehr gilt das wenn es x, y [mm] \in\IR^{n} [/mm] gibt mit [mm] ay^{t}=A [/mm] und [mm] y^{t}x=1. [/mm] Dann gilt nämlich:
[mm] A^{t}a=b \gdw
[/mm]
[mm] A^{t}ay^{t}=by^{t} \gdw
[/mm]
[mm] A^{t}A=by^{t} \gdw
[/mm]
[mm] A^{t}Ax=by^{t}x=b*1=b.
[/mm]
Gruß,
dormant
|
|
|
|
