动态规划应用举例.ppt.ppt

动态规划方法应用举例
学习例题的方法建议:
第一步先看问题,充分理解问题的条件、情况及求解目标。
第二步结合前面讲到的理论和解题过程,考虑如何确定问题的状态变量,决策变量以及指标函数等——这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。
第三步动手把建模思路数学地表达出来,或者说,把该问题作
为习题独立地来做。
第四步把自己的求解放到一边,看书中的求解方法,要充分理
解教材中的论述.
第五步对照自己的求解,分析成败。
注意:动态规划的四大要素
①状态变量及其可能集合 skSk
②决策变量及其允许集合 xk  Dk
③状态转移方程 sk+1= Tk (sk ,xk )
④阶段指标 vk ( sk ,xk )
资源分配问题
求对三个项目的最优投资分配,使总投资效益最大。
例1 有资金4万元,投资A、B、C三个项目,每个项目
的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益(吨)和投入资金(万元)关系见下表:
项目
投入资金
A
B
C
1万元
15吨
13吨
11吨
2万元
28吨
29吨
30吨
3万元
40吨
43吨
45吨
4万元
51吨
55吨
58吨
阶段k:每投资一个项目作为一个阶段;k=1,2,3
状态变量sk:投资第k个项目前的资金数;
决策变量xk:第k个项目的投资额;
决策允许集合:0≤xk≤sk (k=1,2), x3=s3
状态转移方程:sk+1=sk-xk
阶段指标:vk(sk ,sk)见表中所示;
基本(递推)方程:fk(sk)=max{vk(sk ,xk)+fk+1(sk+1)}
终端条件:f4(s4)=0
s3
D3(s3)
v3(s3,x3)
v3(s3,x3)+f4(s4)
f3(s3)
x3*
0
0
0
0+0=0
0
0
1
11
1
1
11
11+0=11*
2
30
2
2
30
30+0=30*
3
45
3
3
45
45+0=45*
4
58
4
4
58
58+0=58*
s2
D2(s2)
s3
v2(s2,x2)
v2(s2,x2)+f3(s3)
f2(s2)
x2*
0
0
0
0
0+0=0
0
0
1
0
1
0
0+11=11
13
1
1
0
13
13+0=13*
2
0
2
0
0+30=30*
30
0
1
1
13
13+11=24
2
0
29
29+0=29
3
0
3
0
0+45=45*
45
0
1
2
13
13+30=43
2
1
29
29+11=40
3
0
43
43+0=43
4
0
4
0
0+58=58
59
2
1
3
13
13+45=58
2
2
29
29+30=59*
3
1
43
43+11=54
4
0
55
55+0=55
s1
D1(s1)
s2
v1(s1,x1)
v1(s1,x1)+f2(s2)
f1(s1)
x1*
4
0
4
0
0+59=59
60
1
1
3
15
15+45=60*
2
2
28
28+30=58
3
1
40
40+13=53
4
0
51
51+0=51