INDIAN INSTITUTE OF SCIENCE

Water Resources Systems:

Modeling Techniques and Analysis
Lecture - 15
Course Instructor : Prof. P. P. MUJUMDAR
Department of Civil Engg., IISc.

1
Summary of the previous lecture

• Introduction to Dynamic Programming

• Representation of multi-stage decision problems
Rn Rn-1 R2 R1
Sn Sn-1 Sn-2 S1 S0

Xn Xn-1 X2 X1
• Bellman’s principle of optimality

2
 Dynamic Programming

Water allocation problem:

• A total of 6 units of water is to be allocated optimally
to three users, User 1, User 2 and User 3.
Amount of Return from
water allocated User 3 User 2 User 1
x R3(x) R2(x) R1(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
3
 Dynamic Programming
R1
Stage 1: S1 User 1

x1
f1*  S1   Max  R1  x1  
0 < x 1 < S1
0 < S1 < Q
S1 : Amount of water available for allocation to User 1
x1 : Amount of water allocated to User 1
x1* : Allocation to User 1, that results in f1  S1 
*

f1*  S1  : Maximum return due to allocation of S1

4
 Dynamic Programming
S1 x1 R1(x1) f1*  S1   Max  R1  x1   x1*
0 0 0 0 0
0 0
1 7 1
1 7
0 0
2 1 7 12 2
2 12
0 0
1 7
3 15 3
2 12
3 15
Contd.

5
Contd.
S1 x1 R1(x1) f1*  S1   Max  R1  x1   x1*
0 0
1 7
4 2 12 16 4
3 15
4 16
0 0
1 7
2 12
5 16 4
3 15
4 16
5 15
0 0
1 7
2 12
6 3 15 16 4
4 16
5 15
6 12 6
 Dynamic Programming
R2(x2)
Stage 2: S2 - x2
S2 User 2 User 1

x2
f 2*  S 2   Max  R2  x2   f1*  S 2  x2  
0 < x 2 < S2
0 < S2 < Q

S2 : Amount of water available for allocation to User 2

and User 1 together
x2 : Amount of water allocated to User 2
7
 Dynamic Programming

S2 –x2 : Amount of water available for allocation at

stage 1 (to User 1)

f 2*  S 2  : Maximum return due to allocation of S2

x2* : Allocation to User 2, that results in f 2*  S 2 

8
 Dynamic Programming
f 2*  S 2   Max  R2  x2   f1*  S 2  x2  
0 < x2 < S2 ; 0 < S2 < Q

f1*  S 2  x2  R2*  x2  
f1  S 2  x2  2  2 
S2 x2 R2(x2) S 2 – x2 f *
S x2*

0 0 0 0 0 0 0 0
0 0 1 7 7
1 7 0
1 5 0 0 5
0 0 2 12 12
2 1 5 1 7 12 12 0, 1
2 6 0 0 6
0 0 3 15 15
1 5 2 12 17
3 17 1
2 6 1 7 13
3 3 0 0 3
Contd. 9
Contd.
S2 x2 R2(x2) S2 – x2 f1*  S 2  x2  R2  x2  
f1*  S 2  x2 
f 2*  S 2  x 2*
0 0 4 16 16
1 5 3 15 20
4 2 6 2 12 19 20 1
3 3 1 7 10
4 -4 0 0 -4
0 0 5 16 16
1 5 4 16 21
2 6 3 15 21
5 21 1, 2
3 3 2 12 15
4 -4 1 7 3
5 -15 0 0 -15
0 0 6 16 16
1 5 5 16 21
2 6 4 16 22
6 3 3 3 15 18 22 2
4 -4 2 12 8
5 -15 1 7 -8
6 -30 0 0 -30 10
 Dynamic Programming

Stage 3: R3(x3)

S3 – x3
S3 User 3 User 2 User 1

x3

f 3*  S3   Max  R3  x3   f 2*  S3  x3  

0 < x 3 < S3
S3 = Q
11
 Dynamic Programming
S3 : Amount of water available for allocation to User 1,
User 2 and User 3 together = 6 units
x3 : Amount of water allocated to User 3

S3 –x3 : Amount of water available for allocation at

stage 2 (to User 1 and User 2 together)

f3*  S3  : Maximum return due to allocation of S3

x3* : Allocation to User 3, that results in f3  S3 

*

12
 Dynamic Programming
f3*  S3   Max  R3  x3   f 2*  S3  x3  
0 < x3 < S3
S3 = Q

R x 
S3 x3 R3(x3) S 3 – x3 f 2*  S3  x3  f 3*  S3  x  f3*  S3  x3*
2 3 3

0 0 6 22 22
1 5 5 21 26
2 8 4 20 28
6 3 9 3 17 26 28 2
4 8 2 12 20
5 5 1 5 10
6 0 0 0 0

13
 Dynamic Programming
• When the third stage is solved, all the three users
are considered for allocation; thus the total
maximum return is
f3*  6   28
• The allocations to individual users are traced back.

From the table for stage 3,

x3*  2
From this the water available for stage 2 is obtained as,
S2  Q  x3*  6  2  4
14
 Dynamic Programming
From the table for stage 2, with the value of S2 = 4 ,

x 1
*
2

From this the amount of water available for allocation at

stage 1 is obtained as,

S1  S2  x  4  1  3
*
2

From the table for stage 1, with the value of S1 = 3 ,

x 3
*
1

15
 Dynamic Programming

Thus the optimal allocations are

x1* = Allocation to User 1 = 3 units

x2* = Allocation to User 2 = 1 units

x3* = Allocation to User 3 = 2 units

Maximum return resulting from the allocations = 28

16
 Dynamic Programming

Characteristics of DP problem:
• 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
water available for allocation at a stage defines
the state at that stage.

17
 Dynamic Programming

• 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)

18
 Dynamic Programming

• Recursive relationship identifies the optimal

decision at stage n, for state Sn, given the optimal
decisions for each state at stage (n – 1).
f n  S n   Max  rn  xn   f n 1 T  S n , xn 
 xn 

rn (xn) : Return for decision xn in current state

T(Sn , xn) : Transfer function to get the state Sn-1
corresponding to Sn and xn.
Stage 1
Stage 2
In allocation problem, Stage 3
f n  S n   Max  rn  xn   f n 1  S n  xn  
 xn 
19
 Dynamic Programming

• Solution moves backward (or forward) stage by

stage, till optimal decisions for the last stage are
found.
• Optimal decisions for other stages are traced
back.

20