Dynamic
Programming
D y n a m ic P ro g r a m m in g is a m a th e m a tic a l te c h n iq u e d e a lin g w ith th e
o p tim iz a tio n o f m u ltis ta g e d e c is io n p r o b le m s .
Procedure
Define the Problem Variable, determine the Objective function and Specify the constraints.
Define the Stages of the Problem.
Develop the recursive relationship.
Forward or backward method to solve the Problem.
Make a tabular representation to show the required Values and Calculation for each Stage.
Find the optimal decision at each Stage and then the overall Optimal Policy.
Dynamic Programming Approach
STAGE
The Problem id broken down into Subproblems and each Subproblems is referred to as
a Stage.
STATE
The variable which specify the condition of decision process and summarize the
current “Status” of the system are called the State Variables.
Dynamic Programming Problem
A Medicine Manufacturing concern has a medical representatives working in three sales areas.
The Profitability for each representative in three Sales areas is as follows:
Profi tability (in thousands) Problem:
No. of
Representati ve Determine the
Area 1 Area 2 Area 3
Optimum Allocation of
0 32 37 44 medical representatives in
order to maximize the Profits.
1 47 47 56
2 62 54 62 Solution:
3 72 66 72 In this problem, the
three areas represent the
4 81 74 84
three Stages, and the number
5 92 84 97 of representatives represent
6 100 95 104
the State Variables.
7 107 100 112
8 102 102 112
9 92 102 112
Stage 1:We start with Area 1
Area 1
# of Representative 0 1 2 3 4 5 6 7 8 9
Profit (in thousands) 32 47 62 72 81 92 100 107 102 92
Stage 2:Consider the first-two Areas
(Area 1 & 2)
Area 1 X1 0 1 2 3 4 5 6 7 8 9
Area 2
f1(x1 32 47 62 72 81 92 100 107 102 92
x2 f2(x2)
0 37 69 84 99 109 118 129 137 144 139 129
1 47 79 94 109 119 128 139 147 154 149
2 54 86 101 116 126 135 146 154 164
3 66 98 113 128 138 147 158 166
4 74 106 121 136 146 155 166
5 84 116 131 146 156 165
6 95 127 142 157 167
7 100 132 147 162
8 102 134 149
9 102 134
Stage 3: 9 Representative to be allocated to the three
Areas
# of Representative 0 1 2 3 4 5 6 7 8 9
Total Profit
f2(x2) + f1(x1) 69 84 99 109 119 129 139 147 158 167
Representative in Area 2 + Area 1
0+0 0+1 0+2 1+2 1+3 0+5 1+5 1+6 3+5 6+3
[x2+x1]
0+3 3+4
# of Representative Area 3 9 8 7 6 5 4 3 2 1 0
Profit f3(x3) 112 112 112 104 97 84 72 62 56 44
Total Profit
181 196 211 213 216 213 211 209 214 211
All Areas
The maximum Profit for 9 Representatives is RS. 216,000 if 5 representative are allotted to Area 3 and
from the remaining 4 representative is allotted to Area 2 and 3 representative to Area 1.