文档介绍：动态规划模型的分类,根据多阶段决策过程的时间参量是离散的还是连续的变量;,、离散随机性、连续确定性、,介绍动态规划的基本概念、理论和方法,并通过几个典型的问题来说明它的应用,——有一批军用物资需要从A地调运到E地,如下图所示,请求出一条从A到E的一条线路,使总的运输距离最短。图中线条上的数字为距离。AEB2C2B1B3C1C3D1D24358101214181012945897734111多阶段决策过程及实例B地C地D地E地A地在生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响到以后的决策。AEB2C2B1B3C1C3D1D2435810121418101294589773411如果一个问题的过程可以化分为若干个互相联系的阶段,而且每个阶段都需要作出决策,而且当每个阶段的决策都确定之后,整个问题也就确定了,那么,这个问题就叫做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法。如上图所示的线路网络,,来说明动态规划方法的基本思想,并阐述它的基本概念。.AEB2C2B1B3C1C3D1D2435810121418101294589773411如上图可知,,从B到C为第二阶段…从D到E为第四阶段在第一阶段,A为起点,终点有B1,B2,B3三个,因而这时走的路线有三个选择,分别是走B1,B2,B3。如果选择走B2的决策,,又是第二阶段路线的始点。在第二阶段,再从B2点出发,对应于B2点就有一个可供选择的终点集合{C1,C2,C3};如果选择由B2走至C2为第二阶段的决策,则C2就是第二阶段的终点,,可看到:各个阶段的决策不同,,当某一阶段的始点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,:在各个阶段选取一个恰当的决策,使由这些决策组成的一个决策序列所决定的一条路线,其总路程最短。AEB2C2B1B3C1C3D1D2435810121418101294589773411如何解决这个问题呢?,然后互相比较找出最短者,,由A到E一共有3X3X2X1=18条不同的路线,比较这18条不同的路线的距离值,才找出最短路线。显然,,各段的不同选择也很多时,这种解法的计算将变得极其繁杂,**********用动态规划的方法来求解以上最短路问题B地C地D地E地A地(1)顺序解法求解得到的结果内容丰富(2)逆序解法AEB2C2B1B3C1C3D1D24358101214181012945897734110B地C地D地E地A地34711**********动态规划的基本概念(1)阶段把所给问题的过程,恰当地分为若干个相互联系的阶段,,一般是根据时间和空间的自然特征来划分。描述阶段的变量称为阶段变量,,k=1、2、3、4。AEB2C2B1B3C1C3D1D2435810121418101294589773411(2)状态状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况,,,,第一阶段有一个状态就是点A,第二阶段有两个状态,即点集合{B1,B2},第k阶段的状态就是第k是阶段所有始点的集