Dynamic Programming -Introduction

 Dynamic Programming (DP) is a mathematical technique dealing with the

optimization of multistage decision problem.

 In dynamic programming problems, decision variables vary with time, and these
situations are called to be dynamic in nature.

 Dynamic programming splits the original large problem (which involves many
variables) into many sub-problems involving few variables. This technique is called as
recursive optimization.

 Dynamic programming technique is based on Bellman’s Principle of Optimality.

Techniques to solve Dynamic Programming Problems
 Top-Down(Memoization):

Break down the given problem in order to begin

solving it. If you see that the problem has already
been solved, return the saved answer. If it hasn’t
been solved, solve it and save it. This is usually easy
to think of and very intuitive, This is referred to as
Memoization.

 Bottom-Up(Dynamic Programming):

Analyze the problem and see in what order the sub-

problems are solved, and work your way up from
the trivial sub-problem to the given problem. This
process ensures that the sub-problems are solved
before the main problem. This is referred to as
Dynamic Programming.
Dynamic Programming -Example
Dynamic Programming -Example
Bellman’s Principle of Optimality
 An optimal policy ( a sequence of decision ) has the property that whatever the initial
state and decision are, the remaining decisions must constitute an optimal policy for
the state resulting from first decision.
Terminology used in Dynamic Programming
 Stage: The DP problem is broken into sub-problems and each sub-problem is called
stage.

 Stage decision: At each stage there are number of alternatives and the selection of one
of the most suitable and feasible alternative is called stage decision.

 State Variables: The variables whose value specify the condition of decision process
and summarize the current status of the system are called state variables.

 Decision Variables: The unknown in the given problem that needed to be determined
are called decision variables.
Procedures adopted in Dynamic Programming

 Define the variables, objective function and constraints.

 Divide the problem into number of sub-problems.

 Develop recursive relationship for optimality.

 Decide whether to follow the forward or the backward method to solve the problem.

 Make the tabular presentation to show the required values and calculations for each

stage.

 Find the optimal policy at each stage and then the overall optimal policy.
Formulation of Dynamic Programming
Formulation of Dynamic Programming (Contd.)
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Principle of Optimality
Example 1- Resource Allocation - Dynamic Programming
 A firm has divided its marketing area in to three zones. The amount of sales depends upon the number of salesmen in
each zone. The firm has been collecting the data regarding sales and salesmen in each area over a number of past
years.
 The information is summarised in below Table in thousands of rupees. For the next year firm has only 9 salesmen
and the problem is to allocate these salesmen to three different zones so that the sales are maximum.

No. of Salesmen Zone I Zone II Zone III

0 30 35 42
1 45 45 54
In this Problem the three
2 60 52 60 zones represent the
3 70 64 70 three stages and the
4 79 72 82 number of salesmen
5 90 82 95 represent the state
6 98 93 102 variables.
7 105 98 110
8 100 100 110
9 90 100 110
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 1- Resource Allocation - Dynamic Programming
Example 2- Resource Allocation - Dynamic Programming

 Find out the number of medical teams to be allocated in each country so that the total years of life of a person are
maximum.

Solution: 1 – 3- 1 & 170

 Example 2- Cargo loading- Dynamic Programming
 In a Cargo loading problem, there are 4 items of different weights/unit and different value unit is given below.

Item (i) Weight /Unit Value/Unit

(Wi Kg/Unit) (Pi Rs./Unit)
1 1 1
2 3 5
3 4 7
4 6 11

 The maximum cargo load is restricted to 17. How many units of each item be loaded to maximize the value?
Example 2- Cargo loading- Dynamic Programming

Max Z = 4𝑖=1 𝑎𝑖 𝑝𝑖
Subject to
4
𝑖=1 𝑎𝑖 𝑤𝑖 ≤W
Example 2- Cargo loading- Dynamic Programming
𝑊 17
 Stage 1: Here 𝑤1 = 1 kg/unit, 𝑝𝑖 = Rs 1 /unit; = =17  Let 𝑓1 (𝑥1 ), 𝑓2 (𝑥2 ), 𝑓3 (𝑥3 ) and 𝑓4 (𝑥4 )
𝑤1 1
 i.e. 𝑎1 = 0, 1, 2, 3, ….., 17 be the values of the loaded items at
stage 1,2,3, 4 respectively.
𝑊 17
 Stage 2: Here 𝑤2 = 3 kg/unit, 𝑝2 = Rs 5 /unit; = =5.67
𝑤2 3
≌5
 i.e. 𝑎2 = 0, 1, 2, 3, 4, 5

𝑊 17
 Stage 3: Here 𝑤3 = 4 kg/unit, 𝑝3 = Rs 7 /unit; = =4.25
𝑤3 4
≌4
 i.e. 𝑎3 = 0, 1, 2, 3, 4

𝑊 17
 Stage 4: Here 𝑤4 = 6 kg/unit, 𝑝4 = Rs 11 /unit; = =2.83
𝑤4 6
≌2
 i.e. 𝑎4 = 0, 1, 2
Example 2- Cargo loading- Dynamic Programming
Example 2- Cargo loading- Dynamic Programming
Example 2- Cargo loading- Dynamic Programming
Example 2- Cargo loading- Dynamic Programming
Example 2- Cargo loading- Dynamic Programming
Example 2- Cargo loading- Dynamic Programming

Optimal Solution: (2units of item 4 +1 unit of item 3+1 unit of item 1) & Max.value = 30