Lineare Optimierung, Dualitätssatz

Neue Frage »

loiuloiuloiu Auf diesen Beitrag antworten »
Lineare Optimierung, Dualitätssatz
Meine Frage:
Hallo,

Der Satz lautet:

Seien ein primales und das zugehörige duale Programm gegeben

max c^T x , so dass Ax <= b , x>=0
min b^T y, so dass A^T y >= c,y>=0.

Wenn beide Programme jeweils mindestens eine zulässige Lösung haben, dann sind beide Programme lösbar. Für die optimalen Lösungen x* und y* gilt c^Tx* = b^Ty*.
Wenn eines der beiden Programme keine zulässige Lösung besitzt, dann hat keines der beiden Programme eine optimale Lösung.

Meine Ideen:
Zum Beweis und was ich nicht verstehe:
Beim ersten Teil verstehe ich nicht, warum P={...,c^T x - b^T y >= 0}
Wir haben zwei Seiten vorher im Buch, dass immer gilt : c^T x <= b^T y.

Dann verstehe ich nicht, wie man auf die Zeile (24.14) kommt. Man ersetzt quasi y durch u,v,k, da y ja ein vektor ist, der in R^(m+n+1) liegt und dieser kann dann nicht mit A^T multipliziert werden. Also ist u,v,k sozusagen ein "Aufteilen" ?
Aber wieso kommt rechts immer das k dazu?

Beim zweiten Teil verstehe ich nicht, wieso automatisch auch y'+ky eine zulässige Lösung ist? (k >= 0).


Wäre wirklich sehr dankbar, wenn mir wer weiterhelfen kann!!

Will das unbedingt verstehen, freue mich über eine Antwort. LG
Math1986 Auf diesen Beitrag antworten »
RE: Lineare Optimierung, Dualitätssatz
Es sollte doch klar sein, dass die Leute hier nicht wissen, was genau auf "Zeile (24.14)" und so steht. Poste doch bitte den kompletten Beweis.
smileyyy Auf diesen Beitrag antworten »
RE: Lineare Optimierung, Dualitätssatz
Das tut mir leid, ich habe vor lauter grübeln vergessen, den Link zu posten:

http://books.google.at/books?id=I-r1ywhu...P%20%3D&f=false

Seite 332 steht der Beweis.

Liebe Grüße, danke für's Aufmerksam machen!
smileyyy Auf diesen Beitrag antworten »
RE: Lineare Optimierung, Dualitätssatz
Kann hier niemand weiterhelfen?

Bräuchte nur mehr beim zweiten Teil den Grund warum y'+ky auch eine zulässige Lösung ist..
Komm einfach nicht drauf.

Liebe Grüße
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »