Integrale Hülle < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:26 Fr 11.05.2012 | | Autor: | Pacapear |
Hallo zusammen!
Ich habe eine Frage zu integralen Hüllen und ganzzahligen Polyedern.
Als Definition für die integrale Hülle habe ich:
Für ein rationales Polyeder P sei [mm] P_I [/mm] die integrale Hülle, d.h. die konvexe Hülle der ganzzahligen Vektoren in P.
So, also die konvexe Hülle einer Menge X ist ja die Menge aller Konvexkombinationen aus den Vektoren in X, also die Menge aller Linearkombinationen, die ich aus den Vektoren in X bilden kann, vorbei die Summe der Koeffizienten in der Linearkombination gleich 1 sein muss, und jeder Koeffizient größer Null ist, d.h. die Koeffizienten liegen zwischen 0 und 1.
Ist das richtig?
Nehme ich dann für die integrale Hülle nur alle ganzzahligen Vektoren aus meiner Menge X, und bilde damit die Menge der Komvexkombinationen? Dabei können doch aber auch nicht-ganze Vektoren rauskommen, z.B. wenn ich die ganzzahligen Vektoren [mm] x_1=\vektor{1 \\ 1} [/mm] und [mm] x_2=\vektor{3 \\ 4} [/mm] habe, und für [mm] \lambda_1 [/mm] nehme ich [mm] \bruch{3}{4} [/mm] und für [mm] \lambda_2 [/mm] nehme ich [mm] \bruch{1}{4}. [/mm] Dann habe ich [mm] \bruch{3}{4}*\vektor{1 \\ 1}+\bruch{1}{4}*\vektor{3 \\ 4}=\vektor{\bruch{3}{4} \\ \bruch{3}{4}}+\vektor{\bruch{3}{4} \\ 1}=\vektor{\bruch{6}{4} \\ 1\bruch{3}{4}}.
[/mm]
Habe ich die Definition richtig verstanden?
Dann habe ich als Anmerkung, dass offensichtlich gilt, dass [mm] $P_I \subseteq [/mm] P$. Weiter steht dort, dass wenn die andere Inklusion gilt (ich denke es ist $P [mm] \subseteq P_I$ [/mm] gemeint), dass dann das Polyeder P ganzzahlig ist.
Das verstehe ich nicht. Ich habe gedacht, dass $P [mm] \subset P_I$ [/mm] immer gilt, weil in meinen Augen [mm] P_I [/mm] sowohl die Vektoren aus P enthält (nämlich wenn ich in der Konvexkombination den Vektor [mm] $x_1 \in [/mm] P$ darstelle als [mm] $1x_1+0x_2+...+0x_n$, [/mm] analog für alle anderen Vektoren aus P), aber auch noch viele weitere, nämlich die, die ich aus anderen Konvexkombinationen mit anderen Koeffizienten bilden kann.
Ist das falsch so? Scheinbar scheint diese Inklusion ja nicht immer zu gelten... Wieso aber gilt die andere immer?
Wie kann ich mir ganzzahliges Polyeder noch vorstellen? Ein Polyeder ist ja die Menge [mm] $\{ x | Ax \le b \}$, [/mm] muss dann bei einem ganzzahligen Polyeder gelten, dass x eine ganze Zahl ist?
Ich hoffe, ihr könnt mir helfen.
Vielen Dank schonmal.
LG Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:53 Di 22.05.2012 | | Autor: | Stoecki |
> Hallo zusammen!
>
> Ich habe eine Frage zu integralen Hüllen und ganzzahligen
> Polyedern.
>
> Als Definition für die integrale Hülle habe ich:
>
>
> Für ein rationales Polyeder P sei [mm]P_I[/mm] die integrale
> Hülle, d.h. die konvexe Hülle der ganzzahligen Vektoren
> in P.
>
>
> So, also die konvexe Hülle einer Menge X ist ja die Menge
> aller Konvexkombinationen aus den Vektoren in X, also die
> Menge aller Linearkombinationen, die ich aus den Vektoren
> in X bilden kann, vorbei die Summe der Koeffizienten in der
> Linearkombination gleich 1 sein muss, und jeder Koeffizient
> größer Null ist, d.h. die Koeffizienten liegen zwischen 0
> und 1.
>
> Ist das richtig?
ja, ist es
>
> Nehme ich dann für die integrale Hülle nur alle
> ganzzahligen Vektoren aus meiner Menge X, und bilde damit
> die Menge der Komvexkombinationen? Dabei können doch aber
> auch nicht-ganze Vektoren rauskommen, z.B. wenn ich die
> ganzzahligen Vektoren [mm]x_1=\vektor{1 \\ 1}[/mm] und [mm]x_2=\vektor{3 \\ 4}[/mm]
> habe, und für [mm]\lambda_1[/mm] nehme ich [mm]\bruch{3}{4}[/mm] und für
> [mm]\lambda_2[/mm] nehme ich [mm]\bruch{1}{4}.[/mm] Dann habe ich
> [mm]\bruch{3}{4}*\vektor{1 \\ 1}+\bruch{1}{4}*\vektor{3 \\ 4}=\vektor{\bruch{3}{4} \\ \bruch{3}{4}}+\vektor{\bruch{3}{4} \\ 1}=\vektor{\bruch{6}{4} \\ 1\bruch{3}{4}}.[/mm]
>
> Habe ich die Definition richtig verstanden?
ja, das hast du. bei einem ganzzahligen polyeder sind i.A. nur die ecken ganzzahlig. die anderen punkte dürfen durchaus fraktional sein (sind sie auch immer, außer das polyeder hat nur einen punkt)
>
> Dann habe ich als Anmerkung, dass offensichtlich gilt, dass
> [mm]P_I \subseteq P[/mm]. Weiter steht dort, dass wenn die andere
> Inklusion gilt (ich denke es ist [mm]P \subseteq P_I[/mm] gemeint),
> dass dann das Polyeder P ganzzahlig ist.
ja, das stimmt.
>
> Das verstehe ich nicht. Ich habe gedacht, dass [mm]P \subset P_I[/mm]
> immer gilt, weil in meinen Augen [mm]P_I[/mm] sowohl die Vektoren
> aus P enthält (nämlich wenn ich in der Konvexkombination
> den Vektor [mm]x_1 \in P[/mm] darstelle als [mm]1x_1+0x_2+...+0x_n[/mm],
> analog für alle anderen Vektoren aus P), aber auch noch
> viele weitere, nämlich die, die ich aus anderen
> Konvexkombinationen mit anderen Koeffizienten bilden kann.
>
> Ist das falsch so? Scheinbar scheint diese Inklusion ja
> nicht immer zu gelten... Wieso aber gilt die andere immer?
es gilt tatsächlich nur die inklusion [mm] P_I \subseteq [/mm] P immer und gleichheit gilt genau dann, wenn alle ecken von P ganzzahlig sind. hierzu ein einfaches beispiel:
P = [mm] conv(\vektor{0 \\ 0}, \vektor{0 \\ 1,5}) [/mm] (also die konvexe hülle dieser beiden vektoren.
die einzigen ganzzahligen punkte sind:
[mm] \vektor{0 \\ 0} [/mm] und [mm] \vektor{0 \\ 1} [/mm]
damit ist aber [mm] conv(\vektor{0 \\ 0}, \vektor{0 \\ 1} [/mm] ) = [mm] P_I \subset [/mm] P = [mm] conv(\vektor{0 \\ 0}, \vektor{0 \\ 1,5}) [/mm] eine echte teilmenge.
>
> Wie kann ich mir ganzzahliges Polyeder noch vorstellen? Ein
> Polyeder ist ja die Menge [mm]\{ x | Ax \le b \}[/mm], muss dann bei
> einem ganzzahligen Polyeder gelten, dass x eine ganze Zahl
> ist?
>
nein, aber es nuss für alle ecken gelten. meine vorstellung von ganzzahligen polyedern ist immer einfach nur eine menge von ganzzahligen punkten + der bereich, der durch verbindungslinien erreicht werden kann.
> Ich hoffe, ihr könnt mir helfen.
> Vielen Dank schonmal.
>
> LG Nadine
hoffe es hilft dir weiter. ansonsten meld dich einfach noch mal 
gruß bernhard
|
|
|
|
