Chapter 11

Dynamic Programming

Copyright 2020 © McGraw-Hill Education. All rights

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distributionreserved. Noprior
without the reproduction or distribution
written consent of without
Frederick
McGraw-HillS. Hillier ∎ Gerald J. Lieberman
Education. the prior written consent of McGraw-Hill Education.
11.1 A Prototype Example for Dynamic
Programming
• The stagecoach problem
– Mythical fortune-seeker travels West by
stagecoach to join the gold rush in the mid-
1900s
– The origin and destination is fixed
• Many options in choice of route
– Insurance policies on stagecoach riders
• Cost depended on perceived route safety
– Choose safest route by minimizing policy cost
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 2
A Prototype Example for Dynamic
Programming
• Incorrect solution: choose cheapest run
offered by each successive stage
– Gives A→B → F → I → J for a total cost of 13
– There are less expensive options

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 3
A Prototype Example for Dynamic
Programming
• Trial-and-error solution
– Very time consuming for large problems
• Dynamic programming solution
– Starts with a small portion of original problem
• Finds optimal solution for this smaller problem
– Gradually enlarges the problem
• Finds the current optimal solution from the
preceding one
Dynamic Programming Tutorial - Basics, Backward Recursion, and Principle of
Optimality [Link]
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 4
A Prototype Example for Dynamic
Programming
• Stagecoach problem approach
– Start when fortune-seeker is only one
stagecoach ride away from the destination
– Increase by one the number of stages
remaining to complete the journey
• Problem formulation
– Decision variables x1, x2, x3, x4
– Route begins at A, proceeds through x1, x2,
x3, x4, and ends at J
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 5
A Prototype Example for Dynamic
Programming
• Let fn(s, xn) be the total cost of the overall
policy for the remaining stages
– Fortune-seeker is in state s, ready to start
stage n
• Selects xn as the immediate destination
– Value of csxn obtained by setting i = s and j = xn

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 6
A Prototype Example for Dynamic
Programming
• Immediate solution to the n = 4 problem

• When n = 3:

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 7
A Prototype Example for Dynamic
Programming
• The n = 2 problem

• When n = 1:

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 8
A Prototype Example for Dynamic
Programming
• Construct optimal solution using the four
tables
– Results for n = 1 problem show that fortune-
seeker should choose state C or D
– Suppose C is chosen
• For n = 2, the result for s = C is x2* = E …
• One optimal solution: A→ C → E → H → J
– Suppose D is chosen instead
A → D → E → H → J and A → D → F → I → J
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 9
A Prototype Example for Dynamic
Programming
• All three optimal solutions have a total cost
of 11

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 10
11.2 Characteristics of Dynamic
Programming Problems
• The stagecoach problem is a literal
prototype
– Provides a physical interpretation of an
abstract structure
• Features of dynamic programming
problems
– Problem can be divided into stages with a
policy decision required at each stage
– Each stage has a number of states
associated with the beginning of the stage
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 11
Characteristics of Dynamic Programming
Problems
• Features (cont’d.)
– The policy decision at each stage transforms
the current state into a state associated with
the beginning of the next stage
– Solution procedure designed to find an
optimal policy for the overall problem
– Given the current state, an optimal policy for
the remaining stages is independent of the
policy decisions of previous stages

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 12
Characteristics of Dynamic Programming
Problems
• Features (cont’d.)
– Solution procedure begins by finding the
optimal policy for the last stage
– A recursive relationship can be defined that
identifies the optimal policy for stage n, given
the optimal policy for stage n + 1
– Using the recursive relationship, the solution
procedure starts at the end and works
backward

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 13
11.3 Deterministic Dynamic Programming

• Deterministic problems
– The state at the next stage is completely
determined by the current stage and the
policy decision at that stage

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 14
Deterministic Dynamic Programming

• Categorize dynamic programming by form

of the objective function
– Minimize sum of contributions of the individual
stages
• Or maximize a sum, or minimize a product of the
terms
– Nature of the states
• Discrete or continuous state variable/state vector
– Nature of the decision variables
• Discrete or continuous
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 15
Deterministic Dynamic Programming

• Example 2: distributing medical teams to

countries
– Problem: determine how many of five
available medical teams to allocate to each of
three countries
• The goal is to maximize teams’ effectiveness
• Performance measured in terms of increased life
expectancy
• Follow example solution in the text on
Pages 433-438
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 16
Deterministic Dynamic Programming

• Distribution of effort problem

– Medical teams example is of this type
– Differences from linear programming
• Four assumptions of linear programming
(proportionality, additivity, divisibility, and certainty)
need not apply
• Only assumption needed is additivity
• Example 3: distributing scientists to
research teams
– See Pages 440-442 in the text
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 17
Deterministic Dynamic Programming

• Example 4: scheduling employment levels

– State variable is continuous
• Not restricted to integer values
– See Pages 443-448 in the text for solution

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 18
11.4 Probabilistic Dynamic Programming

• Different from deterministic dynamic

programming
– Next state is not completely determined by
state and policy decisions at the current stage
• Probability distribution describes what the next
state will be
• Decision tree
– See Figure 11.10 on next slide

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 19
Probabilistic Dynamic Programming

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 20
Probabilistic Dynamic Programming

• A general objective
– Minimize the expected sum of the
contributions from the individual stages
• Problem formulation
– fn(sn, xn) represents the minimum expected
sum from stage n onward
– State and policy decision at stage n are sn
and xn , respectively

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 21
Probabilistic Dynamic Programming

• Problem formulation

• Example 5: determining reject allowances

– Has same form as above
– See Pages 449-451 in the text for solution
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 22
Probabilistic Dynamic Programming

• Example 6: winning in Las Vegas

– Statistician has a procedure that she believes
will win a popular Las Vegas game
• 67% chance of winning a given play of the game
– Colleagues bet that she will not have at least
five chips after three plays of the game
• If she begins with three chips
– Assuming she is correct, determine optimal
policy of how many chips to bet at each play
• Taking into account results of earlier plays
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 23
Probabilistic Dynamic Programming

• Objective: maximize probability of winning

her bet with her colleagues
• Dynamic programming problem
formulation
– Stage n: nth play of game (n = 1, 2, 3)
– xn: number of chips to bet at stage n
– State sn: number of chips in hand to begin
stage n

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 24
Probabilistic Dynamic Programming

• Problem formulation (cont’d.)

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 25
Probabilistic Dynamic Programming

• Solution

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 26
Probabilistic Dynamic Programming

• Solution (cont’d.)

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 27
Probabilistic Dynamic Programming

• Solution (cont’d.)

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 28
Probabilistic Dynamic Programming

• Solution (cont’d.)
– From the tables, the optimal policy is:

– Statistician has a 20/27 probability of winning

the bet with her colleagues

Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 29
11.5 Conclusions

• Dynamic programming
– Useful technique for making a sequence of
interrelated decisions
– Requires forming a recursive relationship
– Provides great computational savings for very
large problems
• This chapter: covers dynamic programming
with a finite number of stages
– Chapter 19 covers probabilistic DP when
stages continue ro recur indefinitely
Copyright 2020 © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of
McGraw-Hill Education. 30