Polyeder < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:52 Do 06.11.2008 | | Autor: | Pacapear |
Hallo zusammen!
Ich komme mit der Definition einer stüzenden Hyperebene überhaupt nicht klar.
Hier erstmal meine Definition:
Sei [mm] P:=\{x\in\IR^n|Ax\le b\} \not=\emptyset [/mm] und [mm] c\in\IR^n\not=0 [/mm] so dass [tex]\delta:=max\{cx|x\in P\}<\infty[/tex] gilt. Man nennt [mm] \{x|cx=\delta\} [/mm] dann stützende Hyperebene von P.
So, irgendwie versteh ich das nicht. Also ich habe ein nicht leeres Polyeder P und einen Vektor c, der auch nicht 0 ist. Nun bilde ich für alle Vektoren x aus dem Polyeder ein Skalarprodukt, in dem ich x und c miteinander multipliziere. Und das größte nenne ich [mm] \delta. [/mm]
[mm] \delta [/mm] ist also nur eine Zahl.
Hab ich das soweit richtig verstanden?
So, nun zum Problem. Die stützende Hyperebene soll nun die Menge aller Vektoren x (wahrscheinlich auch nur die x aus P, oder?) sein, für die gilt, dass c multipliziert mit x genau [mm] \delta [/mm] ergibt.
Aber das kann doch keine Menge sein ![[haee]](/images/smileys/haee.gif "[haee]")
Ich mein, ich habe ein festes c vorgegeben, und mein [mm] \delta [/mm] bereits gefunden. Und [mm] \delta [/mm] ist ja mein maximales Skalarprodukt, welches nur für ein x multipliziert mit c rauskommt. Also erhalte ich als stützende Hyperebene nur einen Vektor, und zwar genau den, für den das Skalarprodukt maximal wird... Irgendwie versteh ich das nicht, wo ist denn jetzt eine Ebene ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
Könnte mir das vielleicht jemand erklären?
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:50 Do 06.11.2008 | | Autor: | felixf |
Hallo Nadine!
> Ich komme mit der Definition einer stüzenden Hyperebene
> überhaupt nicht klar.
>
> Hier erstmal meine Definition:
>
> Sei [mm]P:=\{x\in\IR^n|Ax\le b\} \not=\emptyset[/mm] und
> [mm]c\in\IR^n\not=0[/mm] so dass [tex]\delta:=max\{cx|x\in P\}<\infty[/tex]
> gilt. Man nennt [mm]\{x|cx=\delta\}[/mm] dann stützende Hyperebene
> von P.
>
> So, irgendwie versteh ich das nicht. Also ich habe ein
> nicht leeres Polyeder P und einen Vektor c, der auch nicht
> 0 ist. Nun bilde ich für alle Vektoren x aus dem Polyeder
> ein Skalarprodukt, in dem ich x und c miteinander
> multipliziere. Und das größte nenne ich [mm]\delta.[/mm]
> [mm]\delta[/mm] ist also nur eine Zahl.
> Hab ich das soweit richtig verstanden?
Ja.
Zumindest tust du das soweit ein groesstes Skalarprodukt existiert. Es kann auch sein dass es beliebig grosse gibt; in dem Fall ist [mm] $\delta [/mm] = [mm] \infty$.
[/mm]
> So, nun zum Problem. Die stützende Hyperebene soll nun die
> Menge aller Vektoren x (wahrscheinlich auch nur die x aus
> P, oder?)
Nein, alle aus [mm] $\R^n$.
[/mm]
> sein, für die gilt, dass c multipliziert mit x
> genau [mm]\delta[/mm] ergibt.
>
> Aber das kann doch keine Menge sein
Eine Menge ist das immer :) Du meinst eher keine Ebene?
> Ich mein, ich habe ein festes c vorgegeben, und mein [mm]\delta[/mm]
> bereits gefunden. Und [mm]\delta[/mm] ist ja mein maximales
> Skalarprodukt, welches nur für ein x multipliziert mit c
> rauskommt. Also erhalte ich als stützende Hyperebene nur
> einen Vektor, und zwar genau den, für den das Skalarprodukt
> maximal wird...
Vorsicht. Erstens kann es selbst in $P$ mehrere Vektoren geben, fuer die das Skalarprodukt maximal ist.
Und da die Vektoren nicht nur aus $P$, sondern aus ganz [mm] $\IR^n$ [/mm] sind, gibt es sogar unendlich viele. Und zwar kannst du alle Vektoren nehmen, die orthogonal zu $c$ sind (diese bilden einen $n - 1$-dimensionalen Untervektorraum von [mm] $\R^n$) [/mm] und diese um einen Vektor, fuer den das Skalarprodukt maximal ist, verschieben.
Du bekommst also einen verschobenen Untervektorraum von Dimension $n - 1$, also eine Hyperebene!
Also zu der stuetzenden Hyperebene: du hast einen Vektor $c$ gegeben. Dann schauts du dir eine Hyperebene an, auf der $c$ senkrecht steht, und schiebst die so, dass $P$ ganz auf einer Seite liegt und es Punkte in $P$ gibt, die auf der Hyperebene liegt. Das Ergebnis ist dann die stuetzende Hyperebene von $P$. Wenn du die Hyperebene nie so verschieben kannst, dass $P$ auf einer Seite liegt (weil $P$ in die Richtung $c$ unbeschraenkt ist), dann gibt es sie halt nicht; das ist dann der Fall wenn [mm] $\delta [/mm] = [mm] \infty$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:30 Do 06.11.2008 | | Autor: | Pacapear |
Hallo Felix!
> Eine Menge ist das immer :) Du meinst eher keine Ebene?
Ähm, ja, ich glaube schon 
> Vorsicht. Erstens kann es selbst in [mm]P[/mm] mehrere Vektoren
> geben, fuer die das Skalarprodukt maximal ist.
>
> Und da die Vektoren nicht nur aus [mm]P[/mm], sondern aus ganz [mm]\IR^n[/mm]
> sind, gibt es sogar unendlich viele.
Hmm, ja, ok.
Sieht man ja z.b. an dem Beispiel:
Sagen wir, c ist [mm] \vektor{1 \\ 2} [/mm] und [mm] \delta [/mm] ist 24, dann wäre [mm] \vektor{22 \\ 1} [/mm] ein Vektor, der das erfüllt und auch [mm] \vektor{18 \\ 3}.
[/mm]
Richtig?
> Und zwar kannst du
> alle Vektoren nehmen, die orthogonal zu [mm]c[/mm] sind (diese
> bilden einen [mm]n - 1[/mm]-dimensionalen Untervektorraum von [mm]\R^n[/mm])
> und diese um einen Vektor, fuer den das Skalarprodukt
> maximal ist, verschieben.
Hmm, das versteh ich irgendwie (noch) nicht.
1) Warum bilden die Vektoren, die senkrecht zu c sind, einen (n-1)-dimensionalen Untervektorraum? Irgendwie, alle Vektoren, die senkrecht sind zu c, das ist doch eine normale 2-dimensionale Fläche, oder nicht? Angenommen, c ist aus dem [mm] \IR^9, [/mm] wie kann dann eine 2-dimensionale Fläche ein 8-dimensionaler Unterraum sein?
2) Was genau meinst du mit "um einen Vektor verschieben"? In welche Richtung und wie weit?
> Du bekommst also einen verschobenen Untervektorraum von
> Dimension [mm]n - 1[/mm], also eine Hyperebene!
Hmm, das ergibt sich wahrscheinlich, wenn ich den Absatz davor verstanden habe.
> Also zu der stuetzenden Hyperebene: du hast einen Vektor [mm]c[/mm]
> gegeben. Dann schauts du dir eine Hyperebene an, auf der [mm]c[/mm]
> senkrecht steht, und schiebst die so, dass [mm]P[/mm] ganz auf einer
> Seite liegt und es Punkte in [mm]P[/mm] gibt, die auf der Hyperebene
> liegt. Das Ergebnis ist dann die stuetzende Hyperebene von
> [mm]P[/mm]. Wenn du die Hyperebene nie so verschieben kannst, dass [mm]P[/mm]
> auf einer Seite liegt (weil [mm]P[/mm] in die Richtung [mm]c[/mm]
> unbeschraenkt ist), dann gibt es sie halt nicht; das ist
> dann der Fall wenn [mm]\delta = \infty[/mm] ist.
Was meinst du hier damit, dass P ganz auf einer Seite liegt? Das verstehe ich nicht so ganz. Und wo kann ich das (und all das andere was du mir gesagt hast) in der Definition ablesen?
Ich hab bis hierhin soviel (aus der Definition, in Verbindung mit deinen Erklärungen) verstanden:
1) Ich suche für alle x (also alle Punkte) aus dem Polyeder den maxinamlen Skalarproduktwert und nenne ihn [mm] \delta.
[/mm]
2) Ich suche aus allen Vektoren des gegebenen Raumes die, die multipliziert mit dem c-Vektor das [mm] \delta [/mm] ergeben.
3) Die Menge aller dieser Vektoren ist die stützende Hyperebene.
Nur das mit Punkt 3), dass ist mir noch schleierhaft. Ich kann mir noch nicht so ganz vorstellen, wie eine Menge an Vektoren eine Hyperebene bilden. Betrachte ich die Vektoren als Geraden, die irgendwie ein Polyeder begrenzen? Betrachte ich die Vektoren als Ortsvektoren und sind die zugehörigen Punkte dann Punkte in der (Hyper-)Ebene?
Irgendwie komme ich damit noch nicht klar. Ich bin mir auch gar nicht so sicher, was eine Hyperebene genau ist, ich kann mich nicht daran erinnern, es so explizit gemacht zu haben. Was ich weiß, ist, dass eine Hyperebene in einem n-dimensionalen Raum ein (n-1)-dimensionaler Unterraum ist. Reicht das?
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:40 Fr 07.11.2008 | | Autor: | felixf |
Hallo Nadine!
> > Vorsicht. Erstens kann es selbst in [mm]P[/mm] mehrere Vektoren
> > geben, fuer die das Skalarprodukt maximal ist.
> >
> > Und da die Vektoren nicht nur aus [mm]P[/mm], sondern aus ganz [mm]\IR^n[/mm]
> > sind, gibt es sogar unendlich viele.
>
> Hmm, ja, ok.
> Sieht man ja z.b. an dem Beispiel:
> Sagen wir, c ist [mm]\vektor{1 \\ 2}[/mm] und [mm]\delta[/mm] ist 24, dann
> wäre [mm]\vektor{22 \\ 1}[/mm] ein Vektor, der das erfüllt und auch
> [mm]\vektor{18 \\ 3}.[/mm]
> Richtig?
Genau!
> > Und zwar kannst du
> > alle Vektoren nehmen, die orthogonal zu [mm]c[/mm] sind (diese
> > bilden einen [mm]n - 1[/mm]-dimensionalen Untervektorraum von [mm]\R^n[/mm])
> > und diese um einen Vektor, fuer den das Skalarprodukt
> > maximal ist, verschieben.
>
> Hmm, das versteh ich irgendwie (noch) nicht.
>
> 1) Warum bilden die Vektoren, die senkrecht zu c sind,
> einen (n-1)-dimensionalen Untervektorraum? Irgendwie, alle
> Vektoren, die senkrecht sind zu c, das ist doch eine
> normale 2-dimensionale Fläche, oder nicht? Angenommen, c
> ist aus dem [mm]\IR^9,[/mm] wie kann dann eine 2-dimensionale Fläche
> ein 8-dimensionaler Unterraum sein?
Nein: du betrachtest ja sozusagen das orthogonale Komplement des eindimensionalen Untervektorraums mit Basis $c$, also [mm] $\IR [/mm] c$. Die Dimension vom Komplement ist nach der Dimensionsformel $n - 1$.
Im dreidimensionalen Raum ist $n - 1$ gerade 2, aber ansonsten ist die Menge der Vektoren, die zu $c$ orthogonal ist, hoeher- ($n > 3$) oder niedrigerdimensional ($n = 1, 2$)!
> 2) Was genau meinst du mit "um einen Vektor verschieben"?
> In welche Richtung und wie weit?
In die Richtung von $c$, und zwar um den Abstand [mm] $\frac{\delta}{\| c \|}$.
[/mm]
> > Du bekommst also einen verschobenen Untervektorraum von
> > Dimension [mm]n - 1[/mm], also eine Hyperebene!
>
> Hmm, das ergibt sich wahrscheinlich, wenn ich den Absatz
> davor verstanden habe.
Ich hoffe es mal ;)
> > Also zu der stuetzenden Hyperebene: du hast einen Vektor [mm]c[/mm]
> > gegeben. Dann schauts du dir eine Hyperebene an, auf der [mm]c[/mm]
> > senkrecht steht, und schiebst die so, dass [mm]P[/mm] ganz auf einer
> > Seite liegt und es Punkte in [mm]P[/mm] gibt, die auf der Hyperebene
> > liegt. Das Ergebnis ist dann die stuetzende Hyperebene von
> > [mm]P[/mm]. Wenn du die Hyperebene nie so verschieben kannst, dass [mm]P[/mm]
> > auf einer Seite liegt (weil [mm]P[/mm] in die Richtung [mm]c[/mm]
> > unbeschraenkt ist), dann gibt es sie halt nicht; das ist
> > dann der Fall wenn [mm]\delta = \infty[/mm] ist.
>
> Was meinst du hier damit, dass P ganz auf einer Seite
> liegt? Das verstehe ich nicht so ganz.
Die Hyperebene [mm] $\{ x \mid x c = \delta \}$ [/mm] unterteilt den [mm] $\IR^n$ [/mm] in zwei Teile: [mm] $\{ x \mid x c \le \delta \}$ [/mm] und [mm] $\{ x \mid x c > \delta \}$. [/mm] Nun ist [mm] $\delta$ [/mm] moeglichst klein gewaehlt, so dass $P [mm] \subseteq \{ x \mid x c \le \delta \}$ [/mm] gilt. Dies bedeutet, dass $P$ auf einer Seite von der Hyperebene liegt.
> Und wo kann ich das
> (und all das andere was du mir gesagt hast) in der
> Definition ablesen?
Dazu brauchst du etwas Intuition mit linearer Algebra / analytischer Geometrie (die aus der Schule) im $n$-dimensionalen. (Die Anschauung im 2- oder 3-Dimensionalen reicht im Prinzip schon, versuch's dir doch mal da zu veranschaulichen.)
> Ich hab bis hierhin soviel (aus der Definition, in
> Verbindung mit deinen Erklärungen) verstanden:
>
> 1) Ich suche für alle x (also alle Punkte) aus dem Polyeder
> den maxinamlen Skalarproduktwert und nenne ihn [mm]\delta.[/mm]
Ja.
> 2) Ich suche aus allen Vektoren des gegebenen Raumes die,
> die multipliziert mit dem c-Vektor das [mm]\delta[/mm] ergeben.
Ja.
> 3) Die Menge aller dieser Vektoren ist die stützende
> Hyperebene.
Genau.
> Nur das mit Punkt 3), dass ist mir noch schleierhaft. Ich
> kann mir noch nicht so ganz vorstellen, wie eine Menge an
> Vektoren eine Hyperebene bilden. Betrachte ich die Vektoren
> als Geraden, die irgendwie ein Polyeder begrenzen?
> Betrachte ich die Vektoren als Ortsvektoren und sind die
> zugehörigen Punkte dann Punkte in der (Hyper-)Ebene?
Du betrachtest sie als Ortsvektoren, und die sind dann die Punkte der Hyperebene. (Und eine Hyperebene ist im allgemeinen nicht zweidimensional!)
> Irgendwie komme ich damit noch nicht klar. Ich bin mir auch
> gar nicht so sicher, was eine Hyperebene genau ist, ich
> kann mich nicht daran erinnern, es so explizit gemacht zu
> haben. Was ich weiß, ist, dass eine Hyperebene in einem
> n-dimensionalen Raum ein (n-1)-dimensionaler Unterraum ist.
> Reicht das?
Ja.
LG Felix
|
|
|
|
