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

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