文档介绍：作业:P215 第八章动态规划 第一节多阶段决策问题 动态规划是用来求解多阶段决策问题的。
多阶段决策问题:可将问题分为若干个相互联系的阶段,在每一阶段分别对应着若干个可以选择的决策,当每个阶段的决策选定之后,也就确定了问题的一个决策过程。将各阶段的决策综合起来,就构成了一个决策序列,称为问题的一个策略。 显然,决策不同,过程的策略也不同。对应于每一个策略,都有一个确定的效果(值)。一般情况下,策略不同,效果也不同。 多阶段决策的目的就是在所有可采取的策略中选取一个最优策略,使在一定条件下取得最优的效果。
例三:将一个数c( c>0)分为n个部分c1,c2,…,cn 之和,且ci>0(i=1,2,…,n), 问如何分割使其乘积最大?
第二节最优化原理与动态规划数学模型 基本思想 将多阶段问题转化为单阶段问题,按着目标要求和递推关系求出最优结果。 (用逆序解法解例1)
[例1] 最短路线问题。
设有一个旅行者从图8-1中的A点出发,途中要经过B、C、D等处,最后到达终点E。从A到E有很多条路线可以选择,各点之间的距离如图中所示,问该旅行者应选择哪一条路线,使从A到达E的总路程为最短。
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
f4(D2)=4
f3(C1)=4
f3(C2)=7
f3(C3)=6
f2(B1)=11
f2(B2)=7
f2(B3)=8
f1(A)=11
状态最优决策状态最优决策状态最优决策状态最优决策状态
A,( A,B3), B3 ,(B3,C2),C2,(C2,D2), D2,(D2,E), E
从A到E的最短路径为11,路线为A→B3→C2 →D2 →E 。