【安全课件】动态规划

第五节第五节 动态规划动态规划 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法大约产生于50年代1951年美国数学家贝尔曼(RBellman)等人，根据一类多阶段 决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法动态规划他的名著“动态规划”于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一共有3 X 3 X 2 X 118条不同的路线，比较这18条不同的路线的距离值，才找出最短路线。 显然，这样作计算是相当繁的如果当段数很多，各段的不同选择也很多时，这种解法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的AEB2C2B1B3C1C3D1D2435810121418101294589773411AEB2C2B1B3C1C3D1D243581012141810129458977341112043514141617192 用动态规划的方法来求解以上最短路问题用动态规划的方法来求解以上最短路问题B 地C 地D 地E 地A 地（1） 顺序解法求解得到的结果内容丰富（2） 逆序解法AEB2C2B1B3C1C3D1D24358101214181012945897734110B 地C 地D 地E 地A 地3471110151819193 动态规划的基本概念动态规划的基本概念(1)阶段阶段 把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解 阶段的划分，一般是根据时间和空间的 自然特征来划分。 描述阶段的变量称为阶段变量，常用 k 表示如例1可分为4个阶段来求解，k1、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的函数，称为最优指标函数，记为f k ( x k )AEB2C2B1B3C1C3D1D2435810121418101294589773411 例如 f 2 ( B 2 )表示从第二阶段中的B2状态到终点E的最短距离。 例如 f 4 ( D 1 )表示从第四阶段中的D 1 状态到终点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,2,3u1(X1)x1-u1(x1)=x2xk+1 = xk-uk(xk)X4=0 012310371120481230579导弹数战场效益战场2战场3战场1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3u2(X2) 设uk(xk)为第K个阶段所采取的决策变量，也就是分配给第K个战场的导弹数量。 设g(uk(xk) ) 为分配给第K个战场uk(xk)的导弹所产生的效益。 设 f (x k) 为第K阶段状态为(x k时，第K阶段到最后阶段所得到的最优效益。1）实际求解）实际求解012310371120481230579导弹数战场效益战场2战场3战场1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3f2(0)=g(u2(0) )+ f3(0)=0f2(1)=g(u2(0) )+ f3(1)=5g(u2(1) )+ f3(0)=4max=5f2(2)=g(u2(0) )+ f3(2)=7g(u2(1) )+ f3(1)=9g(u2(2) )+ f3(0)=8=9maxf2(3)=g(u2(0) )+ f3(3)=9g(u2(1) )+ f3(2)=11g(u2(2) )+ f3(1)=13g(u2(3) )+ f3(0)=12max=13u2(X2)012310371120481230579导弹数战场效益战场2战场3战场1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3f2(0)=g(u2(0) )+ f3(0)=0f2(1)=g(u2(0) )+ f3(1)=5g(u2(1) )+ f3(0)=4max=5f2(2)=g(u2(0) )+ f3(2)=7g(u2(1) )+ f3(1)=9g(u2(2) )+ f3(0)=8=9maxf2(3)=g(u2(0) )+ f3(3)=9g(u2(1) )+ f3(2)=11g(u2(2) )+ f3(1)=13g(u2(3) )+ f3(0)=12max=13u2(X2)012310371120481230579导弹数战场效益战场2战场3战场1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9x2X2=0,1,2,3xk+1 = xk-uk(xk) f2(0)=g(u2(0) )+ f3(0)= 0f2(1)=g(u2(0) )+ f3(1)=5f2(2)=g(u2(1) )+ f3(1)=9f2(3)=g(u2(2) )+ f3(1)=13=5u2(0)f2(0)= 0决策是、u3(0)f2(1)= 5u2(0)决策是、u3(1)f2(2)= 9u2(1)决策是、u3(1)f2(3)= 13u2(2)决策是、u3(1)u2(X2)012310371120481230579导弹数战场效益xk+1 = xk-uk(xk) 战场2战场3战场1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0决策是、u3(0)f2(1)= 5u2(0)决策是、u3(1)f2(2)= 9u2(1)决策是、u3(1)f2(3)= 13u2(2)决策是、u3(1)x1X1=0,1,2,3用不用再求f1(0)， f1 (1)， f1 (2)了？f1(3)=g(u1(0) )+ f2 (3)= 13g(u1(1) )+ f2 (2)= 12g(u1(2) )+ f2 (1)= 12g(u1(3) )+ f2 (0)= 11max= 13012310371120481230579导弹数战场效益xk+1 = xk-uk(xk) 战场2战场3战场1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0决策是、u3(0)f2(1)= 5u2(0)决策是、u3(1)f2(2)= 9u2(1)决策是、u3(1)f2(3)= 9u2(2)决策是、u3(1)x1X1=0,1,2,3f1(3)=g(u1(0) )+ f2 (3)= 13g(u1(1) )+ f2 (2)= 12g(u1(2) )+ f2 (1)= 12g(u1(3) )+ f2 (0)= 11max= 13012310371120481230579导弹数战场效益xk+1 = xk-uk(xk) 战场2战场3战场1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0决策是、u3(0)f2(1)= 5u2(0)决策是、u3(1)f2(2)= 9u2(1)决策是、u3(1)f2(3)= 9u2(2)决策是、u3(1)x1X1=0,1,2,3f1(3)=g(u1(0) )+ f2 (3)= 13f1(3)= 13u1(0)决策是、u2(2)、u3(1) 动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代企业管理中的一种重要的决策方法许多问题用动态规划的方法去处理，常比线性规划或非线性规划更有成效特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法(如线性规划是一种算法)因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理因此，读者在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解小 节