Water Resources Systems:: Modeling Techniques and Analysis | PDF | Dynamic Programming | Mathematical Optimization
Scribd
Upload
33 views

Water Resources Systems:: Modeling Techniques and Analysis

1. Dynamic programming is a mathematical technique for solving sequential decision problems and is well-suited for optimization problems involving multi-stage decisions like reservoir operation and irrigation scheduling. 2. The document provides an example of using dynamic programming to optimally allocate a total of 6 units of water across 3 users in discrete steps to maximize total return. 3. Bellman's principle of optimality states that the optimal policy for remaining stages is independent of previous stages, allowing problems to be broken into sequential single-stage decisions.

Uploaded by

007ank007
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
33 views

Water Resources Systems:: Modeling Techniques and Analysis

1. Dynamic programming is a mathematical technique for solving sequential decision problems and is well-suited for optimization problems involving multi-stage decisions like reservoir operation and irrigation scheduling. 2. The document provides an example of using dynamic programming to optimally allocate a total of 6 units of water across 3 users in discrete steps to maximize total return. 3. Bellman's principle of optimality states that the optimal policy for remaining stages is independent of previous stages, allowing problems to be broken into sequential single-stage decisions.

Uploaded by

007ank007
Copyright
© Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

INDIANINSTITUTEOFSCIENCE

Water Resources Systems:


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

Summary of the previous lecture


Dual problem Formulation of dual problem Dual problem solution from solution of the primal problem Sensitivity analysis Change in the RHS of constraints

DYNAMIC PROGRAMMING

Dynamic Programming
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 1950s. Applications : Reservoir operation, water allocation, capacity expansion, irrigation scheduling, water quality control, shortest route problems etc.

An Example of Multi-stage Decisions


Sequential decisions Missile Target

Missile tracking radar Computer

Target tracking radar

Ref: S.S.Rao (1996), Engineering optimization, Theory and practice, John Wiley & Sons, Inc.

Dynamic Programming
State of the system Current position, speed and orientation of Missile and Target. Decision: Speed and orientation for the Missile during next time interval. Objective: To hit the Target in minimum time.

Dynamic Programming
Representation of DP problem: Single stage decision problem Return R = r(S, X)

Input state S

Output state T

Decision X
7

Dynamic Programming
Serial multi-stage decision problem Output from one state is input to the next

Rn Sn Sn-1

Rn-1 Sn-2

R2 S1

R1 S0

Xn
Stage n

Xn-1
Stage n-1

X2
Stage 2

X1
Stage1
8

Dynamic Programming
Bellmans principle of optimality: Given the current state of system, the optimal policy (sequence of decisions) for the remaining stages is independent of the policy adopted in the previous stages. The principle implies that, given the state Si of the system at a stage i, one must proceed optimally till the last stage, irrespective of how one arrived at the state Si.

Dynamic Programming
Stage-wise optimization: S1
Stage1

X1 S2

' 1

Stage 2

S T S2 , X 2
' 1

X2 . State transformation: A function of state variable S2 and decision X2 .


10

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. The allocation is made in discrete steps of one unit ranging from 0 to 6.
Progress of computations

User 3

User 2

User 1

x3

x2

x1
11

Dynamic Programming
The returns obtained from the users for a given allocation are as follows
Amount of water allocated X 0 1 2 3 4 5 6 Return from User 3 R3(x) 0 5 8 9 8 5 0 User 2 R2(x) 0 5 6 3 -4 -15 -30 User 1 R1(x) 0 7 12 15 16 15 12
12

Dynamic Programming
R1 Stage 1: S1
User 1

f1* S1 Max R1 x1
0 < x 1 < S1 0 < S1 < Q

x1

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
13

Dynamic Programming
S1 0 1 x1 0 0 1 0 2 1 2 0 3 1 2 3 R1(x1) 0 0 7 0 7 12 0 7 12 15
Contd.
14

f1* S1 Max R1 x1

* x1

0 7

0 1

12

15

Contd.
S1 x1 0 1 4 2 3 4 0 1 5 2 3 4 5 0 1 2 6 3 4 5 6 R1(x1) 0 7 12 15 16 0 7 12 15 16 15 0 7 12 15 16 15 12

f1* S1 Max R1 x1

* x1

16

16

16

15

You might also like