Dynamic Programming

Introduction:

In operation research Dynamic programming is a technique for getting solutions for multistage decision problems. In management literature, we have several quantitative decision models that help managers identify optima or best courses of action.

Dynamic problem:

A problem, in which the decision has to be made at successive stages, is called a multistage decision problem.
In this case, the problem solver will take decision at every stage, so that the total effectiveness defined over all the stages is optimal.
In dynamic programming the original problem is broken down or decomposed into small problems, which are known as sub problems or stages which is much convenient to handle and to find the optimal stage. For example, consider theproblem of a sales manager, who wants to start from his head office and tour various branches of thecompany and reach the last branch. He has to plan his tour in such a way that he has to visit number of branches and cover less distance as far as possible. He has to divide the network of theroute connecting all the branches into various stages and workout, which is the best route, which willhelp him to cover more branches and less distance.

History:

The technique of Dynamic programming was developed by RichardBellman in the early 1950.
The computational technique used is known as Dynamic Programming or Recursive Optimization.
We do not have a standard mathematical formulation of the Dynamic ProgrammingProblem (D.P.P). For each problem, depending on the variables given, and objective of the problem,one has to develop a particular equation to fit for situation. Though we have quite good number ofdynamic programming problems, sometimes to take advantage of dynamic programming, we introducemultistage nature in the problem and solve it by dynamic programming technique.
Nowadays, applicationof Dynamic Programming is done in almost all day to day managerial problems, such as, inventoryproblems, waiting line problems, resource allocation problems etc.

Classification:

Dynamic programming problemmay be classified depending on the following conditions.

(i) Dynamic programming problems may be classified depending on the nature of data available as Deterministic and Stochastic or Probabilistic models.

In deterministic models, the outcome at any decision stage is unique, determined and known.
In Probabilistic models, there is a set of possible outcomes with some probability distribution.

(ii) The possible decisions at any stage, from which we are to choose one, are called ‘states’.

These may be finite or infinite. States are the possible situations in which the system may be at any stage.

(iii) Total number of stages in the process may be finite or infinite and may be known or unknown.

Stage:

A stage signifies a portion of the total problem for which a decision can be taken. At each stage there are a number of alternatives, and the best out of those is called stage decision, which may be optimal for that stage, but contributes to obtain the optimal decision policy.

State:

The condition of the decision process at a stage is called its state. The variables, which specify the condition of the decision process, i.e. describes the status of the system at a particular stage are called state variables. The number of state variables should be as small as possible, since larger the number of the state variables, more complicated is the decision process.

Policy:

A rule, which determines the decision at each stage, is known as Policy. A policy is optimal one, if the decision is made at each stage in a way that the result of the decision is optimal over all the stages and not only for the current stage.

Principle of Optimality:

Bellman’s Principle of optimality states that ‘‘An optimal policy (a sequence of decisions) has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.’’

This principle implies that a wrong decision taken at a stage does not prevent from taking optimal decision for the reaming stages. This principle is the firm base for dynamic programming technique. In the light of this, we can write a recurrence relation, which enables us to take the optimal decision at each stage.

Steps in getting the solution for dynamic programming problem:

• Mathematical formulation of the problem and to write the recursive equation (recursive relation connecting the optimal decision function for the ‘n’ stage problem with the optimal decision function for the (n – 1) stage sub problems).

• To write the relation giving the optimal decision function for one stage sub problem and solve it.

• To solve the optimal decision function for 2-stage, 3-stage ……….. (n – 1) stage and then n-stage problem.