CPT 413: OPERATION RESEARCH

1.      Introduction to Dynamic Programming

Dynamic programming is a general type of approach to problem solving, and the particular equations used must be developed to fit each situation. Therefore, a certain degree of ingenuity and insight into the general structure of dynamic programming problems is required to recognize when and how a problem can be solved by dynamic programming procedures. These abilities can best be developed by an exposure to a wide variety of dynamic programming applications and a study of the characteristics that are common to all these situations.

Dynamic Programming is a very useful technique for making a sequence of interrelateddecisions. It requires formulating an appropriate recursive relationship for each individual problem. However, it provides a great computational savings over using exhaustive enumeration to find the best combination of decisions, especially for large problems. For example, if a problem has 10 stages with 10 states and 10 possible decisions at each stage, then exhaustive enumeration must consider up to 10 billion combinations, whereas dynamic programming need make no more than a thousand calculations (10 for each state at each stage).

The characteristics of Dynamic Programming are as follow:

1.      The problem can be divided into stages, with a policy decision required at each stage.

2.      Each stage has a number of states associated with the beginning of that stage. The number of states may be either finite (as in the stagecoach problem) or infinite.

3.      The effect of the policy decision at each stage is to transform the current state to a state associated with the beginning of the next stage (possibly according to a probabilitydistribution).

4.      The solution procedure is designed to find an optimal policy for the overall problem, i.e., a prescription of the optimal policy decision at each stage for each of the possible states.

5.      Given the current state, an optimal policy for the remaining stages is independent of the policy decisions adopted in previous stages.

The solution procedure begins by finding the optimal policy for the last stage. The optimal policy for the last stage prescribes the optimal policy decision for each of the possible states at that stage.