Dynamic Programming
Dynamic Programming (or Recursive Optimization) is a technique for solving
multistage decision problems. The technique is Developed by Richard Bellman in the
1950s.
Its core idea
1. The original problem is decomposed into a series of smaller, interconnected sub-
problems.
2. Optimal solutions are found for the sub-problems.
3. These are reassembled to find the optimal strategy for the whole.
To apply DP, we must first structure the problem using four key terms
1. Stage: A point in the problem where a decision is made.
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.
2. State: The specific conditions or information we have at the beginning of a stage.
State variables describe the state (describes the status of the system at a particular
stage).
3. Decision: The choice made at a particular stage.
4. Policy: A rule that determines the decision to be made at each stage. An optimal
policy is one that optimizes the final outcome across all stages.
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”.
Directional Procedures
Dynamic programming problems involving stages are solved using recursive equations
(f1, f2, …, fn) in one of two directions:
• Forward Computational Procedure: This method solves equations in sequential
order from f1 to fn, determining optimal returns (r1, r2 etc.) as it progresses.
• Backward Computational Procedure: This method reverses the order, solving from
fn down to f1 . This specific approach is used, for example, when solving Linear
Programming Problems (L.P.P.) through dynamic programming.
The General Algorithm for Dynamic Programming
1. Identify decision variables and specify the objective function.
2. Divide problem into stages (Break the problem down into smaller sub-problems or
time periods).
3. Identify state variables for each stage and the transformation function.
4. Formulate an equation that connects the optimal solution of one stage to the next
(Write the Recursive Relationship).
5. Determine the order in which to solve the sub-problems (Forward or Backward
Approach).
6. Determine the overall optimal policy and Its value.
Example:
A company has 8 salesmen, who have to be allocated to four marketing zones. The return
of profit from each zone depends upon the number of salesmen working that zone. The
expected returns for different number of salesmen in different zones, as estimated from
the past records, are given below. Determine the optimal allocation policy.
SALES MARKETING IN ZONES X 000
No. of
Zone 1 Zone 2 Zone 3 Zone 4
Salesmen
0 45 30 35 42
1 58 45 45 54
2 70 60 52 60
3 82 70 64 70
4 93 79 72 82
5 101 90 82 95
6 108 98 93 102
7 113 105 98 110
8 118 110 100 110
Solution:
The problem here is how many salesmen are to be allocated to each zone to maximize
the total return.
In this problem each zone can be considered as a stage, number of salesmen in each
stage as decision variables. Number of salesmen available for allocation at a stage is the
state variable of the problem.
the objective function is
Maximize Z = f1 (x1) + f2 (x2) + f3 (x3) + f4 (x4)
Subject to: x1 + x2 + x3 + x4 ≤ 8 and x1, x2, x3 and x4 are non-negative integers.
No. of Salesmen in zone 1. 0 1 2 3 4 5 6 7 8
No. of Salesmen in zone 2. 8 7 6 5 4 3 2 1 0
Construct a table to calculate the return from the above combination.
Zone1 Salesmen 0 1 2 3 4 5 6 7 8
Return 45 58 70 82 93 101 108 113 118
Zone2
Return
Salesmen
0 30 75 88 100 112 123 141 138 143 148
1 45 90 103 115 127 138 146 153 158
2 60 105 118 130 142 153 161 168
3 70 115 128 140 152 163 171
4 79 124 137 149 161 172
5 90 135 148 160 172
6 98 143 156 168
7 105 150 163
8 110 155
let us write the outcomes below:
No. of Salesmen 0 1 2 3 4 5 6 7 8
Zone 1 0 0 0 0 2 3 4 4 4 3
Zone 2 0 1 2 2 2 2 2 3 4 5
Outcome in × 1000 75 90 105 118 130 142 153 163 172 172
Now in the second stage, let us combine zone 3 and zone 4 and get the total market
returns.
Combination of zone 3 and zone 4:
Zone 3 Salesmen 0 1 2 3 4 5 6 7 8
Return 35 45 52 64 72 82 93 98 100
Zone 4
Return
Salesmen
0 42 77 97 94 106 114 124 136 140 142
1 54 89 99 106 118 126 136 147 152
2 60 95 105 112 124 132 142 153
3 70 105 115 122 134 142 152
4 82 117 127 134 146 154
5 95 130 140 147 159
6 102 137 147 154
7 110 145 155
8 110 145
Now the table below shows the allocation and the outcomes for zone 3 and zone 4.
No. of Salesmen 0 1 2 3 4 5 6 7 8
Zone 3 0 1 1 2 3 5 1 1 2 3
Zone 4 0 0 1 1 1 0 5 6 5 5
Outcome in × 1000 77 97 99 106 118 130 140 147 147 159
In third stage we combine both zones 1 & 2 outcomes and zones 3 and 4 outcomes.
Zones 1 and 2 and zones 3 and 4 combined.
(0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (4, 2) (4, 3) (4, 5) (3, 5)
Zones 1&2 Salesmen
0 1 2 3 4 5 6 7 8
Return 75 90 105 118 130 142 153 163 172
Zones 3&4
Return
Salesmen
0 (0, 0) 77 152 187 182 195 207 219 230 240 247
1 (1, 0) 97 172 187 202 215 227 239 243 260
2 (1, 1) 99 174 189 204 217 229 241 252
3 (2, 1) 106 181 196 211 223 236 248
4 (3, 1) 118 193 208 223 236 248
5 (5, 0) 130 205 220 235 248
6 (1, 5) 140 214 230 245
7 (1, 6)
147 222 237
(2, 5)
8 (3, 5) 159 234
Optimal allocation is:
Salesmen 0 1 2 3 4 5 6 7 8
Zone 1 0 0 1 0 1 2 3 4 4
Zone 2 0 0 0 2 2 2 2 2 3
Zone 3 0 1 1 1 1 1 1 1 1
Zone 4 0 0 0 0 0 0 0 0 0
Total return in 1000 152 187 187 202 215 227 239 243 260
The table shows that how salesmen are allocated to various zones and the optimal
outcome for the allocation. Maximum outcome is 260 × 1000 = 260000