10 Dynamic Programming

江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
2
运筹学
Operations Research
10 Dynamic Programming
10.1 A Prototype example for dynamic programming
运筹学
Operations Research
10 Dynamic Programming
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
1
运筹学
Operations Research
Then the last result is followed: B E
1
3
H F
3
3
A
4 3
C
பைடு நூலகம்
J
4
4 1
I G
D
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
11
运筹学
Operations Research
10.2 Characteristics of DP problems
A recursive relationship that identifies the optimal policy for stage n, given the optimal policy for stage n+1, is available. When we use this 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 if finds the optimal policy starting at the initial stage.
7
运筹学
Operations Research
10.1 A Prototype example
f2(s, x2)= Csx2+f3*(x2) E 11 7 8 F 11 9 8 G 12 10 11
x2 s
f2*(s) 11 7 8
x2 * E or F E E or F
N=2
B C D
x1 s
f1(s, x1)= Csx1+f2*(x1) B 13 C 11 D 11
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
6
运筹学
Operations Research
10.1 A Prototype example
N=4
s H I*
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
10
运筹学
Operations Research
10.2 Characteristics of DP problems
3 4
E
4
1
A
C 2
4
F
6 3
H
3
J
4
4 1
3
I
3
D
5
G
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
4
运筹学
Operations Research
The solution procedure is designed to find an optimal policy for the overall problem, I.e, a prescription of the optimal policy decision at each stage for each of the possible states. Given the current state, an optimal policy for the remaining stages is independent of the policy decisions on only the current state and not on how you got there. This is the principle of optimality for dynamic programming. The solution procedure begins by finding the optimal policy for the last stage.
10 Dynamic Programming
10.1 A Prototype example for dynamic programming 10.2 Characteristics of dynamic programming 10.3 Deterministic Dynamic Programming 10.4 Probabilistic Dynamic Programming 10.5 Conclusions
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
3
运筹学
Operations Research
10.1 A Prototype example
B
6 2 3 4 3
f4*(s) 3 4
x4* J J
x3 s
f3(s, x3)= Csx3+f3*(x3) H 4 9 6 I 8 7 7
f3*(s) 4 7 6
x3 * H I H
N=3
E F G
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
10.1 A Prototype example
This fortune seeker was a prudent man who was quite concerned about his safety. After some thought, he came up with a rather clever way of determining the safest route. Life insurance polices were offered to stagecoach passengers. Because the cost of the policy for taking any given stagecoach run was based on a careful evaluation of the safety of that run, the safest route should be the one with the cheapest total life insurance policy.
Solving the Problem
f n * ( s ) = min f n ( s, xn ) = min Csxn + f n ( s, xn )
xn xn
= min {immediate cos t ( stage n) +
xn
minimum future cos t stages n + 1 onward )
江西财经大学 信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006
5
运筹学
Operations Research
10.1 A Prototype example
The cost for the standard policy on the stagecoach run from state I to state j, which will be denoted by cij. We shall now focus on the question of which route minimizes the total cost of the policy.
9
运筹学
Operations Research
10 Dynamic Programming
10.2 Characteristics of dynamic programming problems