Polyedertheorie < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Was ist eine Facette und für was brauch ich diese bei einem Polyeder?
b) Es sei folgendes Problem gegeben:
[mm] $\max\limits_{t \in T} w_t x_t $\\
[/mm]
[mm] $\forall [/mm] p [mm] \in [/mm] P : [mm] \sum\limits_{t:p \in T} x_t \leq [/mm] 1$ [mm] \\
[/mm]
[mm] $\forall [/mm] t [mm] \in [/mm] T: [mm] x_t \in \{ 0,1 \}$
[/mm]
Wie kann man hier die Begriffe "Seitenflächen", "Facetten", "Ecken" und "Polyeder" anwenden. |
Denke die Aufgabenstellung ist selbsterklärend. Hab allerdings leider keine Ahnung wie ich die Sachen konkret darauf anwenden kann.
|
|
| |
|
> a) Was ist eine Facette und für was brauch ich diese bei
> einem Polyeder?
Auf "gewöhnliche" Polyeder im [mm] \IR^3 [/mm] angewandt ist wohl
"Facette" = (2-dimensionale) "Seitenfläche".
In einem Artikel zur Polyedertheorie fand ich:
"Eine Facette von P ist definiert als eine maximale
nicht leere echte Seitenfläche von P.
Für jede Facette F von P gilt dim(F) = dim(P)-1."
> b) Es sei folgendes Problem gegeben:
>
> [mm]\max\limits_{t \in T} w_t x_t[/mm][mm] \\[/mm]
> [mm]\forall p \in P : \sum\limits_{t:p \in T} x_t \leq 1[/mm]
> [mm]\\[/mm]
> [mm]\forall t \in T: x_t \in \{ 0,1 \}[/mm]
>
> Wie kann man hier die Begriffe "Seitenflächen",
> "Facetten", "Ecken" und "Polyeder" anwenden.
> Denke die Aufgabenstellung ist selbsterklärend. ![[haee]](/images/smileys/haee.gif "[haee]")
Unter "selbsterklärend" würde ich mir allerdings
was ganz anderes vorstellen ...
Ich sehe jedenfalls überhaupt nicht, was hier
gegeben und was gesucht sein soll !
> Hab allerdings leider keine Ahnung wie ich die Sachen konkret
> darauf anwenden kann.
Teile uns doch bitte erst mal mit, was die Mengen P
(vielleicht Menge der Eckpunkte ??) und T sowie die
Faktoren [mm] x_t [/mm] und [mm] w_t [/mm] bedeuten sollen. Und eben:
was ist denn wirklich gesucht ?
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:23 Mi 13.04.2011 | | Autor: | sveny-boi |
Hier noch ein Zusatz zur Aufgabenstellung.
P: Anzahl der Personen
T: Teams
$ T [mm] \subseteq 2^P [/mm] $
[mm] $w_t \in \mathbb [/mm] R$
Jede Person soll nur in einem Team sein.
[mm] $w_t$ [/mm] ist hier die "Erwünschtheit"
Es gilt weiter: [mm] $\forall [/mm] t [mm] \in [/mm] T: [mm] x_t [/mm] = [mm] \left\{ \begin{array}{ll} 0 & \text{wenn wir Team T nicht waehlen} \\ 1 & \text{Wenn wir Team T waehlen} \end{array} \right\}$
[/mm]
Das sind alle Angaben die dazu gemacht sind. Ich hoffe es ist jetzt klarer.
Und vielen Dank schon mal für die Anmerkung.
|
|
|
| |
|
Ich hab versucht ein bisschen rumzumachen und mir folgenden Fall überlegt:
Zerlege die Menge $P = L [mm] \cup [/mm] R$
Jedes Team bekommt eine Person aus L und eine aus R.
Jetzt versuche ich zu zeigen, dass Alle Ecken der LP-Relaxierung dieses Falles ganzzahlig sind.
Also die LP-Relaxierung macht aus der Bedingung [mm] $\sum x_t \leq [/mm] 1$ die Bedingung [mm] $\sum x_t [/mm] = 1$.
Ich denke dass funktioniert wohl am leichtesten über einen Widerspruch. Also dass ich annehme, dass eine Ecke der LP-Relaxierung nicht ganzzahlig ist.
Aber wie genau ich jetzt weiter vorgehen soll, weiß ich leider nicht.
Habt ihr Ideen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Fr 29.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
