Dynamic Programming Questions and Answers

Answer: B

The maximum product is \((K/5)^{5}\), writing K for the integer.

For positive parts \(x_{1}, \ldots, x_{5}\) with \(\sum x_{i} = K\), the AM-GM inequality gives

\[ \begin{aligned} \sqrt[5]{x_{1}x_{2}\cdots x_{5}} &\le \frac{x_{1} + \cdots + x_{5}}{5} \\ &= \frac{K}{5} \end{aligned} \]

so the product is at most \((K/5)^{5}\), with equality when all five parts equal \(K/5\). This is also the standard dynamic programming result for dividing a quantity into \(n\) parts: \(f_{n}(K) = (K/n)^{n}\).

5K and 5 + K grow only linearly, and \((5K)^{5}\) is far larger than any achievable product.

Answer: D

The first stage involves maximizing \(5x_{2}\) subject to \(x_{2} \le 6\) and \(3x_{1} + 2x_{2} \le 18\).

In the dynamic programming formulation each variable is a stage, and the state is the capacity of the shared constraint \(3x_{1} + 2x_{2} \le 18\) still available. The backward recursion starts with the last variable, \(x_{2}\): for a given \(x_{1}\), it finds

\[ \begin{aligned} f(x_{1}) = \max\{5x_{2} &: x_{2} \le 6, \\ &\ \ 2x_{2} \le 18 - 3x_{1}\} \end{aligned} \]

which keeps both constraints involving \(x_{2}\). The next stage then maximizes \(3x_{1} + f(x_{1})\) subject to \(x_{1} \le 4\). (Here \(x_{2} = 6\), \(x_{1} = 2\) and Z = 36.)

Options A and B describe the \(x_{1}\) stage, which comes second, and option C drops the bound \(x_{2} \le 6\), so it is not the full first-stage problem.

Answer: A

The correct statement is (i) only.

Bellman's principle of optimality says that an optimal policy has optimal sub-policies: if the shortest route from city 1 to city 10 passes through city \(j\), then the part of it from \(j\) to 10 must be a shortest route from \(j\) to 10. Otherwise a shorter sub-route could be substituted, giving a shorter total route.

Nothing requires uniqueness. There may be several shortest routes from \(j\) to 10 with the same length, so (ii) does not follow.

Answer: B

The minimum value is \(2c\).

For non-negative \(y_{1}, y_{2}\),

\[ \begin{aligned} &y_{1}^{2} + y_{2}^{2} - 2y_{1}y_{2} \\ &= (y_{1} - y_{2})^{2} \ge 0 \end{aligned} \]

so \(y_{1}^{2} + y_{2}^{2} \ge 2y_{1}y_{2} = 2c\), with equality when \(y_{1} = y_{2} = \sqrt{c}\). (Dynamic programming gives the same: with \(y_{2} = c/y_{1}\), minimise \(y_{1}^{2} + c^{2}/y_{1}^{2}\), which is least at \(y_{1}^{2} = c\).) The options in \(c^{2}\) have the wrong dimension: if \(y\) is doubled, \(c\) quadruples and the minimum must quadruple too.

Answer: C

The value is f₃(15) = 75, option C.

The printed recurrence leaves out the transition between stages. I read it as \(b_{k-1} = b_k - x\), which is what makes the printed line \(f_1(b_1) = (b_2 - x)^{2}\) consistent: it is \(f_1\) evaluated at \(b_1 = b_2 - x\), that is \(f_1(b) = b^{2}\). This is the problem of minimising \(x_1^{2} + x_2^{2} + x_3^{2}\) subject to \(x_1 + x_2 + x_3 = 15\).

\[ \begin{aligned} f_1(b) &= b^{2} \\ f_2(b) &= \min_x \{x^{2} + (b-x)^{2}\} = \frac{b^{2}}{2} \quad (x = b/2) \\ f_3(b) &= \min_x \{x^{2} + \tfrac{(b-x)^{2}}{2}\} = \frac{b^{2}}{3} \quad (x = b/3) \end{aligned} \]

Hence \(f_3(15) = 225/3 = 75\): each of the three variables equals 5, and \(3 \times 25 = 75\). Option A (25) is one term only, and 112.5 is \(15^{2}/2\), the two-stage value \(f_2(15)\).

Answer: C

The statement that is not true is that linear programming problems cannot be solved using dynamic programming.

Linear programmes can be solved by dynamic programming: each variable is treated as a stage and the remaining resources as the state, and the recursion works through the variables one at a time. It is usually less efficient than the simplex method, but it is possible, and textbooks include such examples.

The other statements are the defining features of dynamic programming: the problem is split into stages (A), each stage has a number of states (B), and the optimal solution is built from optimal solutions of sub-problems, Bellman's principle of optimality (D).