Dynamic Programmimg - OBJECTIVE QUESTIONS
I. Fill up the blanks :
1. In many situations, where a series of consecutive decisions are involved,
it is not necessary that the overall return for the total period (say, e.g.,
one year) will be optimal, if we optimize the return over each individual
period (say, e.g., a month) – this principle is employed in ………………….
2. Dynamic programming may be defined as a ………………………………….
…………………………………………………………………………………….
3. Dynamic programming problem can be divided into a sequence of sub –
problems, which are called the ……………………of the original problem.
4. In dynamic programming problems, the ……………...represent the different
time periods in the overall period of the problem.
5. In solving a travelling salesman problem by dynamic programming, each
………………… may be considered as a stage of the problem.
6. In solving the salesman problem for the shortest route by dynamic programming
a specific city is referred to as a …………………………………….
7. At each stage, a decision is made, which affects the ……………………….
at the next stage.
8. In dynamic programming, every decision has its own merit in terms of the
worth or benefit associated with it, which may be described in algebraic
form by an equation called the ………………………………………
9. The return function depends upon the ………………………………..and the
……………………… made at a particular stage.
10. The number of states in a stage (in a dynamic programming problem)
may be …………………………………….
11. In solving the shortest route problem by dynamic programming, let
dn= Decision variable which defines the immediate destinations when there
are n stages to go ( n=1,2,3,4,…, etc.,),
sn= State variable which defines a specific city at any stage,
ds n , dn= The distance associated with the state variable sn, and the
decision variable dn for the current (nth ) stage,
fn(sn , dn)= Minimum total distance for the last n stages, given that the
salesman is in the state sn, and selects dn as the immediate
destination,
fn* (sn) = Optimal path (minimum distance) when the salesman is in state
sn with n more stages to go to reach the final stage.
Then, the recursion relationship for this problem is given by :
………………………………………………………………………
12. Suppose a positive quantity ‘c’ is to be divided into ‘n’ parts such that
the product of the n parts is maximum. The optimal sub-division resulting
from the application of dynamic programming for this problem will be
……………………………………………
13. An optimal policy (i.e., a set of decisions) has the property that whatever
be the initial state and initial decision, the remaining decisions must
constitute an optimal policy for the state resulting from the first decision
- this is known as the ………………………………………………………..
14. By solving using dynamic programming, we can show that ,
pi
subject to and > 0, will be minimum when …………………….
15. An L.P. problem of the type Maximize Z = c1x1 + c2x2 + - - - - + cnxn, subject
to ai1x1 +ai2x2 +…+ aijxj + ……+ainxn{≤ , = , ≥}bi , (i = 1, 2, 3, …., m) can be
considered as a ……………….. and ………………….. problem of dynamic
programming.
Answers
1. Dynamic programming.
2. Mathematical technique of optimizing a sequence of inter-related
decisions over a period of time.
3. Stages.
4. Stages.
5. (Sales) Zone.
6. State variable.
7. State of the system.
8. Return function.
9. State variable ; Decision.
10. Finite or Infinite.
11. fn* (sn) = Min{ dsn , dn +f *(n-1)(dn) } , n=1,2,3,4, … where f *(n-1)(d)n is the
dn
optimal distance for the previous stages.
12. , , , ………………., fn (c) =
&
13. Bellman’s principle of optimality.
14. p1 = p2 = p3 = - - - - - = pn = (1/n)
15. n – stage, m – state.
