Doppelpost! Beweis Ecke Polyeder Basis |
02.12.2014, 17:34 | lydiabydia | Auf diesen Beitrag antworten » |
Beweis Ecke Polyeder Basis 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 |
||
02.12.2014, 17:38 | smileyyy | Auf diesen Beitrag antworten » |
RE: Beweis Ecke Polyeder Basis Meinst du diesen Beweis?: http://www.onlinemathe.de/forum/Beweis-Ecke-Basis-Polyeder |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|