§7.1 动态规划基本原理
一、动态规划的基本概念
动态规划中所涉及到的概念有阶段、状态、决策与策略、 状态转移、指标函数．
(1)阶段 将所给问题的过程，按时间或空间特征分解成若干互相联系 的阶段，以便按顺序去求每阶段的解，常用字母k表示阶段变 量．
(2)状态 各阶段开始时的客观条件叫做状态．描述各阶段状态的变量 称的为取状值态集变合量称，为常状用态集sk表合示，第用kS阶k表段示的．状态变量，状态变量sk 动态规划中的状态必须具有无后效性，即当某阶段状态给定 以后，在这阶段以后过程的发展不受这段以前各段状态的影 响．也就是说，当前的状态是过去历史的一个完整总结，过 程的过去历史只能通过当前状态去影响它未来的发展．
最优性原理是动态规划理论的核心．这个原理 说明，最优策略的任一后部子策略也是最优的．根 据这个原理，在求解多阶段决策问题时，前面的各 状态和决策，对其后面的子问题来说，只不过相当 于其初始条件而已，并不影响后面过程的最优决 策．因此，可以把多阶段决策问题求解过程表示成 一个连续的递推过程，由后向前逐步计算．这要利 用第k阶段与第k+1阶段之间的关系，通常如下：
第七章 动态规划
动态规划是解决多阶段决策过程最优化问题的一 种方法，它将多阶段决策问题转化成一系列比较简 单的最优化问题．动态规划首先将复杂的问题分解 才相互关联的若干阶段，每一个阶段都是一个最优 化子问题，然后逐阶段的决策，当所有阶段决策都 确定了，整个问题的决策也就确定了．动态规划中 阶段可以用时间表示，这就是“动态”的含义．当 然，对于与时间无关的一些静态问题也可以人为地 引入“时间”转化成动态问题．
sk+l＝Tk(sk，uk) 表示．该公式表示了由第k阶段到第k+l阶段 的状态转移规律，所以称为状态转移方程．
(5)指标函数
用于衡量所选定策略优劣的数量指标称为指标
函数，它是定义在全过程或则子过程上的数量函数，
是各阶段的状态和决策变量的函数．它分为阶段指
标函数和过程指标函数两种．阶段指标函数是指第
第 n 阶段：指标函数的最优值
f n(sn ) opt vn (sn , un )
xnDn ( sn )
此为一维极值问题，不妨设有最优解 u n un (sn )
，于是可有最优值 f n(sn ) ．
第 n 1阶段：类似地有
f n1(sn1 ) opt Vn1(sn1, un1 ) * fn (sn )
阶段的求优结果，最后一段计算的结果就是全过程
的最优结果．一般而言，如果已知过程的初始状
态 态
ssn11，，则 则用 用逆 顺序 序解解法法；．如这果两已种知方过法程除的了终 寻止 优状 方向不
同外，状态转移方程、指标函数的定义和基本方程
形式一般也有差异，但并无本质上的区别．下面主
要介绍逆序解法．
设已知初始状态为 s1 ．
fk (sk )
opt(dk (sk，uk )
uK
fk 1(sk 1))，
fn1(sn1) c， (边界条件，已知)
k n，n 1，，1，
或
fk
(sk
)
opt(dk
uk
(sk，uk
)
fk 1(sk 1))，
k
n，n
1，，1，
fn1(sn1) c， (边界条件，已知)．
该方程称为动态规划的基本方程．
或．
jk
n
Vk,n (sk，pk,n ) d j (s j，u j )
jk
最优指标函数表示从第k阶段状态sk采用 最优策略到过程终止时的最佳效益值，记 为fk(sk)．fk(sk)与Vk，n(sk，pk，n)间的关系
为 fk (sk ) Vk,n(sk，pk*,n) opt Vk,n(sk，pk,n)
k阶段状态sk采取决策uk时的效益，用dk (sk，uk)表
示．过程指标函数指在第k阶段状态为sk采用策略pk，
n时，后部子过程的收益，用Vk，n(sk，pk，n)表 示．Vk，n(sk，pk，n)与dk(sk，uk)之间的关系常见的 有求和型和乘积型两种：
n
Vk,n (sk，pk,n ) d j (s j，u j )
(3)决策和策略
当各段的状态取定以后，就可以作出不同 的决定(或选择)，从而确定下一阶段的状态， 这种决定称为决策．表示决策的变量，称为决 策变量，常用uk(sk)表示第k阶段当状态为sk时的 决策变量．在实际问题中，决策变量的取值往 往限制在一定范围内，称此范围为允许决策集 合，常用Dk(sk)表示第k阶段从状态sk出发的允 许决策集合，即uk(sk)∈Dk(sk)．
当k=1时，p1，n(s1)就是全过程的一个策略．
对每个实际问题，其k子过程可供选择的策略有
一定范围，称为允许策略集合，记作Pk，n，使整
个问题达到最优效果的策略就是最优策略．
(4)状态转移方程
动态规划中本阶段的状态往往是上一阶 段状态和上一阶段的决策结果．如果给定了 第k阶段的状态sk，本阶段决策为uk，则第k+l 阶段的状态sk+1也就完全确定，它们的关系 可用公式
一个按顺序排列的决策组成的集合称为策
略．一个n阶段决策过程，从第k阶段到第n阶段的 过程称为问题的一个后部子过程，或k子过程．由k 子过程的每一阶段的决策按顺序排列组成的策略序
列称为k子策略，记为pk，n(sk)，即 pk，n(sk)={ uk(sk)， uk+1(sk+1)， uk+解方法
动态规划的求解有两种基本方法：逆序解法(后
向动态规划方法)、顺序解法(前向动态规划方
法)．当寻优的方向与多阶段决策过程的实际行进方
向相反，从最后一段开始计算逐段前推，求得全过
程的最优策略，称为逆序解法．与之相反，顺序解
法的寻优方向与过程的行进方向相同，计算时从第
一段开始逐段向后递推，计算后一阶段要用到前一
pk,n Pk,n
式中opt表示最优化，根据具体问题表示为 max或min．
当k=1时，f1(s1)就是从初始状态s1到全过 程结束的整体最优函数．
二、动态规划的基本方程
动态规划方法基于贝尔曼(R.Bellman)提出的最 优化原理：一个过程的最优策略具有这种性质，即 不管先前的状态和决策如何，余下的所有决策必构 成的最优子策略．