Dynamische Programmierung

Dr Franke Ghostwriter
kann mir jemand erklären, wie man die Tabelle erweitert auf den 2. Block? Wobei ich ja anfangs die Lösung noch nachvollziehen kann, dann aber geben sich mir wieder Rätsel auf. Hat jemand dazu ne gute Erklärung gefunden?

Gruß
Silvana
 
Silvana,

die dynamische Programmierung ist im Übungsbuch in Aufgabe 6.9
ausführlich für einige Tabellenelemente erklärt.

Zu beachten ist noch, dass die Ergebnisse manchmal nicht eindeutig
sind, d.h. es gibt mehrere Kombinationen, die zu minimalen Kosten führen.
In diesem Fall sollen die Maschinen in aufsteigender Reihenfolge eingesetzt
werden.

Beispiel: Übungsaufgabe 22:

F2(6)
= Min ( F1(6-x) + K2(x) ) für 0 <= x <= 6

Einsetzen aller möglichen x ergibt:

= Min (F1(6)+K2(0);F1(5)+K2(1);F1(4)+K2(2);F1(3)+K2(3);F1(2)+K2(4);F1(1)+K2(5);F1(0)+K2(6))

Die F1(x) können aus der bisher gefüllten Tabelle abgelesen werden:

= Min (90+K2(0);63+K2(1);48+K2(2);42+K2(3);32+K2(4);18+K2(5);0+K2(6))

Die K2(x) ergeben sich aus der Aufgabenstellung:

= Min (90+0;63+18;48+32;42+42;32+48;18+63;0+90)

= Min (90;81;80;84;80;81;90) = 80 und damit x = 2 oder x = 4

Hier wird jetzt x = 2 gewählt. Damit ist M-x = 4

Gruß
Joachim
 
Ja, und wie errechne ich diese mengen?
ich komme zwar auf die fx werte aber x bleibt mir noch unerschlossen

frage mich ja auch, wie cih die werte zu berechnen habe, wenn ich in der davorstehenden spalte in der entsprechenden zeile keine werte mehr gegeben habe

irgendwie bin ich zu blöd dafür

björn
 
Leider ist es hier etwas schwierig eine Tabelle einzufügen - mal sehen

F1(x) F2(x) x-x2 x2
x
0 0 0 0 0
1 8 8 1 0
2 10 10 2 0
3 16 16 3 0
4 25 20 2 2
5 32 26 3 2
6 32 3 3



ein kleines Beispiel.

Spalte x-x2:
Menge x=1 Du produzierst die eine Einheit des Gutes auf der Maschine 1, also x (produzierte Gesamtmenge - hier : 1) minus produzierte Menge auf Maschine 2 (hier 0) = 1

Spalte x2
für x = 1
Menge auf Maschine 2 produziert: 0

Gleiches für x = 6
hier ist es günstiger auf jeweils einer Maschine je 3 Einheiten zu produzieren, da 2 * Kosten für 3 Einheiten= 2* 16=32 günstiger ist als jede andere Kombination, wie z.B. 4+2 oder 5+1

x-x2 ist also
Gesamtmenge = 6 minus Menge der auf Maschine 2 produzierten Einheiten (hier 3) = 3

x2
ist dann auch 3, da auf Maschine 2, 3 Einheiten hergestellt werden

PS: Ich hoffe. Du kannst Dir diese Tabelle "entzerren" , ich habe schon befürchtet, dass die Darstellung nicht klappt.
 
Super, danke

hoffe, dass ich auch verstehe, wie ich die mengen berechne, dinicht mehr in der ersten spalte aufgelistet sind, also wenn die menge so groß ist, dass diese die kapazität einer maschine übersteigt
 
Jo danke, der groschen ist bereits gefallen

die tabelle kann ich erstellen,dann muss ich ja jetzt nur noch herausfinden, wie ich die jeweiuls günstigste variante finde, auch bei mehr als 2 maschinen
 
Das ist auch nicht schwer, angenommen jede Maschine kann 5 Einheiten produzieren...

x=1 bis X = 10 hast Du dann schon über zwei Maschinen erstellt, nun kommt die dritte Maschine hinzu...

angenommen, es geht um x = 8

dann berechnest Du die Kosten für 8 + 0 (das wäre lt. meiner Tabelle 48+0=48)

weitere Möglichkeit wäre 7+1 (Kosten: 41+8= 49)
weitere Möglichkeit wäre 6+2 (Kosten 32+10=42)
5+3 (Kosten 26+16= 42) die 5 setzen sich aus x1=3, x2=2 zusammen siehe die ersten Spalten der Liste
4+4 (Kosten 20+25=45)

bei Kostengleichheit ist immer die Kapazität der vorhergehenden Maschine zu nutzen also ist die günstigste Variante 6 + 2

setzt sich zusammen aus x1=3, x2=3 und x3=2
 
ich sehe es richtig, wenn ich die werte für f3 und x3 berechne, gar nciht in die spalten für x1 und f1 gehen muss?

nicht ganz 😉 , Du brauchst die F1-Werte für die Kosten, die auf der Maschine drei entstehen.

Wenn alle drei Maschinen produzieren, dann setzen sich die Werte aus der voroptimierten Spalte F2 (Kombination von Maschine 1 und 2) und der Spalte F1 (für die Kosten der Maschine 3) zusammen.
 
nicht ganz 😉 , Du brauchst die F1-Werte für die Kosten, die auf der Maschine drei entstehen.

Wenn alle drei Maschinen produzieren, dann setzen sich die Werte aus der voroptimierten Spalte F2 (Kombination von Maschine 1 und 2) und der Spalte F1 (für die Kosten der Maschine 3) zusammen.



du meinst f3 für de kosten der maschine 3?
es reicht aber, wenn ich bis spalte f2 zurückgehe, da f2 ja bereits inkl. f1 voroptimiert wurde?

und wie erkenne ich, ob es besser ist, alle drei maschinen einzusetzen, zb bei x=10 und jede maschine kann max 5 einhieten produzieren?
durch ausrechnen, probieren nur, oder?

in jedem fall seit ihr eine große hilfe und habt es mir ermöglicht mein heutiges lernziel zu erreichen

möchte proko in rund 5 tagen à je 2 bis 3h schaffen (inkl. klasuraufgaben)

nächste woche ist dann pet ande rreihe uind dann habe ich 2,5 wochen urlaub für
infi, marketing (bereits das schwerpunktfachgeschrieben, daher dafür nur 2 tage einkalkuliert) und steuern, ich hoffe, dass die zeit dafür reicht und ich so noch 5 tage zum wiederholen habe

was denkt ihr?
 
mit 2 Maschinen komme ich ja klar, aber ich habe Probleme dabei, wann und wie ich eine dritte Maschine einkalkuliere (uch muss im Hinterkopf doch immer behalten, wenn zb die max. Intensiät einer Maschine 4 ist und ich 10 ME produzieren möchte, dass ich mit den beiden ersten Maschinen max 8 produzieren kann und mit der dritten 2, ich könnte diese 1 ME aber auch mit 6 Einheiten auf den ersten beiden Maschinen und 4 Einheiten auf der 3. Maschine produzieren, oder?
`
Oder muss man diese sog. Sprungstellen berücksichtigen?
Bzw. wie erkenne ich die Sprungstellen?
 
bjoern,
du musst dann halt schauen was kostengünstiger ist
zbs wenn man 10 me betrachtet und die maschinen jew.eine int. von 4 haben gibt es folgende möglichkeiten
4m1+4m2+2m3 oder
3m1+3m2+4m3
dann musst du schauen was diese intensitäten kosten(ich weiss jetzt net welche Aufgabe du meinst,ich erfinde mal was)
2 int. kosten 8
angenommen 3 int.kosten 10
4 int. kosten 15

so dann hätte ich bei der ersten möglichkeit kosten von
15+15+8=38
2 möglickeit kosten von
10+10+15=35
also nehme ich variante2
 
Ok aber die aktivitäten der ersten beiden maschinen lese ich doch nur aus spalt F(2) ab, oder, da diese ja bereits optimiert sind

oder gehe ich auch nochmal zurück in spaöte f(1) für die 3. maschine

also kurzum: kombiniere ich für die 3. maschine nur us f(2) oder aus f(2) für maschinen 1 und 2 und für maschine 3 aus F(1), oder etwa aus F3 für Maschine 3?
 
So habe die Aufgabe jetzt berechnet...
bis x=6 ist eine produktion mit nur 2 aggregaten kostenopti..mit kosten von 36
so ab x=7 ist eine produktion mit 3 aggregaten kostenopti. mit kosten 42 ,spalte f2 kommt 48 raus das wäre 3x1+4x2 aber mit 3 aggreg. 2x1+2x2+3x3
die spalte f2 endet ja bei x=8 mit wert 60,wobei ich bei f3 einen wert von 48 habe...
ich weiss nicht,ob ich deine Frage beantworten konnte...ich erkläre immer so wie ich es selbst verstehe und nicht unbedingt exakt formal...
 
Es ist die frage, wenn ein leistungsvermögen pro maschine von 4 besteht und ich zb. 7 einheiten produzieren muss, darf ich dann lediglic auf maschine 1 und 2 zurückgrefen oder daf auch hier bereits die 3 maschine zum eisatz kommen?

wenn die 3. maschine zum einsatz kommt, dann gehe ich aber immer von tabelle f2 aus, oder?
 
Also ich schaue dann immer auf die aufgabenstellung...manchmal steht,es kommen nur 2 aggregate zum einsatz oder direkt 3....und dann schaue ich was kostengünstiger ist...wenn zbsp alle aggregate zum einsatz kommen berechne ich natürlich auch die spalte f2 (nur 2 maschinen) und f3 auch und bei der beantwortung dann der Frage nach dem kostenopti lese ich dann von der tabelle ab ob f2 oder f3 günstig ist.....wenn nur 2 aggregate erstmal im betrieb sein sollen rechne ich f2, übernehme ich in der spalte f3 was in f2 steht und bei x3 gebe ich eine 0 an
 
Hallo

ich habe auch so meine Probleme mit der Dynamischen Programmierung.

Habt ihr eine Art Kochrezept wonach ihr die einzelnen Kombinationen in einer bestimmten Art und Weise durchgeht, oder versucht ihr es von der ersten bis zur letzten Kombination ?
 
Oh, ich hab den Thread ja eröffnet und mittlerweile auch die Dynamische Programmierung verstanden, welch Wunder *g*. Also man malt sich auf einen Papierschnipsel die Stückzahl + zugehörige Kosten in der umgekehrten Reihenfolge auf und legt das dann neben das Aggregat. Dann hat man die Kombis nebeneinander und es passieren nicht mehr so viele Fehler. Aber durchschauen muss man sie dann doch alle.
 
ich stehe mal wieder auf dem Schlauch bei dynamischer Programmierung.

Kann mir einer von Euch erklären, warum in den Beispiel 6.9 aus dem Fandel-Übungsbuch bei 9 Einheiten auf Maschine 3 "69" eingetragen ist?

Die Kombinationsmöglichkeiten sind doch:

8/1 oder 7/2 oder 6/3 oder 5/4. Die Kosten dazu
70+12=82 oder 58+15=73 oder 46+23=69 oder 38+30=68

Das Minimum wären 68, warum also 69. Ist die Kombi 5/4 irgendwie nicht zulässing oder rechne ich irgendwo mit den falschen Kosten?

Danke für Eure Hilfe
 
wenn ich das richtig verstehe, ist die Kombination 5 und 4 nicht zulässig, da sowohl bei 4 als auch bei 5 zur kostenminimalen Herstellung Aggregat 1 und Aggregat 2 genutzt werden.

Da die Aggregate nur je 4 ME herstellen können ist die Kombination von 4 und 5 nicht möglich, da du dann die maximale Ausbringungsmenge je Maschine übersteigst.

Daher ist die Minimalkombination für Ausbringungsmenge 9: Je Aggregat werden 3 Einheiten hergestellt.
 
Hallo,

ich stehe mal wieder auf dem Schlauch bei dynamischer Programmierung.

Kann mir einer von Euch erklären, warum in den Beispiel 6.9 aus dem Fandel-Übungsbuch bei 9 Einheiten auf Maschine 3 "69" eingetragen ist?

Die Kombinationsmöglichkeiten sind doch:

8/1 oder 7/2 oder 6/3 oder 5/4. Die Kosten dazu
70+12=82 oder 58+15=73 oder 46+23=69 oder 38+30=68

Das Minimum wären 68, warum also 69. Ist die Kombi 5/4 irgendwie nicht zulässing oder rechne ich irgendwo mit den falschen Kosten?

verstehe durch die Bwegründung von Jeannine immer noch nicht wirklich wieso ich die 68 nicht nehme ...

könnte jemand vielleicht eine einfachere Begründung geben??
Vielleicht fällt es mir auch schwer weil ich noch die anderen 5 Themengebiete zeitnah erarbeite.

Rechnet man den zuerst die x2 und x3 aus und geht dann an die F2 und F3 dran oder umgekehrt oder spielt es gar keine Rolle?

Durch die Erklärungen im Übungsbuch werde ich auch nicht schlauer . Setze mich nochmal dran um weiter zu kommen aber zweifle seit gestern abend dran . Muss nur den Kniff heraus bekommen damit ich auch die Aufgabe des Kolloquiums nachvollziehen kann. Das kann doch echt nicht schwer sein ?!?!?!?!?!
 
verstehe durch die Bwegründung von Jeannine immer noch nicht wirklich wieso ich die 68 nicht nehme ...Gruss

Also, ich versuche mal zu erklären, wie ich meine, es verstanden zu haben:

Bei Kosten von 68 hast Du die Aufteilung von 5 zu 4

F2(5) heißt, Du machst 3 auf Masch.1 und 2 auf Masch.2 und müßtest dann noch 4 auf Masch.3 machen.

Es ist aber unzulässig eine neue Maschine höher zu betreiben als eine bereits eingesetzte Maschine.

F2(6) heißt, Du machst 3 auf Masch.1 und 3 auf Masch.2 und müßtest dann noch 3 auf Masch.3 machen. ZULÄSSIG, aber nur die 2-beste Kostenalternative.

Ich weiß nicht, ob das die perfekt Erklärung ist, aber so kam ich bei meinen Übungsaufgaben wenigsten zu den korrekten Ergebnissen.
 
Würde ja gerne helfen aber ich habe leider die Übungsaufgaben nicht, hast du eventuell ein anderes Beispiel aus dem Skript oder alte Klausuren, was das Problem wiederspiegelt?

hier ist die Aufgabe vom Kolloquium
https://www.fernuni-hagen.de/BWLPIT/LADV_/PDF_Dateien/ABWL_500_501.pdf

vielleicht könntest Du mir die einzelnen schritte deutlich machen . Vielleicht ist es zuviel verlangt da auch ne Erklärung erläutert wird aber meiner Meinung nach zu unzureichend
 
Christoph

Bei Kosten von 68 hast Du die Aufteilung von 5 zu 4

F2(5) heißt, Du machst 3 auf Masch.1 und 2 auf Masch.2 und müßtest dann noch 4 auf Masch.3 machen.

Es ist aber unzulässig eine neue Maschine höher zu betreiben als eine bereits eingesetzte Maschine.

F2(6) heißt, Du machst 3 auf Masch.1 und 3 auf Masch.2 und müßtest dann noch 3 auf Masch.3 machen. ZULÄSSIG, aber nur die 2-beste Kostenalternative.

wenn ich dich richtig verstanden habe müsste ich nachdem ich alle Min Werte habe , schauen ob z.B. Min wie in deinem Beispiel 68 überhaupt zulässig ist ?!

Um Zeit zu sparen kann man doch direkt für die Maschine die man nimmt sofort sehen ob es zulässig ist oder nicht; wie in deinem Bespiel :

F2(5) ich produziere auf 3 auf Maschine F1 ; 2 auf Maschine F2 ; dann ist es nicht mehr möglich 4 auf Maschine F3 zu produzieren richtig ??????? zulässig für Maschine F3 wäre jetzt noch 1 oder 2?
 
Ist aber jetzt nicht die Aufgabe die Christoph meinte!?

Also F2(M=4) ist ja klar du produzierst mit 2 Maschinen, also alle Kombinationen benutzen die eine 4 ergeben, 3:1 ; 2:2 ; 4:0 davon nimmst du die Kombination die kostengünstigsten ist. Das wäre 2:2 mit 22.

F2(M=7) hier machst du genau das Gleiche, allerdings gibt es nur eine Möglichkeit 4:3 , M=5 darfst du nicht verwenden da es mit M-x2 = 3 und x2 = 2 prduziert wird + 0, du würdest dann also mit 3 Maschinen produzieren ---> unzulässig. Aus dem selben Grund darfst du auch nicht den neuerrechneten F2(M=4)-Wert benutzen.


F3(M=9)

Ist 3:6 mit 51

zuerst guckst du in die Zeile 6, den 33 Wert darfst du nicht benutzen, da er 2:2:2 wäre und somit schon 3 Maschinen besetzen würde, also muss du den Wert 34 nehmen mit 3:3 und dazu dann einfach nochmal die 3 ---> wäre also nichts anderes als 17+17+17.

F3(M=17)

Ist 3:7 mit 59

Hier genauso 2:5 ist unzulässig also benutzt du 3:4 wäre also insgesamt 3:3:4 mit 17:17:25, hier wieder nicht den 22er Wert nehmen, sonst bräuchte man wieder 4 Maschinen, was unzulässig ist.


Hoffe einigermaßen verständlich erklärt.
 
Sacha

tut mir leid ich tue mich echt schwer aber sitze die ganze Zeit an der Aufgabe
danke für eure Bemühungen mir zu helfen!!!

Also zu deinen Erklärungsschritten :

Also F2(M=4) ist ja klar du produzierst mit 2 Maschinen, also alle Kombinationen benutzen die eine 4 ergeben, 3:1 ; 2:2 ; 4:0 davon nimmst du die Kombination die kostengünstigsten ist. Das wäre 2:2 mit 22.

verstanden!

F2(M=7) hier machst du genau das Gleiche, allerdings gibt es nur eine Möglichkeit 4:3 , M=5 darfst du nicht verwenden da es mit M-x2 = 3 und x2 = 2 prduziert wird + 0, du würdest dann also mit 3 Maschinen produzieren ---> unzulässig. Aus dem selben Grund darfst du auch nicht den neuerrechneten F2(M=4)-Wert benutzen.

da fängt mein Problem an . Verstehe die Unzulässigkeit nicht.

ich hätte versucht so zu lösen:

F2(7) = Min ( F1(6) + K2(1); F1(5) + K2(2); F1(4) + K2(3); F1(3) + K2(4); hier höre ich bei K2(4) auf weil nur bis hierher die Kosten bekannt sind => K2(4) = 25

Ergebnis: F2(7) = Min ( 41;39;42;42)

ich würde 39 wählen . Das ist nicht korrekt aber ich verstehe nicht wieso ich 42 wähle wo ich dann auch vielleicht 41 wählen kann wenn 39 nicht geht .


Wieso kann ich bei F3(9) alle min bis zu den Kosten K3(4) betrachten ?
 
Hallo Sacha

....
da fängt mein Problem an . Verstehe die Unzulässigkeit nicht.

ich hätte versucht so zu lösen:

F2(7) = Min ( F1(6) + K2(1); F1(5) + K2(2); F1(4) + K2(3); F1(3) + K2(4); hier höre ich bei K2(4) auf weil nur bis hierher die Kosten bekannt sind => K2(4) = 25

Ergebnis: F2(7) = Min ( 41;39;42;42)

ich würde 39 wählen . Das ist nicht korrekt aber ich verstehe nicht wieso ich 42 wähle wo ich dann auch vielleicht 41 wählen kann wenn 39 nicht geht .


Wieso kann ich bei F3(9) alle min bis zu den Kosten K3(4) betrachten ?

F2(M) du kannst mit max. 2 Maschinen produzieren!

du würdest nun für F2(7) 39 wählen, das kannst du aber nicht, da du dann mit 2:5 produzieren müsstes.

Und nun schau mal in die Spalte F2(5) da steht 28 mit 2:3, wäre also 2:2:3 was 3 Maschinen bedeuten würde, aber das geht wie gesagt nicht, also wählst du 3:4 mit den Werten 17 und 25 ( hier nochmal nicht den Wert 22 mit 2:2 wären widerum 3 Maschinen ). Aus dem selben Grund geht auch 1 und 6 nicht, weil 6 nur mit 2 Maschinen produziert werden kann, wären also auch wieder insgesamt 3 Maschinen.

Und genau gehst du auch bei F3(M) ran, du kannst mit max. 3 Maschinen produzieren, alle Ergebnisse wo du insgesamt 4 Maschinen benutzt darfst du nicht benutzen.
 
Also soweit verstanden das ich mit F2 maximal 2 Maschinen produzieren kann und mit F3
max. 3 Maschinen produzieren kann.
Nehmen wir F2(7) =39 das geht nicht weil ich F1(5) + K2(2) auf Maschine eins schon mit 2 produziere
und auf Maschine zwei nur noch mit maximal 2 produzieren kann. Ich müsste aber damit es aufgeht
mit 5 weiter produzieren und das ist nicht möglich ... richtig ?
könntest du mir dann bitte noch F3(9) erklären ?
mein Ansatz :
F3 ich kann auf 3 Maschinen produzieren :
F3(9) = Min ( F2(8) + K3(1); ist zulässig das auf Maschine 1: vier produziert werden und auf Maschine 2: vier
=> 4(Maschine1) + 4 (Maschine2) =8 es ist noch zulässig auf der dritten Maschine mit eins zu produzieren .
das gilt auch für F2(7) +K3(2); F2(6)+K3(3); F2(5)+K3(4) ?
dann wählen wir F2(6)+K3(3) => Maschine 3 können wir mit 3 produzieren d.h. wir haben Kosten von 17
auf Maschine 1 wird mit 3 produziert, Kosten 17 und auch auf Maschine 2 wird mit 3 produziert , Kosten 17
Ergebnis 17+17+17 = 51
 
DANKE

Ich hoffe ich habe es gerafft !?!?

ich taste mich an die Übungsaufgaben dran und versuche selbständig zu lösen

Hoffentlich können andere die es bis jetzt nicht verstanden haben anhgand von den Erklärungen der anderen nachvollziehen.

Gruss an alle und viel Erfo
 
Oben