- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
上式中“opt”表示“max”或“min”。
对于可乘性指标函数，上式可以写为
f k (s k )
opt
x k D k ( s k )
{v k (s k , x k ) f k 1 (s k 1 )}
k 1,2, , n
以上式子称为动态规划最优指标的递推方程，是动态规划的 基本方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设 定最优指标的终端条件，一般最后一个状态n+1下最优指标 fn+1(sn+1) = 0。
表10-4
阶段1 本阶段始 点(状态) B1 A 4+12=16 本阶段各终点（决策） B2 3+13=16 B3 3+14=17 B4 2+12=14 到E的最 短距离 12 本阶段最优终 点(最优决策)
B4
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E
2012-8-18
8
以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。
2012-8-18 11
动态规划是用来解决多阶段决策过程最优化的一种方法。
多阶段决策： 是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态相互联系 而又相互区别的各个阶段； 每个阶段都要进行决策,目的是使整个过程的决策 达到 最优效果
多阶段决策求解思路：
将多阶段决策问题（n阶段）分解成n个具有递推关系的单阶 段决策问题，进行正推或逆推计算。
( s k 1 s k x k ) 阶段指标函数：p k ( x k ) 派遣 x k 支巡逻队时第K阶段产生的预 期损失；
最优指标函数：前K个阶段的最优目标
f k ( s k 1 )
状态转移方程： s k s k 1 x k
xk D ( S K )
min
PK ( X K )
f 3 ( s 3 ) min{ p 3 ( x 3 ) f 4 ( s 4 )}
x3
v 3 (s 3 , x 3 )
s3
2
24 24 24 24
3
22 22 22
4
f 3 ( s3 )
x
* 3
2 3 4 5
24
21 21
2 3 4 4
22 21 21
2012-8-18
19
当K=2时，给B派巡逻队， D ( s 2 ) 5 , 6 , 7
V k , 3 p k ( x k ) V k 1, 3
最优指标函数：
f k (sk )
2012-8-18
xk D ( S K )
min
PK ( X K )
f k 1 ( s k 1 )
18
逆序解法： 边界条件 f 4 ( s 4 ) 0
当K=3时，给C派巡逻队， D ( s 3 ) 2 ,3 , 4 ,5 ， x 3 2 ,3 , 4
2012-8-18 16
三、最优化原理
作为整个过程的最优策略具有如下性质：
不管在此最优策略上的某个状态以前的状
态和决策如何，对该状态来说，以后的所有决
策必定构成最优子策略。就是说，最优策略的
任意子策略都是最优的。
2012-8-18
17
§3 离散确定性动态规划模型求解
例：书P205 ，例4 解：设将向三个部位A，B，C派巡逻队作为三个阶段，K=1，2，3。 决策变量 x k 表示向第K个部位派遣的巡逻队数。 状态变量 s 表示第K个阶段时可供派遣的巡逻队数量。 k 状态转移方程： s k 1 s k x k 阶段指标函数： p k ( x k ) 派遣 x k 支巡逻队时第K阶段产生的预 期损失； 过程指标函数： 第K阶段到第3阶段的预期损失。
D1
8+10=18 7+10=17 1+10=11
D2
6+6=12 5+6=11 6+6=12
分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。
2012-8-18
6
第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和 终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路 径问题： 表-3
本阶段最优终 点（最优决策)
C2 C3 C3 C3
分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。
2012-8-18 7
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
阶段2
本阶段始点 （状态）
B1 B2 B3 B4
本阶段各终点（决策）
C1 2+12=14 4+12=16 4+12=16 7+12=19 C2 1+11=12 7+11=18 8+11=19 5+11=16 C3 6+11=17 2+11=13 3+11=14 1+11=12
到E的最 短距离 12 13 14 12
总共有3k-1×2条路径；
计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比 较的次数将迅速增加；
例如当 k=20时，加法次数为 4.2550833966227×1015 次， 比较 1.3726075472977×1014 次。若用1亿次/秒的计算机计 算需要约508天。
35+21
31+24
31+22
55
53
4
4
2012-8-18
20
当K=1时，给A派巡逻队，
D ( s1 ) 9
， x1 2 ,3 , 4
f 1 ( s1 ) min{ p 1 ( x1 ) f 2 ( s1 x1 )}
s1
x1
p 1 ( x1 ) f 2 ( s1 x1 )
2012-8-18 13
4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列， 称k子策略。P1,n(s1)即为全过程策略。 5、状态转移方程 Sk+1=Tk(Sk, Xk)：某一状态以及该状态下的 决策，与下一状态之间的函数关系。
6、阶段指标函数Vk(Sk, Xk)：从状态Sk出发，选择决策Xk所产 生的第k阶段指标。
12 B1 4 14 A 3 2 B3 3 2 6 1 11 7 2 4 8 3 1 12 C1 6 7 5 D2 6 6 6 8 10 D1 10
13 4 B2
0 E
C2
C3
11 1
14 7 5
B4
12
以上过程，仅用了22次加法，计算效率远高于穷举法。
2012-8-18 9
例2 资源分配问题 设有某种机器数台，用于完成两类工作A，B。由于机 器使用后有一定的损坏率，所以每年初的机器数量是变化 的；A、B两项工作产生的收益也不同。如何合理的分配机 器的使用，可使得三年的总收益最大? 假设第k年年初完好机器数是SK，用于A生产的机器数 是XK，则用于B生产的机器数是（SK- XK）；
f k 1 ( s k )
2012-8-18
22
顺序解法： 边界条件
f 0 ( s1 ) 0
当K=1时，给A派巡逻队，
， D ( s 2 ) 2 , 3 , 4 , 5
x1 2 , 3 , 4
下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。 2 C
B 1 1 8
4
4 A 3 2 3 B2
1 6 7 7 2 C2
6 D 1 10 E
5 6
4
B3 7 3
8 C3 1
1 6
D 2
5
4
2012-8-18 3
用穷举法的计算量:
如果从A到E的站点有k个，除A、E之外每站有3个位置则
过程指标函数Vk,n(Sk；Xk, Xk+1,…, Xn)：从状态Sk出发，选 择决策Xk, Xk+1, …, Xn所产生的过程指标。
2012-8-18
14
动态规划要求过程指标具有可分离性，即
Vk,n(sk, xk, xk+1, …, xn) = Vk(sk, xk)+Vk+1(sk+1, xk+1, …, xn)
分析得知：从D1和D2到E的最短路径唯一。
2012-8-18 5
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表-2
阶段3 本阶段始点 （状态） C1 C2 C3 本阶段各终点（决策） 到E的最短距离 12 11 11 本阶段最优终点 （最优决策) D2 D2 D1
opt
xk Dk ( sk )
{V k , n ( s k , Pk , n )}
2012-8-18
15
对于可加性指标函数，上式可以写为
f k (s k )
opt
x k D k ( s k )
{v k (s k , x k ) f k 1 (s k 1 )}
k 1,2,, n
用于A工作的设备的完好率是：a%，用于B工作的设备 的完好率是：b%。则下一年初的完好机器数是
SK+1= a% XK+ b% （SK- XK） 第k年的收益：
