第四节-连续型动态规划问题优秀课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,资源分配问题,（连续型）,：,设备负荷分配问题,例,某公司有,500,辆运输卡车，在超负荷运输（即每天满载行,驶,500km,以上）情况下，年利润为,25,万元,/,辆，这时卡车的年,损坏率为,0.3,；在低负荷下运输（即每天行驶,300km,以下）情,况下，年利润为,16,万元,/,辆。年损坏率为,0.1,。现要制定一个,5,年计划，问每年年初应如何分配完好车辆，在两种不同的负荷,下运输的卡车数量，使在,5,年内的总利润最大？,解：这是一个以时间为特征的多阶段决策问题。,1,第,1,年,第,2,年,第,3,年,第,4,年,投,x,1,辆超负荷车,状态,状态,状态,投,x,2,辆超负荷车,投,x,3,辆超负荷车,投,x,4,辆超负荷车,第,5,年,投,x,4,辆超负荷车,状态,状态,阶段：将,5,年运输计划看成,5,个阶段的决策问题。,k=1,2,3,4,5,状态变量 ：第,k,阶段初完好卡车数量，其中,决策变量 ：表示第,k,阶段分配给超负荷运输的卡车数量。,显然，分配给低负荷的卡车数为,2,注：,这里视 ，为连续变量。若,=0.6,表示有一辆卡,车在第,k,年度有,60,的时间处于完好状态。,=0.7,表示有,一辆卡车在第,k,年度有,70,时间在超负荷运输等等。,状态转移方程：,阶段指标函数 ：表示第,k,年度利润。,3,最优指标函数 ：第,k,年度初完好车辆数为 时，采,用最优策略到第,5,年末所产生的最大利润。,逆序递推式为：,1,）,k=5,时,（注意到此时,=0,）,4,此时,2,）,k=4,时,同理，只有当,时，函数,5,才能达到极大值。故有,3,）,k=3,时,不难得到,6,4,）,k=2,时,可见，只有当,时，函数,才能达到,极大值。故有,7,5,）,k=1,时,同理，只有当,时，函数,才能达到,极大值。故有,（万元）,所对应的最优策略分别为：,8,时，由状态转移方程,由,且,再由,且,9,第一年初：,500,辆车全部用于低负荷运输。,第二年初：还有,450,辆完好的车，也全部用于低负荷运输。,第三年初：还有,405,辆完好的车，全部用于超负荷运输。,第四年初：还有,238.5,辆完好的车，全部用于超负荷运输。,第五年初：还有,198.45,辆完好的车，全部用于超负荷运输。,到第五年末，即第六年初，还剩余,138.15,辆完好的车。,实现最大利润,（亿元）,10,思考：某公司有,1000,辆运输卡车，在超负荷运输（即每天,满载行驶,500km,以上）情况下，年利润为,25,万元,/,辆，这时,卡车的年损坏率为,0.3,；在低负荷下运输（即每天行驶,300km,以下）情况下，年利润为,16,万元,/,辆。年损坏率为,0.1,。现要制定一个,5,年计划，问每年年初应如何分配完好车,辆在两种不同的负荷下运输的卡车数量，使在第,5,年年末,剩余的完好卡车数量为,500,台，并且使在,5,年内的总利润最,大？,11,第,1,年,第,2,年,第,3,年,第,4,年,投,x,1,辆超负荷车,状态,状态,状态,投,x,2,辆超负荷车,投,x,3,辆超负荷车,投,x,4,辆超负荷车,第,5,年,投,x,4,辆超负荷车,状态,状态,12,第,1,年,第,2,年,第,3,年,第,4,年,投,x,1,辆超负荷车,状态,状态,状态,投,x,2,辆超负荷车,投,x,3,辆超负荷车,投,x,4,辆超负荷车,第,5,年,投,x,5,辆超负荷车,状态,状态,逆序递推式为：,13,第,1,年,第,2,年,第,3,年,第,4,年,投,x,1,辆超负荷车,状态,状态,状态,投,x,2,辆超负荷车,投,x,3,辆超负荷车,投,x,4,辆超负荷车,第,5,年,投,x,4,辆超负荷车,状态,状态,1,）,k=5,时,（注意到此时,=0,）,14,2,）,k=4,时,15,3,）,k=3,时,不难得到,16,4,）,k=2,时,17,5,）,k=1,时,（万元）,18,时，由状态转移方程,由,且,再由,且,19,第一年初：,1000,辆车全部用于低负荷运输。,第二年初：还有,900,辆完好的车，也全部用于低负荷运输。,第三年初：还有,810,辆完好的车，全部用于超负荷运输。,第四年初：还有,567,辆完好的车，全部用于超负荷运输。,第五年初：还有,396.9,辆完好的车，全部用于超负荷运输。,到第五年末，即第六年初，还剩余,500,辆完好的车。,实现最大利润,（万元）,20,背 包 问 题,一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为,a(,千克,),，现有,n,种物品可供他选择装入背包。第,i,种物品的单位重量为,(,千克,),，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数 （,i=1,，,2,，,n,）,.,问旅行者应如何选择携带物品的件数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题,。,其数学模型为：,21,设 为第,i,种物品装入的件数，则背包问题可归结为如下形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例,有一辆最大货运量为,10 t,的卡车，用以装载,3,种,货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？,22,货物编号,i,1,2,3,单位重量（,t,）,3,4,5,单位价值,c,i,4,5,6,设第 种货物装载的件数为,则问题可表为：,阶段,k:,将可装入物品按,1,，,2,，,3,的顺序排序，每段装入一种物品，共划分,3,个阶段，即,k=1,2,3.,23,状态变量 ：在第,k,段开始时，背包中允许装入前,k,种,物品的总重量。,决策变量 ：装入第,k,种物品的件数。,状态转移方程：,最优指标函数,：在背包中允许装入物品的总重量不超过,t,，采取最优策略只装前,k,种物品时的最大使用价值,货物,1,货物,2,货物,3,24,由此可得动态规划的顺序递推方程为：,货物,1,货物,2,货物,3,K=1,时,25,货物,1,货物,2,货物,3,K=1,时,注意到：,例如：,时，,其它计算结果见下表：,26,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,27,货物,1,货物,2,货物,3,K=2,时,其中,例如：,时，,28,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,29,其它计算结果见下表：,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,30,货物,1,货物,2,货物,3,K=3,时,31,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,32,从,再由状态转移方程,货物,1,货物,2,货物,3,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,33,再由状态转移方程,最大装载价值为,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,34,总结：今后解背包问题应先从,k=3,入手：,k=3,时,下面应有重点地从,k=2,中求解三个最优函数值：,35,K=2,时,36,所以从第一阶段应有重点地求以下四个数：,K=1,时,37,由此逐一逆推代回上式：,38,由此逐一逆推代回上式：,39,由此逐一逆推代回上式：,40,最后,最优策略：,再由状态转移方程,再由状态转移方程,最大装载价值为,41,用动态规划方法求解：,解：我们用背包问题顺序解的思路：,人为的划分三个阶段：,k=1,2,3,阶段指标函数及其他分配情况如下图,：,1,2,3,42,1,2,3,动态规划的顺序递推方程为：,43,1,2,3,44,45,1,2,3,46,47,48,49,50,最优决策为,所对应的最优解为,51,例（,二维背包,）有一辆最大货运量为,13t,、最大容量为,10,件的卡车，用以装载,3,种货物，每种货物的单位重量及相,应单位价值如下表所示。应如何装载可使总价值最大？,货物编号,i,1,2,3,单位重量（,t,）,1,3,6,单位价值,c,i,4,5,8,解：设装载第,i,种货物的件数为 （,i=1,2,3,），则问题可表述为,52,1,2,3,关于件数的约束,:,关于重量的约束,:,基本方程式：,53,1,2,3,54,问题就是求：,1,2,3,55,56,57,1,2,3,58,同理可求得,59,60,所以最优决策方案为：,最优装载价值为：,61,1,、动态规划与静态规划,动态规划研究的,“,多阶段决策问题,”,基本上都和时间有关，所得的决策序列是在变化的状态中迭代产生的，故有,“,动态,”,的含义。,而一般的线性规划和非线性规划所研究的问题，通常都与时间无关，故又称为,“,静态,”,规划。,7.,4,连续型动态规划问题,62,例、用动态规划方法求解下面的问题,但对某些,“,静态,”,问题，可以人为地引入时间因素，把它变成一个多阶段决策问题，从而用动态规划的方法加以解决。,63,分析,1,、阶段,可把对三个变量最优值的确定过程分别作为第一、二、三阶段,3,、状态变量：,、决策变量：,4,、状态转移方程,64,5,、最优值函数及递推关系,65,解 用逆序法,设 ，则,66,故 是 的极大值点，从而可得,67,同样，由微分法可得，,当 时，,于是，该问题的最优值为,最优解为,68,练习,1,用动态规划方法求解下面的问题,答案：,69,2,、逆序法与顺序法,逆序法与顺序法的主要区别有如下几点：,方向不同,一个是从 向 逆推，一个是从 向 顺推,状态变量的意义不同,逆推法，表示第,k,阶段,初,的状态；,顺推法，表示第,k,阶段,末,的状态,70,已知条件不同,逆推法已知的是第一阶段初的状态 ，,顺推法已知的是第,n,阶段末的状态 ,状态转移方程不同,逆推法,顺推法,71,例,2,、用,顺推法,求解下面的问题,72,分析,1,、阶段的划分同逆推法,把对三个变量最优值的确定过程分别作为第一、二、三阶段,3,、状态变量：,、决策变量：,4,、状态转移方程,73,5,、最优值函数及递推关系,74,解 用,“,顺序法,”,75,练习,2,用动态规划的,顺推法,求解下面的问题,答案：,76,