Beweis, Ecke, Basis lin. unabh < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:16 Do 27.11.2014 | | Autor: | Kosamui |
| Aufgabe | Ein Punkt x [mm] \in [/mm] P ist eine Ecke von P genau dann, wenn die zu x gehörende Basis von A linear unabhängig ist.
Wobei P= { x | A x = b, [mm] x\ge [/mm] 0} der zulässige Bereich von dem linearen Programm
max [mm] c^T [/mm] * x, so dass Ax=b, [mm] x\ge [/mm] 0 ist. |
![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
Datei-Anhang
Im angehängten Bild ist der Beweis. Dazu habe ich einige Fragen. Zuerst geht man davon aus, dass die Basis von A linear abhängig ist und x trotzdem eine Ecke ist. Dann nimmt man (statt üblicherweise [mm] \lambda) [/mm] ein d her, um (da es lin. abh. ist) es als Linearkombination darzustellen.
Der nächste Schritt mit dj =0 ist mir noch nicht ganz klar. Dabei sind alle j gemeint, die nicht in I liegen, also [mm] {1,...,n}\I. [/mm] Wieso setzt man dj=0? Das verstehe ich nicht...
Weiter: Mit y= x - [mm] \theta [/mm] *d und z=x+ [mm] \theta [/mm] *d schaut man sich die Umgebung der Ecke x an, oder? Und schaut, ob es sich auch noch in P befindet. Stimmt das so?
Und wie kommt man dann auf [mm] \theta [/mm] = min {xi/|di| | i [mm] \in [/mm] I, di ungleich null} > 0.
Wie kommt man bei [mm] \theta [/mm] auf xi/|di| ? Bzw. auf den ganzen Term?
Würde mich sehr über Antworten freuen :)
Liebe Grüße :)
Kosamui
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 2 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:25 Fr 28.11.2014 | | Autor: | Kosamui |
Niemand eine Idee? Glg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 So 30.11.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:29 Mo 01.12.2014 | | Autor: | Kosamui |
Niemand eine Idee? LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:37 Mo 01.12.2014 | | Autor: | chrisno |
Vielleicht steigen die Chancen mit einer benutzerfreundlicheren Version die man hier direkt lesen kann. Mich schreckt das Handgeschriebene zu sehr ab, da klicke ich schnell wieder weg.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:18 Mo 01.12.2014 | | Autor: | Kosamui |
Ok danke, leider ist der beweis recht aufwendig zum eintippen ^^. An sich ist es aber fast derselbe Beweis wie auf:
https://lp.uni-goettingen.de/get/text/2153 Lemma 15.3.
Vl kann sich den ja jemand mal anschauen und weiß was dazu.. LG
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 09:52 Di 02.12.2014 | | Autor: | Kosamui |
Guten Morgen,
hatte jetzt die Zeit den Beweis zu tippen :)
Ein Punkt x [mm] \in [/mm] P ist eine Ecke von P genau dann, wenn die zu x gehörende Basis von A linear unabhängig ist.
Wobei P= { x | A x = b, [mm] x\ge [/mm] 0} der zulässige Bereich von dem linearen Programm
max [mm] c^T [/mm] * x, so dass A*x=b, x [mm] \ge [/mm] 0 ist.
Beweis: Sei x eine Ecke von P und I ={ i | [mm] x_{i} [/mm] >0}. Angenommen, {a^(i) | i [mm] \in [/mm] I} wäre lin. abhängig. Dann gibt es Zahlen di, i [mm] \in [/mm] I, die nicht alle gleich Null sind, so dass [mm] \summe_{i \in I} d_{i} [/mm] a^(i) = 0. Setzen wir [mm] d_{j}= [/mm] 0 für alle j [mm] \in [/mm] {1,.....,n} [mm] \setminus [/mm] I , dann ist
A*d=0 für d [mm] =(d_{1},...,d_{n})^T. [/mm]
Wir zeigen, dass y=x- [mm] \theta*d [/mm] und z =x+ [mm] \theta [/mm] *d in P liegen, wobei
[mm] \theta [/mm] = min [mm] (x_{i} /|d_{i}| [/mm] | i [mm] \in [/mm] I, [mm] d_{i} [/mm] ungleich null) > 0.
Wg. A*d=0 ist A*y=b=A*z. Sei 1 [mm] \le [/mm] I [mm] \le [/mm] n. Ist i [mm] \notin [/mm] I , dann ist [mm] d_{i} [/mm] = 0 und somit [mm] y_{i} [/mm] = 0 = [mm] z_{i}. [/mm] Ist i [mm] \in [/mm] I und [mm] d_{i} [/mm] = 0, so ist [mm] y_{i}= x_{i} [/mm] = [mm] z_{i}. [/mm] Ist i [mm] \in [/mm] I und [mm] d_{i} [/mm] != , dann ist [mm] \theta [/mm] * [mm] |d_{i}| [/mm] <= [mm] x_{i} /|d_{i}| [/mm] * [mm] |d_{i}| =x_{i} [/mm] und deshalb [mm] y_{i} =x_{i} [/mm] - [mm] \theta [/mm] * [mm] d_{i} [/mm] >= 0 und [mm] z_{i} =x_{i} [/mm] + [mm] \theta [/mm] * [mm] d_{i} [/mm] >= 0 . Also liegen y und z in P. Die Punkte y und z sind wg [mm] \theta [/mm] >0 von x verschieden und es gilt x= 1/2 * y + 1/2 *z. Also ist x widersprüchlicherweise keine Ecke von P .
Also das ist der erste Teil des Beweises.
Zuerst wird d mit 0 Komponenten erweitert um im [mm] R^n [/mm] 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 [mm] \theta [/mm] 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!
Schönen Tag, kosamui
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Do 04.12.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[a]](uploads/forum/01043292/forum-i01043292-n001.jpg "Dateianhänge"){kind=small}
Datei-Anhang![[a]](uploads/forum/01043292/forum-i01043292-n002.jpg "Dateianhänge"){kind=small}
Datei-Anhang