LP Formulation — Multi-Period Production Planning with Storage: 23-Ind-A1 Operations Research, December 2014, Q4

Question 4: LP Formulation — Multi-Period Production Planning with Storage (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given data — monthly sales, capacity, and costs
Month	Contracted sales	Production capacity	Production cost/unit	Storage cost/unit
1	60	90	$70	$2
2	70	60	$72	$1
3	90	80	$70	$1
4	70	100	$65	$3

Find. An LP that decides how much to produce each month (subject to that month's capacity) and how much to carry over, minimizing total production plus storage cost while meeting every month's contracted sales — formulated only, not solved.

Approach. Use one production variable and one end-of-month inventory variable per month, link them with a monthly material-balance (conservation) constraint, and cap production by that month's capacity.

Decision variables. For $t=1,\dots,4$: $x_t\ge0$ = units produced in month $t$; $I_t\ge0$ = units carried in inventory from the end of month $t$ into month $t+1$ (with $I_0=0$, no opening stock, and $I_4$ free to be forced to zero since there is no month 5 to sell into).
Capacity constraints. $x_t\le \text{Cap}_t$ for each month: $x_1\le90$, $x_2\le60$, $x_3\le80$, $x_4\le100$.
Material-balance (conservation) constraints. Production plus carried-in stock must cover that month's contracted sales plus whatever is carried forward: $I_{t-1}+x_t = S_t+I_t$ for $t=1,\dots,4$, i.e. $$x_1=60+I_1,\quad I_1+x_2=70+I_2,\quad I_2+x_3=90+I_3,\quad I_3+x_4=70+I_4.$$ No item sold the month it is produced pays storage, exactly what this balance form captures (storage is charged only on $I_t$, the amount actually carried past month $t$).
Ending condition and objective. Since the contract horizon is four months, add $I_4=0$ (no reason to hold stock past the last contracted sale). The full LP is $$\boxed{\text{Minimize } Z=\sum_{t=1}^{4}\big(c_t x_t + h_t I_t\big)\ \text{ s.t. } I_{t-1}+x_t-I_t=S_t\ (t=1,\dots,4),\ 0\le x_t\le\text{Cap}_t,\ I_t\ge0,\ I_0=I_4=0,}$$ with $c=(70,72,70,65)$, $h=(2,1,1,3)$, $S=(60,70,90,70)$, $\text{Cap}=(90,60,80,100)$ — formulated only, as the question directs.

Final results — Question 4
Element	Form
Decision variables	$x_t$ (produced), $I_t$ (carried), $t=1,\dots,4$
Objective	Minimize $\sum c_t x_t + h_t I_t$
Constraints	monthly balance, capacity caps, $I_0=I_4=0$, nonnegativity
Solved numerically?	No — formulation only, per instructions

Topic: Multi-period LP production planning with inventory carry-over.

Key relations: Material balance $I_{t-1}+x_t-I_t=S_t$; capacity bound $x_t\le\text{Cap}_t$; objective $\min\sum(c_tx_t+h_tI_t)$.

Why this works: The balance equation is the standard "conservation of units" trick used throughout multi-period LPs (also seen in cash-flow and blending models): whatever comes in (opening stock + this month's production) must equal what goes out (this month's sale + closing stock). Chaining that equation across months automatically lets the model shift production from a cheap month into a later expensive one, paying the storage cost only when that shift is worthwhile.

Common pitfall: Charging storage cost on production instead of on the carried inventory variable $I_t$, or forgetting the $I_4=0$ closing condition, which would let the model "produce and store forever" with no penalty at the model's edge.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 3 — LP formulation of production-scheduling/inventory problems.

Question 4 of 10: LP Formulation — Multi-Period Production Planning with Storage

Question 4: LP Formulation — Multi-Period Production Planning with Storage (15 marks)