11.6 Practice Problems
Problem 11.6.1. Use dynamic programming to find the shortest route from \(A\) to \(H\) in a staged network with arcs \(A\)–\(B\): \(2\), \(A\)–\(C\): \(4\), \(A\)–\(D\): \(3\); \(B\)–\(E\): \(7\), \(B\)–\(F\): \(4\), \(C\)–\(E\): \(3\), \(C\)–\(F\): \(2\), \(D\)–\(E\): \(4\), \(D\)–\(F\): \(5\); \(E\)–\(H\): \(3\), \(F\)–\(H\): \(4\).
Show solution
Solution. Backwards: \(f(E) = 3\), \(f(F) = 4\). Then \(f(B) = \min (7 + 3, 4 + 4) = 8\), \(f(C) = \min (3 + 3, 2 + 4) = 6\), \(f(D) = \min (4 + 3, 5 + 4) = 7\). Finally \(f(A) = \min (2 + 8, 4 + 6, 3 + 7) = 10\), attained three ways: \(A, B, F, H\); \(A, C, E, H\) or \(A, C, F, H\); and \(A, D, E, H\), all of length \(10\).
Problem 11.6.2. In Example 11.3.1, how should \(4\) salesmen be allocated, and what is the marginal value of the fifth and sixth?
Show solution
Solution. \(f_1(4) = \max _x\{R_1(x) + f_2(4 - x)\}\) with \(f_2 = (0, 25, 40, 53, 66)\): for \(x = 0, 1, 2, 3, 4\) the values are \(66\), \(73\), \(73\), \(67\), \(48\), so \(f_1(4) = 73\), attained by the allocations \((1, 1, 2)\), \((1, 2, 1)\) and \((2, 1, 1)\). In the same way \(f_1(5) = 86\), by \((1, 2, 2)\), \((2, 1, 2)\) or \((2, 2, 1)\), and \(f_1(6) = 99\), only by \((2, 2, 2)\). The fifth salesman adds \(86 - 73 = 13\) and the sixth \(99 - 86 = 13\).
Problem 11.6.3. Five jobs on one machine have times \(4, 2, 7, 1, 5\). Find the order minimising the mean completion time, and the mean.
Show solution
Solution. SPT: times \(1, 2, 4, 5, 7\), with completion times \(1, 3, 7, 12, 19\), mean \(\frac {42}5 = 8.4\). Any other order is worse; for example the given order has completion times \(4, 6, 13, 14, 19\), mean \(11.2\).
Problem 11.6.4. Apply Johnson’s rule to jobs with times \((a, b)\): \((3, 6)\), \((7, 2)\), \((4, 4)\), \((5, 8)\), \((6, 3)\), and find the makespan.
Show solution
Solution. \(a < b\): jobs \(1\) \((3)\) and \(4\) \((5)\), in that order. The rest, in decreasing \(b\): job \(3\) \((b = 4)\), job \(5\) \((3)\), job \(2\) \((2)\). Order \(1, 4, 3, 5, 2\). Machine \(1\) finishes jobs at \(3, 8, 12, 18, 25\); machine \(2\) at \(9, 17, 21, 24, 27\). Makespan \(27\).
Problem 11.6.5. Show that the knapsack recursion, with \(W\) given in binary, takes time exponential in the input length, and explain why this does not contradict its usefulness.
Show solution
Solution. The input uses about \(n\log _2W\) bits for the weights, but the table has \(nW\) entries, and \(W = 2^{\log _2W}\) is exponential in \(\log _2W\). When the weights are moderate integers, say capacities of a few thousand, \(nW\) is small and the method is fast; it is only for huge or very precise weights that it fails, which is where the NP-hardness lives.
Problem 11.6.6. State the dynamic programming recursion for a production plan over \(T\) months with demand \(d_t\), production cost \(c(x)\), holding cost \(h\) per unit, stock bounded by \(S\), and no initial stock.
Show solution
Solution. State: stock \(I\) at the start of month \(t\). Decision: production \(x\) with \(0 \leq I + x - d_t \leq S\). Recursion: \(f_t(I) = \min _x\{c(x) + h(I + x - d_t) + f_{t + 1}(I + x - d_t)\}\), \(f_{T + 1}(I) = 0\), and the answer is \(f_1(0)\). Unlike the LP of Example 1.2.3, \(c(x)\) may include set-up costs or economies of scale.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.