11.3 Allocating a resource
Example 11.3.1. A company has \(6\) salesmen to assign to three regions. The expected sales (Rs. 1000) with \(0, 1, \ldots , 6\) salesmen in a region are
| salesmen | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) |
| region \(1\) | \(0\) | \(20\) | \(33\) | \(42\) | \(48\) | \(52\) | \(54\) |
| region \(2\) | \(0\) | \(15\) | \(28\) | \(39\) | \(48\) | \(55\) | \(60\) |
| region \(3\) | \(0\) | \(25\) | \(38\) | \(46\) | \(51\) | \(54\) | \(56\) |
Take the regions as stages and the number of salesmen still available as the state, and work backwards. \(f_3(s)\) is region \(3\)’s row; \(f_2(s) = \max _x\{R_2(x) + f_3(s - x)\}\), which gives \(f_2 = (0, 25, 40, 53, 66, 77, 86)\); and \(f_1(6) = \max _x\{R_1(x) + f_2(6 - x)\} = 99\), at \(x = 2\). Reading forwards, region \(1\) gets \(2\), leaving \(4\), of which region \(2\) gets \(2\) and region \(3\) gets \(2\): sales \(33 + 28 + 38 = 99\) (Software 11.5.2). The returns are concave (diminishing), and the optimal allocation equalises the marginal returns as nearly as integers allow, the discrete form of the KKT conditions.
The same scheme handles production planning with inventories (state: the stock), equipment replacement (state: the machine’s age) and capital budgeting. With random transitions the recursion takes expected values, \(f_k(s) = \max _x\mathbb E[r_k(s, x, \xi ) + f_{k + 1}(T_k(s, x, \xi ))]\); this is stochastic dynamic programming, developed further for Markov decision processes in a later section.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.