www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete OptimierungIntegrale Hülle
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Diskrete Optimierung" - Integrale Hülle
Integrale Hülle < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Integrale Hülle: Ganzzahlige Polyeder
Status: (Frage) beantwortet Status 
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

        
Bezug
Integrale Hülle: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]