Beweis, Ecke, Basis lin. unabh < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:47 Mo 15.12.2014 | | Autor: | Kosamui |
| Aufgabe | Ein Punkt [mm] x\in [/mm] P ist eine Ecke von P genau dann, wenn die zu x gehörende Basis von A linear unabhängig ist.
Sei P= {x|Ax=b, x [mm] \ge0} [/mm] und bezeichne [mm] a^{(i)} [/mm] die i-te Spalte von A . Sei x Element aus P und I = {i| [mm] x_{i} [/mm] >0} die Menge aller Indizes mit [mm] x_{i} [/mm] >0. Die Menge [mm] {a^{(i)} |i \in I} [/mm] wird die zu x gehörende Basis von A genannt. Für die zu x gehörende Basis von A gilt: [mm] \summe_{i\in I} x_{i} a^{(i)}=b. [/mm] |
Hallo liebe Leute :)
Ich habe den Beweis schon mal gepostet, brauche jetzt aber nochmals eure Hilfe. Ich habe bei der einen Richtung ein Problem beim Beweis:
Sei [mm] {a^{(i)}|i \in I } [/mm] linear unabhängig. Angenommen, es wäre x= [mm] \lambda [/mm] y +(1- [mm] \lambda)z, [/mm] wobei 0< [mm] \lambda [/mm] < 1 und y,z [mm] \in [/mm] P.
Nach Voraussetzung ist x die eindeutige Lösung des lin. Gleichungssystems Ax=b mit [mm] x_{i} [/mm] = 0 für alle i [mm] \not\in [/mm] I. Da y der Gleichung Ay=b genügt, gibt es einen Index i [mm] \not\in [/mm] I mit [mm] y_{i} [/mm] >0. Wg. z [mm] \ge [/mm] 0 ist dann die i-te Komponente von [mm] \lambda [/mm] y +(1- [mm] \lambda)z [/mm] widersprüchlicherweise positiv.
So, das meiste ist klar, nur leider verstehe ich überhaupt nicht, wieso i [mm] \not\in [/mm] I mit [mm] y_{i} [/mm] >0 . Kann mir jemand helfen?
Wäre super !! :)
GLG Kosamui
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:33 Mo 15.12.2014 | | Autor: | Kosamui |
Niemand eine Idee? :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:42 Di 16.12.2014 | | Autor: | abakus |
Crossposting:
http://www.onlinemathe.de/forum/Beweis-Ecke-Basis-Polyeder-1
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:54 Di 16.12.2014 | | Autor: | fred97 |
> Ein Punkt [mm]x\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
P ist eine Ecke von P genau dann, wenn die
> zu x gehörende Basis von A linear unabhängig ist.
> Sei P= {x|Ax=b, x [mm]\ge0}[/mm] und bezeichne [mm]a^{(i)}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
die i-te
> Spalte von A . Sei x Element aus P und I = {i| [mm]x_{i}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>0}
> die Menge aller Indizes mit [mm]x_{i}[/mm] >0. Die Menge [mm]{a^{(i)} |i \in I}[/mm]
> wird die zu x gehörende Basis von A genannt. Für die zu x
> gehörende Basis von A gilt: [mm]\summe_{i\in I} x_{i} a^{(i)}=b.[/mm]
>
> Hallo liebe Leute :)
>
> Ich habe den Beweis schon mal gepostet, brauche jetzt aber
> nochmals eure Hilfe. Ich habe bei der einen Richtung ein
> Problem beim Beweis:
>
> Sei [mm]{a^{(i)}|i \in I }[/mm] linear unabhängig. Angenommen, es
> wäre x= [mm]\lambda[/mm] y +(1- [mm]\lambda)z,[/mm] wobei 0< [mm]\lambda[/mm] < 1 und
> y,z [mm]\in[/mm] P.
> Nach Voraussetzung ist x die eindeutige Lösung des lin.
> Gleichungssystems Ax=b mit [mm]x_{i}[/mm] = 0 für alle i [mm]\not\in[/mm] I.
> Da y der Gleichung Ay=b genügt, gibt es einen Index i
> [mm]\not\in[/mm] I mit [mm]y_{i}[/mm] >0. Wg. z [mm]\ge[/mm] 0 ist dann die i-te
> Komponente von [mm]\lambda[/mm] y +(1- [mm]\lambda)z[/mm]
> widersprüchlicherweise positiv.
>
> So, das meiste ist klar, nur leider verstehe ich überhaupt
> nicht, wieso i [mm]\not\in[/mm] I mit [mm]y_{i}[/mm] >0 . Kann mir jemand
> helfen?
Da y [mm] \in [/mm] P sind alle [mm] y_i \ge [/mm] 0. Nimm an, für alle i [mm] \notin [/mm] I wäre [mm] y_i=0
[/mm]
Wegen Ay=b hätten wir dann neben x eine 2. Lösung des LGS Ax=b mit [mm] x_i=0 [/mm] für alle i [mm] \notin [/mm] I.
Also wäre y=x=z.
FRED
>
> Wäre super !! :)
>
> GLG Kosamui
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:52 Sa 20.12.2014 | | Autor: | Kosamui |
Danke dir !! :)
|
|
|
|
