Doppelpost! Beweis Ecke Polyeder Basis

Neue Frage »

lydiabydia Auf diesen Beitrag antworten »
Beweis Ecke Polyeder Basis
Meine Frage:
Guten Morgen,

ich stehe wieder mal bei einem Beweis an und würde mich freuen, wenn mir jemand weiterhelfen kann.

Ein Punkt x?P ist eine Ecke von P genau dann, wenn die zu x gehörende Basis von A linear unabhängig ist.
Wobei P={x|Ax=b,x?0} der zulässige Bereich von dem linearen Programm
maxcT?x, so dass A?x=b,x?0 ist.

Meine Ideen:
Beweis: Sei x eine Ecke von P und I ={i|xi>0}. Angenommen, {a(i)??i?I} wäre lin. abhängig. Dann gibt es Zahlen di, i?I, die nicht alle gleich Null sind, so dass ?i?Idia(i)=0. Setzen wir dj=0 für alle j?{1,.....,n}\I, dann ist
A?d=0 für d=(d1,...,dn)T.
Wir zeigen, dass y=x???d und z=x+??d?P liegen, wobei

?=min{xi|di|???i?I,di ungleich null} >0.

Wg. A?d=0 ist A?y=b=A?z. Sei 1?I?n. Ist i?I, dann ist di=0 und somit yi=0=zi. Ist i?I und di=0, so ist yi=xi=zi. Ist i?I und di?, dann ist ??|di|?xi|di|?|di|=xi und deshalb yi=xi???di?0 und zi=xi+??di?0. Also liegen y und z?P. Die Punkte y und z sind wg ?>0 von x verschieden und es gilt x=12?y+12?z. Also ist x widersprüchlicherweise keine Ecke von P .

Das ist der erste Teil des Beweises.

Zu meinen Fragen:

Zuerst wird d mit 0 Komponenten erweitert um im Rn zu sein, damit eine Multiplikation mit A möglich ist, oder?
A?d=0 ist so, weil es lin. abhängig ist, oder? Also wir gehen davon aus..

Wieso definiert man dann ? so?
Und bei dem y und z schaut man sich einfach Punkte in der näheren Umgebung von x an, ob diese in P liegen, denn dann ist x keine Ecke?

Dann zu yi: Woher kommt das überhaupt? Wie kommen wir darauf, dass das null ist?

Wäre super, wenn mir wer helfen könnte!


Liebe Grüße
smileyyy Auf diesen Beitrag antworten »
RE: Beweis Ecke Polyeder Basis
Meinst du diesen Beweis?:
http://www.onlinemathe.de/forum/Beweis-Ecke-Basis-Polyeder
Neue Frage »
Antworten »



Verwandte Themen

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