Economic Lot$-$Sizing $(15$ points in total$)$

Economic lot sizing is a well$-$known problem in the area of production and operations man$-$ agement, as it has a variety of applications. For example, the economic lot$-$sizing problem is the core problem in aggregate production planning in Material Requirements Planning $($MRP$)$ systems.

We define the problem as follows: Consider a company that aims to manufacture a product to satisfy demand at minimum cost. Specifically, at each time period t in J$1,$TK$,$ there is a demand of dt in Z$>=0$ units of product that must be satisfied. At each period t in J$1,$ T K$,$ the cost of manufacturing the product follows a fixed plus variable expression: We denote ct the setup $($i$.$e$.,$ fixed$)$ cost$,$ and pt the variable cost for each unit of manufactured product in period t$.$ The demand must be met on time. If some inventory is remaining at the end of period t $($after satisfying the demand$),$ a holding cost of ht is incurred for each unit of product in inventory. We assume that there is no capacity constraint on the holding facility, and we suppose that there is no initial inventory.