Chapter 21
Dynamic Programming
Learning Objectives
1. Understand the basics of dynamic programming and its approach to problem solving.
2. Learn the general dynamic programming notation.
3. Be able to use the dynamic programming approach to solve problems such as the shortest route
problem, the knapsack problem and production and inventory control problems.
4. Understand the following terms:
stages
state variables
principle of optimality
stage transformation function
return function
knapsack problem
21 - 1
,Chapter 21
Solutions:
1.
Route Value Route Value
(1-2-5-8-10) 22 (1-3-6-8-10) 26
(1-2-5-9-10) 25 (1-3-6-9-10) 22
(1-2-6-8-10) 24 (1-3-7-8-10) 22
(1-2-6-9-10) 20 (1-3-7-9-10) 21
(1-2-7-8-10) 25 (1-4-5-8-10) 22
(1-2-7-9-10) 24 (1-4-5-9-10) 25
(1-3-5-8-10) 19 (1-4-6-8-10) 27
(1-3-5-9-10) 22 (1-4-6-9-10) 23
The route (1-3-5-8-10) has the smallest value and is thus the solution to the problem.
The dynamic programming approach results in fewer computations because all 16 paths from node 1
to node 10 need not be computed. For example, at node 1 we considered only 3 paths: the one from
1-2 plus the shortest path from node 2 to node 10, the one from 1-3 plus the shortest path from node
3 to node 10, and the one from 1-4 plus the shortest path from node 4 to node 10.
2. a. The numbers in the squares above each node represent the shortest route from that node to node 10.
18 8
2 7 7
11 7
10 5 8
26 19 8 9 10
8 10 10
1 3 10 8
6 17
5 5 6
21 6 6
4 11
4 9
The shortest route is given by the sequence of nodes (1-4-6-9-10).
b. The shortest route from node 4 to node 10 is given by (4-6-9-10).
c.
Route Value Route Value
(1-2-5-7-10) 32 (1-3-6-8-10) 34
(1-2-5-8-10) 36 (1-3-6-9-10) 31
(1-2-5-9-10) 28 (1-4-6-8-10) 29
(1-3-5-7-10) 31 (1-4-6-9-10) 26
(1-3-5-8-10) 35
(1-3-5-9-10) 27
See 1 above for an explanation of how the computations are reduced.
21 - 2
, Dynamic Programming
3. Use 4 stages; one for each type of cargo.
Let the state variable represent the amount of cargo space remaining.
a. In hundreds of pounds we have up to 20 units of capacity available.
Stage 1 (Cargo Type 1)
x1 0 1 2 d1* f1(x1) x0
0-7 0 0 0 0-7
8-15 0 22 1 22 0-7
16-20 0 22 44 2 44 0-4
Stage 2 (Cargo Type 2)
x2 0 1 2 d 2* f2(x2) x1
0-4 0 0 0 0-4
5-7 0 12 1 12 0-2
8-9 22 12 0 22 8-9
10-12 22 12 24 2 24 0-2
13-15 22 34 24 1 34 8-10
16-17 44 34 24 0 44 16-17
18-20 44 34 46 2 46 8-10
Stage 3 (Cargo Type 3)
21 - 3
, Chapter 21
x3 0 1 2 3 4 d 3* f3(x3) x2
0-2 0 0 0 0-2
3-4 0 7 1 7 0-1
5 12 7 0 12 5
6-7 12 7 14 2 14 0-1
8 22 19 14 0 22 8
9 22 19 14 21 0 22 9
10 24 19 14 21 0 24 10
11 22 29 26 21 1 29 8
12 24 29 26 21 28 1 29 9
13 34 31 26 21 28 0 34 13
14-15 34 31 36 33 28 2 36 8-9
16 44 41 38 33 28 0 44 16
17 44 41 38 43 40 0 44 17
18 46 41 38 43 40 0 46 18
19 46 51 48 45 40 1 51 16
20 46 51 48 45 50 1 51 17
Stage 4 (Cargo Type 4)
x4 0 1 2 3 d 4* f4(x4) x3
20 51 49 50 45 0 51 20
Tracing back through the tables we find
State Variable Optimal State Variable
Stage Entering Decision Leaving
4 20 0 20
3 20 1 17
2 17 0 17
1 17 2 1
Load 1 unit of cargo type 3 and 2 units of cargo type 1 for a total return of $5100.
b. Only the calculations for stage 4 need to be repeated; the entering value for the state variable is 18.
x4 0 1 2 3 d 4* f4(x4) x3
18 46 47 42 38 1 47 16
Optimal solution: d4 = 1, d3 = 0, d2 = 0, d1 = 2
21 - 4
Dynamic Programming
Learning Objectives
1. Understand the basics of dynamic programming and its approach to problem solving.
2. Learn the general dynamic programming notation.
3. Be able to use the dynamic programming approach to solve problems such as the shortest route
problem, the knapsack problem and production and inventory control problems.
4. Understand the following terms:
stages
state variables
principle of optimality
stage transformation function
return function
knapsack problem
21 - 1
,Chapter 21
Solutions:
1.
Route Value Route Value
(1-2-5-8-10) 22 (1-3-6-8-10) 26
(1-2-5-9-10) 25 (1-3-6-9-10) 22
(1-2-6-8-10) 24 (1-3-7-8-10) 22
(1-2-6-9-10) 20 (1-3-7-9-10) 21
(1-2-7-8-10) 25 (1-4-5-8-10) 22
(1-2-7-9-10) 24 (1-4-5-9-10) 25
(1-3-5-8-10) 19 (1-4-6-8-10) 27
(1-3-5-9-10) 22 (1-4-6-9-10) 23
The route (1-3-5-8-10) has the smallest value and is thus the solution to the problem.
The dynamic programming approach results in fewer computations because all 16 paths from node 1
to node 10 need not be computed. For example, at node 1 we considered only 3 paths: the one from
1-2 plus the shortest path from node 2 to node 10, the one from 1-3 plus the shortest path from node
3 to node 10, and the one from 1-4 plus the shortest path from node 4 to node 10.
2. a. The numbers in the squares above each node represent the shortest route from that node to node 10.
18 8
2 7 7
11 7
10 5 8
26 19 8 9 10
8 10 10
1 3 10 8
6 17
5 5 6
21 6 6
4 11
4 9
The shortest route is given by the sequence of nodes (1-4-6-9-10).
b. The shortest route from node 4 to node 10 is given by (4-6-9-10).
c.
Route Value Route Value
(1-2-5-7-10) 32 (1-3-6-8-10) 34
(1-2-5-8-10) 36 (1-3-6-9-10) 31
(1-2-5-9-10) 28 (1-4-6-8-10) 29
(1-3-5-7-10) 31 (1-4-6-9-10) 26
(1-3-5-8-10) 35
(1-3-5-9-10) 27
See 1 above for an explanation of how the computations are reduced.
21 - 2
, Dynamic Programming
3. Use 4 stages; one for each type of cargo.
Let the state variable represent the amount of cargo space remaining.
a. In hundreds of pounds we have up to 20 units of capacity available.
Stage 1 (Cargo Type 1)
x1 0 1 2 d1* f1(x1) x0
0-7 0 0 0 0-7
8-15 0 22 1 22 0-7
16-20 0 22 44 2 44 0-4
Stage 2 (Cargo Type 2)
x2 0 1 2 d 2* f2(x2) x1
0-4 0 0 0 0-4
5-7 0 12 1 12 0-2
8-9 22 12 0 22 8-9
10-12 22 12 24 2 24 0-2
13-15 22 34 24 1 34 8-10
16-17 44 34 24 0 44 16-17
18-20 44 34 46 2 46 8-10
Stage 3 (Cargo Type 3)
21 - 3
, Chapter 21
x3 0 1 2 3 4 d 3* f3(x3) x2
0-2 0 0 0 0-2
3-4 0 7 1 7 0-1
5 12 7 0 12 5
6-7 12 7 14 2 14 0-1
8 22 19 14 0 22 8
9 22 19 14 21 0 22 9
10 24 19 14 21 0 24 10
11 22 29 26 21 1 29 8
12 24 29 26 21 28 1 29 9
13 34 31 26 21 28 0 34 13
14-15 34 31 36 33 28 2 36 8-9
16 44 41 38 33 28 0 44 16
17 44 41 38 43 40 0 44 17
18 46 41 38 43 40 0 46 18
19 46 51 48 45 40 1 51 16
20 46 51 48 45 50 1 51 17
Stage 4 (Cargo Type 4)
x4 0 1 2 3 d 4* f4(x4) x3
20 51 49 50 45 0 51 20
Tracing back through the tables we find
State Variable Optimal State Variable
Stage Entering Decision Leaving
4 20 0 20
3 20 1 17
2 17 0 17
1 17 2 1
Load 1 unit of cargo type 3 and 2 units of cargo type 1 for a total return of $5100.
b. Only the calculations for stage 4 need to be repeated; the entering value for the state variable is 18.
x4 0 1 2 3 d 4* f4(x4) x3
18 46 47 42 38 1 47 16
Optimal solution: d4 = 1, d3 = 0, d2 = 0, d1 = 2
21 - 4
