Dynamische Programmierung

View all featured content
Nach Datum sortieren Nach Stimmen sortieren
*Audrey* schrieb:
Ich komme irgendwie trotzdem nicht weiter ... kann die F1(X) Spalte & die F2(x) bis Reihe 5 nachvollziehen, danach hört es aber leider schon auf ... kann mir jemand weiterhelfen?
Zum Vergrößern anklicken....

Hmm... wo konkret ist das Problem? Nehmen wir f_2(x) Reihe 6: Es sollen 6 Einheiten produziert werden, da jede Maschine max. 4 Einheiten ausgeben kann, gibt es dazu nur zwei Möglichkeiten: die erste Maschine produziert 4 Einheiten und die zweite 2, oder beide produzieren jeweils 3 Einheiten. Wenn die erste 4 Einheiten produziert und die zweite 2, dann kostet das 47 Geldeinheiten (35+12), wenn beide 3 Einheiten produzieren, kostet das 2*23, also 46 Einheiten, ist also die billigste Variante. Jetzt klarer?
 
Positive Stimme 0 Negative Stimme
Chapeau Claque schrieb:
Danke... hat mir ein großes Fragezeichen weggenommen. Aber noch mal für den Fall, dass 3 Aggregate genommen werden... Das sind ja total viele Kombinationen, die man aufschreiben muss.... eijeijei.
Zum Vergrößern anklicken....

Beim dritten (vierten, fünften, etc.) Aggregat muss man nicht alle Möglichkeiten durchgehen. Wenn beispielsweise das dritte Aggregat berechnet wird, dann ist ja bereits die Minimalkombination bekannt, mit der eine gewisse Menge nur mit Aggregat 1 und 2 produziert wird.


Beispiel aus dem pdf oben:

Gesucht ist F3(7), d.h. die minimalen Kosten für die Produktion von 7 ME unter Einsatz von Aggregat 3.

Hierfür sind 5 Kombinationen oder besser gesagt Konstellationen zu betrachten von denen das Minium gewählt wird, weil Aggregat 3 eben 0, 1, 2, 3 oder 4 ME produzieren kann:

1. Konstellation: x3 = 0 und x - x3 = 7 - 0 = 7.

Das bedeutet Aggregat 3 produziert 0 ME und die restlichen 7 ME werden von den Aggregaten 1 und 2 produziert. Wie 7 ME mit 1 und 2 minimal produziert werden, wurde aber schon berechnet, das ist F2(7) = 58. Die Kombinationen von 1 und 2 müssen hier also nicht nochmals betrachtet werden.

Die Kosten sind K1 = F2(7) + K(0) = 58 + 0 = 58

2. Konstellation: x3 = 1 und x - x3 = 7 - 1 = 6.

Das bedeutet Aggregat 3 produziert 1 ME und die restlichen 6 ME werden von den Aggregaten 1 und 2 produziert. Wie 6 ME mit 1 und 2 minimal produziert werden, wurde aber schon berechnet, das ist F2(6) = 46. Die Kombinationen von 1 und 2 müssen hier also nicht nochmals betrachtet werden.

Die Kosten sind K2 = F2(6) + K(1) = 46 + 12 = 58

3. Konstellation: x3 = 2 und x - x3 = 7 - 2 = 5.

Das bedeutet Aggregat 3 produziert 2 ME und die restlichen 5 ME werden von den Aggregaten 1 und 2 produziert. Wie 5 ME mit 1 und 2 minimal produziert werden, wurde aber schon berechnet, das ist F2(5) = 38.

Die Kosten sind K3 = F2(5) + K(2) = 38 + 15 = 53

4. Konstellation: x3 = 3 und x - x3 = 7 - 3 = 4.

Das bedeutet Aggregat 3 produziert 3 ME und die restlichen 4 ME werden von den Aggregaten 1 und 2 produziert. Wie 4 ME mit 1 und 2 minimal produziert werden, wurde aber schon berechnet, das ist F2(4) = 30.

Die Kosten sind K4 = F2(4) + K(3) = 30 + 23 = 53

5. Konstellation: x3 = 4 und x - x3 = 7 - 4 = 3.

Das bedeutet Aggregat 3 produziert 4 ME und die restlichen 3 ME werden von den Aggregaten 1 und 2 produziert. Wie 3 ME mit 1 und 2 minimal produziert werden, wurde aber schon berechnet, das ist F2(3) = 23.

Die Kosten sind K5 = F2(3) + K(4) = 23 + 35 = 58

Fertig. Mehr Konstellationen gibt es für F3(7) nicht. Das Minimum ist F3(7) = K3 = K4 = 53

Die Rechnung ist also sehr systematisch. Wenn es <n> Intensitätsstufen gibt, muss für Aggregat <m> genau <m> * <n> Zahlen berechnet werden.

In unserem Beispiel im pdf ist <n> = 5 und wir haben 3 Aggregate so dass für

Aggregat 1: 1 * 4 = 4 Zahlen berechnet werden müssen
Aggregat 2: 2 * 4 = 8 Zahlen berechnet werden müssen
Aggregat 3: 3 * 4 = 12 Zahlen berechnet werden müssen

und für jede dieser Zahlen werden immer höchstens die Kosten von <n> Konstellationen berechnet (oder weniger), nämlich je eine Konstellation für die Menge x = 0, 1, 2, ...., <n-1> die das Aggregat produzieren kann, wenn der Rest von den vorherigen Aggregaten produziert werden kann.

Anderes Beispiel in Kurzschreibweise: F3(11)

x3 .... x - x3 ........... K
0 ..... 11 - 0 = 11 .... geht nicht, weil 2 Aggregate höchstens 8 ME produzieren können
1 ..... 10 - 1 = 10 .... geht nicht, weil 2 Aggregate höchstens 8 ME produzieren können
2 ..... 11 - 0 = 9 ..... geht nicht, weil 2 Aggregate höchstens 8 ME produzieren können
3 ..... 11 - 3 = 8 ...... F2(8) + K(3) = 70 + 23 = 93
4 ..... 11 - 4 = 7 ...... F2(7) + K(4) = 58 + 35 = 93

Man erkennt: Für Fx(y) sind immer höchstens 5 Zahlen zu berechnen, egal welche Aggregatsstufe gerade berechnet wird.

Liebe Grüße
 
Positive Stimme 0 Negative Stimme
ChrissiLLB schrieb:
Man erkennt: Für Fx(y) sind immer höchstens 5 Zahlen zu berechnen, egal welche Aggregatsstufe gerade berechnet wird.
Zum Vergrößern anklicken....

Man muss für Fx(y) das Minimum gar nicht berechnen, weil man es schon kennt.

Wenn alle n (2, 3, 4, 5, 6, etc.) Aggregate funktions- und kostengleich sind, dann ist es bekanntlich optimal die Produktionsmenge so aufzuteilen, dass jedes Aggregat denselben Output beisteuert. Wenn die Produktionsmenge x beliebig teilbar ist, dann ist es also optimal, wenn jedes der n Aggregate den Output x/n beisteuert.

Bei dieser Aufgabe ist allerdings das Problem, dass jedes Aggregat nur eine ganzzahlige Menge produzieren kann (z.B. eine Anzahl von Regenschirmen in Stück), d.h. die Produktionsmengen sind nicht beliebig teilbar.

Wenn die Produktionsmenge x ein ganzzahliges Vielfaches p der Anzahl der Anzahl der betrachteten Aggregate n ist, dann ist x = p * n und x/n = p die ganzzahlige Outputmenge, die jedes Aggregat produziert. In unserem Beispiel mit den maximal 3 Aggregaten und den 4 Outputmengen 1, 2, 3, 4 ist damit klar, dass

- Bei Einsatz von 2 Aggregaten (Aggregat 3 werde nicht eingesetzt) für ...

x = 2 gilt: x1 = x2 = 1

x = 4 gilt: x1 = x2 = 2

x = 6 gilt: x1 = x2 = 3

x = 8 gilt: x1 = x2 = 4

- Bei Einsatz von 3 Aggregaten für ...

x = 3 gilt: x1 = x2 = x3 = 1

x = 6 gilt: x1 = x2 = x3 = 2

x = 9 gilt: x1 = x2 = x3 = 3

x = 12 gilt: x1 = x2 = x3 = 4


Hier wird übrigens schon die Regel der Aufgabenstellung angewendet, dass bei Kostengleichheit die Maschinen mit aufsteigender Nummernfolge eingesetzt werden. Denn für x = 8 ist x1 = 0; x2 = x3 = 4 genauso kostenminimal wie x1 = x2 = 4; x3 = 0.

Wenn man nun also die Tabelle aufbaut kann man z.B.

Tabelleneintrag für F2(8): x-x2 = 4; x2 = 4; F2(8) = F1(4) + K(4) = 35 + 35 = 70

Tabelleneintrag für F3(12): x-x3 = 8; x3 = 4; F3(12) = F2(8) + K(4) = 70 + 35 = 105

bestimmen, ohne die einzelnen Möglichkeiten durchrechnen zu müssen.

Wenn die gesamte Produktionsmenge kein Vielfaches der Anzahl der Aggregate ist, muss auch nicht gerechnet werden. Die Produktionsmenge wird dann kostenoptimal so aufgeteilt, dass die Differenzen der Produktionsmengen zwischen den Aggregaten möglichst gering ist, wobei noch die Regel beachtet werden muss, dass bei Kostengleichheit kleine Maschinennummern die größeren Mengen bekommen.

In unserer Aufgabe hier z.B.

x = 7 wird mit 3 Aggregaten kostenoptimal so produziert: x1 = 3; x2 = x3 = 2
x1 = 2; x2 = 3; x3 = 2 wäre zwar genauso optimal, verstößt aber gegen die Regel aus der Aufgabenstellung kleine Maschinennummern zu bevorzugen (für die Eindeutigkeit der Lösung).

Der Tabelleneintrag für F3(7) ist damit: x-x3 = 5; x3 = 2; F3(7) = F2(5) + K(2) = 38 + 15 = 53

x = 7 wird mit 2 Aggregaten kostenoptimal so produziert: x1 = 4; x2 = 3; x3 = 0

Der Tabelleneintrag für F2(7) ist damit: x-x2 = 4; x2 = 3; F2(7) = F1(4) + K(3) = 35 + 23 = 58

x = 8 wird mit 3 Aggregaten kostenoptimal so produziert: x1 = x2 = 3; x3 = 2

Der Tabelleneintrag für F3(8) ist damit: x-x2 = 6; x2 = 3; F3(8) = F2(6) + K(2) = 46 + 15 = 61

Kostenoptimal werden die Mengen also möglichst gleichmäßig auf die gerade betrachteten Aggregate verteilt. Für x = 8 ME mit 3 Aggregaten bekommt jedes Aggregat zunächst 2 ME und die restlichen 8 - 3 * 2 = 2 ME werden dann auf Aggregat 1 und 2 verteilt (Ergebnis: x1 = x2 = 3; x3 = 2).

Liebe Grüße
 
Positive Stimme 0 Negative Stimme
ChrissiLLB schrieb:
- Bei Einsatz von 3 Aggregaten für ...

x = 3 gilt: x1 = x2 = x3 = 1

x = 6 gilt: x1 = x2 = x3 = 2

x = 9 gilt: x1 = x2 = x3 = 3

x = 12 gilt: x1 = x2 = x3 = 4
Zum Vergrößern anklicken....

Einen kleinen Haken gibt es.

Meine Ausführungen stimmen, wenn ein Aggregat tatsächlich eingesetzt wird. Werden beispielsweise für x = 3 ME 2 Aggregate eingesetzt, so ist die Aufteilung x1 = 2; x2 = 1 ME kostenoptimal. Allerdings ist es für x = 3 ME kostengünstiger, das Aggregat 2 gar nicht einzusetzen und die 3 ME mit Aggregat 3 zu produzieren. Es muss also immer geprüft werden, ob der Verzicht auf das jeweilige Aggregat nicht noch kostengünstiger ist.

Mit Aggregat 2 ist F2(3) = F1(2) + K(1) = 15 + 12 = 27

Aber ohne Aggregat 2 wird x = 3 ME nur mit Aggregat 1 erzeugt: x1 = 3 also F1(3) = 23 < 27. Es ist also kostengünstiger 3 ME mit nur einem Aggregat herzustellen. Deshalb ist F2(3) = F1(3) = 23; x-x2 = 3; x2 = 0.

Anderes Beispiel:

x = 3 ME wird mit 3 Aggregaten kostenoptimal so hergestellt: x1 = x2 = x3 = 1.
Das ergibt F3(3) = F2(2) + K(1) = 15 + 12 = 27. Allerdings ist es günstiger 3 ME gar nicht mit Aggregat 3 zu produzieren: F2(3) = 23 < 27. Deshalb ist F3(3) = F2(3) = 23; x-x2 = 3; x3 = 0.

Wenn man F<i>(x) nach dem Verfahren in #9 (mit Aggregat <i>, also x<i> > 0) berechnet, muss immer noch geprüft werden, ob es ohne Aggregat <i> nicht noch günstiger ist (Vergleich mit F<i-1>(x), das ja schon berechnet wurde und in der Tabelle steht). Falls F<i-1>(x) <= F<i>(x), dann ist x<i> = 0 und F<i>(x) = F<i-1>(x).

Liebe Grüße
 
Positive Stimme 0 Negative Stimme
Antworten
Oben