Module 4

Dynamic Programming
 Recursive Nature of Dynamic Programming (DP) computations

The main idea of DP is to decompose the problem into (more manageable)

subproblems.

Computations are then carried out recursively where the optimum solution of
one subproblem is used as an input to the next subproblem.

The optimum solution for the entire problem is at hand when the last
subproblem is solved.

The manner in which the recursive computations are carried out depends on
how the original problem is decomposed.

In particular, the subproblems are normally linked by common constraints. The

feasibility of these common constraints is maintained at all iterations.
Shortest-Route Problem

To solve the problem by DP, first decompose

it into stages as delineated by the vertical
dashed lines in the figure.

Next, carry out the computations for each

stage separately.

f1 f1 f2 f2 f3 The general idea for determining the shortest

route is to compute the shortest (cumulative)
distances to all the terminal nodes of a stage
fo and then use these distances as input data to
the immediately succeeding stage. Starting
from node 1, stage 1 reaches three end
nodes (2, 3, and 4), and its computations are
simple.
 f1 f1 f2 f2 f3
7
STAGE 1
fo
0 8 Starting from node 1, stage 1 reaches
three end nodes (2, 3, and 4), and its
computations are simple.
5

Stage 1 Summary.
Shortest distance from node 1 to node 2 = 7 miles (from node 1)

Shortest distance from node 1 to node 3 = 8 miles (from node 1)

Shortest distance from node 1 to node 4 = 5 miles (from node 1)

 f1 f1 f2 f2 f3 STAGE 2
7 7
Next, stage 2 has two end nodes, 5 and 6.
fo 12 The figure shows that node 5 can be
8 reached from nodes 2, 3, and 4 via routes
0 8
(2, 5), (3, 5), and (4, 5).

5 This information, together with the

5 summary results (shortest distances) in
stage 1, determines the shortest
(cumulative) distance to node 5 as
𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑓𝑟𝑜𝑚
= min +
𝑡𝑜 𝑛𝑜𝑑𝑒 5 𝑖=2,3,4 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑖 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 5

7 + 12 = 19
= 𝑚𝑖𝑛 8 + 8 = 16 = 12(𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 4)
5 + 7 = 12
Node 6 can be reached from nodes 3 and 4 only. Thus

𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑓𝑟𝑜𝑚

= min +
𝑡𝑜 𝑛𝑜𝑑𝑒 6 𝑖=3,4 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑖 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 6

8 + 9 = 17
= 𝑚𝑖𝑛 = 17(𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 3)
5 + 13 = 18

Stage 2 Summary.

Shortest distance from node 1 to node 5 = 12 miles

(from node 4)

Shortest distance from node 1 to node 6 = 17 miles

(from node 3)
 STAGE 3

The last step is to consider stage 3. The destination

12
node 7 can be reached from either node 5 or 6.
21 Using the summary results from stage 2 and the
17 distances from nodes 5 and 6 to node 7,
we get

𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑆ℎ𝑜𝑟𝑡𝑒𝑠𝑡 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 𝑓𝑟𝑜𝑚

= min +
𝑡𝑜 𝑛𝑜𝑑𝑒 7 𝑖=5,6 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑖 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 7

12 + 9 = 21
= 𝑚𝑖𝑛 = 21(𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 5)
17 + 6 = 23
Stage 3 Summary.
Shortest distance from node 1 to node 7 = 21 miles (from node 5)

To determine the optimal route, start at stage 3 summary, where node 7 links
to node 5;

Stage 2 summary links node 4 to node 5; and stage 1 summary links node 4
to node 1.

Thus, the shortest route is 1 → 4 → 5 → 7.

The example reveals the basic properties of DP computations:

1. The computations at each stage are a function of the feasible routes of that
stage, and only that stage.

2. A current stage is linked to the immediately preceding stage only (without

regard to earlier stages) based on the shortest-distance summary of the
immediately preceding stage.
Let us see how the recursive computations in this problem can be expressed
mathematically. Let fi(xi) be the shortest distance to node xi at stage i, and define
d(xi-1, xi) as the distance from node xi-1 to node xi. The DP recursive equation is
defined as

𝑓0 𝑥0 = 1 = 0

𝑓𝑖 𝑥𝑖 = min 𝑑 𝑥𝑖−1 , 𝑥𝑖 + 𝑓𝑖−1 𝑥𝑖−1 , 𝑖 = 1,2,3

𝑎𝑙𝑙 𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒
𝑥𝑖−1 ,𝑥𝑖 𝑟𝑜𝑢𝑡𝑒𝑠

All distances are measured from 0 by setting f0(x0 = 1) = 0. The main recursive
equation expresses the shortest distance fi(xi) at stage i as a function of the next
node, xi.
In DP terminology, xi is referred to as the state at stage i. The state links
successive stages in a manner that permits making optimal feasible decisions at
a future stage independently of the decisions already made in all preceding
stages.
Forward and Backward recursion:

The previous uses forward recursion in which the computations proceed from stage 1
stage 3. The same problem can be solved by backward recursion, starting at stage 3
and ending at stage 1

Naturally, both the forward and backward recursions yield the same optimum.
Although the forward procedure appears more logical, DP literature mostly uses
backward recursion. The reason for this preference is that, in general, backward
recursion can be more efficient computationally.

We will demonstrate the use of backward recursion by applying it to

the previous problem. The demonstration will also provide the opportunity to present
the DP computations in a compact tabular form.
Determine the shortest route by backward recursion
f2 f2
f3 f3
f1
f4

The backward recursive equation is

𝑓4 𝑥4 = 7 = 0

𝑓𝑖 𝑥𝑖 = min 𝑑 𝑥𝑖 , 𝑥𝑖+1 + 𝑓𝑖+1 𝑥𝑖+1 , 𝑖 = 1,2,3

𝑎𝑙𝑙 𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒
𝑥𝑖 ,𝑥𝑖+1 𝑟𝑜𝑢𝑡𝑒𝑠
Stage 3 Node 7 (x4 = 7) is connected to nodes 5 and 6 (x3 = 5 and 6)
with exactly one route each. The following table summarizes
stage 3 computations:

d(x3,x4) Optimum solution

x3 x4=7 f3(x3) x4*
5 9 9 7
6 6 6 7
Stage 2
Route (2, 6) does not exist. Given f3(x3) from stage 3, we can compare
the feasible alternatives as the following table shows:

d(x2,x3) + f3(x3) Optimum solution

x2 x3=5 x3=6 f2(x2) x3*

2 12 + 9 = 21 - 21 5
3 8 + 9 = 17 9 + 6 = 15 15 6
4 7 + 9 = 16 13 + 6 = 19 16 5

The optimum solution of stage 2 reads as follows: For cities 2 and 4,

the shortest routes pass through city 5, and for city 3, the shortest
route passes through city 6.
 Stage 1 From node 1, we have three alternative routes: (1, 2), (1, 3),
and (1, 4). Using f2(x2) from stage 2, we get

d(x1,x2) + f2(x2) Optimum solution

x1 x2 = 2 x2 = 3 x2 = 4 f1(x1) x2*

1 7+21 = 28 8+15 = 23 5+16 = 21 21 4

Stage 1 solution links city 1 to city 4. Next, stage 2 solution links city 4 to city 5.

Finally, stage 3 solution connects city 5 to city 7. The optimum route is

1 → 4 → 5 → 7, and the associated distance is 21 miles.
Cargo loading
Knapsack/fly-away kit/ cargo loading Problem 1

Item i Unit weight wi tons Unit cost ri

1 2 31
mi – Number of
2 3 47 units of item i
3 1 14

Cargo capacity is 4 tons. Determine the optimum loading so that the cost value is maximum

Solution:

Stage : Items
Let mi is number of units of item i State: weight loaded
Alternatives: Number of units of items

xi – weight loaded in stage i

Knapsack/fly-away kit/ cargo loading
Item i Unit weight wi Unit cost ri
1 2 31
mi – Number of
2 3 47 units of item i
3 1 14

Stage 3 14m3 Optimum

solution
x3 m3 = 0 m3 = 1 m3 = 2 m3 = 3 m3 = 4 f3(x3) m3*

0 0 - - 0 0
1 0 14 - 14 1
2 0 - 28 - 28 2
3 0 - - 42 - 42 3
4 0 - - - 56 56 4
Stage 2
47m2+f3(x2-3m2) Optimum solution
x2 m2 = 0 m2 = 1 f2(x2) m2*

0 0+0 = 0 - 0 0
1 0+14 = 14 - 14 0
2 0+28 = 28 - 28 0
3 0+42 = 42 47+0 = 47 47 1
4 0+56 = 56 47+14 = 61 61 1
 47m2+f3(x2-3m2) Optimum solution
x2 m2 = 0 m2 = 1 f2(x2) m2 *

0 0+0 = 0 - 0 0
1 0+14 = 14 - 14 0
2 0+28 = 28 - 28 0
3 0+42 = 42 47+0 = 47 47 1
4 0+56 = 56 47+14 = 61 61 1

31m1+f2(x1-2m1) Optimum solution

Stage 1 x1 m1 = 0 m1 = 1 m1 = 2 f1(x1) m1*

0 0+0 = 0 - - 0 0
1 0+14 = 14 - - 14 0
2 0+28 = 28 31+0 = 31 - 31 1
3 0+47 = 47 31+14 = - 47 0
45
Answer:

Max value : 62

Optimum number of units:

Item 1: 2
Cargo loading: Problem 2

Item i Unit weight wi tons Unit cost ri

1 4 70
Cargo capacity = 6
2 2 40
3 1 20

STAGE 3
20m3 Optimum
x3 m3=0 m3=1 m3=2 m3=3 m3=4 m3=5 m3=6 f3(x3) m3*
0 0 - 0 0
1 - 20 20 1
2 - 40 40 2
3 - 60 60 3
4 - 80 80 4
5 - 100 100 5
6 - 120 120 6
STAGE 2

40m2+f3(x3-2m2) Optimum
x2 m2=0 m2=1 m2=2 m2=3 f2(x2) m2*
0 0+0 = 0 - 0 0
1 0+20 = 20 20 0
2 0+40 = 40 40+0 = 40 40 0,1
3 0+60 = 60 40+20 = 60 60 0,1
4 0+80 = 80 40+40 = 80 80+0 = 80 80 0,1,2
5 0+100 = 100 40+60 = 100 80+20 = 100 100 0,1,2
6 0+120 =120 40+80 = 120 80+40 = 120 120+0 =120 120 0,1,2,3
STAGE 1

Optimum
70m1+f2(x1-4m1)
Solution: Maximum value = 120
x1 m1=0 m1=1 f1(x1) m1*
0 0+0 = 0 - 0 0
1 0+20 = 20 20 0
Item Optimum
2 0+40 = 40 40 0 Number
3 0+60 = 60 60 0 1 0
4 0+80 = 80 70+0 = 70 80 0 2 0, 1, 2, 3
5 0+100 = 100 70+20 = 90 100 0 3 6, 4, 2, 0
6 0+120 =120 70+40 = 110 120 0
 Cargo loading : Problem 3

Item i Unit weight wi tons Unit cost ri

1 6 11
2 4 7
3 3 5
4 1 1
Cargo capacity is 17 tons. Determine the optimum loading so that the cost value is maximum
 Stage 4 1m4 Opti. sol
X4 m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= m4= f4(x m4*
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 4)
0 0 0 0
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9
10 10 10 10
11 11 11 11
12 12 12 12
13 13 13 13
14 14 14 14
15 15 15 15
16 16 16 16
 5m3+f4 (x3-3m3) Optimum solution
X3 m3=0 m3=1 m3=2 m3=3 m3=4 m3=5
0 0 - - 0 0 Stage 3
1 1 - - 1 0
2 2 - - 2 0
3 3 5+0= - 5 1
4 4 5+1= - 6 1
5 5 5+2 - 7 1
6 6 5+3 10+0= 10 2
7 7 5+4 10+1= 11 2
8 8 5+5 10+2= - 12 2
9 9 5+6 10+3= 15+0= 15 3
10 10 5+7 10+4= 15+1= 16 3
11 11 5+8 10+5= 15+2= - 17 3
12 12 5+9 10+6= 15+3= 20+0= 20 4
13 13 5+10 10+7= 15+4= 20+1= 21 4
14 14 5+11 10+8= 15+5= 20+2= - 22 4
15 15 5+12 10+9= 15+6= 20+3= 25+0= 25 5
16 16 5+13 10+10= 15+7= 20+4= 25+1= 26 5
17 17 5+14 10+11= 15+8= 20+5= 25+2= 27 5
 7m2+f3 (x2-4m2) Optimum solution
X2 m2=0 m2=1 m2=2 m2=3 m2=4 Stage 2
0 0 - 0 0
1 0+1 - 1 0
2 0+2 - 2 0
3 0+5 - 5 0
4 0+6 7+0 7 1
5 0+7 7+1 8 1
6 0+10 7+2 10 0
7 0+11 7+5 - 12 1
8 0+12 7+6 14+0 14 2
9 0+15 7+7 14+ 1 15 0,2
10 0+16 7+10 14+2 17 1
11 0+17 7+11 14+5 - 19 2
12 0+20 7+12 14+6 21+0 21 3
13 0+21 7+15 14+7 21+1 22 1,3
14 0+22 7+16 14+10 21+2 23 1,3
15 0+25 7+17 14+11 21+5 - 26 3
16 0+26 7+20 14+12 21+6 28+0 28 4
17 0+27 7+21 14+15 21+7 28+1 29 2,4
 11m1+f2 (x1-6m1) Optimum solution
X1 m1=0 m1=1 m1=2 Stage 1
0 0+0 0 0
1 0+1 1 0
2 0+2 2 0
3 0+5 5 0
4 0+7 7 0
5 0+8 - 8 0
6 0+10 11+0 11 1
7 0+12 11+1 12 0,1 Solution: Max value = 30
8 0+14 11+2 14 0
9 0+15 11+5 16 1
Item Optimum number
10 0+17 11+7 18 1
1 1, 2
11 0+19 11+8 - 19 0,1
12 0+21 11+10 22+0 22 2
2 2 1
13 0+22 11+12 22+1 23 1,2 3 1 0
14 0+23 11+14 22+2 25 1 4 0 1
15 0+26 11+15 22+5 27 2
16 0+28 11+17 22+7 29 1
17 0+29 11+19 22+8 30 1,2
Workforce Size
• Dynamic Programming:
1. Shortest path
2. Cargo – loading
3. Workforce sizing
4. Resource allocation
 Resource Allocation – Problem 1
 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
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Example 1- Resource Allocation - Dynamic Programming
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
Resource Allocation – Problem 1
 Resource Allocation – Problem 2 - Homework

 Find out the number of medical teams to be allocated to each country so that the total number of beneficiaries is
maximum.

Solution: 1 – 3- 1 & 170