Duales Simplexverfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein Verkäufer hat Zuckerstangen(ZS) der Länge 40cm auf Lager. Für eine Veranstaltung benötigt er:
mindestens 4000 ZS der Länge 18cm,
mindestens 5000 ZS der Länge 16cm,
mindestens 3000 ZS der Länge 12cm.
Wie muss der Verkäufer die ZS zuschneiden, damit der Abfall möglichst gering wird?
Hinweis: Es gibt 6 Strategien (Begründung), die 40cm langen ZS zuzuschneiden. Setzen Sie x = [mm] (x_{1},...x_{6})^{T}, [/mm] wobei [mm] x_i [/mm] die Anzahl der Stangen ist, die nach Strategie i zugeschnitten werden. Lösen Sie das Problem mit dem dualen Simplex Verfahren. |
Das duale Simplex-Verfahren kriege ich rein rechnerisch hin.
Mir fehlt der eigentlich Ansatz. Wie sieht die Zielfunktion aus?
Wieso habe ich sechs Strategien?
Wenn ich die Aufgabe so aus dem Bauch lösen sollte, würde ich einfach folgendes machen:
Schneide 1500 Stangen zu in 3000 * 12cm und 1500*16cm. (= 0 Abfall)
Schneide 3500 Stangen zu in 3500*16cm und 3500*18cm = (3500*6cm Abfall)
Schneide 250 Stangen zu in 500*18cm (=250*4cm Abfall)
Summe also:
3000 Stangen á 12cm
5000 Stangen á 16cm
4000 Stangen á 18cm
Abfall:250*4 + 3500*6 =22.000cm
Doch ´ne ganze Menge, aber vom Gefühl her würde ich die Lösung für optimal halten.
Übrigens wusste ich auch gar nicht so genau, wo ich diese Frage thematisch einordnen sollte. Es scheint wohl diesen Themenkomplex Optimierung noch gar nicht zu geben?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:17 Di 26.05.2009 | | Autor: | jini_9791 |
Hallo,
vielleicht hast du 6 Strategien, da du z.B. aus einer Stange entweder:
2 x 18cm
2 x 16cm
3 x 12cm
1 x 18cm und 1 x 16cm
1 x 18cm und 1 x 12cm
oder 1 x 16cm und 2 x 12cm machen könntest.
Der Themenbereich ist nicht neu, schau mal unter "Lineare Optimierung" nach.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:25 Di 26.05.2009 | | Autor: | willikufalt |
OK. Das macht natürlich Sinn und so sollte es dann ja auch stimmen.
Daraus kann man dann die Nebenbedingungen wie folgt ableiten:
min z(x)=...
unter:
[mm] 2x_1 [/mm] + [mm] 0x_2 [/mm] + [mm] 0x_3 [/mm] + [mm] 1x_4 [/mm] + [mm] 1x_5 [/mm] + [mm] 0x_6 \ge [/mm] 4000
[mm] 0x_1 [/mm] + [mm] 2x_2 [/mm] + [mm] 0x_3 [/mm] + [mm] 1x_4 [/mm] + [mm] 0x_5 [/mm] + [mm] 1x_6 \ge [/mm] 5000
[mm] 0x_1 [/mm] + [mm] 0x_2 [/mm] + [mm] 3x_3 [/mm] + [mm] 0x_4 [/mm] + [mm] 1x_5 [/mm] + [mm] 0x_6 \ge [/mm] 3000
Fehlt also noch die Zielfunktion.
Ich bin mir da ehrlich gesagt noch nicht mal 100%ig sicher, was ich genau minimieren muss: Soll einfach nur die Anzahl der verwendeten 40cm ZS minimiert werden, oder nur der Abfall, aus dem keine weiteren ZS der oben angegebenen Größen mehr zugeschnitten werden kann?
Wenn Zweites der Fall ist, ist meine obige "Bauchlösung" sicher falsch, da man dann 5000 40cm Stangen in 5000 16cm Stücke und 10000 12cm Stücke, sowie weitere 2000 40cm Stangen in 4000 18cm Stangen mit einem Gesamtabfall von 8000cm zuschneiden würde.
Wenn Erstes der Fall ist, sollte meine Zielfunktion dann nicht einfach:
min [mm] z(x)=x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 +x_4 +x_5 [/mm] + [mm] x_6 [/mm] lauten?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:33 Di 26.05.2009 | | Autor: | jini_9791 |
also ich denke das du den abfall minimieren sollst (was ja dann nicht aussschliesst, dass du die anzahl der verwendeten stangen minimierst).
ich bin mir grad nicht mehr ganz sicher, wie das mit der zielfunktion ist und will nichts falsche schreiben... sorry
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 16:47 Di 26.05.2009 | | Autor: | willikufalt |
Eigentlich denke ich auch, dass der Abfall minimiert werden soll.
Da müsste die Zielfunktion doch eigentlich:
[mm] z(x)=4x_1 [/mm] + [mm] 8x_2 [/mm] + [mm] 4x_3 [/mm] + [mm] 10x_5 +0x_6
[/mm]
sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:57 Di 26.05.2009 | | Autor: | jini_9791 |
sag mir doch mal kurz wie du auf die koeffizienten der [mm] x_{i} [/mm] gekommen bist
|
|
|
| |
|
Bei der Zielfunktion?
Ich habe einfach jeweils hingeschrieben, wieviel cm bei der jeweiligen Strategie an Abfall überbleiben.
Beispiel: Strategie: 1 40cm = 2*18cm + 4cm Abfall. Koeffizient = 4.
Habe mit diesem Ansatz jetzt mal mein Programm zum dualen Simplexverfahren getestet und bekomme als Ergebnis 8000 heraus.
Das scheint also alles zu passen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:14 Di 26.05.2009 | | Autor: | jini_9791 |
ja stimmt, da stand ich wohl aufm schlauch. supi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 So 31.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
