《第四节-连续型动态规划问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四节-连续型动态规划问题优秀课件.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、资源分配问题资源分配问题（连续型）：设备负荷分配问题设备负荷分配问题例例 某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？解：这是一个以时间为特征的多阶段决策问题。1第1年第2年第3年第4年投 x1辆 超负荷车状态状态状态投 x2辆 超负荷车投 x3辆 超负荷车投 x4辆 超负荷车第5年投 x4辆 超负荷车状态状态阶段
2、：将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、=3 时不难得到64）k=2 时可见，只有当时，函数才能达到极大值。故有75）k=1 时同理，只有当时，函数才能达到极大值。故有（万元）所对应的最优策略分别为：8时，由状态转移方程由且再由且9第一年初：500辆车全部用于低负荷运输。第二年初：还有450辆完好的车，也全部用于低负荷运输。第三年初：还有405辆完好的车，全部用于超负荷运输。第四年初：还有238.5辆完好的车，全部用于超负荷运输。第五年初：还有198.45辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。实现最大利润（亿元）10思考：某公司有1000辆运输卡车，在超负荷运输（即每天满载行驶500k
4、m以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆在两种不同的负荷下运输的卡车数量，使在第5年年末剩余的完好卡车数量为500台，并且使在5年内的总利润最大？11第1年第2年第3年第4年投 x1辆 超负荷车状态状态状态投 x2辆 超负荷车投 x3辆 超负荷车投 x4辆 超负荷车第5年投 x4辆 超负荷车状态状态12第1年第2年第3年第4年投 x1辆 超负荷车状态状态状态投 x2辆 超负荷车投 x3辆 超负荷车投 x4辆 超负荷车第5年投 x5
5、辆 超负荷车状态状态逆序递推式为：13第1年第2年第3年第4年投 x1辆 超负荷车状态状态状态投 x2辆 超负荷车投 x3辆 超负荷车投 x4辆 超负荷车第5年投 x4辆 超负荷车状态状态1）k=5时（注意到此时 =0）142）k=4 时153）k=3 时不难得到164）k=2 时175）k=1 时（万元）18时，由状态转移方程由且再由且19第一年初：1000辆车全部用于低负荷运输。第二年初：还有900辆完好的车，也全部用于低负荷运输。第三年初：还有810辆完好的车，全部用于超负荷运输。第四年初：还有567辆完好的车，全部用于超负荷运输。第五年初：还有396.9辆完好的车，全部用于超负荷运输。
6、到第五年末，即第六年初，还剩余500辆完好的车。实现最大利润（万元）20背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为a(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为 (千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数 （i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：21设 为第 i 种物品装入的件数，则背包问题可归结为如下形式的整数规划模型：下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为10 t 的卡车，用以装
7、载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？22货物编号i 1 2 3单位重量（t）3 4 5单位价值 ci 4 5 6设第 种货物装载的件数为 则问题可表为：阶段阶段k:将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.23状态变量 ：在第k段开始时，背包中允许装入前k种物品的总重量。决策变量 ：装入第k种物品的件数。状态转移方程：状态转移方程：最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超过 t，采取最优策略只装前k种物品时的最大使用价值货物1货物2货物324由此可得动态规划的顺序递推方程为：货物1货
8、物2货物3K=1 时25货物1货物2货物3K=1 时注意到：例如：时，其它计算结果见下表：260 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 42 24 40 40 41 41 42 24 40 40 41 41 42 24 40 40 41 41 42 42 43 34 40 40 41 41 42 42 43 300044488812120001112223327货物1货物2货物3K=2 时其中例如：时，280 1 2 3
9、0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 42 24 40 40 41 41 42 24 40 40 41 41 42 24 40 40 41 41 42 42 43 34 40 40 41 41 42 42 43 300044488812120001112223329其它计算结果见下表：0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 05 50 00 05 50 00 0 5 50 04 4 5 50 04 45
10、 50 04 4 5 51 10 0 5 50 08 8 5 51 10 05 50 08 8 5 51 14 45 50 08 8 5 51 14 45 50 01212 5 51 14 45 50 012 512 51 18 58 52 20 0 00044589912130000010110130货物1货物2货物3K=3 时31 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 05 50 00 05 50 00 0 5 50 04 4 5 50 04 45 50 04 4 5 51 10 0 5 50 08 8 5 51 10 05 50 08 8 5 51 14
11、 45 50 08 8 5 51 14 45 50 01212 5 51 14 45 50 012 512 51 18 58 52 20 0 00044589912130000010110132从从再由状态转移方程再由状态转移方程货物1货物2货物3 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 05 50 00 05 50 00 0 5 50 04 4 5 50 04 45 50 04 4 5 51 10 0 5 50 08 8 5 51 10 05 50 08 8 5 51 14 45 50 08 8 5 51 14 45 50 01212 5 51 14 45 5
12、0 012 512 51 18 58 52 20 0 00044589912130000010110133再由状态转移方程再由状态转移方程最大装载价值为最大装载价值为 0 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 40 0 4 41 1 4 42 24 40 40 41 41 42 24 40 40 41 41 42 24 40 40 41 41 42 42 43 34 40 40 41 41 42 42 43 300044488812120001112
13、223334总结：今后解背包问题应先从总结：今后解背包问题应先从k=3入手：入手：k=3时时 下面应有重点地从下面应有重点地从k=2中求解三个最优函数值：中求解三个最优函数值：35K=2 时时36所以从第一阶段应有重点地求以下四个数：所以从第一阶段应有重点地求以下四个数：K=1 时时37由此逐一逆推代回上式：由此逐一逆推代回上式：38由此逐一逆推代回上式：由此逐一逆推代回上式：39由此逐一逆推代回上式：由此逐一逆推代回上式：40最后最后最优策略：最优策略：再由状态转移方程再由状态转移方程再由状态转移方程再由状态转移方程最大装载价值为最大装载价值为 41用动态规划方法求解：用动态规划方法求解：解
14、：我们用背包问题顺序解的思路：解：我们用背包问题顺序解的思路：人为的划分三个阶段：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图阶段指标函数及其他分配情况如下图：12342123动态规划的顺序递推方程为：4312344451234647484950最优决策为所对应的最优解为51例（二维背包）有一辆最大货运量为13t、最大容量为10件的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？货物编号i 1 2 3单位重量（t）1 3 6单位价值 ci 4 5 8解：设装载第i种货物的件数为 （i=1,2,3），则问题可表述为52123关于
15、件数的约束:关于重量的约束:基本方程式：5312354问题就是求：12355565712358同理可求得 5960所以最优决策方案为：最优装载价值为：611、动态规划与静态规划 动态规划研究的“多阶段决策问题”基本上都和时间有关，所得的决策序列是在变化的状态中迭代产生的，故有“动态”的含义。而一般的线性规划和非线性规划所研究的问题，通常都与时间无关，故又称为“静态”规划。7.4 连续型动态规划问题62例、用动态规划方法求解下面的问题 但对某些“静态”问题，可以人为地引入时间因素，把它变成一个多阶段决策问题，从而用动态规划的方法加以解决。63分析1、阶段 可把对三个变量最优值的确定过程分别作为第
16、一、二、三阶段3、状态变量：、决策变量：4、状态转移方程645、最优值函数及递推关系65解 用逆序法设 ，则66故 是 的极大值点，从而可得67同样，由微分法可得，当 时，于是，该问题的最优值为最优解为68练习1 用动态规划方法求解下面的问题答案：692、逆序法与顺序法逆序法与顺序法的主要区别有如下几点：方向不同一个是从 向 逆推，一个是从 向 顺推 状态变量的意义不同逆推法，表示第k阶段初的状态；顺推法，表示第k阶段末的状态70 已知条件不同逆推法已知的是第一阶段初的状态 ，顺推法已知的是第n阶段末的状态 状态转移方程不同逆推法 顺推法71例2、用顺推法求解下面的问题72分析1、阶段的划分同逆推法 把对三个变量最优值的确定过程分别作为第一、二、三阶段3、状态变量：、决策变量：4、状态转移方程735、最优值函数及递推关系74解 用“顺序法”75练习2 用动态规划的顺推法求解下面的问题答案：76