Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt

03.07.2014, 17:04

Matheneuling1991

Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt

Hallo zusammen,

Ich habe eine Frage zu Polytopen..
Ein Polytop von der Definition und Aussehen ist klar; Solange das im zweidimensionalen ist und die Zahlen schön gerade sind ist kann man die Polytope auch sehr einfach zeichnen und kann auch aus lin. Ungleichungen die Ecken bestimmen bzw. aus Ecken(oder allgemeiner der konvexen Hülle von Punkten Kon(p1,p2,p3...)) die Ungleichungen bestimmen, wobei dann natürlich nicht alle Punkte auch Eckpunkte sein müssen.

Jetzt sitze ich gerade an einer Aufgabe, wie ich die konvexe Hülle von Punkten in lineare Ungleichungen verwandle und andersherum;
Für die Richtung lin. Ungleichungen -> Ecken gab es eine Aufgabe zur Bestimmung des Maximums von einer Funktion mit der Restriktion mehrerer Ungleichungen;
Hier gab es folgendes Verfahren: Es war dreidimensional; Dann hat man immer 3 Ungleichungen genommen und hat das <= durch ein = ersetzt und hat dann den gemeinsamen Punkt bestimmt; Dies hat man für alle 3er Kombinationen von Ungleichungen gemacht;
Dann hat man mehrere potentielle Ecken, die man in die Funktion einsetzt und eins davon ist das Maximum(evtl. auch die Verbindungsstrecke von mehreren)
Nun stellt sich mir die Frage, ob das System immer funktioniert?
Und wenn wir z.B. im R^4 sind, muss ich dann z.B. 4 Gleichungen gleichsetzen?
Und was ist, wenn die Gleichungen keinen gemeinsamen Punkt haben oder wenn sie linear abhängig haben und z.B. eine Gerade als Lösungsmenge haben?
Und kann es sein, dass manche dieser Schnittpunkte gar keine Ecken sind sondern innere Punkte oder Punkte außerhalb des Polytops?
Wie kann ich diese Punkte aussortieren?

Für die Rückrichtung von Punkten nach Ungleichung habe ich keine Ahnung, kann da jemand helfen? unglücklich

Freue mich über jede Antwort.. smile

Auch eine Antwort zu einem Teil meiner Fragen ist sehr gerne gesehen! smile

Danke!!

04.07.2014, 16:27

Math1986

Auf diesen Beitrag antworten »

RE: Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt
Wie willst du das Polytop im R^4 zeichnerisch darstellen?

Im R^3 definiert dir jede Gleichung eine Ebene, und eine Ungleichung entspricht eben der Menge unterhalb bzw. überhalb dieser Ebene.

Die Lösung des Optimierungsproblems ist im Allgemeinen nicht eindeutig. Ist es eindeutig, so wird es in einer Ecke angenommen, ist es nicht eindeutig dann immer auf einer Seitenflächen, also der konvexen Hülle mehrerer Eckpunkte.
Das gilt in dieser Form auch im R^4.

Das Prinzip des Gleichsetzens funktioniert im Mehrdimensionalen nicht. Hier liefert der Simplex-Algorithmus eine Lösung des Problems oder stellt die Unlösbarkeit fest.

04.07.2014, 17:35

Matheneuling1991

Auf diesen Beitrag antworten »

Erstmal vielen Dank für deine Antwort; smile

Ich weiß, sich ein vierdimensionales Objekt vorzustellen kann recht schwierig zu sein und das Malen noch viel schwerer;
Aber durch das Zurückführen auf Gleichungen von zwei Dimensionen, wo für eine Ecke trivialerweise ein Schnittpunkt von zwei Geraden benötigt wird und von drei Dimensionen, wo für eine Ecke trivialerweise ein Schnittpunkt von drei Geraden benötigt wird würde es als logische Schlussfolgerung durchaus Sinn machen, dass man für den R^n immer n Geraden gleichsetzt um daraus eine mögliche Ecke zu gewinnen?
Also funktioniert das für eine Dimension größer 3 nicht mehr?

Das Simplexverfahren ist natürlich das deutlich einfache und bessere Verfahren, nur kann ich mich bei der Klausur nicht darauf verlassen, dass ich das auf diese Weise berechnen darf..

Zur Richtung: Ecken -> Ungleichungen; Kann ich dir mal eine Aufgabe dazu schicken? Will vielleicht nur die Uniaufgabe nicht gerade hier direkt öffentlich posten, weil ich nicht weiß, ob dies so gerne gesehen ist..

04.07.2014, 20:57

Matheneuling1991

Auf diesen Beitrag antworten »

RE: Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt
Da es dir lieber im Thema ist, hier also die Aufgabe;

Ich habe ein Polytop aus den folgenen Punkten $\begin{eqnarray*} P_1=\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, P_2=\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}, P_3=\begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix}, P_4=\begin{pmatrix} 1 \\ -1 \\ -1 \end{pmatrix}, P_5=\begin{pmatrix} -1 \\ 1 \\ 1 \end{pmatrix}, P_6=\begin{pmatrix} -1 \\ -1 \\ 1 \end{pmatrix}, P_7=\begin{pmatrix} -1 \\ 1 \\ -1 \end{pmatrix}, P_8=\begin{pmatrix} -1 \\ -1 \\ -1 \end{pmatrix}, P_9=\begin{pmatrix} 2 \\ 0 \\ 0 \end{pmatrix} \end{eqnarray*}$

Dies will ich durch lineare Ungleichungen der Form:
$\begin{eqnarray*} \varphi(x) \leq b \end{eqnarray*}$ oder $\begin{eqnarray*} \varphi(x) \geq b \end{eqnarray*}$ darstellen, wobei x ein 3 dimensionaler Vektor ist

darstellen; Zu den ersten 8 Punkten ist das trivial:
$\begin{eqnarray*} x_1 \leq 1,x_2 \leq 1,x_3 \leq 1,x_1 \geq -1, x_2 \geq -1, x_3 \geq -1 \end{eqnarray*}$

Nun will ich den 9. Punkt einbeziehen, hab aber keine Ahnung wie das gehen soll..
Später soll ich dann alle Facetten für k=0,1,2, also die Ecken, die Kanten und die Seiten des Polyeders in der Form:

$\begin{eqnarray*} \varphi(x) = b \end{eqnarray*}$ angeben..

05.07.2014, 12:53

Math1986

Auf diesen Beitrag antworten »

RE: Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt
Nein, das ist eben kein Würfel. Der letzte Punkt liefert dir noch ein pyramiedenförmiges "Dach". Zeichne dir mal diese Punkte in der Ebene, dann wird es klarer.

05.07.2014, 13:37

Matheneuling1991

Auf diesen Beitrag antworten »

Ich habe ja auch nie behauptet, dass es ein Würfel ist, oder? smile

Falls ja, dann tut es mir leid.. Ich weiß natürlich, dass die ersten 8 Gleichungen einen Würfel darstellen und der 9. diesen Würfel dann erweitert;
Sich das räumlich vorzustellen ist denke ich noch sehr gut machbar;
Allerdings soll ich jetzt daraus die Ungleichungen erstellen - und danach auch die Ungleichung für Facetten von k=0(Ecken), k=1(Kanten) und k=2(Ebenen)
Kannst du mir einen Tipp geben?

05.07.2014, 14:50

Math1986

Auf diesen Beitrag antworten »

Du solltest zunächst einmal Gleichungen für die Seitenflächen des Polyeders aufstellen indem du die Ebenengleichungen für jeweils 3 Randpunkte aufstellst.

05.07.2014, 15:42

Matheneuling1991

Auf diesen Beitrag antworten »

Vielen Dank für den Hinweis, das sieht schon sehr gut aus: Es ist also

$\begin{eqnarray*} z-y=2 \end{eqnarray*}$
$\begin{eqnarray*} z-x=2 \end{eqnarray*}$
$\begin{eqnarray*} z+y=2 \end{eqnarray*}$
$\begin{eqnarray*} z+x=2 \end{eqnarray*}$

Daraus kann ich sicherlich dann die Ungleichungen basteln;

Ich nehme an, die 0-dimensionalen Facetten(also Ecken bekomme ich durch das Gleichsetzten dreier Ebenen und die Kanten durch das Gleichsetzen von zwei Ebenen, richtig?
Damit wäre dann die Aufgabe durch etwas Rechenanstrengung gelöst? smile

Nun aber eine Frage: Um die Aufgabe zu lösen braucht es durchaus räumliche Vorstellungskraft, damit man die richtigen Ebenen bestehend aus den richtigen Punkten erstellt(z.B. wäre die Ebene durch z.B. (1,1,-1) und (1,-1,1) und (0,0,2) keine Ebene, die das Polytop beschreibt, weil der Punkt (0,0,2) nur mit den 4 Punkten für z=1 verbunden wird, nicht aber für einen Punkt mit z=-1;
Ebenfalls würde z.B. die Ebene durch die Diagonale (-1,-1,1) (1,1,1), (0,0,2) eine falsche Ebene beschreiben, was man sich leicht vorstellen kann;

Auch bei den Ungleichungen ist es nicht immer leicht ob es hier <= oder >= heißen muss... Drum meine Frage;
So eine Lösung ist doch eigentlich nur bei einfachen Objekten im 3 dimensionalen durchführbar, weil beim 4 dimensionalen oder bei komplizierteren Objekten im 3 dimensionalen es unmöglich erscheint die richtigen Ebenen etc. zu finden, oder?

05.07.2014, 15:52

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Matheneuling1991
Vielen Dank für den Hinweis, das sieht schon sehr gut aus: Es ist also

$\begin{eqnarray*} z-y=2 \end{eqnarray*}$
$\begin{eqnarray*} z-x=2 \end{eqnarray*}$
$\begin{eqnarray*} z+y=2 \end{eqnarray*}$
$\begin{eqnarray*} z+x=2 \end{eqnarray*}$

Daraus kann ich sicherlich dann die Ungleichungen basteln;

Ich nehme an, die 0-dimensionalen Facetten(also Ecken bekomme ich durch das Gleichsetzten dreier Ebenen und die Kanten durch das Gleichsetzen von zwei Ebenen, richtig?
Damit wäre dann die Aufgabe durch etwas Rechenanstrengung gelöst? smile

Wozu gehören die obigen Gleichungen?
Prinzipiell ist das Vorgehen richtig.

Zitat:

Original von Matheneuling1991
Nun aber eine Frage: Um die Aufgabe zu lösen braucht es durchaus räumliche Vorstellungskraft, damit man die richtigen Ebenen bestehend aus den richtigen Punkten erstellt(z.B. wäre die Ebene durch z.B. (1,1,-1) und (1,-1,1) und (0,0,2) keine Ebene, die das Polytop beschreibt, weil der Punkt (0,0,2) nur mit den 4 Punkten für z=1 verbunden wird, nicht aber für einen Punkt mit z=-1;
Ebenfalls würde z.B. die Ebene durch die Diagonale (-1,-1,1) (1,1,1), (0,0,2) eine falsche Ebene beschreiben, was man sich leicht vorstellen kann;

Auch bei den Ungleichungen ist es nicht immer leicht ob es hier <= oder >= heißen muss... Drum meine Frage;
So eine Lösung ist doch eigentlich nur bei einfachen Objekten im 3 dimensionalen durchführbar, weil beim 4 dimensionalen oder bei komplizierteren Objekten im 3 dimensionalen es unmöglich erscheint die richtigen Ebenen etc. zu finden, oder?

Naja im vierdimensionalen wird das Ganze schon sehr hässlich, da hat man dann aber in der Regel den zulässigen Bereich schon durch Ungleichungen gegeben.

05.07.2014, 16:04

Matheneuling1991

Auf diesen Beitrag antworten »

Zu den vier Ebenen durch (0,0,2) und

1: (-1,-1,1),(1,-1,1)
2: (-1,-1,1),(-1,1,1)
3: (-1,1,1),(1,1,1)
4: (1,1,1),(1,-1,1)

06.07.2014, 09:29

Math1986

Auf diesen Beitrag antworten »

Ja, das ist richtig.

Neue Frage »

Antworten »

Polytope - aus Ecken Ungleichungen bestimmen und umgekehrt

Verwandte Themen