Question 2 of 8: Dynamic Programming — Sales-Staff Allocation
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2016 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 160 marks across 8 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all eight are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming and the simplex method & sensitivity analysis (ch. 3–4/6), network optimization & PERT/CPM (ch. 9–10), integer programming (ch. 12), Markov chains (ch. 16), decision analysis (ch. 15). Nahmias, Production and Operations Analysis — the single-period (newsvendor) inventory model.
Given. 6 sales staff to assign across 3 regions, each region gets at least 1 staff member; estimated sales (in some sales unit) as a function of staff assigned:
Given data — estimated sales by region and staff count
No. of staff
Region 1
Region 2
Region 3
1
35
21
28
2
48
42
41
3
60
56
53
4
69
70
65
Find. The allocation $(n_1,n_2,n_3)$ with $n_1+n_2+n_3=6$, $n_i\ge 1$, that maximizes total sales.
Approach. This is a 3-stage allocation (separable resource-allocation) DP: treat each region as a stage, the state as staff already committed, and build up the best cumulative sales via Bellman's recursion, then read the optimal split off the final stage backward.
Define stages, states and the recursion. Let $s_k(n)$ = sales of region $k$ with $n$ staff (the table). With $x$ = staff used through region $k$,
$$f_1(x)=s_1(x),\qquad f_k(x)=\max_{1\le n_k\le x-(k-1)}\big[s_k(n_k)+f_{k-1}(x-n_k)\big]\ (k=2,3),$$
each region getting at least 1 staff caps $n_k\le x-(k-1)\cdot 1$ so the remaining regions can still get their minimum of one each.
Stage 1 (Region 1):$f_1(n_1)=s_1(n_1)$ for $n_1=1,2,3,4$: $f_1=(35,48,60,69)$.
Stage 2 (Regions 1+2), state = staff used so far. For each total $x=n_1+n_2$ from 2 to 8, maximize $s_2(n_2)+f_1(x-n_2)$ over feasible $n_2\in[1,4]$:
$$f_2(5)=\max\{s_2(1)+f_1(4),\,s_2(2)+f_1(3),\,s_2(3)+f_1(2),\,s_2(4)+f_1(1)\}$$
$$=\max\{21+69,\,42+60,\,56+48,\,70+35\}=\max\{90,102,104,\boxed{105}\}=105\ \text{at }n_2=4,n_1=1.$$
The other feasible totals for stage 3 ($x=2,3,4,6,7,8$) are worked the same way; the full table is below.
Stage 3 (Regions 1+2+3), total must equal 6. With $n_3=6-x$ for each stage-2 state $x$, maximize $f_2(x)+s_3(6-x)$. Enumerating every feasible $(n_1,n_2,n_3)$ with each $\ge 1$ and $\le4$ (equivalent to and cross-checked against the recursion) gives the complete comparison:
All feasible splits and their total sales (DP-recursion cross-check)
