【安全课件】动态规划.pptx

第五节 动态规划;; 引例——有一批军用物资需要从 A 地调运到E地，如下图所示，请求出一条从 A 到 E 的一条线路，使总的运输距离最短。图中线条上的数字为距离。; 在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响到以后的决策。; 如上图所示的线路网络，求 A 到 E 点的最短路线问题是动态规划中一个较为直观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的基本概念。．; 在第一阶段，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择， 分别是走B1，B2，B3。 如果选择走B2的决策，则B2就是第 一阶段在我们决策之下的结果．它既是第一阶段路线的终点，又是第二阶段路线的始点。 在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合{C1，C2，C3}； 如果选择由B2走至C2为第二阶段的决策，则C2 就是第二阶段的终点，同时又是第三阶段的始点． 同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。 ; 如何解决这个问题呢? 可以采取穷举法．即把由A到E所有可能的每一条路线的距 离都算出来，然后互相比较找出最短者，相应地得出了最短路线．这样，由A到E一共有3 X 3 X 2 X 1＝18条不同的路线，比较这18条不同的路线的距离值，才找出最短路线。 显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的．;;;3 动态规划的基本概念;(2)状态 状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素．在例1中，状态就是某阶段的出发位置．它既是该阶段某支路的起点，又是前一阶段某支路的终点．通常一个阶段有若于个状态，第一阶段有一个状态就是点A，第二阶段有两个状态，即点集合{B1，B2}， 第k阶段的状态就是第k是阶段所有始点的集合． .;可达状态集合 某个阶段的所有的状态所构成的集合，称为可达状态集合。例如，第三阶段的所有状态为c1,c2,c3，则第三阶段的可达状态集合成为点集合{ c1,c2,c3} 。记为x3={ c1,c2,c3 }。;状态的基本特性——无后效性（否则就不能成为动态规划里所讲的状态）; 例如，研究物体(把它看作一个质点)受外力作用后其空间运动的轨迹问题．从描述轨迹这点着眼，可以只选坐标位置(xk，yk)作为过程的状态，但这样不能满足无后效性，因为即使知道了外力的大小和方向，仍无法确定物体受力后的运动方向和轨迹。 ;(3)决策 决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策。;决策变量—— uk ( xk ) 描述决策的变量，称为决策变量．它可用一个数、一组数或一个向量来描述． uk ( xk ) 表示第 k 阶段当状态处于xk 时的决策变量．它是状态变量的函数． ;允许决策集合——Dk(xk) 在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合．;A;3 动态规划的基本概念;3 动态规划的基本概念;3 动态规划的基本概念;;;;;;;;;;;;; 动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果．在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代企业管理中的一种重要的决策方法．许多问题用动态规划的方法去处理，常比线性规划或非线性规划更有成效．特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具．应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法(如线性规划是一种算法)．因而，它不象线性规划那样有一个标准的数学表达式和