Aufstellen eines Modells < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:12 Sa 24.11.2007 | | Autor: | bob86a |
| Aufgabe | Rundeisenstangen der Länge l = 20 m sind in kürzere Stangen
zu zerschneiden. Benötigt werden:
mindestens 4000 Stück der Länge [mm] l_{1} [/mm] = 9 m,
mindestens 5000 Stück der Länge [mm] l_{2} [/mm] = 8 m,
mindestens 3000 Stück der Länge [mm] l_{3} [/mm] = 6 m.
Stellen Sie ein mathematisches Modell zur Ermittlung eines Zuschnittplanes
mit minimalem Verbrauch an 20 m-Stangen auf. Benutzen Sie als Variablen
die Anzahl der jeweils möglichen Zuschnittvarianten. |
Hallo!
Ich habe bei dieser Aufgabe ein wenig Probleme, ein Modell aufzustellen...
So wie ich das sehe gibt es 6 Zuschnittsvarianten (z.B. 1x [mm] l_{1} [/mm] und 1x [mm] l_{2}), [/mm] sprich meine Zielfunktion hinge von 6 Variablen ab.
Als Zielfunktion habe ich mir [mm] min{z=x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}} [/mm] überlegt... Allerdings weiß ich nicht, wie die Nebenbedingungen aussehen sollen. Kann mir jemand weiterhelfen?
MfG,
Bernd
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:11 Sa 24.11.2007 | | Autor: | koepper |
Hallo,
es handelt sich um das sogenannte CSP (Cutting Stock Problem)
Unter diesem Stichwort findest du im Netz ziemlich viele Infos. Interessant sind insbesondere die aktuellen Arbeiten von Gleb Belov und Valerio de Carvalho.
Poste bitte erstmal die 6 sinnvollen Zuschnittvarianten. Du kannst sie am einfachsten als Vektoren mit je 3 Einträgen darstellen. Offenbar soll eine (ganzzahlige, nichtnegative) Linearkombination dieser Vektoren größer-gleich dem Vektor der Bestellmengen sein. Daraus ergibt sich die Nebenbedingung.
Probleme dieser Art haben typischerweise die sog. IRUP-Eigenschaft (Integer-RoundUp-Property). Das heißt, du bekommst die optimale Lösung schlicht durch sinnvolles Runden der mit dem Simplex-Verfahren ermittelten gebrochenen Lösung.
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:35 Sa 24.11.2007 | | Autor: | Basti86 |
D.h. ich kann 2x 9m nehmen oder 1x9m + 1x8m oder 9m+6m usw.
Damit hätte ich dann folgendes:
x1 [mm] \* \vektor{2 \\ 0 \\ 0} [/mm] + x2 [mm] \* \vektor{1 \\ 1 \\ 0} [/mm] + x3 [mm] \* \vektor{1 \\ 0 \\ 1} [/mm] + x4 [mm] \* \vektor{0 \\ 2 \\ 0} [/mm] + x5 [mm] \* \vektor{0 \\ 1 \\ 2} [/mm] + x6 [mm] \* \vektor{0 \\ 0 \\ 3} [/mm] >= [mm] \vektor{4000 \\ 5000 \\ 3000}
[/mm]
Damit hätte ich dann 3 Gleichungen, jede kann ich mit (-1) multiplizieren, damit aus dem >= ein <= wird und dann kann ich 3 Schlupfvariablen einfügen, um aus den 3 Ungleichungen 3 Gleichungen zu formen.
Am Ende habe ich dann folgendes Modell:
[mm] max\{ <\overrightarrow{1}, \overrightarrow{x}> : \pmat{ -2 & -1 & -1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & -2 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & -2 & -3 & 0 & 0 & 1 } \* \overrightarrow{x} = \vektor{-4000 \\ -5000 \\ -3000}, \overrightarrow{x} >= \overrightarrow{0} \}
[/mm]
Meine Lösungen würden mir dann angeben, wie oft ich den jeweiligen der 6 obigen Schnitte anwenden muss.
Habe ich das jetzt soweit richtig verstanden?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 Sa 24.11.2007 | | Autor: | koepper |
Hallo,
> D.h. ich kann 2x 9m nehmen oder 1x9m + 1x8m oder 9m+6m
> usw.
> Damit hätte ich dann folgendes:
>
> x1 [mm]\* \vektor{2 \\ 0 \\ 0}[/mm] + x2 [mm]\* \vektor{1 \\ 1 \\ 0}[/mm] +
> x3 [mm]\* \vektor{1 \\ 0 \\ 1}[/mm] + x4 [mm]\* \vektor{0 \\ 2 \\ 0}[/mm] +
> x5 [mm]\* \vektor{0 \\ 1 \\ 2}[/mm] + x6 [mm]\* \vektor{0 \\ 0 \\ 3}[/mm] >=
> [mm]\vektor{4000 \\ 5000 \\ 3000}[/mm]
korrekt.
> Damit hätte ich dann 3 Gleichungen, jede kann ich mit (-1)
> multiplizieren, damit aus dem >= ein <= wird und dann kann
> ich 3 Schlupfvariablen einfügen, um aus den 3 Ungleichungen
> 3 Gleichungen zu formen.
schon wahr, aber wozu?
Du sollst ja nicht dieses Problem lösen, sondern dualisieren.
Und das geht besser mit den größer-gleich Bedingungen, wie ich in meiner letzten Antwort schon ausgeführt hatte.
> Am Ende habe ich dann folgendes Modell:
>
> [mm]max\{ <\overrightarrow{1}, \overrightarrow{x}> : \pmat{ -2 & -1 & -1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & -2 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & -2 & -3 & 0 & 0 & 1 } \* \overrightarrow{x} = \vektor{-4000 \\ -5000 \\ -3000}, \overrightarrow{x} >= \overrightarrow{0} \}[/mm]
>
> Meine Lösungen würden mir dann angeben, wie oft ich den
> jeweiligen der 6 obigen Schnitte anwenden muss.
> Habe ich das jetzt soweit richtig verstanden?
ja.
Gruß
Will
|
|
|
|
