Randfläche von Polyeder < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:25 Mi 09.12.2015 | | Autor: | mathstu |
| Aufgabe | | Zu A [mm] \in \IR^{mxn} [/mm] , m [mm] \ge [/mm] n und b [mm] \in \IR^{m} [/mm] sei das Polyeder X:={x [mm] \in \IR^{n} [/mm] : Ax [mm] \ge [/mm] b} gegeben. Zu einer Indexmenge J [mm] \subseteq [/mm] {1,...,m} bezeichne [mm] M_{J} [/mm] := {x [mm] \in [/mm] X : [mm] a^{(j)}^{T} [/mm] x = [mm] b_{j}, [/mm] j [mm] \in [/mm] J}. Zeigen Sie: Für alle J [mm] \subseteq [/mm] {1,...,m} ist [mm] M_{J} [/mm] eine Randfläche von X oder [mm] M_{J} [/mm] = [mm] \emptyset. [/mm] |
Guten Tag.
Wir haben in der Vorlesung Randflächen folgendermaßen definiert:
Sei R [mm] \not= \emptyset [/mm] und beide Mengen R [mm] \subseteq [/mm] M [mm] \subseteq \IR^{n} [/mm] konvex. Dann heißt R Randfläche von M, wenn [mm] \forall [/mm] x,y [mm] \in [/mm] M: (x,y) [mm] \cap [/mm] R [mm] \not= \emptyset \Rightarrow [/mm] x,y [mm] \in [/mm] R.
Ich habe nun gedacht, dass ich bei dieser Aufgabe vielleicht einen Widerspruchsbeweis machen kann.
Also seien x, y [mm] \in [/mm] X, mit (x,y) [mm] \cap M_{J} \not= \emptyset, [/mm] aber x,y [mm] \not\in M_{J}.
[/mm]
Da x,y [mm] \in [/mm] X gilt: Ax [mm] \ge [/mm] b und Ay [mm] \ge [/mm] b.
Da (x,y) [mm] \cap M_{J} \not= \emptyset \Rightarrow \exists [/mm] z [mm] \in [/mm] (x,y) [mm] \cap M_{J} [/mm] mit [mm] a^{(j)}^{T} [/mm] z = [mm] b_{j}, [/mm] j [mm] \in [/mm] J und z = [mm] \lambda [/mm] x + (1- [mm] \lambda) [/mm] y mit [mm] \lambda \in [/mm] ]0,1[, da die Punkte x und y in (x,y) nicht enthalten sind.
Wir ersetzen z jetzt durch [mm] \lambda [/mm] x + (1- [mm] \lambda) [/mm] y in [mm] a^{(j)}^{T} [/mm] z = [mm] b_{j}:
[/mm]
Dann gilt:
[mm] a^{(j)}^{T}z [/mm]
= [mm] a^{(j)}^{T}(\lambda [/mm] x + (1- [mm] \lambda) [/mm] y)
= [mm] \lambda a^{(j)}^{T}x [/mm] + (1- [mm] \lambda)a^{(j)}^{T}y
[/mm]
= [mm] b_{j}
[/mm]
Für [mm] \lambda [/mm] = 0 gilt : [mm] a^{(j)}^{T}y [/mm] = [mm] b_{j} [/mm] und für [mm] \lambda [/mm] = 1 gilt : [mm] a^{(j)}^{T}x [/mm] = [mm] b_{j} [/mm] (Bei diesem Schritt bin ich mir sehr unsicher, weil ich oben ja [mm] \lambda \in [/mm] ]0,1[ gesetzt habe, aber ich dachte dass man das so machen kann, weil [mm] M_{J} [/mm] konvex ist)
[mm] \Rightarrow [/mm] x,y [mm] \in M_{J} [/mm] ist ein Widerspruch, also gilt hier immer: [mm] \forall [/mm] x,y [mm] \in [/mm] X: (x,y) [mm] \cap M_{J} \not= \emptyset \Rightarrow [/mm] x,y [mm] \in M_{J}.
[/mm]
Falls dies nun nicht gilt, folgt sofort, dass [mm] M_{J} [/mm] = [mm] \emptyset.
[/mm]
Wäre super, wenn jemand mal hier drüber gucken kann und mir sagen kann, ob das so stimmt.
MfG, mathstu
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:01 Mi 09.12.2015 | | Autor: | fred97 |
> Zu A [mm]\in \IR^{mxn}[/mm] , m [mm]\ge[/mm] n und b [mm]\in \IR^{m}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
sei das
> Polyeder X:={x [mm]\in \IR^{n}[/mm] : Ax [mm]\ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
b} gegeben. Zu einer
> Indexmenge J [mm]\subseteq[/mm] {1,...,m} bezeichne [mm]M_{J}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
:= {x [mm]\in[/mm]
> X : [mm]a^{(j)}^{T}[/mm] x = [mm]b_{j},[/mm] j [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
J}. Zeigen Sie: Für alle
> J [mm]\subseteq[/mm] {1,...,m} ist [mm]M_{J}[/mm] eine Randfläche von X oder
> [mm]M_{J}[/mm] = [mm]\emptyset.[/mm]
> Guten Tag.
>
> Wir haben in der Vorlesung Randflächen folgendermaßen
> definiert:
> Sei R [mm]\not= \emptyset[/mm] und beide Mengen R [mm]\subseteq[/mm] M
> [mm]\subseteq \IR^{n}[/mm] konvex. Dann heißt R Randfläche von M,
> wenn [mm]\forall[/mm] x,y [mm]\in[/mm] M: (x,y) [mm]\cap[/mm] R [mm]\not= \emptyset \Rightarrow[/mm]
> x,y [mm]\in[/mm] R.
>
> Ich habe nun gedacht, dass ich bei dieser Aufgabe
> vielleicht einen Widerspruchsbeweis machen kann.
>
> Also seien x, y [mm]\in[/mm] X, mit (x,y) [mm]\cap M_{J} \not= \emptyset,[/mm]
> aber x,y [mm]\not\in M_{J}.[/mm]
Korrekt lautet das so:
seien x, y [mm]\in[/mm] X, mit (x,y) [mm]\cap M_{J} \not= \emptyset,[/mm] , aber x [mm][mm] \not\in M_{J} [/mm] oder y [mm]\not\in M_{J} [/mm]
> Da x,y [mm]\in[/mm] X gilt: Ax [mm]\ge[/mm] b und Ay
> [mm]\ge[/mm] b.
> Da (x,y) [mm]\cap M_{J} \not= \emptyset \Rightarrow \exists[/mm] z
> [mm]\in[/mm] (x,y) [mm]\cap M_{J}[/mm] mit [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j},[/mm] j [mm]\in[/mm] J und
> z = [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y mit [mm]\lambda \in[/mm] ]0,1[, da
> die Punkte x und y in (x,y) nicht enthalten sind.
>
> Wir ersetzen z jetzt durch [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y in
> [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j}:[/mm]
>
> Dann gilt:
> [mm]a^{(j)}^{T}z[/mm]
> = [mm]a^{(j)}^{T}(\lambda[/mm] x + (1- [mm]\lambda)[/mm] y)
> = [mm]\lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y[/mm]
> = [mm]b_{j}[/mm]
Jetzt nutze aus: x [mm] \notin M_J [/mm] oder y [mm] \notin M_J.
[/mm]
Dann bist Du fertig.
FRED
>
> Für [mm]\lambda[/mm] = 0 gilt : [mm]a^{(j)}^{T}y[/mm] = [mm]b_{j}[/mm] und für
> [mm]\lambda[/mm] = 1 gilt : [mm]a^{(j)}^{T}x[/mm] = [mm]b_{j}[/mm] (Bei diesem Schritt
> bin ich mir sehr unsicher, weil ich oben ja [mm]\lambda \in[/mm]
> ]0,1[ gesetzt habe, aber ich dachte dass man das so machen
> kann, weil [mm]M_{J}[/mm] konvex ist)
> [mm]\Rightarrow[/mm] x,y [mm]\in M_{J}[/mm] ist ein Widerspruch, also gilt
> hier immer: [mm]\forall[/mm] x,y [mm]\in[/mm] X: (x,y) [mm]\cap M_{J} \not= \emptyset \Rightarrow[/mm]
> x,y [mm]\in M_{J}.[/mm]
>
> Falls dies nun nicht gilt, folgt sofort, dass [mm]M_{J}[/mm] =
> [mm]\emptyset.[/mm]
>
> Wäre super, wenn jemand mal hier drüber gucken kann und
> mir sagen kann, ob das so stimmt.
>
> MfG, mathstu
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:13 Mi 09.12.2015 | | Autor: | mathstu |
> Da x,y [mm]\in[/mm] X gilt: Ax [mm]\ge[/mm] b und Ay
> [mm]\ge[/mm] b.
> Da (x,y) [mm]\cap M_{J} \not= \emptyset \Rightarrow \exists[/mm] z
> [mm]\in[/mm] (x,y) [mm]\cap M_{J}[/mm] mit [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j},[/mm] j [mm]\in[/mm] J und
> z = [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y mit [mm]\lambda \in[/mm] ]0,1[, da
> die Punkte x und y in (x,y) nicht enthalten sind.
>
> Wir ersetzen z jetzt durch [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y in
> [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j}:[/mm]
>
> Dann gilt:
> [mm]a^{(j)}^{T}z[/mm]
> = [mm]a^{(j)}^{T}(\lambda[/mm] x + (1- [mm]\lambda)[/mm] y)
> = [mm]\lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y[/mm]
> = [mm]b_{j}[/mm]
Jetzt nutze aus: x [mm]\notin M_J[/mm] oder y [mm]\notin M_J.[/mm]
Dann bist Du fertig.
FRED
Da x [mm] \not\in M_{J} [/mm] und y [mm] \not\in M_{J}, [/mm] folgt :
[mm] a^{(j)}^{T}x \not= b_{j} [/mm] und [mm] a^{(j)}^{T}y \not= b_{j}
[/mm]
[mm] \Rightarrow \lambda a^{(j)}^{T}x [/mm] + (1- [mm] \lambda)a^{(j)}^{T}y \not= b_{j}
[/mm]
[mm] \Rightarrow a^{(j)}^{T}z \not= b_{j} [/mm] und dies ist ein Widerspruch
Habe ich deinen Tipp so richtig umgesetzt?
MfG, mathstu
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:42 Mi 09.12.2015 | | Autor: | fred97 |
> > Da x,y [mm]\in[/mm] X gilt: Ax [mm]\ge[/mm] b und Ay
> > [mm]\ge[/mm] b.
> > Da (x,y) [mm]\cap M_{J} \not= \emptyset \Rightarrow \exists[/mm]
> z
> > [mm]\in[/mm] (x,y) [mm]\cap M_{J}[/mm] mit [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j},[/mm] j [mm]\in[/mm] J und
> > z = [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y mit [mm]\lambda \in[/mm] ]0,1[, da
> > die Punkte x und y in (x,y) nicht enthalten sind.
> >
> > Wir ersetzen z jetzt durch [mm]\lambda[/mm] x + (1- [mm]\lambda)[/mm] y in
> > [mm]a^{(j)}^{T}[/mm] z = [mm]b_{j}:[/mm]
> >
> > Dann gilt:
> > [mm]a^{(j)}^{T}z[/mm]
> > = [mm]a^{(j)}^{T}(\lambda[/mm] x + (1- [mm]\lambda)[/mm] y)
> > = [mm]\lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y[/mm]
> > = [mm]b_{j}[/mm]
>
>
> Jetzt nutze aus: x [mm]\notin M_J[/mm] oder y [mm]\notin M_J.[/mm]
>
> Dann bist Du fertig.
>
> FRED
>
>
>
>
>
>
> Da x [mm]\not\in M_{J}[/mm] und y [mm]\not\in M_{J},[/mm] folgt :
Nein. Nochmal: x [mm]\not\in M_{J}[/mm] oder(!) y [mm]\not\in M_{J},[/mm]
>
> [mm]a^{(j)}^{T}x \not= b_{j}[/mm] und [mm]a^{(j)}^{T}y \not= b_{j}[/mm]
>
> [mm]\Rightarrow \lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y \not= b_{j}[/mm]
Hä ? Nehmen wir an: x [mm] \notin M_J. [/mm] Dann
[mm] a^{(j)}^{T}x [/mm] blablablubber [mm] b_{j}
[/mm]
Was muss für blablablubber hinein ?
FRED
>
> [mm]\Rightarrow a^{(j)}^{T}z \not= b_{j}[/mm] und dies ist ein
> Widerspruch
>
> Habe ich deinen Tipp so richtig umgesetzt?
>
> MfG, mathstu
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:35 Mi 09.12.2015 | | Autor: | mathstu |
> Nein. Nochmal: x [mm]\not\in M_{J}[/mm] oder(!) y [mm]\not\in M_{J},[/mm]
>
>
> >
> > [mm]a^{(j)}^{T}x \not= b_{j}[/mm] und [mm]a^{(j)}^{T}y \not= b_{j}[/mm]
> >
> > [mm]\Rightarrow \lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y \not= b_{j}[/mm]
>
> Hä ? Nehmen wir an: x [mm]\notin M_J.[/mm] Dann
>
> [mm]a^{(j)}^{T}x[/mm] blablablubber [mm]b_{j}[/mm]
>
> Was muss für blablablubber hinein ?
>
> FRED
Wenn wir OE annehmen, dass [mm] x\not\in M_{J} [/mm] dann gilt:
[mm] a^{(j)}^{T}x\not= b_{j}
[/mm]
Und damit will ich nun einen Widerspruch herbeiführen.
Folgt daraus auch schon, dass
[mm] \lambda*a^{(j)}^{T}\not= b_{j} [/mm] ?
Und wenn ja, muss ich das dann in meine Gleichung einsetzen un zu zeigen, dass [mm] a^{(j)}^{T}z\not= b_{j} [/mm] ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:37 Mi 09.12.2015 | | Autor: | fred97 |
>
> > Nein. Nochmal: x [mm]\not\in M_{J}[/mm] oder(!) y [mm]\not\in M_{J},[/mm]
> >
> >
> > >
> > > [mm]a^{(j)}^{T}x \not= b_{j}[/mm] und [mm]a^{(j)}^{T}y \not= b_{j}[/mm]
>
> > >
> > > [mm]\Rightarrow \lambda a^{(j)}^{T}x[/mm] + (1- [mm]\lambda)a^{(j)}^{T}y \not= b_{j}[/mm]
>
> >
> > Hä ? Nehmen wir an: x [mm]\notin M_J.[/mm] Dann
> >
> > [mm]a^{(j)}^{T}x[/mm] blablablubber [mm]b_{j}[/mm]
> >
> > Was muss für blablablubber hinein ?
> >
> > FRED
>
> Wenn wir OE annehmen, dass [mm]x\not\in M_{J}[/mm] dann gilt:
> [mm]a^{(j)}^{T}x\not= b_{j}[/mm]
Ja, das stimmt schon, aber wir wissen mehr !
Es ist x [mm] \in [/mm] X, also Ax [mm] \ge [/mm] b. Das bedeutet
[mm] a^{(j)}^{T}x \ge b_{j} [/mm] für alle j
Ist x [mm] \notin M_J, [/mm] so gilt sogar
[mm] a^{(j)}^{T} [/mm] > [mm] b_{j} [/mm] für alle j [mm] \in [/mm] J.
FRED
> Und damit will ich nun einen
> Widerspruch herbeiführen.
>
> Folgt daraus auch schon, dass
> [mm]\lambda*a^{(j)}^{T}\not= b_{j}[/mm] ?
>
> Und wenn ja, muss ich das dann in meine Gleichung einsetzen
> un zu zeigen, dass [mm]a^{(j)}^{T}z\not= b_{j}[/mm] ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:30 Mi 09.12.2015 | | Autor: | mathstu |
Vielen Dank, ich habe den Beweis mit dem Widerspruch hingekriegt.
MfG, mathstu
|
|
|
|
