23-Ind-A1 Operations Research · December 2018
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
National Exams — December 2018 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 170 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming, the simplex method & sensitivity analysis/duality (ch. 3–4/6), integer programming & branch and bound (ch. 12), queueing theory (ch. 17), decision analysis (ch. 15), computer simulation (ch. 20). Nahmias, Production and Operations Analysis — single-period (newsvendor) and multi-period (dynamic lot-sizing / Wagner–Whitin) inventory models.
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. Four months of contracted sales, monthly production capacity, production cost/unit, and storage cost/unit (charged on stock carried into the next month):
| Month $t$ | Contracted sales $S_t$ | Production capacity $P_t$ | Production cost/unit $c_t$ | Storage cost/unit $s_t$ |
|---|---|---|---|---|
| 1 | 60 | 90 | $70 | $2 |
| 2 | 70 | 60 | $72 | $1 |
| 3 | 90 | 80 | $70 | $1 |
| 4 | 70 | 100 | $65 | $3 |
Find. A linear program that decides how many units to produce each month (formulate only, do not solve).
Approach. This is a multi-period production-inventory planning problem: define a production variable per month and an end-of-month inventory (carry-over) variable per month, link them with a period-by-period material-balance equation, 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 starting stock, and $I_4=0$ assumed — nothing need be held past the contract's last month).
$$\min Z=\sum_{t=1}^{4} c_t x_t+\sum_{t=1}^{3} s_t I_t = 70x_1+72x_2+70x_3+65x_4+2I_1+I_2+I_3$$subject to, for each month $t=1,\dots,4$:
$$\text{Capacity:}\quad x_t\le P_t\qquad\text{(i.e. }x_1\le90,\ x_2\le60,\ x_3\le80,\ x_4\le100\text{)}$$ $$\text{Material balance:}\quad I_{t-1}+x_t=S_t+I_t\qquad\text{(i.e. }x_1=60+I_1;\ I_1+x_2=70+I_2;\ I_2+x_3=90+I_3;\ I_3+x_4=70\text{)}$$ $$x_t\ge0,\ I_t\ge0\ \ \text{for all }t,\qquad I_0=0$$