搜索
第五节动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法．大约产生于50年代．1951年美国数学家贝尔曼(R．Bellman)等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法——动态规划．他的名著“动态规划”于1957年出版，该书是动态规划的第一本著作．动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续的变量；过程分为离散决策过程和连续决策过程．根据决策过程的演变是确定性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程．组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型．本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容．离散决策过程连续决策过程根据多阶段决策过程的时间参量根据决策过程的演变确定性决策过程随机性决策过程离散确定性决策过程离散确定性决策过程连续确定性决策过程连续随机性决策过程引例——有一批军用物资需要从A地调运到E地，如下图所示，请求出一条从A到E的一条线路，使总的运输距离最短。图中线条上的数字为距离。AEB2C2B1B3C1C3D1D24358101214181012945897734111多阶段决策过程及实例B地C地D地E地A地在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响到以后的决策。AEB2C2B1B3C1C3D1D2435810121418101294589773411如果一个问题的过程可以化分为若干个互相联系的阶段，而且每个阶段都需要作出决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法。如上图所示的线路网络，求A到E点的最短路线问题是动态规划中一个较为直观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的基本概念。．AEB2C2B1B3C1C3D1D2435810121418101294589773411如上图可知，从A点到E点可以分为4个阶段．从A到B为第一阶段，从B到C为第二阶段…从D到E为第四阶段在第一阶段，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择，分别是走B1，B2，B3。如果选择走B2的决策，则B2就是第一阶段在我们决策之下的结果．它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合{C1，C2，C3}；如果选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点．同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。AEB2C2B1B3C1C3D1D2435810121418101294589773411如何解决这个问题呢?可以采取穷举法．即把由A到E所有可能的每一条路线的距离都算出来，然后互相比较找出最短者，相应地得出了最短路线．这样，由A到E一共有3X3X2X1＝18条不同的路线，比较这18条不同的路线的距离值，才找出最短路线。显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的．AEB2C2B1B3C1C3D1D2435810121418101294589773411AEB2C2B1B3C1C3D1D243581012141810129458977341112043514141617192用动态规划的方法来求解以上最短路问题B地C地D地E地A地（1）顺序解法求解得到的结果内容丰富（2）逆序解法AEB2C2B1B3C1C3D1D24358101214181012945897734110B地C地D地E地A地3471110151819193动态规划的基本概念(1)阶段把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解．阶段的划分，一般是根据时间和空间的自然特征来划分。描述阶段的变量称为阶段变量，常用k表示．如例1可分为4个阶段来求解，k＝1、2、3、4。AEB2C2B1B3C1C3D1D2435810121418101294589773411(2)状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素．在例1中，状态就是某阶段的出发位置．它既是该阶段某支路的起点，又是前一阶段某支路的终点．通常一个阶段有若于个状态，第一阶段有一个状态就是点A，第二阶段有两个状态，即点集合{B1，B2}，第k阶段的状态就是第k是阶段所有始点的集合．.AEB2C2B1B3C1C3D1D24358101214181012945897734113动态规划的基本概念描述过程状态的变量称为状态变量。它可用一个数、一组数或一个向量(多维情形)来描述．常用xk表示第受阶段的状态变量．如在例1中第三阶段有3个状态，则状态变量x3可取3个值，即x3=c1,c2,c3。可达状态集合某个阶段的所有的状态所构成的集合，称为可达状态集合。例如，第三阶段的所有状态为c1,c2,c3，则第三阶段的可达状态集合成为点集合{c1,c2,c3}。记为x3={c1,c2,c3}。AEB2C2B1B3C1C3D1D24358101214181012945897734113动态规划的基本概念状态的基本特性——无后效性（否则就不能成为动态规划里所讲的状态）AEB2C2B1B3C1C3D1D2435810121418101294589773411如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各段状态的影响．换句活说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的一个总结．这个性质称为无后效性(即马尔科夫性)．前效性相反，如果状态仅仅描述过程的具体特征，并不满足无后效性的要求。应适当地改变状态的规定方法，以达到能使它满足无后效性的要求。才能成为动态规划里所讲的状态。例如，研究物体(把它看作一个质点)受外力作用后其空间运动的轨迹问题．从描述轨迹这点着眼，可以只选坐标位置(xk，yk)作为过程的状态，但这样不能满足无后效性，因为即使知道了外力的大小和方向，仍无法确定物体受力后的运动方向和轨迹。不具有后效性的例子但是如果把位置(xk，yk)和速度(vxk，vvk)都作为过程的状态变量，就可以确定物体运动下一步的方向和轨迹，实现无后效性的要求．(3)决策决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策。AEB2C2B1B3C1C3D1D24358101214181012945897734113动态规划的基本概念决策变量——uk(xk)描述决策的变量，称为决策变量．它可用一个数、一组数或一个向量来描述．uk(xk)表示第k阶段当状态处于xk时的决策变量．它是状态变量的函数．AEB2C2B1B3C1C3D1D24358101214181012945897734113动态规划的基本概念允许决策集合——Dk(xk)在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合．AEB2C2B1B3C1C3D1D2435810121418101294589773411Dk(xk)表示第k阶段从状态xk出发的允许决策集合，显然有uk(xk)∈Dk(xk)．从状态B1出发，就可作出三种不同的决策，其允许决策集合是D2(B1)＝{C1，C2，C3}，如果选取的点为C2，则C2是状态Bl在决策u2(B1)作用下的一个新的状态，记作u2(B1)＝C2．3动态规划的基本概念AEB2C2B1B3C1C3D1D2435810121418101294589773411K子过程策略由过程的第k阶段开始直到终止状态为止的过程，称为问题的后部子过程(或称为k子过程)．全过程的一个策略当k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为p1,n(x1).3动态规划的基本概念3动态规划的基本概念允许策略集合在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示.从允许决策集合中就能找出达到最优效果的策略，它被称为最优策略。AEB2C2B1B3C1C3D1D24358101214181012945897734113动态规划的基本概念指标函数使用不同的策略，其效果是不一样的，把衡量过程效果的好坏的函数叫做指标函数。Vkn=Vkn(xk,uk,xk+1,uk+1,…,xk+1)(k=1,2,…,n)V是value的缩写AEB2C2B1B3C1C3D1D2435810121418101294589773411在这个函数里面，各个状态的取值是变化的不定的。3动态规划的基本概念最优指标函数对于不同的状态xk,指标函数Vkn有不同的最优值，这个最优值可以表示为xk的函数，称为最优指标函数，记为fk(xk)AEB2C2B1B3C1C3D1D2435810121418101294589773411例如f2(B2)表示从第二阶段中的B2状态到终点E的最短距离。例如f4(D1)表示从第四阶段中的D1状态到终点E的最短距离。012310371120481230579导弹数战场效益战场1战场2战场3将问题分为三个阶段，第三阶段给战场3分配导弹，第二阶段给战场2和战场3分配导弹。第一阶段给战场1、2、3分配导弹第三阶段给战场3分配导弹第二阶段给战场2和战场3分配导弹第一阶段给战场1、2、3分配导弹4动态规划解决问题的一般步骤(1)首先确定阶段变量K.K=1,2,3.(2)确定各阶段的状态xk战场2战场3012310371120481230579导弹数战场效益战场1(1)首先确定阶段变量K.K=1,2,3.(2)确定各阶段的状态xk(3)确定各阶段允许状态集合.X3可以取值多少呢？X3表示分配给第三阶段（也就是第3战场）的导弹数量。x2表示分配给第二阶段（也就是第2、3战场）的导弹数量。X1表示分配给第一阶段（也就是第1、2、.3战场）的导弹数量。X3={0,1,2,3}要满足无后效性，x3,x2,x1(4)确定决策变量.决策变量uk(xk)表示的是当第K阶段所处的状态为xk时所作的决策。(4)确定决策变量.(5)确定状态转移关系.4动态规划解决问题的一般步骤略过012310371120481230579导弹数战场效益战场2战场3战场1(1)首先确定阶段变量K.(2)首先各阶段的状态xk(3)确定各阶段允许状态集合.(4)确定决策变量uk(xk).(5)确定状态转移关系.x3X3=0,1,2,3u3(X3)X2X2=0,1,2,3u2(X2)x2-u2(x2)=x3012310371120481230579导弹数战场效益(1)首先确定阶段变量K.(2)首先各阶段的状态xk(3)确定各阶段允许状态集合.(4)确定决策变量uk(xk).(5)确定状态转移关系.战场2战场3战场1x3X2X1X1=0,1,2,3u1(X1)x1-u1(x1)=x2012310371120481230579导弹数战场效益(1)首先确定阶段变量K.(2)首先各阶段的状态xk(3)确定各阶段允许状态集合.(4)确定决策变量uk(xk).(5)确定状态转移关系.战场2战场3战场1x3X2X1X1=0,1