Dynamic Programming Questions and Answers

Q: When a positive integer is divided into 5 parts, the maximum value of their product is :

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.

Q: Consider the LPP :Maximize : \(Z = 3x_{1} + 5x_{2}\)Subject to :\(x_{1} \le 4,\)\(x_{2} \le 6,\)\(3x_{1} + 2x_{2} \le 18,\)\(x_{1}, x_{2} \ge 0\)The first stage in the dynamic programming algorithm to solve the above problem involves :

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.

Q: Suppose that R is the shortest route from city 1 to city 10 passing through some other cities. The principle of optimality implies that :(i) For every city \(j\) on R, the subpath in R from city \(j\) to city 10 must be the shortest.(ii) For every city \(j\) on R, there must be a unique path from city \(j\) to city 10.Which of the above statements is correct ?

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.

Q: By the principle of optimality, the minimum value of \(y_{1}^{2} + y_{2}^{2}\) s.t. \(y_{1}y_{2} = c, y_{1} \ge 0, y_{2} \ge 0\) is :

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.

Q: The dynamic programming approach to an optimization problem gives the recurrence equation for optimal solution as :\[ f_k(b_k) = \min_{0 \lt x \le b} \{x^{2} + f_{k-1}(b_{k-1})\} \]for \(k \gt 1\); and \(f_1(b_1) = (b_2 - x)^{2}\). Then, \(f_3(15) =\)

The value is f3(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)\).

Q: Which of the following characteristics of dynamic programming is not true ?

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).

When a positive integer is divided into 5 parts, the maximum value of their product is :

A.5K
B.\((K/5)^{5}\)
C.\((5K)^{5}\)
D.5 + K

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

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.

Discuss in Forum

Consider the LPP :

Maximize : \(Z = 3x_{1} + 5x_{2}\)

Subject to :
\(x_{1} \le 4,\)
\(x_{2} \le 6,\)
\(3x_{1} + 2x_{2} \le 18,\)
\(x_{1}, x_{2} \ge 0\)

The first stage in the dynamic programming algorithm to solve the above problem involves :

A.Maximizing \(3x_{1}\) subject to \(x_{1} \le 4\)
B.Maximizing \(3x_{1}\) subject to \(3x_{1} + 2x_{2} \le 18\)
C.Maximizing \(5x_{2}\) subject to \(3x_{1} + 2x_{2} \le 18\)
D.Maximizing \(5x_{2}\) subject to \(x_{2} \le 6\) and \(3x_{1} + 2x_{2} \le 18\)

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

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.

Discuss in Forum

Suppose that R is the shortest route from city 1 to city 10 passing through some other cities. The principle of optimality implies that :

(i) For every city \(j\) on R, the subpath in R from city \(j\) to city 10 must be the shortest.
(ii) For every city \(j\) on R, there must be a unique path from city \(j\) to city 10.

Which of the above statements is correct ?

A.(i) only
B.(ii) only
C.Both (i) and (ii)
D.Neither (i) nor (ii)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Discuss in Forum

By the principle of optimality, the minimum value of \(y_{1}^{2} + y_{2}^{2}\) s.t. \(y_{1}y_{2} = c, y_{1} \ge 0, y_{2} \ge 0\) is :

A.\(2c^{2}\)
B.\(2c\)
C.\(\left(\dfrac{c}{2}\right)^{2}\)
D.\(c^{2}/2\)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Discuss in Forum

The dynamic programming approach to an optimization problem gives the recurrence equation for optimal solution as :

\[ f_k(b_k) = \min_{0 \lt x \le b} \{x^{2} + f_{k-1}(b_{k-1})\} \]

for \(k \gt 1\); and \(f_1(b_1) = (b_2 - x)^{2}\). Then, \(f_3(15) =\)

A.25
B.112.5
C.75
D.None of the above

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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)\).

Discuss in Forum

Which of the following characteristics of dynamic programming is not true ?

A.The problem can be subdivided into stages
B.Every stage consists of a number of states
C.Linear programming problems cannot be solved using dynamic programming
D.The optimal solution to the problem is obtained using optimal solutions to sub-problems

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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).

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Dynamic Programming Questions and Answers || Dynamic Programming MCQ Questions and Answers || Dynamic Programming GK Questions and Answers || Dynamic Programming GK MCQ Questions || Dynamic Programming Multiple Choice Questions and Answers || Dynamic Programming GK || GK on Dynamic Programming || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Dynamic Programming Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications