matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete OptimierungPolyedertheorie
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Optimierung" - Polyedertheorie
Polyedertheorie < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Polyedertheorie: Anwendung
Status: (Frage) beantwortet Status 
Datum: 12:34 Mi 13.04.2011
Autor: sveny-boi

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.



        
Bezug
Polyedertheorie: Antwort
Status: (Antwort) fertig Status 
Datum: 14:41 Mi 13.04.2011
Autor: Al-Chwarizmi


> 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]

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


Bezug
                
Bezug
Polyedertheorie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.



Bezug
        
Bezug
Polyedertheorie: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 14:28 Do 14.04.2011
Autor: sveny-boi

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?

Bezug
                
Bezug
Polyedertheorie: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:20 Fr 29.04.2011
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]