Lagerbelegung mit Dynamic Programming

17/03/2010 - 21:38 von Thomas Plehn | Report spam
Hallo,

Angenommen ich habe eine Lagerbelegung x
und Bestellmengen y1, y2, ...
Dann ergibt sich eine Sequenz der Lagerbelegung x1, x2, ...

mit x_N=0
x_{i-1} = t(x_i,y_i)

gesucht sind nun diejenigen Bestellmengen, so dass die Lagerkosten
minimal werden

Lagerkosten = sum_{i=1}^N \phi_i (x_i,y_i)

nun, wie geht das nun mit dynamic Programming?

Ich meine mich an etwas der Form

F_i(x_i) = min_{y_i} \phi_i (x_i,y_i) + F_{i-1} ( t(x_i,y_i) )

für alle x_i = t(x_i+1,y_i+1)

zu erinnern
 

Lesen sie die antworten

#1 Thomas Plehn
18/03/2010 - 12:15 | Warnen spam
Am 17.03.2010 21:38, schrieb Thomas Plehn:
Hallo,

Angenommen ich habe eine Lagerbelegung x
und Bestellmengen y1, y2, ...
Dann ergibt sich eine Sequenz der Lagerbelegung x1, x2, ...

mit x_N=0
x_{i-1} = t(x_i,y_i)

gesucht sind nun diejenigen Bestellmengen, so dass die Lagerkosten
minimal werden

Lagerkosten = sum_{i=1}^N \phi_i (x_i,y_i)

nun, wie geht das nun mit dynamic Programming?

Ich meine mich an etwas der Form

F_i(x_i) = min_{y_i} \phi_i (x_i,y_i) + F_{i-1} ( t(x_i,y_i) )

für alle x_i = t(x_i+1,y_i+1)

zu erinnern



ich denke, der Trick dabei ist, das sowohl die Menge der diskreten
Zustànde x_i endlich ist, wie auch die Menge der Zustandsübergànge y_i
diskret und endlich ist.
Nun weiß man, dass der Zustand x_N = 0 sein soll, denn dann soll das
Lager leer sein.
Nun muss man nach obiger rekursiver Vorschrift F_N(x_N=0) berechnen,
dabei werden die Aufrufe für F_i(x_i), i < N zwischengespeichert, so
dass man sie bei einer weiteren Auswertung griffbereit hat.
Und das ist schon der wesentliche Trick zur Optimierung.
Das macht natürlich nur bei diskreten Mengen Sinn.
Es handelt sich dabei natürlich um eine Diskretisierung, die man
beliebig fein wàhlen kann (zu lasten des Rechenaufwandes).

kann das mal jemand verifizieren?

gesehen habe ich dynamische Programmierung zuerst zur Bestimmung des
kürzesten Weges durch einen Graphen.

dort: f_i = min_j d(i,j) + f_j

das geht dann wohl àhnlich.

Ähnliche fragen