资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第九章 动态规划,动态规划的基本原理,动态规划方法的基本步骤,动态规划方法应用举例,本章以下内容,1第九章 动态规划动态规划的基本原理本章以下内容,2,最优化原理（贝尔曼最优化原理）,作为一个全过程的最优策略具有这样的性质：,对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。,该原理的具体解释是，若某一全过程最优策略为：,动态规划的基本原理,则对上述策略中所隐含的任一状态而言，,第,k,子过程上对应于该状态的最优策略必然,包含在上述全过程最优策略,p,1,*,中，即为,2最优化原理（贝尔曼最优化原理）动态规划的基本原理,3,3.,动态规划方法的基本步骤,1,应将实际问题恰当地分割成,n,个子问题,(,n,个阶段,),。,通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数,n,，即,k,=,n,。,2,正确地定义状态变量,s,k,，使它既能正确地描述过程的状态，又能满足无后效性,动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：,33.动态规划方法的基本步骤 1应将,4,3.,动态规划方法的基本步骤,(1),要能够正确地描述受控过程的变化特征。,(2),要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响。,(3),要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量,s,k,的维数而前者约束条件所表示的内容，常就是状态变量,s,k,所代表的内容。,43.动态规划方法的基本步骤,5,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,),53.动态规划方法的基本步骤 3正确地定义决策,6,3.,动态规划方法的基本步骤,5,根据题意,正确地构造出目标与变量的函数关系,目标函数,，目标函数应满足下列性质：,(1),可分性，即对于所有,k,后部子过程，其目标函数仅取决于状态,s,k,及其以后的决策,u,k,u,k,+1,u,n,就是说它是定义在全过程和所有后部子过程上的数量函数。,(2),要满足递推关系，即,(3),函数 对其变元,R,k,+1,来说要严格单调。,63.动态规划方法的基本步骤 5根据题意,正确,7,6,写出动态规划函数基本方程,例如常见的指标函数是取各段指标和的形式,其中 表示第,i,阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：,3.,动态规划方法的基本步骤,7 6写出动态规划函数基本方程3.动态规划方法的基本,8,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.,动态规划方法应用举例,8 1.动态规划的四大要素4.动态规划方法应用举例,9,2.,动态规划基本方程,f,n,+1(,xn,+1,)=0,(,边界条件,),f,k,(,xk,)=opt,u,rk,(,xk,uk,)+,f,k,+1(,xk,+1,),k,=,n,1,4.,动态规划方法应用举例,9 2.动态规划基本方程 4.动态规划方法应,10,求 最 短 路 径,10求 最 短 路 径,11,求 最 短 路 径,例,5.5,11 求 最 短 路 径例5.5,12,将问题分成五个阶段，第,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,求 最 短 路 径,12 将问题分成五个阶段，第k阶段到,13,最优指标函数,f,k,(,x,k,),表示从目前状态到,E,的最短路径。终端条件为,f,5,(,x,5,)=,f,5,(,E,)=0,其含义是从,E,到,E,的最短路径为,0,。,第四阶段的递推方程为,:,求 最 短 路 径,13最优指标函数fk(xk)表示从目前状态到E的最短路径。终,14,其中*表示最优值，在上表中，由于决策允许集合,D,4,(,x,4,),中的决策是唯一的，因此这个值就是最优值。,由此得到,f,4,(,x,4,),的表达式。由于这是一个离散的函数，取值用列表表示：,求 最 短 路 径,14其中*表示最优值，在上表中，由于决策允许集合D4(x4),15,第三阶段的递推方程为：,求 最 短 路 径,15第三阶段的递推方程为：求 最 短 路 径,16,由此得到,f,3,(,x,3,),的表达式：,求 最 短 路 径,16由此得到f3(x3)的表达式：求 最 短 路 径,17,求 最 短 路 径,17求 最 短 路 径,18,由此得到,f,2,(,x,2,),的表达式：,求 最 短 路 径,18由此得到f2(x2)的表达式：求 最 短 路 径,19,第一阶段的递推方程为：,求 最 短 路 径,19第一阶段的递推方程为：求 最 短 路 径,20,由此得到,f,1,(,x,1,),的表达式,求 最 短 路 径,20由此得到f1(x1)的表达式求 最 短 路 径,例：,某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙两个中转站，其中乙中转站可以选择乙,1,和乙,2,两个可选地点，丙中转站可以选择丙,1,、丙,2,和丙,3,三个可选地点，各相邻两地之间的距离如表所示，则甲地到丁地之间的最短距离为,：,A,、,64 B,、,74 C,、,76 D,、,68,【,答案,】,：,B,地点,-距离-地点,乙,1,乙,2,丙,1,丙,2,丙,3,丁,甲,26,30,乙,1,18,28,32,乙,2,30,32,26,丙,1,30,丙,2,28,丙,3,22,例：某公司从甲地向丁地运送物资，运送过程中先后需要经过乙、丙,22,资 源 分 配 问 题,22资 源 分 配 问 题,23,例,5.6:,有资金,4,万元，投资,A,、,B,、,C,三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目,A,、,B,、,C,的投资效益（万吨）和投入资金（万元）关系见下表：,求对三个项目的最优投资分配，使总投资效益最大。,资 源 分 配 问 题,23 例5.6:有资金4万元，投资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,资 源 分 配 问 题,24阶段k：每投资一个项目作为一个阶段；资 源 分 配 问,25,k=4,，,f,4,(x,4,)=0k=3,，,0d,3,x,3,，,x,4,=x,3,-d,3,资 源 分 配 问 题,25k=4，f4(x4)=0k=3，0d3x3，x4=,26,k=2,，,0d,2,x,2,，,x,3,=x,2,-d,2,资 源 分 配 问 题,26k=2，0d2x2，x3=x2-d2资 源 分 配,27,k=1,，,0d,1,x,1,，,x,2,=x,1,-d,1,资 源 分 配 问 题,27k=1，0d1x1，x2=x1-d1资 源 分 配,28,背 包 问 题,28背 包 问 题,29,背 包 问 题,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,种物品的件数；,背 包 问 题,30则 Max z=c1x1+c2x2+cnxn,31,4.,决策允许集合：,D,k,(,x,k,)=,d,k,|0,d,k,x,k,/,w,k,，,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,背 包 问 题,314.决策允许集合：背 包 问 题,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,背 包 问 题,32 例5.7:对于一个具体问题c1=65，c2=80，,33,对于,k,=3,列出,f,3,(,x,3,),的数值表如下：,33对于k=3列出 f3(x3)的数值表如下：,34,对于,k,=2,列出,f,2,(,x,2,),的数值表,34对于k=2列出f2(x2)的数值表,35,对于,k,=1,列出,f,1,(,x,1,),的数值表,35对于k=1列出f1(x1)的数值表,36,36,37,机器负荷分配问题,37 机器负荷分配问题,38,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,机器负荷分配问题,39 构造动态规划模型如下：阶段k：运行年份,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,机器负荷分配问题,40递推方程：fk(xk)=maxvk(xk,dk)+fk,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,机器负荷分配问题,41f5(x5)=max8d5+5(x5-d5)+f6(x,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,机器负荷分配问题,42f3(x3)=max8d3+5(x3-d3)+f4(x,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,机器负荷分配问题,43f2(x2)=max8d2+5(x2-d2)+f3(x,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,机器负荷分配问题,44f1(x1)=max8d1+5(x1-d1)+f2(x,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,机器负荷分配问题,45由此可以得到：机器负荷分配问题,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,)=567,d,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,机器负荷分配问题,46每年投入高负荷运行的机器数以每年初完好的机器数为：机器,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,满足,:,机器负荷分配问题,47 在这个例子中，状态变量的终端值x6是未加约束的，,48,则从,1,t,-1,年，年初将全部完好机器投入低负荷运行，从,t,n,年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。,机器负荷分配问题,48则从1t-1年，年初将全部完好机器投入低负荷运行，从t,49,设 备 更 新 问 题,49设 备 更 新 问 题,50,一台设备的价格为,P,，运行寿命为,n,年，每年的维修费用是设备役龄的函数，记为,C,(,t,),，新设备的役龄为,t,=0,。旧设备出售的价格是设备役龄的函数，记为,S,(,t,),。在,n,年末，役龄为,t,的设备残值为,R,(,t,),。现有一台役龄为,T,的设备，在使用过程中，使用者每年都面临,“,继续使用,”,或,“,更新,”,的策略，,设 备 更 新 问 题,50 一台设备的价格为P，运行寿命为n年，每年的维,51,51,52,设 备 更 新 问 题,52设 备 更 新 问 题,53,例,5.10,：设具体数据如下：,设 备 更 新 问 题,53例5.10：设具体数据如下：设 备 更 新 问 题,54,54,55,55,56,56,57,57,58,58,59,59,60,60,61,61,62,97,6297,63,由以上计算可知，本问题有两个决策，它们对应的最小费用都是,115,。,这两个决策是,设 备 更 新 问 题,63 由以上计算可知，本问题有两个决策，它们对应的最小,
展开阅读全文