运筹学 北京邮电大学.动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 动态规划（续）,动态规划的基本原理,动态规划方法的基本步骤,动态规划方法应用举例,本章以下内容,1,最优化原理（贝尔曼最优化原理）,作为一个全过程的最优策略具有这样的性质：,对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。,该原理的具体解释是，若某一全过程最优策略为：,动态规划的基本原理,则对上述策略中所隐含的任一状态而言，,第,k,子过程上对应于该状态的最优策略必然,包含在上述全过程最优策略,p,1,*,中，,即为,2,3.,动态规划方法的基本步骤1,应将实际问题恰当地分割成,n,个子问题,(,n,个阶段,),。,通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数,n,，即,k,=,n,。,2,正确地定义状态变量,s,k,，,使它既能正确地描述过程的状态，又能满足无后效性,动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征,：,3,3.,动态规划方法的基本步骤,(1),要能够正确地描述受控过程的变化特征。,(2),要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。,(3),要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量,s,k,的维数而前者约束条件所表示的内容，常就是状态变量,s,k,所代表的内容。,4,3.,动态规划方法的基本步骤,3,正确地定义决策变量及各阶段的允许决策集合,U,k,(,s,k,),，,根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型,(,如线性与非线性规划),转换为动态规划模型时，常取前者的变量,x,j,为后者的决策变量,u,k,。,4.,能够,正确地写出状态转移方程,，至少要能正确反映状态转移规律。如果给定第,k,阶段状态变量,s,k,的,值，则该段的决策变量,u,k,一经确定，第,k,+1,段的状态变量,s,k,+1,的值也就完全确定，即有,s,k,+1,=,T,k,(,s,k,u,k,),5,3.,动态规划方法的基本步骤,5,根据题意,正确地构造出目标与变量的函数关系,目标函数,，目标函数应满足下列性质：,(1),可分性，即对于所有,k,后部子过程，其目标函数仅取决于状态,s,k,及其以后的决策,u,k,u,k,+1,u,n,就是说它是定义在全过程和所有后部子过程上的数量函数。,(2),要满足递推关系，即,(3),函数 对其变元,R,k,+1,来说要严格单调。,6,6,写出动态规划函数基本方程,例如常见的指标函数是取各段指标和的形式,其中 表示第,i,阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：,3.,动态规划方法的基本步骤,7,学习方法建议：,第一步,先看问题，充分理解问题的条件、情况及求解目标。,第二步,结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的,“,四大要素、一个方程,”,这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。,4.,动态规划方法应用举例,8,第三步,动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。,第四步,把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。,第五步,对照自己 的求解，分析成败。,4.,动态规划方法应用举例,9,1.,动态规划的四大要素,状态变量及其可能集合,x,k,X,k,决策变量及其允许集合,u,k,U,k,状态转移方程,x,k,+1,=,T,k,(,x,k,u,k,),阶段效应,r,k,(,x,k,u,k,),4.,动态规划方法应用举例,10,2.,动态规划基本方程,f,n,+1,(,x,n,+1,)=0,(,边界条件,),f,k,(,x,k,)=opt,u,r,k,(,x,k,u,k,)+,f,k,+1,(,x,k,+1,),k,=,n,1,4.,动态规划方法应用举例,11,求 最 短 路 径,12,求 最 短 路 径,例,5.5,13,将问题分成五个阶段，第,k,阶段到达的具体地点用状态变量,x,k,表示，例如：,x,2,=,B,3,表示第二阶段到达位置,B,3,，,等等。这里状态变量取字符值而不是数值。,将决策定义为到达下一站所选择的路径，例如目前的状态是,x,2,=,B,3,，,这时决策允许集合包含三个决策，它们是,D,2,(,x,2,)=,D,2,(,B,3,)=,B,3,C,1,B,3,C,2,B,3,C,3,求 最 短 路 径,14,最优指标函数,f,k,(,x,k,),表示从目前状态到,E,的最短路径。终端条件为,f,5,(,x,5,)=,f,5,(,E,)=0,其含义是从,E,到,E,的最短路径为,0,。,第四阶段的递推方程为,:,求 最 短 路 径,15,其中*表示最优值，在上表中，由于决策允许集合,D,4,(,x,4,),中的决策是唯一的，因此这个值就是最优值。,由此得到,f,4,(,x,4,),的表达式。由于这是一个离散的函数，取值用列表表示：,求 最 短 路 径,16,第三阶段的递推方程为：,求 最 短 路 径,17,由此得到,f,3,(,x,3,),的表达式：,求 最 短 路 径,18,求 最 短 路 径,19,由此得到,f,2,(,x,2,),的表达式：,求 最 短 路 径,20,第一阶段的递推方程为：,求 最 短 路 径,21,由此得到,f,1,(,x,1,),的表达式,求 最 短 路 径,22,资 源 分 配 问 题,23,例,5.6:,有资金,4,万元，投资,A,、,B,、,C,三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目,A,、,B,、,C,的投资效益（万吨,）,和投入资金（万元）关系见下表：,求对三个项目的最优投资分配，使总投资效益最大。,资 源 分 配 问 题,24,阶段,k,：,每投资一个项目作为一个阶段；,状态变量,x,k,：,投资第,k,个项目前的资金数；,决策变量,d,k,：第,k,个项目的投资；,决策允许集合：,0,d,k,x,k,状态转移方程：,x,k,+1,=,x,k,-,d,k,阶段指标：,v,k,(,x,k,d,k,),见表中所示；,递推方程：,f,k,(,x,k,)=,max,v,k,(,x,k,d,k,)+,f,k,+1,(,x,k,+1,),终端条件：,f,4,(,x,4,)=0,资 源 分 配 问 题,25,k=4，f,4,(x,4,)=0k=3，0d,3,x,3,，x,4,=x,3,-d,3,资 源 分 配 问 题,26,k=2，0d,2,x,2,，x,3,=x,2,-d,2,资 源 分 配 问 题,27,k=1，0d,1,x,1,，x,2,=x,1,-d,1,资 源 分 配 问 题,28,背 包 问 题,29,背 包 问 题,30,则,Max,z,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,s.t.,w,1,x,1,+,w,2,x,2,+,+,w,n,x,n,W,x,1,x,2,x,n,为正整数,阶段,k,：第,k,次装载,第,k,种物品（,k,=1,2,n,）,状态变量,x,k,：第,k,次装载时背包还可以装载的重量；,决策变量,d,k,：第,k,次装载第,k,种物品的件数；,背 包 问 题,31,4.,决策允许集合：,D,k,(,x,k,)=,d,k,|0,d,k,x,k,/,wk,，,d,k,为整数,；,5.,状态转移方程,：,x,k,+1,=,x,k,-,w,k,d,k,6,.,阶段指标：,v,k,=,c,k,d,k,7,.,递推方程,f,k,(,x,k,)=max,c,k,d,k,+,f,k,+1,(,x,k,+1,),=max,c,k,d,k,+,f,k,+1,(,x,k,-,w,k,d,k,),8.,终端条件,：,f,n+1,(,x,n+1,)=0,背 包 问 题,32,例,5.7:,对于一个具体问题,c,1,=65,，,c,2,=80,，,c,3,=30,；,w,1,=2,，,w,2,=3,，,w,3,=1,；,以及,W,=5,用动态规划求解,f,4,(x,4,)=0,对于,k,=3,背 包 问 题,33,对于,k,=3,列出,f,3,(,x,3,),的数值表如下：,34,对于,k,=2,列出,f,2,(,x,2,),的数值表,35,对于,k,=1,列出,f,1,(,x,1,),的数值表,36,37,机器负荷分配问题,38,39,构造动态规划模型如下：,阶段,k,：,运行年份（,k,=1,2,3,4,5,6,），,其中,k,=1,表示第一年初，,，依次类推；,k,=6,表示第五年末（即第六年初）。,状态变量,x,k,：,第,k,年初完好的机器数（,k,=1,2,3,4,5,6,），,其中,x,6,表示第五年末（即第六年初）的完好机器数。,决策变量,d,k,：,第,k,年投入高负荷运行的机器数；,状态转移方程,：,x,k,+1,=0.7,d,k,+0.9(,x,k,-,d,k,),决策允许集合,：,D,k,(,x,k,)=,d,k,|0,d,k,x,k,阶段指标,：,v,k,(,x,k,d,k,)=8,d,k,+5(,x,k,-,d,k,),终端条件,：,f,6,(,x,6,)=0,机器负荷分配问题,40,递推方程：,f,k,(,x,k,)=max,v,k,(,x,k,d,k,)+,f,k,+1,(,x,k,+1,),d,k,D,k,(,x,k,),=,max8,d,k,+5(,x,k,-,d,k,)+,f,k,+1,0.7,d,k,+0.9(,x,k,-,d,k,),0,d,k,x,k,机器负荷分配问题,41,f,5,(,x,5,)=max8,d,5,+5(,x,5,-,d,5,)+,f,6,(,x,6,),0,d,5,x,5,=max3,d,5,+5,x,5,=8,x,5,d,5,*=,x,5,0,d,5,x,5,f,4,(,x,4,)=max8,d,4,+5(,x,4,-,d,4,)+,f,5,(,x,5,),0,d,4,x,4,=max8,d,4,+5(,x,4,-,d,4,)+8,x,5,0,d,4,x,4,=max8,d,4,+5(,x,4,-,d,4,)+80.7,d,4,+0.9(,x,4,-,d,4,),0,d,4,x,4,=max1.4,d,4,+12.3,x,4,=13.7,x,4,d,4,*=,x,4,0,d,4,x,4,机器负荷分配问题,42,f,3,(,x,3,)=max8,d,3,+5(,x,3,-,d,3,)+,f,4,(,x,4,),0,d,3,x,3,=max8,d,3,+5(,x,3,-,d,3,)+13.7,x,4,0,d,3,x,3,=max8,d,3,+5(,x,3,-,d,3,)+13.70.7,d,3,+0.9(,x,3,-,d,3,),0,d,3,x,3,=max0.28,d,3,+17.24,x,3,=17.52,x,3,d,3,*=,x,3,0,d,3,x,3,机器负荷分配问题,43,f,2,(,x,2,)=max8,d,2,+5(,x,2,-,d,2,)+,f,3,(,x,3,),0,d,2,x,2,=max8,d,2,+5(,x,2,-,d,2,)+17.52,x,3,0,d,2,x,2,=,max8,d,2,+5(,x,2,-,d,2,)+17.520.7,d,2,+0.9(,x,2,-,d,2,),0,d,2,x,2,=max-0.504,d,2,+20.77,x,2,=20.77,x,2,d,2,*=0,0,d,2,x,2,机器负荷分配问题,44,f,1,(,x,1,)=max8,d,1,+5(,x,1,-,d,1,)+,f,2,(x,2,),0,d,1,x,1,=max8,d,1,+5(,x,1,-,d,1,)+20.77,x,2,0,d,1,x,1,=,max8,d,1,+5(,x,1,-,d,1,)+20.770.7,d,1,+0.9(,x,1,-,d,1,),0,d,1,x,1,=max-0.05,d,1,+23.69,x,1,=23.69,x,1,d,1,*=0,0,d,1,x,1,机器负荷分配问题,45,由此可以得到：,f,1,(,x,1,)=23.69,x,1,d,1,*=0,f,2,(,x,2,)=20.77,x,2,d,2,*=0,f,3,(,x,3,)=17.52,x,3,d,3,*=,x,3,f,4,(,x,4,)=13.60,x,4,d,4,*=,x,4,f,5,(,x,5,)=8,x,5,d,5,*=,x,5,用,x,1,=1000,代入，得到五年最大产量为,f,1,(,x,1,)=,f,1,(1000)=23690,机器负荷分配问题,46,每年投入高负荷运行的机器数以每年初完好的机器数为,：,x,1,=1000,d,1,*=0,x,2,=0.7,d,1,+0.9(,x,1,-,d,1,)=900,d,2,*=0,x,3,=0.7,d,2,+0.9(,x,2,-,d,2,)=810,d,3,*=,x,3,=810,x,4,=0.7,d,3,+0.9(,x,3,-,d,3,)=567d,4,*=,x,4,=567,x,5,=0.7,d,4,+0.9(,x,4,-,d,4,)=397,d,5,*=,x,5,=397,x,6,=0.7,d,5,+0.9(,x,5,-,d,5,)=278,机器负荷分配问题,47,在这个例子中，状态变量的终端值,x,6,是未加约束的，如果要求在第五年末（即第六年初）完好的机器数不少于,500,台，这时决策变量,d,5,的决策允许集合将成为：,D,5,(,x,5,)=,d,5,|0.7,d,5,+0.9(,x,5,-,d,5,),500,d,5,0,即,0.9,x,5,-0.2,d,5,500,d,5,0,或,0,d,5,4.5,x,5,-2500,容易想象，这时的最大产量将比,x,6,是自由的情况下小。,这个例子可以推广到一般情况。设高负荷生产时机器的完好率为,k,1,，,单台产量为,p,1,；,低负荷完好率为,k,2,，,单台产量为,p,2,。,若有,t,满足,:,机器负荷分配问题,48,则从,1,t,-1,年，年初将全部完好机器投入低负荷运行，从,t,n,年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。,机器负荷分配问题,49,生 产 库 存 问 题,50,例,5.9,：,一个工厂生产某种产品,1-7,月份生产成本和产品需求量的变化情 况如下表：,生 产 库 存 问 题,51,阶段,k,：,月份，,k,=12,7,8,；,状态变量,x,k,：,第,k,个月初（发货以前）的库存量；,决策变量,d,k,：,第,k,个月的生产量；,状态转移方程：,x,k,+1,=,x,k,-,r,k,+,d,k,；,决策允许集合：,D,k,(,x,k,)=,d,k,|,d,k,0,r,k,+1,x,k,+1,H,=,d,k,|,d,k,0,r,k,+1,x,k,-,r,k,+,d,k,H,；,阶段指标：,v,k,(,x,k,d,k,)=,c,k,d,k,；,终端条件：,f,8,(,x,8,)=0,x,8,=0,；,生 产 库 存 问 题,52,递推方程：,f,k,(,x,k,)=,min,v,k,(,x,k,d,k)+,f,k,+1,(,x,k,+1,),d,k,D,k,(x,k,),=min,c,k,d,k,+,f,k,+1,(,x,k,-,r,k,+,d,k,),d,k,D,k,(,x,k,),对于,k,=7,因为,x,8,=0,有,d,7,=0,递推方程为,f,7,(,x,7,)=min,c,7,d,7,+,f,8,(,x,8,)=0,d,7,=0,生 产 库 存 问 题,53,对于,k,=6,因为,d,7,=0,，,所以,x,7,=,r,7,=4,而,x,6,-,r,6,+,d,6,=,x,7,=4,因此有,d,6,=,x,7,+,r,6,-,x,6,=4+7-,x,6,=11-,x,6,也是唯一的决策。因此递推方程为：,f,6,(,x,6,)=min,c,6,d,6,+,f,7,(,x,7,),d,6,=11-,x,6,=10,d,6,=10(11-,x,6,)=110-10,x,6,生 产 库 存 问 题,54,对于,k,=5,f,5,(,x,5,)=min,c,5,d,5,+,f,6,(,x,6,),d,5,D,5,(,x,5,),=min20,d,5,+110-10,x,6,d,5,D,5,(,x,5,),=min20,d,5,+110-10(,x,5,-,r,5,+,d,5,),d,5,D,5,(,x,5,),=min20,d,5,+110-10(,x,5,-2+,d,5),d,5,D,5,(,x,5,),=min10,d,5,-10,x,5,+130,d,5,D,5,(,x,5,),D,5,(,x,5,)=,d,5,|,d,5,0,r,6,x,5,-,r,5,+,d,5,H,=,d,5,|,d,5,0,r,6,+,r,5,-,x,5,d,5,H,+,r,5,-,x,5,=,d,5,|,d,5,0,9-,x,5,d,5,11-,x,5,生 产 库 存 问 题,55,因为,x,5,H,=9,，,因此,9-,x,5,0,，,决策允许集合可以简化为,D,5,(,x,5,)=,d,5,|9-,x,5,d,5,11-,x,5,递推方程成为,f,5,(,x,5,)=min10,d,5,-10,x,5,+130,9-,x,5,d,5,11-,x,5,=10(9-,x,5,)-10,x,5,+130 =220-20,x,5,d,5,*=9-,x,5,生 产 库 存 问 题,56,对于,k,=4,f,4,(,x,4,)=min,c,4,d,4,+,f,5,(,x,5,),d,4,D,4,(,x,4,),=min17,d,4,+220-20,x,5,d,4,D,4,(,x,4,),=min17,d,4,+220-20(,x,4,-,r,4,+,d,4,),d,4,D,4,(,x,4,),=min17,d,4,+220-20(,x,4,-3+,d,4,),d,4,D,4,(,x,4,),=min-3,d,4,-20,x,4,+280,d,4,D,4,(,x,4,),生 产 库 存 问 题,57,D,4,(,x,4,)=,d,4,|,d,4,0,r,5,x,4,-,r,4,+,d,4,H,=,d,4,|,d,4,0,r,5,+,r,4,-,x,4,d,4,H,+,r,4,-,x,4,=,d,4,|,d,4,0,5-,x,4,d,4,12-,x,4,=,d,4,|max0,5-,x,4,d,4,12-,x,4,由于,在,f,4,(,x,4,),的表达式中,d,4,的系数是,-3,，,因此,d,4,在决策允许集合中应取集合中的,最大值，即,d,4,=12-,x,4,由此,f,4,(,x,4,)=-3(12-,x,4,)-20,x,4,+280,=-17,x,4,+244,生 产 库 存 问 题,58,对于,k,=3,f,3,(,x,3,)=min,c,3,d,3,+,f,4,(,x,4,),d,3,D,3,(,x,3,)=min 13,d,3,+244-17,x,4,d,3,D,3,(,x,3,)=min 13,d,3,+244-17(,x,3,-,r,3,+,d,3,),d,3,D,3,(,x,3,),=min-4,d,3,-17,x,3,+329,d,3,D,3,(,x,3,),D,3,(,x,3,)=,d,3,|,d,3,0,r,4,x,3,-r,3,+,d,3,H,=,d,3,|,d,3,0,r,4,+,r,3,-,x,3,d,3,H,+,r,3,-,x,3,=,d,3,|,d,3,0,8-,x,3,d,3,14-,x,3,=,d,3,|max0,8-,x,3,d,3,14-,x,3,由此,f,3,(,x,3,)=-4(14-,x,3,)-17,x,3,+329 =-13,x,3,+273,d,3,*=14-,x,3,生 产 库 存 问 题,59,对于,k,=2,f,2,(,x,2,)=min,c,2,d,2,+,f,3,(,x,3,),d,2,D,2,(,x,2,)=min18,d,2,+273-13,x,3,d,2,D,2,(x,2,)=min18,d,2,+273-13(,x,2,-,r,2,+,d,2,),d,2,D,2,(,x,2,),=min18,d,2,+273-13(,x,2,-8+,d,2,),d,2,D,2,(,x,2,),=min5,d,2,-13,x,2,+377,d,2,D,2,(,x,2,),D,2,(,x,2,)=,d,2,|,d,2,0,r,3,x,2,-,r,2,+,d,2,H,=,d,2,|,d,2,0,r,3,+,r,2,-,x,2,d,2,H,+,r,2,-,x,2,=,d,2,|,d,2,0,13-,x,2,d,2,17-,x,2,生 产 库 存 问 题,60,因为,13-,x,2,0,所以,d,2,(,x,2,)=,d,2,|13-,x,2,d,2,17-,x,2,由此,f,2,(,x,2,)=5(13-,x,2,)-13,x,2,+377=-18,x,2,+442,d,2,*=13-,x,2,生 产 库 存 问 题,61,对于,k,=1,f,1,(,x,1,)=min,c,1,d,1,+,f,2,(,x,2,),d,1,D,1,(,x,1,)=min11,d,1,+442-18,x,2,d,1,D,1,(,x,1,)=min11,d,1,+442-18(,x,1,-,r,1,+,d,1,),d,1,D,1,(,x,1,),=min11,d,1,+442-18(x,1,-0+,d,1,),d,1,D,1,(,x,1,),=min-7,d,1,-18,x,1,+442,d,1,D,1,(,x,1,),D,1,(,x,1,)=,d,1,|,d,1,0,r,2,x,1,-,r,1,+,d,1,H,=,d,1,|,d,1,0,r,2,+,r,1,-,x,1,d,1,H,+,r,1,-,x,1,=,d,1,|,d,1,0,8-,x,1,d,1,9-,x,1,生 产 库 存 问 题,62,根据题意,x,1,=2,所以,D,1,(,x,1,)=,d,1,|6,d,1,7,由此,d,1,=7,f,1,(,x,1,)=-7,d,1,-18,x,1,+442=-77,182,442=357,将以上结果总结成下表,：,生 产 库 存 问 题,63,设 备 更 新 问 题,64,一台设备的价格为,P,，,运行寿命为,n,年，每年的维修费用是设备役龄的函数，记为,C,(,t,),，,新设备的役龄为,t,=0,。,旧设备出售的价格是设备役龄的函数，记为,S,(,t,),。在,n,年末，役龄为,t,的设备残值为,R,(,t,),。,现有一台役龄为,T,的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，,设 备 更 新 问 题,65,66,设 备 更 新 问 题,67,例,5.10,：设具体数据如下：,设 备 更 新 问 题,68,69,70,71,72,73,74,75,76,97,77,由以上计算可知，本问题有两个决策，它们对应的最小费用都是,115,。,这两个决策是,设 备 更 新 问 题,78,