A dynamic programming algorithm for dynamic lot size models with piecewise linear costs (Q1327429)

A single item dynamic lot size model with finite time horizon \(T\) is considered. The problem is formulated as the following optimization problem: \[ \min_{x_ 1,\dots, x_ T} \sum^ T_{i=1} (P_ t(x_ t)+ H_ t(X_ t)). \] The process \(X_ t\) is given by \(X_ 0= 0\), \(X_ T= D_ T\), \(X_ t= X_{t-1}+ x_ t\), \(t= 1,\dots, T\), \(X_ t\in {\mathbf R}_ t\), \(x_ t\in {\mathbf H}_ t\), where the costs \(P_ t(\cdot)\) and \(H_ t(\cdot)\) are described by piecewise linear functions. \(D_ t\) denotes the cumulative demand, \({\mathbf H}_ t\) a set of feasible production levels and \({\mathbf R}_ t\) a set of feasible cumulative production levels. The methods of dynamic programming are used. It is proved that the corresponding value functions are piecewise linear with finitely many pieces for any \(t\). Some numerical examples are presented.