Question 3 of 9: Minimum-Cost Network Flow — Napkin Procurement Over 5 Days

Question 3: Minimum-Cost Network Flow — Napkin Procurement Over 5 Days (20 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. Planning horizon $t=1,\dots,5$; demand $d_t$ clean napkins each day $t$ (symbolic — no numeric table supplied, so the model is built with named parameters). Costs per napkin: new $c_n$, regular laundry $c_r$, overnight (express) laundry $c_o$. Zero starting inventory, clean or dirty.

Find. A minimum-cost network-flow model (nodes, arcs, arc costs/capacities) whose optimal flow gives the cheapest 5-day procurement plan.

Approach. Build two node families per day — a clean-demand node and a dirty-napkin pool node — connect them with the three supply options (new / overnight / regular) plus a zero-cost holding arc for dirty napkins waiting on laundry, then read off the min-cost-flow LP directly from arc costs and node balances.

1. Nodes. For each day $t=1,\dots,5$: a demand node $D_t$ (external demand $d_t$ clean napkins) and a dirty-pool node $U_t$ (napkins used on day $t$ that are now soiled). A source $S$ supplies unlimited new napkins.
2. Arcs and costs. $S\to D_t$, cost $c_n$, all $t$ (buy new, same-day). $D_t\to U_t$, cost 0, capacity forced $=d_t$ (every napkin used becomes dirty the same day). $U_t\to U_{t+1}$, cost 0 (dirty napkins may wait before being sent out; $U_1$ has no predecessor since starting inventory is zero). $U_t\to D_{t+1}$, cost $c_o$, for $t=1,\dots,4$ (overnight: dirty end of day $t$ → clean start of day $t+1$). $U_t\to D_{t+2}$, cost $c_r$, for $t=1,2,3$ (regular: a full-day turnaround beyond overnight, so clean again on day $t+2$).
3. Boundary condition. Since the firm starts with zero napkins, $D_1$ can only be met by $S\to D_1$ (no dirty pool exists yet to launder) — the network already enforces this because $U_t$ nodes for $t<1$ don't exist, so no laundry-return arc points into $D_1$.
4. LP form of the flow. Let $x_t^n=$ flow on $S\to D_t$, $x_t^o=$ flow on $U_t\to D_{t+1}$ ($t\le4$), $x_t^r=$ flow on $U_t\to D_{t+2}$ ($t\le3$), $h_t=$ flow on $U_t\to U_{t+1}$ ($t\le4$). Demand balance at $D_t$: $x_t^n+x_{t-1}^o\,[t\ge2]+x_{t-2}^r\,[t\ge3]=d_t$. Dirty-pool balance at $U_t$: $h_{t-1}\,[t\ge2]+d_t = x_t^o\,[t\le4]+x_t^r\,[t\le3]+h_t\,[t\le4]$. $$\boxed{\min Z=c_n\sum_{t=1}^{5}x_t^n+c_o\sum_{t=1}^{4}x_t^o+c_r\sum_{t=1}^{3}x_t^r}\ \text{ s.t. the balance equations above and all variables}\ge0.$$