【安全】动态规划ppt课件

1、第五节 动态规划 动态规划是运筹学的一个分支，它是处理多阶段决策过程最优化的一种数学方法大约产生于50年代1951年美国数学家贝尔曼(RBellman)等人，根据一类多阶段 决策问题的特点，把多阶段决策问题变换为一系列相互联络单阶段问题，然后逐个加以处理。与此同时，他提出理处理这类问题的“最优性原理，研讨了许多实践问题，从而创建理处理最优化问题的一种新的方法动态规划他的名著“动态规划于1957年出版，该书是动态规划的第一本著作 动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是延续的变量；过程分为离散决策过程和延续决策过程根据决策过程的演化是确定性的还是随机性的，过程又可分为确定性决

2、策过程和随机性决策过程组合起来就有离散确定性、离散随机性、延续确定性、延续随机性四种决策过程模型本部分主要研讨离散决策过程，引见动态规划的根本概念、实际和方法，并经过几个典型的问题来阐明它的运用，这些都是整个动态规划的根本内容 离散决策过程延续决策过程根据多阶段决策过程的时间参量根据决策过程的演化确定性决策过程随机性决策过程离散确定性决策过程离散确定性决策过程延续确定性决策过程延续随机性决策过程 引例有一批军用物资需求从 A 地调运到E地，如以下图所示，恳求出一条从 A 到 E 的一条线路，使总的运输间隔最短。图中线条上的数字为间隔。AEB2C2B1B3C1C3D1D2435810121418

3、1012945897734111 多阶段决策过程及实例B 地C 地D 地E 地A 地 在消费和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为假设干个相互联络的阶段，在它的每一个阶段都需求作出决策，才干使整个过程到达最好的活动效果因此，各个阶段决策的选取不是恣意确定的，它依赖于当前面临的形状，又影响到以后的决策。AEB2C2B1B3C1C3D1D2435810121418101294589773411 假设一个问题的过程可以化分为假设干个相互联络的阶段，而且每个阶段都需求作出决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫做一个多阶段决策问题。动态规划就是

4、处理这类问题的一个重要的数学方法。 如上图所示的线路网络，求 A 到 E 点的最短道路问题是动态规划中一个较为直观的典型例子现经过讨论它的解法，来阐明动态规划方法的根本思想，并论述它的根本概念。AEB2C2B1B3C1C3D1D2435810121418101294589773411 如上图可知，从A点到E点可以分为4个阶段从A到B为第一阶段，从B到C为第二阶段从D到E为第四阶段 在第一阶段，A为起点，终点有B1，B2，B3三个，因此这时走的道路有三个选择， 分别是走B1，B2，B3。 假设选择走B2的决策，那么B2就是第 一阶段在我们决策之下的结果它既是第一阶段道路的终点，又是第二阶段道路的

5、始点。 在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合C1，C2，C3； 假设选择由B2走至C2为第二阶段的决策，那么C2 就是第二阶段的终点，同时又是第三阶段的始点 同理递推下去，可看到：各个阶段的决策不同，调运的道路就不同很明显，当某一阶段的始点给定时，它直接影响着后面各阶段的行进道路和整个道路的长短，而后面各阶段的道路的开展不受这点以前各阶段道路的影响故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决议的一条道路，其总路程最短。 AEB2C2B1B3C1C3D1D2435810121418101294589773411 如何处理这个问题

6、呢? 可以采取穷举法即把由A到E一切能够的每一条道路的距 离都算出来，然后相互比较找出最短者，相应地得出了最短道路这样，由A到E一共有3 X 3 X 2 X 118条不同的道路，比较这18条不同的道路的间隔值，才找出最短道路。 显然，这样作计算是相当繁的假设当段数很多，各段的不同选择也很多时，这种解法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的AEB2C2B1B3C1C3D1D2435810121418101294589773411AEB2C2B1B3C1C3D1D243581012141810129458977341112043514141617192 用动态规划的方法来求解以上

7、最短路问题B 地C 地D 地E 地A 地1 顺序解法求解得到的结果内容丰富2 逆序解法AEB2C2B1B3C1C3D1D24358101214181012945897734110B 地C 地D 地E 地A 地3471110151819193 动态规划的根本概念(1)阶段 把所给问题的过程，恰当地分为假设干个相互联络的阶段，以便能按一定的次序去求解 阶段的划分，普通是根据时间和空间的 自然特征来划分。 描画阶段的变量称为阶段变量，常用 k 表示如例1可分为4个阶段来求解，k1、2、3、4。AEB2C2B1B3C1C3D1D2435810121418101294589773411(2)形状 形状表

8、示每个阶段开场所处的自然情况或客观条件，它描画了研讨问题过程的情况，又称不可控要素在例1中，形状就是某阶段的出发位置它既是该阶段某支路的起点，又是前一阶段某支路的终点通常一个阶段有假设于个形状，第一阶段有一个形状就是点A，第二阶段有两个形状，即点集合B1，B2， 第k阶段的形状就是第k是阶段一切始点的集合 .AEB2C2B1B3C1C3D1D24358101214181012945897734113 动态规划的根本概念 描画过程形状的变量称为形状变量。它可用一个数、一组数或一个向量(多维情形)来描画常用 xk 表示第受阶段的形状变量如在例1中第三阶段有 3 个形状，那么形状变量 x3 可取3个

9、值，即x3=c1,c2,c3。可达形状集合 某个阶段的一切的形状所构成的集合，称为可达形状集合。例如，第三阶段的一切形状为c1,c2,c3，那么第三阶段的可达形状集合成为点集合 c1,c2,c3 。记为x3= c1,c2,c3 。AEB2C2B1B3C1C3D1D24358101214181012945897734113 动态规划的根本概念形状的根本特性无后效性否那么就不能成为动态规划里所讲的形状AEB2C2B1B3C1C3D1D2435810121418101294589773411 假设某阶段形状给定后，那么在这阶段以后过程的开展不受这阶段以前各段形状的影响换句活说，过程的过去历史只能经过

10、当前的形状去影响它未来的开展，当前的形状是以往历史的一个总结这个性质称为无后效性(即马尔科夫性)前效性 相反，假设形状仅仅描画过程的详细特征，并不满足无后效性的要求。应适当地改动形状的规定方法，以到达能使它满足无后效性的要求。才干成为动态规划里所讲的形状。 例如，研讨物体(把它看作一个质点)受外力作用后其空间运动的轨迹问题从描画轨迹这点着眼，可以只选坐标位置(xk，yk)作为过程的形状，但这样不能满足无后效性，由于即使知道了外力的大小和方向，仍无法确定物体受力后的运动方向和轨迹。 不具有后效性的例子 但是假设把位置(xk，yk)和速度(vxk，vvk)都作为过程的形状变量，就可以确定物体运动下

11、一步的方向和轨迹，实现无后效性的要求(3)决策 决策表示当过程处于某一阶段的某个形状时，可以作出不同的决议(或选择)，从而确定下一阶段的形状，这种决议称为决策。AEB2C2B1B3C1C3D1D24358101214181012945897734113 动态规划的根本概念决策变量 uk ( xk ) 描画决策的变量，称为决策变量它可用一个数、一组数或一个向量来描画uk ( xk ) 表示第 k 阶段当形状处于xk 时的决策变量它是形状变量的函数 AEB2C2B1B3C1C3D1D24358101214181012945897734113 动态规划的根本概念允许决策集合Dk(xk)在实践问题中，

12、决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合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阶段开场直到终止形状为

13、止的过程，称为问题的后部子过程(或称为k子过程)全过程的一个战略 当k=1时，此决策函数序列称为全过程的一个战略，简称战略，记为p1,n(x1). 3 动态规划的根本概念3 动态规划的根本概念允许战略集合 在实践问题中，可供选择的战略有一定的范围，此范围称为允许战略集合，用P表示.从允许决策集合中就能找出到达最优效果的战略，它被称为最优战略。 AEB2C2B1B3C1C3D1D24358101214181012945897734113 动态规划的根本概念目的函数 运用不同的战略，其效果是不一样的，把衡量过程效果的好坏的函数叫做目的函数。Vkn=Vkn(xk,uk,xk+1, uk +1, xk

14、+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的最短间隔。012

15、310371120481230579导弹数战场效益战场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表示分配给第三

16、阶段也就是第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=

17、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战场1x

18、3X2X1X1=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阶

19、段形状为(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)

20、 )+ 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(

21、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

22、)=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,

23、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)决策