Dynamic programming
• Dynamic programming is a useful mathematical technique for making
a sequence of interrelated decisions
• It provides a systematic procedure for determining the optimal
combination of decisions
• In contrast to linear programming, there does not exist a standard
mathematical formulation of “the” dynamic programming problem.
• Rather, dynamic programming is a general type of approach to
problem solving, and the equations used must be developed to fit
each situation.
Dynamic programming example
• Stagecoach problem (shortest path problem)
Arc Distance Arc Distance Arc Distance Arc Distance
1–2 5 2–7 8 4–6 5 6–9 7
1–3 5 3–5 8 4–7 7 7–8 5
1–4 6 3–6 10 5–8 6 7–9 7
2–5 4 3–7 5 5–9 8 8 – 10 8
2–6 7 4–5 4 6–8 9 9 – 10 9
Dynamic programming example
• Solution - Stagecoach n = 1 more stage to go
problem (shortest path f1(s, x1) = dsx1; f1*(s) = min. f1(s, x1)
problem) s x1 f1(s) x1*
8 10 8 10
For this problem, 9 10 9 10
Stage – each stage of journey
State – current location (node) of the traveler n = 2 more stages to go
Decision variable – next destination (node) f2(s, x2) = dsx2+f1*(x2); f2*(s) = min. f2(s, x2)
Criterion of effectiveness – minimize total
x2
distance travelled s f2*(s) x2*
8 9
General recursive relationship: 5 14 17 14 8
6 17 16 16 9
fn(s, xn) = dsxn+fn-1*(xn); fn*(s) = min. fn(s, xn)
7 13 16 13 8
Dynamic programming example
n = 3 more stages to go
• Solution -
f3(s, x3) = dsx3+f2*(x3); f3*(s) = min. f3(s, x3)
Stagecoach problem
X3
(shortest path S f3*(s) x3*
5 6 7
problem)
2 18 23 21 18 5
3 22 26 18 18 7
Shortest paths: 4 18 21 20 18 5
1-2-5-8-10
1-3-7-8-10 n = 4 more stages to go
Shortest total distance: 23 units
f4(s, x4) = dsx4+f3*(x4); f4*(s) = min. f4(s, x4)
X4
S f4*(s) x4*
2 3 4
1 23 23 24 23 2, 3
Dynamic programming problem - characteristics
• The 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 that
stage
• The effect of the policy decision at each stage is to transform the current
state to a state associated with the beginning of the next stage
• The solution procedure is 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 adopted in previous stages.
Dynamic programming problem - characteristics
• The solution of a dynamic programming problem is based upon
Bellman’s principle of optimality (recursive optimization technique),
which states:
“The optimal policy must be one such that, regardless of how a particular state
is reached, all later decisions (choices) proceeding from that state must be
optimal.”
• Based on this principle of optimality, an optimal policy is derived by
solving one stage at a time, and then sequentially adding a series of
one-stage-problems that are solved until the optimal solution of the
initial problem is obtained.
Dynamic programming problem -
characteristics
• The solution procedure begins by finding the optimal policy for the
last stage.
• A recursive relationship that identifies the optimal policy for stage n,
given the optimal policy for stage n + 1, is available (for min objective)
• When we use the recursive relationship, the solution procedure starts
at the end and moves backward stage by stage—each time finding
the optimal policy for that stage— until it finds the optimal policy
starting at the initial stage.
Distribution of effort problem
• The world health council has five medical teams available to allocate
among three countries to improve their medical care, health
education, and training programs. The council needs to determine
how many teams (if any) to allocate to each of these countries to
maximize the total effectiveness of the five teams. The number
allocated to each country must be an integer. The measure of
performance being used is additional person-years of life. (For a
particular country, this measure equals the increased life expectancy
in years times the country’s population.)
• Three interrelated decisions, namely, how many medical teams to
allocate to each of the three countries to be made
Distribution of effort problem
• The three countries can be considered as the three stages.
• Decision variables xn (n = 1, 2, 3) - number of teams to allocate to stage (country) n.
• State, sn = number of medical teams still available for allocation to remaining
countries (n=1,2, 3). E.g. s1 = 5; s2 = 5- x1; s3 = s2 - x2
• Graphical display of the problem,
showing the possible states at each
stage, the possible transitions in
states, and the corresponding
contributions to the measure of
performance.
• The overall problem is to find the
path from the initial state 5
(beginning stage 1) to the final state
0 (after stage 3) that maximizes the
sum of the numbers along the path.
Distribution of effort problem
• Criterion of effectiveness
Let pi(xi) be the measure of performance from allocating xi medical
teams to country i. Thus, the objective is to choose x1, x2, x3 so as to
Distribution of effort problem
• Recursive relationship
Distribution of effort problem
• Solution:
Distribution of effort problem
• Solution:
Knapsack problem
• Classically deals with the situation in which a soldier (or a hiker) must decide on the most
valuable items to carry in a backpack.
• Problem is a general resource allocation problem in which a single limited resource is
allocated to multiple alternatives (e.g. limited funds assigned to projects) with the
objective of maximizing total return
• A 4-ton vessel can be loaded with one or more of three items. The unit weight (wi) and
revenue (ri) corresponding to each item i is given in the table below. How should the
vessel be loaded to maximize the total return?
Item i wi (in Tons) ri (in 1000 USDs)
1 2 31
2 3 47
3 1 14