A new dynamic programming algorithm for the single item capacitated dynamic lot size model (Q1318270)

A dynamic lot size model with nonnegative demands and no backlogging is considered. The inventory process \(\{X_ t,\;t= 0,1,\dots, T\}\) is given by \(I_ 0= 0\), \(I_ t= I_{t-1}+ x_ t- d_ t\), with the following constraints: \(0\leq x_ t\leq c_ t\), \(I_ t\geq 0\). Here, \(d_ t\) denotes demand, \(c_ t\) a production capacity and \(x_ t\) (a decision variable) denotes a production level at time \(t\). The cost is given as \(\sum^ T_{t=1} (p_ t(x_ t)+ h_ t I_ t)\), where \(h_ t> 0\) and \[ p_ t(x_ t)= \begin{cases} 0, &\text{if }x_ t= 0;\\ K_ t+ p_ t' x_ t, &\text{if }0< x_ t.\end{cases} \] with \(p_ t'> 0\) and \(K_ t> 0\). The methods of dynamic programming are used. It is proved that the corresponding value functions are non-decreasing and piecewise linear. An algorithm to obtain the optimal production plan is described.