Dynamic Programming — Patrol Car Allocation: 23-Ind-A1 Operations Research, May 2016, Q7

Question 7: Dynamic Programming — Patrol Car Allocation (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. 5 patrol cars to allocate among 3 precincts; expected crimes as a function of cars assigned, per precinct (table below).

Given data — crimes vs. cars assigned
Precinct	0 cars	1	2	3	4	5
1	25	17	10	4	1	0
2	36	27	20	14	12	11
3	30	20	12	8	6	5

Find. The allocation $(x_1,x_2,x_3)$ with $x_1+x_2+x_3=5$ that minimizes total crimes, solved by (backward) dynamic programming.

Fig. 7 — DP as a shortest-path network: both tied optimal allocations, $(1,2,2)$ and $(2,1,2)$, are shown converging to the same minimum-crime path (total 49).

Approach. Treat "cars remaining to allocate" as the DP state and the precincts as three stages; solve backward from precinct 3 to precinct 1, at each state keeping the best crime total for every possible number of cars still available.

Stage 3 (last precinct). With $s$ cars left to give entirely to precinct 3, the best choice is always to use all of them (crimes strictly decrease with more cars): $f_3(s)=\text{crimes}_3(s)$.
$f_3(s)$
s 0 1 2 3 4 5
$f_3(s)$ 30 20 12 8 6 5
Stage 2. $f_2(s)=\min_{0\le x_2\le s}\big[\text{crimes}_2(x_2)+f_3(s-x_2)\big]$, evaluated for every $s=0,\dots,5$: $$f_2(5)=\min\{36{+}5,\,27{+}6,\,20{+}8,\,14{+}12,\,12{+}20,\,11{+}30\}=\min\{41,33,28,26,32,41\}=\boxed{26}\ \text{at } x_2=3.$$ The full table (needed because stage 1 can hand stage 2 any leftover from 0 to 5):
$f_2(s)$ and best $x_2$
s 0 1 2 3 4 5
$f_2(s)$ 66 56 47 39 32 26
best $x_2$ 0 0 1 1 2 3
Stage 1 (all 5 cars). $f_1(5)=\min_{0\le x_1\le 5}\big[\text{crimes}_1(x_1)+f_2(5-x_1)\big]$: $$\min\{25{+}26,\ 17{+}32,\ 10{+}39,\ 4{+}47,\ 1{+}56,\ 0{+}66\}=\min\{51,49,49,51,57,66\}=\boxed{49}.$$ The minimum is tied at $x_1=1$ (giving $17+f_2(4)=17+32=49$) and $x_1=2$ (giving $10+f_2(3)=10+39=49$).
Recover both optimal policies. For $x_1=1$: remaining $s=4\Rightarrow x_2=2$ (from the stage-2 table), remaining $s=2\Rightarrow x_3=2$, giving $(x_1,x_2,x_3)=(1,2,2)$, crimes $17+20+12=49$. For $x_1=2$: remaining $s=3\Rightarrow x_2=1$, remaining $s=2\Rightarrow x_3=2$, giving $(2,1,2)$, crimes $10+27+12=49$. Both use all 5 cars and both are optimal.

$f_3(s)$
s	0	1	2	3	4	5
$f_3(s)$	30	20	12	8	6	5

$f_2(s)$ and best $x_2$
s	0	1	2	3	4	5
$f_2(s)$	66	56	47	39	32	26
best $x_2$	0	0	1	1	2	3

Final results — Question 7
Item	Value
Minimum total crimes	49
Optimal allocation (a)	$x_1{=}1,\ x_2{=}2,\ x_3{=}2$
Optimal allocation (b), tied	$x_1{=}2,\ x_2{=}1,\ x_3{=}2$

Topic: Discrete resource-allocation dynamic programming.

Key relations: Backward recursion $f_k(s)=\min_{0\le x_k\le s}\big[\text{cost}_k(x_k)+f_{k+1}(s-x_k)\big]$, with the last stage $f_n(s)=\text{cost}_n(s)$; the optimal decisions are recovered by re-tracing the arg-min choices forward from stage 1.

Why this works: Because total crimes are additively separable across precincts, Bellman's principle of optimality applies directly: whatever is left over after precinct 1's decision must itself be allocated optimally between precincts 2 and 3, which is exactly what $f_2(\cdot)$ already captures — so solving each stage once, tabulated over every possible remaining-car count, is enough to solve every possible upstream decision.

Common pitfall: Computing $f_2$ only at the single value of $s that turns out to be needed at the end, rather than for every $s=0,\dots,5$ — the whole point of tabulating a stage is that stage 1 does not yet know which remaining-car count it will hand to stage 2, and here two different values of $x_1$ tie for optimal, so a single-value shortcut would silently miss the second policy.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 11 (deterministic dynamic programming, resource-allocation model).

Question 7 of 8: Dynamic Programming — Patrol Car Allocation

Question 7: Dynamic Programming — Patrol Car Allocation (20 marks)