管理运筹学-第5章--动态规划.ppt

《管理运筹学-第5章--动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、管理运筹学主讲教师：马越峰第五章动态规划5.1.动态规划的基本概念和最优化原理5.2.动态规划模型的建立与求解5.3.动态规划在经济管理中的应用5.1.动态规划的基本概念和最优化原理例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC412312312322164724838675611063751讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；分析得知

2、：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+1

3、0=171+10=116+6=125+6=116+6=12121111D2D2D1第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=121213141

4、2C2C3C3C3第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：最后可以得到：从A到E的最短路径为AB4C3D1E阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B4一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：表示每个阶段开始所处的自然状况或客观条件。状态可以是数量，也可以是字符

5、，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。D3(C1)=｛D1,D2｝基本概念、基本方程与最优化原理例题中K=？s3=?4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。6、阶段指标函数vk(sk,xk)：从状态sk出发，

6、选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,…,xn)：从状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即对于可加性指标函数，上式可以写为终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状

7、态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。一、资源分配问题例2:某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂,各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？盈利工厂设备台数甲厂乙厂丙厂0000135427106391111412111251311125.2动态规划模型的建立与求解解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3)xk=分配

8、给第k个设备台数。已知s1=5,并有从　与　的定义，可知以下我们从第三阶段开始计算。第三阶段:显然将　　　　　　　　台设备都分配给第3工厂时，也就是　　　时，第3阶段的指标值（即第3厂的盈利）为最大，即由于第3阶段是最后的阶段，故有其中　可取值为0,1,2,3,4,5。其数值