Minkowskisumme P+Q < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:03 Di 27.07.2010 | | Autor: | Katrin89 |
| Aufgabe | Beweise:
Die Minkowskisumme S=P+Q zweier beliebiger Polyeder P,Q ist selber ein Polyeder. |
Hi,
ich möchte diesen Beweis mit dem Projektionslemma führen. Dieses besagt:
Projektionslemma:
Die Projektion [mm] P_s [/mm] eines beliebigen Polyeders ist selber ein Polyeder. Es gilt: [mm] P_s=P(C,d)
[/mm]
C,d kann man mit Hilfe des Fourier-Motzkin-Verfahren erhalten, in dem man die Variable, die durch das Projezieren herausfällt, eliminiert.
Kennt jemand diesen Beweis bzw. kann mir helfen?
Viele Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:13 Di 27.07.2010 | | Autor: | fred97 |
Ich würde den Beweis mit dem Darstellungsatz für Polyeder (Satz von Minkowski-Weyl) führen
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:42 Di 27.07.2010 | | Autor: | Katrin89 |
Hi, danke dir.
Meinst du das hier:
P kann man darstellen als:
P=conv(V) + cone(W)?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:34 Di 27.07.2010 | | Autor: | fred97 |
> Hi, danke dir.
> Meinst du das hier:
> P kann man darstellen als:
> P=conv(V) + cone(W)?
>
Ja
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:18 Di 27.07.2010 | | Autor: | Katrin89 |
Hi Fred,
dann würde ich es so machen:
P,Q Polyeder
nach Weyl Minkowski gilt:
P=conv(V)+cone(W)
= P(C,d)+P(B,0)
Q=P(D,a)+P(E,0)
die Polyeder kann man mit dem FM Verfahren bestimmen.
P+Q=P(C,d)+P(B,0)+P(D,a)+P(E,0)
Die Summe ergibt ein Polyeder, oder?
Mmh, da fehlt doch sicher was, oder?
Dass conv(V)=P(C,d) und cone(W)=P(B,0) ist, ergibt sich aus dem FM Verfahren. Lt. Skript kann ich in dem System
Iz-Vx=0
x>=0
die x-Variablen mit dem FM Verfahren eliminieren und erhalte das Gewünschte, das ist ja eine Projektion, also kann ich sagen, dass das wieder Polyeder sind.
Die Summe von Polyedern ist wiederum ein Polyeder.
Was meinst du?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:23 Fr 30.07.2010 | | Autor: | martin2 |
bzw ganz einfach über das Projektionslemma:
Ax [mm] \le [/mm] b
By [mm] \le [/mm] d
z = x+y
Letzteres lässt sich umschreiben in eine Ungleichung mit x,y,z auf der linken Seite und diese Lösungsmenge ist ein Polyeder. Die Minkowski-Summe ist hier einfach die Projektion auf die z Koord. also auch ein Polyeder ;)
|
|
|
|
