水电与数字化工程学院
莫 莉
前节回顾
基本概念
• 状态(每阶段初始的出发点)
• 最短路问题中，各个节点就是状态 • 生产库存问题中，库存量是状态 • 物资分配问题中，剩余的物资量是状态
• 控制变量(决策变量)
• 最短路问题中，走哪条路 • 生产库存问题中，各阶段的产品生产量 • 物资分配问题中，分配给每个地区的物资量
u3U 3 ( x3 )
v3 ( x3 , u3 )
u3
f 4 ( x4 )
因有 U 3 ( x3 ) 2,3,4，又 4 x3 8，故可得到下表的计算结果。
U k ( xk ) {uk 2 uk 4}, (k 1,2,3,4) 状态转移方程：xk＋1＝ xk－uk
若用 vk ( xk , uk ) 表示 k 阶段派出的巡逻队数为u k 时，该阶段的部位的预 期损失值，
水电与数字化工程学院 莫 莉
2.1 引例
设用 f k ( xk ) 表示 k阶段状态为 x k，以此出发采用最优子策略到过
莫 莉
P44-1.1(1),1.3,1.4 P45-1.6(1)(2)
P74-2.3(1)(2),2.7 P75-2.8 P187-7.3,7.4,7.5 P187-7.7,7.13 P188-7.13(3),7.17 P189-7.21,7.23 P211-8.2,8.3
第3次作业 第4次作业
水电与数字化工程学院
的警卫巡逻。对每个部位可分别派出2～4支巡逻队，并且派出
巡逻队数的不同，各部位预期在一段时期内可能造成的损失有
差别，具体数字见下表。问该警卫部门应往各部位分别派多少
巡逻队，使总的预期损失为最小。
部位 预期损失 巡逻队数 2 3 4 A 18 14 10 B 38 35 31 C 24 22 21 D 34 31 25
动态规划所解决的问题：多阶段问题
动态规划的核心:
在于将问题公式化，也可以说 ，动态规划是将多阶段决策问 题进行公式化的一种技术。
动态规划的优缺点:
适用范围广，模型算法一体化，方便编程。 由于没有统一的标准模型，使得动态规划的应用
难度增加 。
水电与数字化工程学院 莫 莉
前节回顾
动态规划根据多阶段决策过程的时间参量类
水电与数字化工程学院
u 4 U 4 ( x4 )
min
v4 ( x4 , u4 )
f 5 ( x5 )
u 4 U 4 ( x4
min
v4 ( x4 , u4 ) )
莫 莉
f 4 ( x4 )
u 4 U 4 ( x4
min
v4 ( x4 , u4 ) )
部位 预期损失 巡逻队数 2 3 4
第三章 动态规划(Dynamic Programming)
主讲人：莫 莉
moli@
2015 年 6 月
水电与数字化工程学院 莫 莉
前节回顾
温
引例
故
多种应用
知
引例
新
动态规划基本概念
离散动态规划
动态规划优劣
经营管理中的应用
水电与数字化工程学院
莫 莉
前节回顾
型可以分为离散型决策过程和连续型决策过程；
根据决策过程的演变性态又可以分为确定型决策
过程和随机型过程。组合起来有下列类型：
离散确定型、离散随机型、连续确定型、连
续随机型。本章主要介绍离散确定型决策过程。
水电与数字化工程学院
莫 莉
前节回顾
例. (最短路径问题) 下图表示从起点A到终点E之间各点的距离。 求A到E的最短路径。
A 18 14 10
2.1 引例 B C D
38 35 31 24 22 21 34 31 25
因 U 4 ( x4 ) 2,3,4，又 x 4的可能值为 2 x 4 6，故由已知数据，可得
下表的结果。 再联合考虑对 C 、 D 两个部位派巡逻队，即 k 3。这时有
f 3 ( x3 ) min
前节回顾
温
引例
故
多种应用
ቤተ መጻሕፍቲ ባይዱ
知
引例
新
动态规划基本概念
离散动态规划
动态规划优劣
经营管理中的应用
水电与数字化工程学院
莫 莉
第三章 动态规划
1 2 基本概念介绍 离散动态规划★
3
连续动态规划
4
在水库调度中的应用
水电与数字化工程学院
莫 莉
2.1 引例
例某警卫部门共有12支巡逻队，负责4个要害部位 A, B ,C , D
水电与数字化工程学院
莫 莉
2.1 引例
解： 阶段数：把12支巡逻队往各部 位派遣看成依次分四个阶段。
部位 预期损失 巡逻队数 2 3 4 A 18 14 10 B 38 35 31 C 24 22 21 D 34 31 25
状态变量：xk表示每个阶段初
拥有的可派遣的巡逻队数。 集合为：
决策变量：uk表示对各部位派出的巡逻队数，各阶段允许的决策
程结束时的预期损失值，则有:
f k ( xk ) min {vk ( xk , uk ) f k 1 ( xk 1 )}
u k U k ( xk )
k 4，则上式可写为： 采用后向算法，先考虑给 D 部位派巡逻队，
f 4 ( x4 )
f 5 ( x5 ) 0
f 4 ( x4 )
• 阶段的编号与递推的方向
• 一般采用反向递推，所以阶段的编号也是逆向的 • 当然也可以正向递推
水电与数字化工程学院 莫 莉
作业
参照公共邮箱的电子版教材中的页码，完成第3次、第4次作 业，于2015年6月17日完成。
序号
第1次作业 第2次作业
课后作业
页码、题号
备注
图解法，基解，单纯形法 大 M法
对偶问题，对偶问题性质求最优解 对偶单纯形法 判定凸规划，斐波那契法，0.618法 最速下降法，共轭梯度法 变尺度法，Kuhn-Tucker条件 SUMT外点法，SUMT内点法 最短路线
B1 4
4
2
1 6 7 2 8
C1
8
6
D1 7 C2 5
10
E
A
2
3
B2
4
3 1
C3 1 6 B3 7 5
D2
6
3
水电与数字化工程学院
B4
莫 莉
前节回顾
用穷举法的计算量:
如果从A到E的站点有k个，除A、E之外每站有3个位
置则总共有3k条路径； 计算各路径长度总共要进行3k-1 次比较。随着 k 的值增加时，需要进行的加法和比较的 次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次，比较 1.3726075472977×1014 次。若用1亿次/秒的计 算机计算需要约508天。