圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台第9章动态规划的基本方法9.1复习笔记1．动态规划的基本概念（1）阶段、阶段变量：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，宗旨是便于把问题的过程转化为多阶段决策的过程（逆序模型、顺序模型）。（2）状态、状态变量：状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究问题过程的状况。通常一个阶段有若干个状态。描述过程状态的变量称为状态变量，常用sk来表示第k阶段的状态变量。一般来说，状态变量的取值有一定的允许集合或范围，此集合称为是状态允许集合。（3）决策、决策变量：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk(sk)?Dk(sk)。（4）多阶段决策过程：就是可以在各个阶段进行决策，去控制过程发展的多段过程。多阶段决策过程的发展是通过一系列的状态转移来实现的，一般来说，系统在某一阶段的状态转移不但与系统的当前（或本阶段）的状态和决策有关，而且还与系统过去的历史状态和决策有关。1/79圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。（5）无后效性或马尔科夫性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，这个性质称为无后效性。在构造决策过程的动态规划模型时，要充分注意是否满足无后效性的要求。如果状态不能满足无后效性的要求，应适当地改变状态的定义或规定方法，以使状态变量能满足无后效性的要求。（6）策略：策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。由每段的决策按顺序排列组成的决策函数序列{uk(sk),?,un(sn)}称为k子过程策略，简称子策略，记为Pk，（。nsk）
在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。从允许策略集合中找出达到最优效果的策略称为最优策略。（7）指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定了的数量函数。常用Vk,n表示，即Vk,n＝Vk,n(sk,uk,sk＋1,?,sn＋1),k＝1,2,?,n
对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可以表示为sk、uk、Vk+1,n的函数。记为Vk,n(sk,uk,sk＋1,?,sn＋1)＝?k[sk,uk,Vk＋1,n(sk＋1,?,sn＋1)]
最优值函数：表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。2．动态规划的基本思想2/79圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台（1）将多阶段决策过程划分阶段，恰当地选取状态变量和决策变量及定义最优指标函数，正确写出基本的递推关系式和恰当的边界条件（简言之为基本方程），从而把问题化成一族同类型的子问题，然后逐个求解。（2）求解时从边界条件开始，按逆（或顺）过程行进方向，逐段递推寻优，在每个子问题求解中，都要使用它前面已求出的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。（3）动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取都是从全局来考虑的，与该段的最优选择答案一般是不同的。（4）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定最优路线。（5）在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系，例如：?fk?sk??mindk?sk,uk?sk
?uk?Dk(sk)???f7?s7??0
????fk?1?uk?sk??? k=6,5,4,3,2,1
3．动态规划的基本方程一般情况，k阶段与k+1阶段的递推关系式可写成：边界条件为：fn?1(sn?1)?0
3/79圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台4．给一个实际问题建立动态规划模型时，必须做到下面五点：（1）将问题的过程划分成恰当的阶段；（2）正确选择状态变量sk，使它既能描述过程的演变，又要满足无后效性；（3）确定决策变量uk及每阶段的允许决策集合Dk?sk?；（4）正确写出状态转移方程；（5）正确写出指标函数Vk,n的关系，它应满足下面三个性质：①是定义在全过程和所有后部子过程上的数量函数；②要具有可分离性，并满足递推关系。即Vk,n?sk,uk,…,sn?1?=?k??sk,uk,Vk?1,n?sk?1,uk?1,…,sn?1???
③函数?ksk,uk,Vk?1,n对于变量Vk?1,n要严格单调。??5．最优性原理与最优性定理最优性原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态及决策如何，对于先前决策所形成的状态而言，余下的诸决策必须构成最优策略。”最优性原理的含义是：最优策略的任何一部分子策略，都是最优策略。每个最优策略只能由最优子策略构成。动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编号为k=0，1，…，n-1，允许策略****
p0?(u,u,?,u,n?101n?1)
为最优策略的充要条件是对任意一个k，0 V0,n?1(s0,p0,n?1)? {V0,k?1(s0,p0,k?1)?optopt?k,pk,n?1)}Vk,n?1(s p0,k?1?P0,k?1(s0)pk,n?1`?Pk,n?1(s?k) ?k?Tk?1(sk?1,uk?1),它是由给定的初始状态s0和子策略式中p0,n?1?(p0,k?1,pk,n?1),s 4/79*圣才电子书www.100xuexi.com十万种考研考证电子书、题库视频学习平台p0,k?1所确定的k段状态。当V是效益函数时，opt取max；当V是损失函数时，opt取min。推论：若允许策略p0,n?1是最优策略，则对任意的k，0 sk是由s0和p0,k?1所确定的）。* **?** ?6．逆推解法设已知初始状态为s1，最优值函数fk(sk)表示第k阶段的初始状态为sk，从k阶段到n阶段所得到的最大效益。以求最大化为例来说明，即V1,n?v1(s1,x1)?v2(s2,x2)???vn(sn,xn) 其中s表示状态，x表示决策（控制）。具体方法如下：当阶段k=n时，有fn?sn??maxvn?sn,xn?xn?Dn(sn)可得最优解xn?xn?sn?和最优值fn?sn?，要注意的是，若D?sn?只有一个决策，则可写成xn?xn?sn?。当阶段k=n-1时，有fn?1?sn?1?? xn?1?Dn(sn?1)max [vn?1?sn?1,xn?1??fn?sn?] 其中状态转移方程sn?Tn?1?sn?1,xn?1?；得到最优解xn?1?xn?1?sn?1?和最优值fn?1?sn?1?。当阶段k=k时，有fk?sk?? sk?Dk(sk)max[v?s,x??f?s?] kkkk?1k?15/79
运筹学教材编写组《运筹学》笔记和课后习题(含考研真题)详解 第(9-10)章【圣才出品】
