disjunkte Polyeder / Halbräume < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Seien P und P* [mm] \subset \IR^n [/mm] nichtleere, disjunke Polyeder.
Zeige: es ex. disjunkte Halbräume H, H*, sodass P [mm] \subset [/mm] H, sowie
P* [mm] \subset [/mm] H*.
Huhu,
also mein Beweis ist folgender:
Ein Polyeder ist der Durchschnitt von endlich vielen abgeschlossenen Halbräumen. Sei also P [mm] \subset [/mm] ( {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \ge [/mm] a } [mm] \cap [/mm] {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \ge [/mm] b } [mm] \cap [/mm] ....... [mm] \cap [/mm] {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \ge [/mm] n } )
(endlich viele)
Angenommen, P* läge ebenfalls im Schnitt dieser Halbräume, dann exisitiere mind. ein x [mm] \in \IR^n [/mm] ,sodass P [mm] \cap [/mm] P* [mm] \not= \emptyset [/mm] , was im widerspruch zur Vor. ist
Daher muss P* im Schnitt der komplementären Halbräume liegen, also
( {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \le [/mm] a } [mm] \cap [/mm] {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \le [/mm] b } [mm] \cap [/mm] ....... [mm] \cap [/mm] {x [mm] \in \IR^n [/mm] | [mm] a^T [/mm] x [mm] \le [/mm] n } ). Wobei ich muss die Halbräume ja disjunkt haben, müsste ich noch argumentieren, dass es mind. ein Halbraum gibt , wo Striktheit gilt, also der offen ist.
meint ihr, das reicht?
Lg,
Eve
P.S. sry hab wohl meine Frage mit in die Aufgabenstellung genommen^^
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:57 Mo 29.04.2013 | | Autor: | hippias |
> Seien P und P* [mm]\subset \IR^n[/mm] nichtleere, disjunke
> Polyeder.
> Zeige: es ex. disjunkte Halbräume H, H*, sodass P > [mm]\subset[/mm]
> H, sowie
> P* [mm]\subset[/mm] H*.
>
>
> Huhu,
>
> also mein Beweis ist folgender:
>
> Ein Polyeder ist der Durchschnitt von endlich vielen
> abgeschlossenen Halbräumen. Sei also P [mm]\subset[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
( {x >[mm]\in \IR^n[/mm]
> | [mm]a^T[/mm] x [mm]\ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
a } [mm]\cap[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{x [mm]\in >\IR^n[/mm] | [mm]a^T[/mm] x [mm]\ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
b } [mm]\cap[/mm]
> ....... [mm]\cap[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{x [mm]\in \IR^n[/mm] | [mm]a^T[/mm] x >[mm]\ge[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
n } )
>
> (endlich viele)
>
> Angenommen, P* läge ebenfalls im Schnitt dieser
> Halbräume, dann exisitiere mind. ein x [mm]\in \IR^n[/mm] >,sodass
> P [mm]\cap[/mm] P* [mm]\not= \emptyset[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
, was im widerspruch zur Vor.
Diese Annahme hat doch gar nichts mit der Aufgabenstellung zu tun.
> ist
>
> Daher muss P* im Schnitt der komplementären Halbräume
> liegen, also
Nein: Es gibt nur mindestens einen Halbraum, in dem $P^{*}$ nicht enthalten ist.
> ( {x [mm]\in \IR^n[/mm] | [mm]a^T[/mm] x [mm]\le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
a } >[mm]\cap[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{x [mm]\in \IR^n[/mm] | [mm]a^T[/mm] x
> [mm]\le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
b } [mm]\cap[/mm] ....... [mm]\cap[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{x [mm]\in \IR^n[/mm] | [mm]a^T[/mm] x [mm]\le[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
n }
> ). Wobei ich muss die Halbräume ja disjunkt haben, müsste
> ich noch argumentieren, dass es mind. ein Halbraum gibt ,
> wo Striktheit gilt, also der offen ist.
Tut mir Leid, das verstehe ich nicht.
>
>
> meint ihr, das reicht?
Nein: Denn ueber die Existenz der disjunkten $H$ und $H^{*}$ hast Du nichts herausgefunden.
>
> Lg,
>
> Eve
>
>
> P.S. sry hab wohl meine Frage mit in die Aufgabenstellung
> genommen^^
>
|
|
|
| |
|
Okay, ich scheine ja ganz auf dem Holzweg zu sein. Wie wäre denn ein richtiger Ansatz?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Mi 01.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
