《系统工程》课件第05章 动态规划

第5章

动态规划5.1多阶段决策过程及实例5.2动态规划的基本概念和基本方程5.3动态规划的最优性原理和最优性定理5.4动态规划和静态规划的关系14:17【知识点聚焦】

本章主要介绍动态规划的状态转移方程、指标函数、最优值函数、最优策略、最优轨线等基本知识。重点要求学生掌握动态规划的顺序解法、逆序解法；最后，介绍最短路线、资源分配、生产计划、货物存储、可靠性问题、背包问题、推销商问题及其解法等。并且简介多维动态规划降维方法、减少离散状态点数方法及随机性问题的动态规划求解方法。5.1多阶段决策过程及实例

多目标问题最早是Franklin在1772年提出来的，1938年Cournot提出了多目标问题的经济学模型，1896年Pareto首次从数学的角度提出多目标最优化问题。当今，多目标规划也受到了人们的普遍重视。

在工农业生产中，常常需要考虑某些限制条件下，多个目标的最优化问题。下面举例说明：14:175.1多阶段决策过程及实例多阶段决策：将决策的全过程依据时间或空间划分为若干个互相联系的阶段；并做出方案的选择，称之为多阶段决策。策略：各个阶段所确定的决策就构成一个决策序列，常称之为策略。策略集合：许多可供选择的策略集合，称之为允许策略集合（简称策略集合）。最优策略：在允许策略集合中，选择一个策略，使预定的目标达到最好的效果。称为最优策略。这类问题就称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策一般来说是与时间有关的，故有“动态”的含义，因此把处理这类问题的方法称为动态规划方法。但有一些与时间因素没有关系的所谓“静态问题”。只要人为地引进“时间”因素，也可以把它视为多阶段决策问题，而用动态规划方法去处理。14:17举例【例5-1】最短路径问题。图5-1中是一个城市分布地图，图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?图5-1最短路径问题14:17【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用表示在第k阶段由初始状态到下阶段的初始状态

的路径距离，表示从第k阶段的到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下：14:17因此由A点到E点的全过程的最短路径为A→B2→C4→D3→E。最短路程长度为13。(4-1)14:17因此由A点到E点的全过程的最短路径为A→B2→C4→D3→E。最短路程长度为13。(4-1)14:175.2动态规划的基本概念和基本方程5.2.1动态规划的基本概念

（1）阶段和阶段变量用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。14:1714:17

（2）状态和状态变量某一阶段的出发位置称为状态，通常一个阶段包含若干状态。状态通过一个变量来描述，这个变量称为状态变量。状态表示的是事物的性质。（3）决策、决策变量对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策和多个决策点，在每一个阶段中都需要有一次决策。决策也可以用一个变量来描述，称为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。14:17

（4）策略和最优策略所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。（5）状态转移方程前一阶段的终点就是后一阶段的起点，前一阶段的决策变量就是后一阶段的状态变量，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。（6）指标函数和最优化概念用来衡量多阶段决策过程优劣的一种数量指标，称为指标函数。它应该在全过程和所有子过程中有定义、并且可度量。指标函数的最优值，称为最优值函数。14:17

1）动态规划的基本思想动态规划是一类解决多阶段决策问题的数学方法。在工程技术、科学管理、工农业生产及军事等领域都有广泛的应用。在理论上，动态规划是求解这类问题全局最优解的一种有效方法，特别是对于实际中的某些非线性规划问题可能是最优解的唯一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法或者说是考察问题的一种途径，而不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法，在实际应用中，需要具体问题具体分析。动态规划模型的求解是影响动态规划理论和方法应用的关键问题所在，而子问题的求解和大量结果的存储、调用更是一个难点所在。然而，随着计算技术的快速发展，特别是内存容量和计算速度的增加，使求解较小规模的动态规划问题成为可能，从而使得动态规划的理论和方法在实际中的应用更加广泛。

5.2.2动态规划的基本思想和基本方程14:17

2）动态规划步骤动态规划算法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐步递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解就是整个问题的最优解。14:17

3）动态规划的基本方程最短路问题例：给定一个线路网络，如图5-2所示，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到G的铺管路线，使总距离为最短（或总费用为最小）。图5-2铺管线路图14:17

最短路线有一个重要特征：如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达终点G的这条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如，在最短路线问题中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最短路线，则D1→E2→F2→G应该是由D出发到G点的所有可能选择的不同路线中的最短路线。14:17

证明：（反证法）如果不是这样，则从点P到G点有另一条距离更短的路线存在，把它和原来最短路线由A点到达P点的那部分连接起来，就会得到一条由A点到G点的新路线，它比原来那条最短路线的距离还要短些。这与假设矛盾，是不可能的。根据最短路线这一特性，寻找最短路线的方法就是从最后一段开始，用由后向前逐步递推的方法，求出各点到G点的最短路线，最后求得由A点到G点的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线。将从最后一段开始计算，由后向前逐步推移至A点，如图5-3所示。14:17

当k=6时，由F1到终点G只有一条路线，故f6(F1)＝4。同理，f6(F2)＝3；当k=5时，出发点有E1、E2、E3三个。若从E1出发，则有两个选择①至F1，②至F2，则

且，当k=4时，有14:17

当k=3时，有

当k=2时，有

当k=1时，出发点有一个A点，则14:17

且，于是得到从起点A到终点G的最短距离为18。为了找出最短路线，再按计算的顺序反推之，可求出最优决策函数序列｛Uk｝，即由逆序的方法得到了问题的答案。从上面的计算过程中可以看出，在求解的各个阶段，利用了k阶段与k+1阶段之间的递推关系：

一般情况，k阶段与k+1阶段的递推关系式可写成14:17

边界条件为。递推关系式（5-1）称为动态规划的基本方程。下面考虑动态规划基本方程：设指标函数是取各阶段指标的和的形式，即

一般情况，k阶段与k+1阶段的递推关系式可写成（5-1）14:17

其中，表示第j段的指标。它显然是满足指标函数三个性质的。所以上式可写成

当初始状态给定时，过程的策略就被确定，则指标函数也就确定了，因此，指标函数是初始状态和策略的函数，可记为14:17

1）动态规划的基本思想14:17

20世纪50年代，Bellman等人在研究具有无后效性的多阶段决策问题的基础上，提出了最优性原理：“作为整个过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必构成最优子策略。”即最优策略的任一后部子策略都是最优的。5.3动态规划的最优性原理和最优性定理

5.3.1最优性原理14:17

对很多多阶段决策问题，在最优策略存在的前提下，根据最优性原理及具体问题可导出基本方程，再由这个方程求解最优策略.从而得到了该多阶段决策问题的圆满结果。但是后来在动态规划的某些应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，而最优性原理只是最优性定理的必要条件.

5.3.2最优性定理14:17

证明略去（5-4）5.4动态规划和静态规划的关系14:17

与静态规划相比，动态规划的优越性在于：（1）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。5.4动态规划和静态规划的关系14:17

（2）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。（3）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。14:17

动态规划的主要缺点是：（1）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。（2）用数值方法求解时存在维数灾。若一维状态变量有m个取值，那么对于n维问题，状态x_k就有mn个值，对于每个状态值都要计算、存储函数f_k(x_k)，对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾难的有效方法。5.4.1逆推解法14:17

设已知初始状态为s1，第k阶段的初始状态为sk，并假定最优值函数fk(sk)表示使从k阶段到n阶段所得到的最大效益。从第n阶段开始，则有5.4.1逆推解法其中Dn(sn)是由状态sn所确定的第n阶段的允许决策集合。解此一维极值问题，就得到最优解xn(sn)和最优值fn(sn)。(注意：若Dn(sn)只有一个决策，则xn∈Dn(sn)就应写成xn=xn(sn)。在第n-1阶段，有14:17其中sk+1=Tk(sk,xk),解得最优解xk=xk(sk)和最优值fk(sk).如此类推，直到第一阶段，有

其中sn=Tn-1(sn-1,xn-1),解此一维极值问题，得到最优解xn-1=xn-1(sn-1)和最优值fn-1(sn-1)在第k阶段，有14:17

其中s2=T1(s1,x1)，解得最优解x1=x1(s1)和最优值f1(s1).由于初始状态s1可知，故x1=x1(s1)和f1(s1)是确定的，从而s2=T1(s1,x1)也就可确定，于是x2=x2(s2)和f2(s2)也就可以确定。这样，按照上述递推过程相反的顺序推算下去，就可逐步确定确定出每阶段的决策及效益。【例5-2】用逆推解法求解下列问题14:17

解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设14:17

解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设14:17

解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设14:17

设已知终止状态Sn+1，并假定最优值函数fk(s)，是以s为k阶段的结束状态，从1阶段到k阶段所获得的最大效益。已知终止状态用顺推方法与已知初始状态用逆推方法本质上是没有区别的。假定状态变换5.4.1逆推解法的逆推变换为首先，第一阶段开始，求出14:17

解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数f