Uncapacitated Lot Sizing (ULS) is a classic OR problem that seeks to minimize the cost of satisfying known demand for a product over time. Demand is subject to varying costs for production, set-up, and storage of the product. Technically, it is a mixed binary integer linear program – the key point separating it from the world of linear optimization being that production cannot occur during any period without paying that period’s fixed costs for set-up. Thus it has linear nonnegative variables for production and storage amounts during each period, and a binary variable for each period that determines whether or not production can actually occur.
For $n$ periods with per-period fixed set-up cost $f_t$, unit production cost $p_t$, unit storage cost $h_t$,and demand $d_t$, we define decision variables related to production and storage quantities:
$$ \small \begin{align*} x_t &= \text{units produced in period}\ t\\ s_t &= \text{stock at the end of period}\ t\\ y_t &= 1\ \text{if production occurs in period}\ t, 0\ \text{otherwise} \end{align*} $$
One can minimize overall cost for satisfying all demand on time using the following model per Wolsey (1998), defined slightly differently here:
$$ \small \begin{align*} \min\quad & z = \sum_t{p_t x_t} + \sum_t{h_t s_t} + \sum_t{f_t y_t}\\ \text{s.t.}\quad& s_1 = d_1 + s_1\\ & s_{t-1} + x_t = d_t + s_t &\quad\forall&\ t > 1\\ & x_t \leq M y_t &\quad\forall&\ t\\ & s_t, x_t \geq 0 &\quad\forall&\ t\\ & y_t \in {0,1} &\quad\forall&\ t \end{align*} $$
According to Wolsey, page 11, given that $s_t = \sum_{i=1}^t (x_i - d_i)$ and defining new constants $K = \sum_{t=1}^n h_t(\sum_{i=1}^t d_i)$ and $c_t = p_t + \sum_{i=t}^n h_i$, the objective function can be rewritten as $z = \sum_t c_t x_t + \sum _t f_t y_t - K$. The book lacks a proof of this and it seems a bit non-obvious, so I attempt an explanation in somewhat painstaking detail here.
$$ \small \begin{align*} &\text{Proof}:\\ & & \sum_t p_t x_t + \sum_t h_t s_t + \sum_t f_t y_t &= \sum_t c_t x_t + \sum _t f_t y_t - K\\ &\text{1. Remove} \sum_t f_t y_t:\\ & & \sum_t p_t x_t + \sum_t h_t s_t &= \sum_t c_t x_t - K\\ &\text{2. Expand}\ K\ \text{and}\ c_t:\\ & & \sum_t p_t x_t + \sum_t h_t s_t &= \sum_t (p_t + \sum_{i=t}^n h_i) x_t - \sum_t h_t (\sum_{i=1}^t d_i)\\ &\text{3. Remove}\ \sum_t p_t x_t:\\ & & \sum_t h_t s_t &= \sum_t x_t (\sum_{i=t}^n h_i) - \sum_t h_t (\sum_{i=1}^t d_i)\\ &\text{4. Expand}\ s_t:\\ & & \sum_t h_t (\sum_{i=1}^t x_i) - \sum_t h_t (\sum_{i=1}^t d_i) &= \sum_t x_t (\sum_{i=t}^n h_i) - \sum_t h_t (\sum_{i=1}^t d_i)\\ &\text{5. Remove}\ \sum_t h_t (\sum_{i=1}^t d_i):\\ & & \sum_t h_t (\sum_{i=1}^t x_i) &= \sum_t x_t (\sum_{i=t}^n h_i) \end{align*} $$
The result from step 5 becomes obvious upon expanding its left and right-hand terms:
$$ h_1 x_1 + h_2 (x_1 + x_2) + \cdots + h_n (x_1 + \cdots + x_n) =\\ x_1 (h_1 + \cdots + h_n) + x2 (h_2 + \cdots + h_n) + \cdots + x_n h_n $$
In matrix notation with $h$ and $x$ as column vectors in $\bf R^n$ and $L$ and $U$ being $n \times n$ lower and upper triangular identity matrices, respectively, this can be written as:
$$ \small \begin{pmatrix} h_1 \cdots h_n \end{pmatrix} \begin{pmatrix} 1 \cdots 0 \\ \vdots \ddots \vdots \\ 1 \cdots 1 \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} x_1 \cdots x_n \end{pmatrix} \begin{pmatrix} 1 \cdots 1 \\ \vdots \ddots \vdots \\ 0 \cdots 1 \end{pmatrix} \begin{pmatrix} h_1 \\ \vdots \\ h_n \end{pmatrix} $$
or $h^T L x = x^T U h$.