第七章 动态规划
主要内容:
§7.1多阶段决策问题 §7.2 动态规划的基本概念和基本原理
§7.3 动态规划应用举例
例 求解最短路问题
A1 2 Q 4 3 A3 A2 6 3 7 4 B1 1 4 2 4 4 1 5 6 B2 3 B3 3 3 C2 C1 3 4 T
Ⅰ
Ⅱ
Ⅲ
Ⅳ
分阶段的最短路径
• • • • • • • Ⅳ ： C1—T Ⅲ --Ⅳ : B1—C1—T Ⅱ--Ⅲ--Ⅳ ：A2—B1—C1—T Ⅰ--Ⅱ--Ⅲ --Ⅳ： Q—A2—B1—C1—T Q--A3—B1—C1—T Q--A3—B2—C2—T 3 4 7
决策为 xk 时的指标，则它就是第 k 段指标函
数，简记为vk 。 （2）过程指标函数（也称目标函数） 用f(sk , xk)表示第k子过程的指标函数。表
示处于第 k 段 sk 状态且所作决策为xk时，
从 sk 点到终点的距离。由此可见， f(sk , xk)
不仅跟当前状态 sk 有关，
还跟该子过程策略 pk(sk) 有关,严格说来，应
(6) 指标函数
用来衡量策略或子策略或决策的效果的 某种数量指标，就称为指标函数。它是定义 在全过程或各子过程或各阶段上的确定数量 函数。对不同问题，指标函数可以是诸如费 用、成本、产值、利润、产量、耗量、距离、 时间、效用，等等。
（1）阶段指标函数（也称阶段效应）
用vk(sk , xk)表示第 k 段处于状态 sk且所作
资规划, 排序问题和生产过程的最优控制
等问题;
§7.2 动态规划的基本概念和基本思想
一、基本概念
使用动态规划方法求解决策问题首先要将 问题改造成符合动态规划求解要求的形式, 要涉及以下概念: (1)阶段 (3)决策与策略 (2)状态 (4)状态转移方程
(5)指标函数
(6)基本方程
(1) 划分阶段 把一个复杂决策问题按时间或空间特 征分解为若干(n)个相互联系的阶段 (stage), 以便按顺序求解; 阶段变量描述当前所处的阶段位置，一
表示为 fk(sk , pk(sk)) 。它是由各阶段的阶段
指标函数 vk(sk , xk)累积形成的，对于 k 部子
过程的指标函数可以表示为：
fk ,n fk ,n (sk , xk , sk 1, xk 1, , sn , xn ) vk (s k , xk ) vk 1 (sk 1 , xk 1 ) vn (sn ,，p={A3,B2,C2,T}
二、动态规划的最优性原理
• 整个过程的最优策略应具有这样的性质: 无 论过去的状态和决策如何, 对前面的决策所 形成的状态而言, 后续的诸决策必须构成最 优策略； • 上一条成立的条件是阶段递推函数严格单 调。
在例题中，求解最短路线的计算公式可以概 括写成：
系统以前经历的状态和决策(历史)无关。
具有无后效性的多阶段决策过程的特点是系统过去的历史， 只能通过现阶段的状态去影响系统的未来，当前的状态就是 后过程发展的初始条件。
动态规划的应用
• 动态规划在工程技术, 企业管理, 军事部 门有广泛的应用; 可解决资源分配, 生产
调度, 库存管理, 路径优化, 设备更新, 投
界条件，表示全过程到第四阶段终点结束。
一般地，对于 n 个阶段的决策过程，假设只
考虑指标函数是“和”与“积”的形式，第 k
阶段和第 k+1 阶段间的递推公式可表示如下：
当过程指标函数为下列“和”的形式时 k k k k k k pk PK ( sk ) n
f (s ) opt { f (s , p (s ))}
采用顺序求解方法, 通过解一系列小问题
达到求解整个问题目的;
• 动态规划的各个决策阶段不但要考虑本阶
段的决策目标, 还要兼顾整个决策过程的
整体目标, 从而实现整体最优决策.
动态规划的分类:
• 离散确定型
• 离散随机型
• 连续确定型
• 连续随机型
动态规划的特点:
• 动态规划没有准确的数学表达式和定义 精确的算法, 它强调具体问题具体分析,
pk ,n{xk , xk 1, , xn} ，显然当
k=1时的 k 部子策略就是全过程策略。
(5) 状态转移方程
状态转移确定从一个状态到另一个状态的转
移过程, 由状态转移方程描述: sk+1 = T (sk, xk);
状态转移方程在大多数情况下可以由数学公 式表达, 如: sk+1 = sk + xk；
般用下标 k 表示;
(2) 确定状态
每阶段有若干状态(state), 表示某一阶段决策 面临的条件或所处位置及运动特征的量,称为 状态。反映状态变化的量叫作状态变量。 k 阶段的状态特征可用状态变量 sk 描述;
每一阶段的全部状态构成该阶段的状态集合 Sk，
并有skSk。每个阶段的状态可分为初始状态
f5 ( s5 ) 0 min {vk ( sk , xk ( sk )) f k 1 ( sk 1 )} f k ( sk ) x k X k ( sk ) k 4,3, 2,1
其中，vk 在这里表示从状态 sk 到由决策 xk
所决定的状态 sk+1 之间的距离。f5(s5)=0 是边
和终止状态，或称输入状态和输出状态，阶
段的初始状态记作sk ，终止状态记为sk+1 ，也 是下个阶段的初始状态。
(3) 决策、决策变量 所谓决策就是确定系统过程发展的方案， 决策的实质是关于状态的选择，是决策者 从给定阶段状态出发对下一阶段状态作出 的选择。 用以描述决策变化的量称之决策变量， 和状态变量一样，决策变量可以用一个数， 一组数或一向量来描述．也可以是状态变量 的函数，记以 xk xk (sk ) ，表示于 k 阶段状 态 sk 时的决策变量．
A1 2 Q 4 3 A3 6 3 A2
7 4
B1
1 4 C1 3 4 3 C2 T
2 4
6 B2 3 B3 3
4 1 5
k=2
f2(A1) = min{7+ f3(B1), 4+ f3(B2), 6+ f3(B3) } = min{11*, 11*, 12} = 11
f2(A2) = min{3+ f3(B1), 2+ f3(B2), 4+ f3(B3) } = min{7*, 9, 10 } = 7 f2(A3) = min{4+ f3(B1), 1+ f3(B2), 5+ f3(B3) } = = min{8*, 8*, 11 } = 8 k=1 f1(Q) = min{2+f2(A1), 4+f2(A2), 3+f2(A3)} = min{13, 11*, 11* } = 11 最短路是：Q A2 B1 C1 T，p={A2,B1,C1,T} Q A3 B1 C1 T ，p={A3,B1,C1,T}
A1 2 4 3 A3 6 3 A2
7 4
B1
1 4 C1 3 4 3 C2 T
2 4
6 B2 3 B3 3
4 1 5
vk sk , xk csk xk
过程指标（阶段递推）函数:
f k ( sk ) min vk ( sk , xk ) f

k 1
( sk 1 )
k=4 f4 (C1) = 3, k=3 f3(B1)=min{1+f4(C1)=4*, 4+f4(C2)=8}=4 f3(B2)=min{6+f4(C1)=9, 3+f4(C2)=7*}=7 f3(B3)=min{3+f4(C1)=6*, 3+f4(C2)=7}=6 f4 (C2) = 4
式中，表示某种运算，可以是加、减、、 乘、除、开方等．
多阶段决策问题中，常见的目标函数形式
之一是取各阶段效应之和的形式，即:
fk
v
i k
n
k
( sk , uk )
有些问题，如系统可靠性问题，其目标函 数是取各阶段效应的连乘积形式，
f k vk ( sk , uk )
i k n
(7) 最优解
11 11 11
最短路径
11
4
A1 2
11
7 4 3
B1
7
1 4
3
6
7
C1
Q
4 3
A2
8
2 4
6 3 3 3 C2
4
3 4 T
B2
6
A3
4 1 5
B3
Ⅰ
Ⅱ
Ⅲ
Ⅳ
最短路径解的特点
• 1、可以将全过程求解分为若干阶段求解；-----多阶段决策问题 • 2、在全过程最短路径中，将会出现阶段的最 优路径；-----递推性 • 3、前面的终点确定，后面的路径也就确定了， 且与前面的路径（如何找到的这个终点）无关； -----无后效性 • 3、逐段地求解最优路径，势必会找到一个全 过程最优路径。-----动态规划
当过程指标函数为下列“积”的形式时
fk (sk ) opt { fk (sk , pk (sk ))}
pk PK ( sk )
opt
pi Pk ( si ) i k
v (s , x )
i i i
n
相应的函数基本方程为 :
f (s ) 1 n1 n1 f k (sk ) opt {vk (sk , xk (sk )) f k 1 (sk 1 )} xk X k k n, n 1, ,2,1
opt
pk Pk ( sk ) i k
v (s , x )