第05章动态规划课件.pptx

系统工程主讲人：第一PPT 联系方式：186 XXXX XXX高新学院高新学院 enter school name enter school name22:53第05章 动态规划 第第5章章 动态规划动态规划5.1 多阶段决策过程及实例5.2 动态规划的基本概念和基本方程5.3 动态规划的最优性原理和最优性定理5.4 动态规划和静态规划的关系22:53第05章 动态规划【知识点聚焦】【知识点聚焦】 本章主要介绍动态规划的状态转移方程状态转移方程、指标函数指标函数、最优值函数最优值函数、最优策略最优策略、最优轨线最优轨线等基本知识。重点要求学生掌握动态规划的顺序解法、逆序解法顺序解法、逆序解法；最后，介绍最短路线、资源分配、生产计划、货物存储、可靠性问题、背包问题、推销最短路线、资源分配、生产计划、货物存储、可靠性问题、背包问题、推销商问题及其解法商问题及其解法等。并且简介多维动态规划降维方法多维动态规划降维方法、减少离散状态点数方法减少离散状态点数方法及随机性问题的动态规划求解方法随机性问题的动态规划求解方法。5.1 多阶段决策过程及实例 多目标问题最早是Franklin在1772年提出来的，1938年Cournot提出了多目标问题的经济学模型，1896年Pareto首次从数学的角度提出多目标最优化问题。当今，多目标规划也受到了人们的普遍重视。 在工农业生产中，常常需要考虑某些限制条件下，多个目标的最优化问题。下面举例说明：22:53第05章 动态规划5.1 多阶段决策过程及实例多阶段决策：多阶段决策：将决策的全过程依据时间或空间划分为若干个互相联系的阶段；并做出方案的选择，称之为多阶段阶段决策决策。策略：策略：各个阶段所确定的决策就构成一个决策序列，常称之为策略策略。策略集合：策略集合：许多可供选择的策略集合，称之为允许策略集合允许策略集合（简称策略集合策略集合）。最优策略最优策略：在允许策略集合中，选择一个策略，使预定的目标达到最好的效果。称为最优策略最优策略。这类问题就称为多阶段决策问题多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策一般来说是与时间有关的，故有“动态动态”的含义，因此把处理这类问题的方法称为动态规划方法动态规划方法。但有一些与时间因素没有关系的所谓“静态问题静态问题”。只要人为地引进“时间时间”因素，也可以把它视为多阶段决策多阶段决策问题，而用动态规划方法去处理。22:53第05章 动态规划举例举例【例5-1】最短路径问题。图5-1中是一个城市分布地图，图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?图5-1 最短路径问题22:53第05章 动态规划【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用 表示在第k阶段由初始状态 到下阶段的初始状态 的路径距离， 表示从第k阶段的 到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下：8=min8,10=F4(d2)+D2)d3(C1,F4(D1),+D1)mind3(C1,=F3(C1):，3=K:S2有6=3+3=f4(D3)+D3)d3(C4,=F3(C4)11=3+8=f4(D3)+D3)d3(C3,=F3(C3)8=3+5=f4(D1)+D1)d3(C2,=F3(C2)3=F4(D3)，4=F4(D2)，3=F4(D1):，有4=K:S122:53第05章 动态规划因此由A点到E点的全过程的最短路径为AB2C4D3E。最短路程长度为13。(4-1)9=4min9,12,1= F3(C3)+C3)d2(B1,f3(C2),+C2)d2(B1,F3(C1),+C1)mind2(B1,=F2(B1)，有2=K:S213=min13,13=F2(B2)+B2)d1(A,F2(B1),+B1)mind1(A,=F1(A) :有1=k:S410=min16,10=F3(C4)+C4)d2(B2,f3(C2),+c2)mind2(B2,=F2(m)，22:53第05章 动态规划因此由A点到E点的全过程的最短路径为AB2C4D3E。最短路程长度为13。(4-1)9=4min9,12,1= F3(C3)+C3)d2(B1,f3(C2),+C2)d2(B1,F3(C1),+C1)mind2(B1,=F2(B1)，有2=K:S213=min13,13=F2(B2)+B2)d1(A,F2(B1),+B1)mind1(A,=F1(A) :有1=k:S410=min16,10=F3(C4)+C4)d2(B2,f3(C2),+c2)mind2(B2,=F2(m)，22:535.2动态规划的基本概念和基本方程5.2.1动态规划的基本概念第05章 动态规划 （1）阶段和阶段变量用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。22:5322:53 （2）状态和状态变量某一阶段的出发位置称为状态，通常一个阶段包含若干状态。状态通过一个变量来描述，这个变量称为状态变量。状态表示的是事物的性质。（3）决策、决策变量对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策和多个决策点，在每一个阶段中都需要有一次决策。决策也可以用一个变量来描述，称为决策变量。在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。第05章 动态规划22:53 （4）策略和最优策略所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。（5）状态转移方程前一阶段的终点就是后一阶段的起点，前一阶段的决策变量就是后一阶段的状态变量，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。（6）指标函数和最优化概念用来衡量多阶段决策过程优劣的一种数量指标，称为指标函数。它应该在全过程和所有子过程中有定义、并且可度量。指标函数的最优值，称为最优值函数。第05章 动态规划22:53 1）动态规划的基本思想动态规划是一类解决多阶段决策问题的数学方法一类解决多阶段决策问题的数学方法。在工程技术、科学管理、工农业生产及军事等领域都有广泛的应用。在理论上，动态规划是求解这类问题全局最优解的一种有效方法，特别是对于实际中的某些非线性规划问题可能是最优解的唯一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法或者说是考动态规划仅仅是解决多阶段决策问题的一种方法或者说是考察问题的一种途径，而不是一种具体的算法察问题的一种途径，而不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法，在实际应用中，需要具体问题具体分析。动态规划模型的求解是影响动态规划理论和方法应用的关键问题所在，而子问题的求解和大量结果的存储、调用更是一个难点所在。然而，随着计算技术的快速发展，特别是内存容量和计算速度的增加，使求解较小规模的动态规划问题成为可能，从而使得动态规划的理论和方法在实际中的应用更加广泛。 5.2.2动态规划的基本思想和基本方程第05章 动态规划22:53 2）动态规划步骤动态规划算法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐步递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解就是整个问题的最优解。第05章 动态规划22:53 3）动态规划的基本方程最短路问题例：给定一个线路网络，如图5-2所示，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到G的铺管路线，使总距离为最短（或总费用为最小）。图5-2铺管线路图第05章 动态规划22:53 最短路线有一个重要特征：如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达终点G的这条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如，在最短路线问题中，若找到了AB1C2D1E2F2G是由A到G的最短路线，则D1E2F2G应该是由D出发到G点的所有可能选择的不同路线中的最短路线。第05章 动态规划22:53 证明：（反证法） 如果不是这样，则从点P到G点有另一条距离更短的路线存在，把它和原来最短路线由A点到达P点的那部分连接起来，就会得到一条由A点到G点的新路线，它比原来那条最短路线的距离还要短些。这与假设矛盾，是不可能的。根据最短路线这一特性，寻找最短路线的方法就是从最后一段开始，用由后向前逐步递推的方法，求出各点到G点的最短路线，最后求得由A点到G点的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线。动态规划的方法是从终点逐段向始点方向寻找最短路线。将从最后一段开始计算，由后向前逐步推移至A点，如图5-3所示。第05章 动态规划22:53 当k=6时，由F1到终点G只有一条路线，故f6(F1)4。同理，f6(F2)3；当k=5时，出发点有E1、E2、E3三个。若从E1出发，则有两个选择至F1，至F2，则73+54+3min)(Ff+)F,(Ed)(Ff+)F,(Edmin)(E262151611515f53+24+5min)(Ff+)F,(Ed)(Ff+)F,(Edmin=)E(262251612525f 且 ，当k=4时，有23sF=)(EU234342242421414E=)(D U 8=)(DfE=)(D U 6=)(DfE=)(D U 7=)(Df第05章 动态规划22:53 当k=3时，有34343233331232311313D=)(C U12=)(CfD=)(CU 9=)(CfD=)(C U10=)(CfD=)(C U13=)(Cf 当k=2时，有 当k=1时，出发点有一个A点，则3222221212C=)(B U16=)(BfC=)(B U13=）(Bf1816+313+5min)(Bf+)Bd(A,)(Bf+)Bd(A,min=(A)2221211f第05章 动态规划22:53 且 ，于是得到从起点A到终点G的最短距离为18。11B)A(U为了找出最短路线，再按计算的顺序反推之，可求出最优决策函数序列Uk，即由逆序的方法得到了问题的答案。从上面的计算过程中可以看出，在求解的各个阶段，利用了k阶段与k+1阶段之间的递推关系：)G),(sd=)(sf(或0)(Sf16,=)k(Sf+)u,mind(S)(Sf6666771+k1kkkkk写成 一般情况，k阶段与k+1阶段的递推关系式可写成第05章 动态规划22:53 边界条件为。递推关系式（5-1）称为动态规划的基本方程。下面考虑动态规划基本方程：设指标函数是取各阶段指标的和的形式，即 一般情况，k阶段与k+1阶段的递推关系式可写成0) 1( 1nnsf1 ，1-nn,=k)(s(uf+)(su，(svopt=)(sfkk1kkkkkkk（5-1）)u，(sV=Vjjjnkjnk,第05章 动态规划22:53 其中 ，表示第j段的指标。它显然是满足指标函数三个性质的。所以上式可写成)u，(sVjjjs ,sV+)u,(sv=V1n1kn1,kkkknk, 当初始状态给定时，过程的策略就被确定，则指标函数也就确定了，因此，指标函数是初始状态和策略的函数，可记为 )(sp,s Vknk,knk,第05章 动态规划22:53 1）动态规划的基本思想第05章 动态规划22:54 20世纪50年代，Bellman等人在研究具有无后效性的多阶段决策问题的基础上，提出了最优性原理：“作为整个过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必构成最优子策略。”即最优策略的任一后部子策略都是最优的。5.3动态规划的最优性原理和最优性定理 5.3.1最优性原理第05章 动态规划22:54 对很多多阶段决策问题，在最优策略存在的前提下，根据最优性原理及具体问题可导出基本方程，再由这个方程求解最优策略.从而得到了该多阶段决策问题的圆满结果。但是后来在动态规划的某些应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，而最优性原理只是最优性定理的必要条件. 5.3.2 最优性定理第05章 动态规划22:54 证明略去)()(1, 111, 1min)(,*, 11, 1111kkxpnnpxVpxVk；);(,min)(,nkknkxPpxVknk（5-4）5.4动态规划和静态规划的关系第05章 动态规划22:54 与静态规划相比，动态规划的优越性在于：（1）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。5.4动态规划和静态规划的关系第05章 动态规划22:54 （2）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。（3）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。第05章 动态规划22:54 动态规划的主要缺点是：（1）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。（2）用数值方法求解时存在维数灾。若一维状态变量有m个取值，那么对于n维问题，状态x_k就有mn个值，对于每个状态值都要计算、存储函数f_k(x_k)，对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾难的有效方法。5.4.1逆推解法第05章 动态规划22:54 设已知初始状态为s1，第k阶段的初始状态为sk，并假定最优值函数fk(sk)表示使从k阶段到n阶段所得到的最大效益。从第n阶段开始，则有5.4.1逆推解法)(max)()(nnnsDxnnxsvsfnnn，其中Dn(sn)是由状态sn所确定的第n阶段的允许决策集合。解此一维极值问题，就得到最优解xn(sn)和最优值fn(sn)。(注意：若Dn(sn)只有一个决策，则xnDn(sn)就应写成xn=xn(sn)。在第n-1阶段，有)()(max)(111)(1111nnnnnsDxnnsfxsvsfnnn，第05章 动态规划22:54其中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阶段，有)()(max)(111)(1111nnnnnsDxnnsfxsvsfnnn，)()(max)(22111)(11111sfxsvsfsDx，第05章 动态规划22:54 其中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】用逆推解法求解下列问题】用逆推解法求解下列问题3 , 2 , 10)0(max3213221ixccxxxxxxzi，第05章 动态规划22:54 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设第05章 动态规划22:54 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设第05章 动态规划22:54 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设第05章 动态规划22:54 设已知终止状态Sn+1，并假定最优值函数fk(s)，是以s为k阶段的结束状态，从1阶段到k阶段所获得的最大效益。已知终止状态用顺推方法与已知初始状态用逆推方法本质上是没有区别的。假定状态变换5.4.1逆推解法)x,s (T=skkk1k的逆推变换为)x,(sT=sk1k*k首先，第一阶段开始，求出)x,s (v)(sf111max )(sDx11111第05章 动态规划22:54 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设第05章 动态规划22:54 的逆变换cs1kk1kx-s=s第05章 动态规划22:54第05章 动态规划22:54 解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为s1，s2，s3，s4，并记s1=c,取问题中的变量x1、x2、x3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(sk)表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。设第05章 动态规划22:54第05章 动态规划22:54第05章 动态规划PPT模板下载：行业PPT模板：节日PPT模板：素材下载：PPT背景图片：图表下载：优秀PPT下载：教程： Word教程： 教程：资料下载：课件下载：范文下载：试卷下载：教案下载：字体下载： 电话：186 XXXX XXX点击输入学校名称点击输入学校名称 enter school name enter school name 22:54第05章 动态规划