CHAPTER FIVE
DYNAMIC PROGRAMMING AND ITS
APPLICATION
Content of the Chapter
Introduction and preliminaries
Water allocation problems
Reservoir operation problems
Capacity expansion and shortest route problems
Introduction
Dynamic programming (DP) is ideally suited for sequential
decision problems
DP is a mathematical technique well suited for the optimization of
multistage decision problems
Developed by Richard Bellman in the early 1950’s
Applications:
• Water allocation; Reservoir operation; Capacity expansion;
• Shortest route problem; Irrigation scheduling
Characteristics of DP problems
• Multi stage decision problem / sequential decision
• Output from one state is input to the next state
• Problem is divided into stages with a policy decision
required at each stage
• Each stage has a number of possible states associated
with it.
• E.g. in the allocation problem, the amount of
resources available for allocation at a stage defines
the state at that stage
Net Benefit, NB1
Input Output
Stage 1
S1 S2
Decision variable, X1
Cont.
DP at Various stage:
NB1 NBt NBT
S2 St St+1 ST ST+1
S1 Stage 1 Stage t Stage T
X1 Xt XT
Stage 1 Stage n-1 Stage n
Cont.
Policy decision transforms the current state into a
state associated with the next stage.
State Transformation : T(Sn , xn)
Sn : Current state in stage n
xn: Decision in stage n
In allocation problem, the transformation
function is, (Sn – xn)
Solution of DP
• Bellman principle of optimality: Given the current
state of a system the optimal policy (sequence of
decision) for the remaining stage is independent of the
policy adopted in the previous stages.
• In serial multistage decision making problems, the stage
number may be assigned in increasing order either in the
forward direction or in the backward direction.
Backward recursion
Water allocation problem
Example: A total of 6 units 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.
Cont.
Data by table:
Solution:
The problem is to find allocations to the three users
such that the total return is maximized. The
following steps show the computations of backward
recursion.
Cont.
Cont.
Stage 2:
Cont.
Cont.
Cont.
B. Reservoir Operation Problem
• A classical multistage decision problem in the area
of water resources management is the reservoir
operation problem
• Simply stated, the problem is to specify release Rt
during a time period t ( such as a month, a season,
etc.),
• When the storage, St at the beginning of the period
t, and the inflow, Qt during the period t are known.
Cont.
• The sequence of the releases, {Rt} in a year, is called
the Reservoir Release Policy for the year
• The release policy is obtained to optimize (minimize
or maximize) a system performance measure (e.g.
hydropower produced during the year), which is in
general, a function of the storage, St and the release
Rt.
Cont.
The storage, St at the beginning of the period t
changes to storage St+1 at the beginning of
period t+1 ( or storage at the end of period t)
because of the inflow Qt and the release Rt.
This transformation is governed by reservoir
mass balance, or the storage continuity
equation, which is written, neglecting all
losses, as
St+1 = St + Qt – Rt
Cont.
• The reservoir storage must also satisfy the capacity
constraint, St ≤ K, where is the live storage capacity
of the reservoir.
Cont.
• The operational objective may be to maximize the total
net benefit during a year, which is stated as
• Where Bt (St, Rt) is the net benefit during period t for
given values of St and Rt, and T is the number of periods
in the year and solved with backward recursion.
Cont.
Cont
Example:
Inflows during four seasons to a reservoir with storage
capacity of 4 units are 2, 1, 3 and 2 units respectively.
Overflows from the reservoir are also included in the
release. Reservoir storage at the beginning of the year is
0 units. Release from the reservoir during the season
results in the following benefits which are same for all
the four seasons.
Solution
To obtain the release policy backward recursive equation
is used, starting with the last stage.
Cont.
Continue:
Cont.
Solution cont.
Cont.
Cont. solution
Cont.
Cont. Solution:
Cont.
Cont. solution: