Optimierung: spitze Polyeder

12.05.2007, 11:16	Sunwater	Auf diesen Beitrag antworten »
Optimierung: spitze Polyeder Hi... ich soll zeigen, dass für einen Polyeder $\begin{eqnarray} P = \{ x \in \mathbb R^n \| Ax \leq b \} \neq \emptyset \end{eqnarray}$ gilt: P ist spitz genau dann wenn jede Seite von P spitz ist. Irgendwie komme ich einfach nicht so gut mit meiner Notation klar um das Problem zu lösen. Die eine Richtung: P spitz daraus folgt jede Seite von P ist spitz wollte ich über nen Widerspruchsbeweis versuchen... also P sei spitz, d.h. es gibt ein Teilsystem $\begin{eqnarray} A'x \leq b' \end{eqnarray}$ von $\begin{eqnarray} Ax \leq b \end{eqnarray}$ derart, dass die Menge $\begin{eqnarray} \{ x \in P \| A'x = b' \} \end{eqnarray}$ einelementig ist. Desweiteren weiß ich dann, dass der Rang von A' = n ist. betrachte also eine beliebige Seite F von P, die wiederum gegeben ist als die Menge: $\begin{eqnarray} F = \{ x \in P \| A''x = b'' \} \end{eqnarray}$ mit einem Teilsystem $\begin{eqnarray} A''x \leq b'' \end{eqnarray}$ von $\begin{eqnarray} Ax \leq b \end{eqnarray}$ soweit erstmal die Vorarbeit... - wie geht's jetzt weiter?
12.05.2007, 20:04	Abakus	Auf diesen Beitrag antworten »
RE: Optimierung: spitze Polyeder Kannst du zunächst definieren, was "spitz" genau bedeutet für eine Seite (für P hast du es ja bereits) ? Mir ist der Begriff neu. Grüße Abakus
13.05.2007, 16:53	Sunwater	Auf diesen Beitrag antworten »
hi... spitz heißt bei uns, dass das Polyeder eine Ecke hat. und da ja die Seiten eines Polyeders wieder Polyeder sind, können wir von spitzen Seiten reden - das heißt Seiten die wiederum eine Ecke haben. z.B. hat ein Würfel Ecken und jede Seite als Quadrat hat Ecken und jede Kante als Strecke hat Ecken... irgendwie wird der Beweis wahrscheinlich über diese Teilsystemdefinition der Ecke geführt - aber so richtig hab ich's noch nicht hinbekommen
13.05.2007, 18:11	Abakus	Auf diesen Beitrag antworten »
Welcher Zusammenhang besteht zwischen den beiden (Un-)Gleichungssystemen (also Polyeder und Seite) ? Ist das eine vielleicht ein Teilsystem von dem anderen ? Grüße Abakus
13.05.2007, 21:21	Sunwater	Auf diesen Beitrag antworten »
genau - das ist die formale Definition... - man kann es sich so vorstellen, dass man ja einen Polyeder durch eine bestimmte Anzahl von Ungleichungen beschreiben kann. Ersetzt man bei einer oder mehrerer Ungleichungen das Ungleichheitszeichen durch ein Gleichheitszeichen erhält man Beschreibungen für die Seiten des Polyeders. deswegen wie folgt: wenn $\begin{eqnarray} P = \{ x \in \mathbb R^n \| Ax \leq b \} \end{eqnarray}$ ein Polyeder ist und F eine Seite von P, dann existiert ein Teilsystem $\begin{eqnarray} A'x \leq b' \end{eqnarray}$ von $\begin{eqnarray} Ax \leq b \end{eqnarray}$ , so dass $\begin{eqnarray} F = \{ x \in P \| A'x = b'\} \end{eqnarray}$ das ist nur die formale Definition dafür, dass bei F ein paar Ungleichungen sogar mit Gleichheit gefordert werden...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »