04.
Dynamic Programming
Learning Objectives
When you complete this chapter you should be able to
understand:
• Understand the concept of dynamic programming
• Know characteristics of dynamic programming
• Know applications of dynamic programming
2
Dynamic programming – The concept
• Complex problems are sometimes solved quickly if approached in a
sequential manner.
• Dynamic Programming (DP) is a sequential or multistage decision making
process. i.e. in DP decisions are made at a number of stages.
• DP transforms a complex problem into a sequence of simpler problems.
• The concept of DP is:
– Problem is divided into smaller sub-problems
– Optimize these sub-problems without losing the integrity of the original
problem.
– Decisions made in a stage will affect the decisions at the subsequent stages
but are independent on each other.
Example: An N variable problem is represented by N single variable problems.
These problems are solved successively to get the optimal value of the original
problem.
Dynamic programming – The concept
• Consider a single stage decision process
– Here,
S1 is the input state variable
S2 is the output state variable
X1 is the decision variables, and
NB1 is the net benefit
The transformation function for the input and output is
S2 = g(X1, S1)
Net benefits are expressed as a function of decision variables and
input variable
NB1 = h(X1, S1)
Dynamic programming – The concept
• Now, consider a multistage decision process consisting of T stages
• For the tth stage the stage transformation and the benefit functions are
– St+1 = g(Xt, St)
– NBt = h(Xt, St)
• Objective of this multistage problem is to find the optimum values of all
decision variables X1, X2,…, XT such that the individual net benefits of each
stage that is expressed by some objective function, f(NBt) and the total net
benefit which is expressed by f(NB1, NB2,…, NBT) should be maximized.
Dynamic programming – The concept
• Therefore, dynamic programming can be applied to this multistage
problem if the objective function is separable and monotonic.
• An objective function is separable, if it can be decomposed and expressed
as a sum or product of individual net benefits of each stage.
Satisfying the equations,
St+1 = g(Xt, St)
NBt = h(Xt, St) for t = 1,2,…,T
Application areas of DPP
• Allocating scarce resources. E.g. water allocation to users
• Shortest route problem. E.g Water supply distribution
• Production scheduling problem E.g. Critical path in CPM and PERT
• Capacity expansion problem. E.g. Road expansion, Water supply
• Reservoir operation problem
• Equipment replacement problem
Approach to DPP
• The process of multi-stage optimization is based on the Bellman’s principle
of optimality which states that
“An optimal policy (or a set of decisions) has the property that
whatever the initial state and initial decision are, the remaining
decisions must constitute an optimal policy with regard to the
state resulting from the first decision.”
How to solve a DPP?
• Recursive equations are used to solve a DPP in sequence.
– Recursive equations are used to structure a multistage decision
problem as a sequential process.
– Each recursive equation represents a stage at which a decision is
required.
– A series of equations are successively solved, each equation
depending on the output values of the previous equations.
• Recursive equations for a multistage decision process can be formulated in
• a backward manner, and
• a forward manner
• Backward recursion - A problem is solved by writing equation first for the
final stage and then proceeding backwards to the first stage.
• Forward recursion - The problem is solved by starting from stage 1 and
proceeding towards the last stage.
How to solve a DPP? – Backward Recursion
S3 = S2-X2
S2 = S1-X1
How to solve a DPP?
To explain the concept of backward and forward recursion
approach, take the following Water Allocation Problem
• Consider a canal supplying water for three different fields
for crop production.
• Maximum capacity of the canal is Q units of water
• Amount of water allocated to each field as Xi
How to solve a DPP?
• Let net benefits (returns) from producing the crops are
expressed as a function of the water allocated. i.e. NB1(x1),
NB2(x2) and NB3(x3)
• Optimization Problem: Determine the optimal allocations xi
to each crop that maximizes the total net benefits from all the
three crops.
How to solve a DPP?
• Objective function: To maximize the net benefits
3
Max NBi (xi )
i =1
• Subjected to the constraints
x1 + x2 + x3 Q
0 xi Q for i = 1, 2, 3
• Let f1(Q) be the maximum net benefits that can be
obtained from allocating water to crops 1, 2 and 3
f1 (Q) = Max NBi (xi )
3
x1 + x2 + x3 Q
i =1
x , x , x 0
1 2 3
How to solve a DPP?
A. Backward Recursion:
How to solve a DPP?
A. Backward Recursion:
f1 (Q) = Max NB1 (x1 ) +
0 x1 Q = S1
Max NB2 (x2 ) + Max NB3 (x3 )
S1 =Q
0 x2 Q − x1 = S 2
0 S 2 Q 0 x3 S 2 − x2 = S3
0 S 3 Q
Transforming this into three problems each having only one
decision variable:
• Now starting from the last stage, let f3(S3) be the maximum
net benefits from crop 3
• State variable S3 for this stage can vary from 0 to Q
How to solve a DPP?
• Thus,
f 3* ( S3 ) = Max NB3 (x3 )
0 x3 S3
0 S 3 Q
• But S3=S2-x2. Therefore, f3(S3) = f3(S2-x2)
• Hence, the maximum benefits derived from crops 2 and 3
for a given quantity S2 which can vary between 0 and Q
f 2* ( S 2 ) = Max
0 x2 S 2
NB (x ) + f
2 2
*
3
( S 2 − x2 )
0 S 2 Q
How to solve a DPP?
• Again,S2=S1-x1= Q-x1. Therefore, f2(S2)=f2(S1-x1). And, S1 =Q.
• Hence, the maximum benefits derived from crops 1, 2 and
3 for a given quantity S1 which is equal to Q
f 1* ( S1 ) = f 1* (Q) = Max NB1 (x1 ) + f 2* ( S1 − x1 )
0 x1 Q
S1 =Q
Note:
Once the value of f3(S3) is calculated the value of f2(S2) can be
determined from which f1(Q) can be determined.
Numerical Example 1 . Resource Allocation Problem
Numerical Example 1 . Resource Allocation Problem
• Net benefits from producing the crops can be expressed
as a function of the water allotted. They are calculated as
below.
NB1 ( x1 ) = 5x1 − 0.5x12
NB2 ( x2 ) = 8x2 − 1.5x22
NB3 ( x3 ) = 7 x3 − x32
xi NB1(x1) NB2(x2) NB3(x3)
0 0.0 0.0 0.0
1 4.5 6.5 6.0
2 8.0 10.0 10.0
3 10.5 10.5 12.0
4 12.0 8.0 12.0
Numerical Example 1 . Resource Allocation Problem
Representation of the problem as a set of nodes and links
Numerical Example 1 . Resource Allocation Problem
Case A. Backward Recursion
• Sub-optimization function for the 3rd crop:
f 3 ( S3 ) = Max NB3 (x3 )
0 x3 S3
0 S 3 Q
Numerical Example 1 . Resource Allocation Problem
• Considering the last two stages together, the sub-
optimization function is
f 2* ( S 2 ) = Max
0 x2 S 2
NB (x ) + f
2 2
*
3
( S 2 − x2 )
0 S 2 Q
Numerical Example 1 . Resource Allocation Problem
Numerical Example 1 . Resource Allocation Problem
• Considering all the three stages together,
f 1* (Q) = Max NB1 (x1 ) + f 2* ( S1 − x1 )
0 x1 Q
S1 =Q
Numerical Example 1 . Resource Allocation Problem
Check :
NB1 ( x1 ) = 5 x1 − 0.5 x12 = 5 1 − 0.5 12 = 4.5
NB2 ( x2 ) = 8 x2 − 1.5 x22 = 8 1 − 1.5 12 = 6.5
NB3 ( x3 ) = 7 x3 − x32 = 7 2 − 2 2 = 10
3
Max NBi = 4.5 + 6.5 + 10 = 21
i =1
Assignment
1. A total of 6units of water is to be allocated optimally to three users. The
allocation is made in discrete steps of one unit ranging from 0 to 6. With the
three users denoted as user 1, user 2 and user 3 respectively. The returns
obtained from the users for a given allocation are given in the following table.
Find allocations to the three users so that the total return is maximized.
Amount of water allocated Return from
User 1 User 2 User 3
B1 (x) B2 (x) B3 (x)
0 0 0 0
1 5 5 7
2 8 6 12
3 9 3 15
4 8 -4 16
5 5 -15 15
6 0 -30 12
Answer: x1 = 2; x2 = 1; x3 = 3 and Maximum return = 28
Exercise
2. The government is planning to implement a mix of four
prioritized developmental projects with 3 million euros
obtained from Africa Development Bank. The profits that can
be gained by implementing the projects with 1 to 3 million
euros allocated are shown below. What is the mix of projects
to develop so that the return will be maximized?
x Proj #1 Proj #2 Proj #3 Proj #4
0 0 0 0 0
1 2 5 4 2
2 8 6 4 4
3 9 7 4 5
Thank You!
Questions?
28