Diskrete Optimierung: Konvexe Hülle angeben

06.04.2011, 11:50	fb25	Auf diesen Beitrag antworten »
Diskrete Optimierung: Konvexe Hülle angeben Meine Frage: Hallo und geht es im Fach Diskrete Optimierung um folgende Aufgabe: $\begin{eqnarray} <br /> \left\{ (x,y): ax \leq b+y, x \in \mathbb Z, 0 \leq y \right\} <br /> \end{eqnarray}$ mit $\begin{eqnarray} a,b \in \mathbb Q \end{eqnarray}$ und 0<a Betrachte die obige Menge. Gib die vollständige Ungleichungsbeschreibung der konvexen Hülle dieser Menge an. Meine Ideen: Die konvexe Hülle ist ja die Menge aller endlichen Konvexkombinationen. Von daher müsste ich grafisch alle Ecken miteinander verbinden, glaub ich. Wie genau ich diese Mengen, aber hinschreibe ist mir unklar. Ich denke auf jeden Fall wieder in der Menge muss folgendes sein: $\begin{eqnarray} \left\{ (x,y): ax \leq b+y, x \in \mathbb{Z}, 0 < y \right\} \end{eqnarray}$ Aber ich brauche ja noch eine weitere Beschränkung diese finde ich allerdings nicht so leicht. Bitte helft mir
06.04.2011, 12:11	René Gruber	Auf diesen Beitrag antworten »
Nur mal deutlich nachgefragt: Komponente $\begin{eqnarray} x \end{eqnarray}$ soll ganzzahlig sein, während das für $\begin{eqnarray} y \end{eqnarray}$ nicht gefordert wird, d.h. $\begin{eqnarray} y \end{eqnarray}$ ist beliebig reell ("beliebig" nattürlich nur im Rahmen der anderen Einschränkungen gemeint) ?
06.04.2011, 12:25	fb25	Auf diesen Beitrag antworten »
Ja ich denke das y beliebig sein soll
07.04.2011, 14:10	René Gruber	Auf diesen Beitrag antworten »
Na versuch doch mal für ein paar selbstgewählte Beispiele $\begin{eqnarray} (a,b) \end{eqnarray}$ die Menge $\begin{eqnarray} M(a,b) := \left\{ (x,y): \; ax \leq b+y,\, x \in \mathbb{Z},\, 0 \leq y \right\} \end{eqnarray}$ zu skizzieren. Dass $\begin{eqnarray} M(a,b) \end{eqnarray}$ selbst in seiner konvexen Hülle $\begin{eqnarray} \operatorname{conv}(M(a,b)) \end{eqnarray}$ liegt, ist ja wohl schon nach Definition klar, man könnte leichtfertig $\begin{eqnarray} \operatorname{conv}(M(a,b)) \stackrel{?}{=} \left\{ (x,y): \; ax \leq b+y,\, 0 \leq y \right\} \end{eqnarray}$ vermuten (also $\begin{eqnarray} x \end{eqnarray}$ nicht nur ganzzahlig) vermuten, aber das ist i.a. falsch. Zumindest gilt stets $\begin{eqnarray} \operatorname{conv}(M(a,b)) \subseteq \left\{ (x,y): \; ax \leq b+y,\, 0 \leq y \right\} \end{eqnarray}$ , es muss aber von der rechts stehenden Menge noch ein kleines Stückchen abgeschnitten werden (durch eine zusätzliche Ungleichungsbedingung) - welches das ist, müsstest du der dir nochmals nachdrücklich empfohlenen Skizze entnehmen können.
12.04.2011, 17:55	fb25	Auf diesen Beitrag antworten »
Vielen Dank, jetzt ist mir klar was ich machen muss. Ich hab aber noch eine andere Frage. Was ist eine Facette und für was brauch ich diese bei einem Polyeder? Ich hab zum Beispiel: $\begin{eqnarray} <br /> max \sum\limits_{t \in T} w_t x_t \\<br /> \forall p \in P. \sum\limits_{t: p \in T} x_t \leq 1 \\<br /> \forall t \in T. x_t \in {0,1}<br /> \end{eqnarray}$ Wie kann ich hier die Begriffe "Seitenflächen", "Facetten", "Ecken" und "Polyeder" anwenden.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »