Question 5 of 10: Dynamic Programming — Sales-Staff Assignment

Question 5: Dynamic Programming — Sales-Staff Assignment (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. 6 sales staff to allocate among 3 regions, each region receiving 1 to 4 staff (each ≥1 since every region must get at least one, leaving at most 4 for any single region); sales table as above (in $'000).

Find. The staff allocation $(n_1,n_2,n_3)$, $n_1+n_2+n_3=6$, that maximizes total estimated sales.

Approach. Solve as a 3-stage allocation dynamic program: stage $k$ = region $k$, state = staff remaining to allocate, decision = staff assigned to that region; build up cumulative-best tables $f_1,f_2,f_3$ stage by stage.

1. Stage 1 (Region 1 only): $f_1(n_1)=$ Region 1 sales with $n_1$ staff ($n_1=1,\dots,4$): $f_1=(35,48,60,69)$.
2. Stage 2 (Regions 1–2 combined): for total staff $n=n_1+n_2$ committed so far, $f_2(n)=\max_{1\le n_1\le 4,\,1\le n_2\le4,\,n_1+n_2=n}\big[f_1(n_1)+\text{Region 2}(n_2)\big]$:

   Stage-2 table: best split of $n$ staff between Regions 1 & 2

   $n$	2	3	4	5	6	7
   $f_2(n)$	56	77	91	105	118	130
   best $(n_1,n_2)$	(1,1)	(1,2)	(1,3)	(1,4)	(2,4)	(3,4)

   e.g. $f_2(5)=\max[f_1(1)+42,\,f_1(2)+56,\,f_1(3)\!+\!... ]$; the best split of 5 staff is $n_1{=}1,n_2{=}4$: $35+70=105$.
3. Stage 3 (add Region 3, all 6 staff committed): $n_1+n_2+n_3=6$, $n_3\in\{1,2,3,4\}$, so $n=n_1{+}n_2=6-n_3\in\{2,3,4,5\}$: $$f_3=\max_{1\le n_3\le4}\big[f_2(6-n_3)+\text{Region 3}(n_3)\big]$$ $$=\max\big[f_2(5){+}28,\ f_2(4){+}41,\ f_2(3){+}53,\ f_2(2){+}65\big]=\max[133,\,132,\,130,\,121]$$ $$\boxed{f_3=133\ \text{(\$'000), at } n_3=1,\ (n_1,n_2)=(1,4)}$$
4. Optimal allocation: tracing back, $n_1=1,\ n_2=4,\ n_3=1$: $$\boxed{\text{Region 1: 1 staff (35); Region 2: 4 staff (70); Region 3: 1 staff (28); total } \$133{,}000}$$