第四节-连续型动态规划问题

资源分配问题（连续型）：设备负荷分配问题例某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？解：这是一个以时间为特征的多阶段决策问题。第1年第2年第3年第4年5001s投x1辆超负荷车状态2s1122.09.0xss2232.09.0xss3342.09.0xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg投x2辆超负荷车投x3辆超负荷车投x4辆超负荷车第5年投x4辆超负荷车)(55xg状态状态6s4452.09.0xss阶段：将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5状态变量：第k阶段初完好卡车数量，其中ks.5001s决策变量：表示第k阶段分配给超负荷运输的卡车数量。kx显然，分配给低负荷的卡车数为kkxs))(1.01()3.01(1kkkkxsxskkxs2.09.0注：这里视，为连续变量。若=0.6表示有一辆卡车在第k年度有60℅的时间处于完好状态。=0.7表示有一辆卡车在第k年度有70℅时间在超负荷运输等等。kskxkskx状态转移方程：))(1.01()3.01(1kkkkxsxskkxs2.09.05,4,3,2,1k阶段指标函数：表示第k年度利润。)(kkxg5,4,3,2,1k)(1625)(kkkkkxsxxgkkxs9165,4,3,2,1k最优指标函数：第k年度初完好车辆数为时，采用最优策略到第5年末所产生的最大利润。)(kksfks逆序递推式为：0)(1,2,3,4,5)()(max)(66110sfksfxgsfkkkksxkkkk1）k=5时)}()({max)(665505555sfxgsfsx（注意到此时=0）)(66sf)}({max55055xgsx}916{max55055xssx}916{max)(5505555xssfsx5f5x5s516so55525916sss5*5sx此时2）k=4时)}()({max)(554404444sfxgsfsx}25916{max544044sxssx)}2.09.0(25916{max4444044xsxssx}45.38{max44044xssx同理，只有当44sx时，函数4445.38xs才能达到极大值。故有4*4sx4445.42)(ssf3）k=3时)}()({max)(443303333sfxgsfsx}5.42916{max433033sxssx)}2.09.0(5.42916{max3333033xsxssx}5.025.54{max33033xssx不难得到3*3sx33375.54)(ssf4）k=2时)}()({max)(332202222sfxgsfsx)}2.09.0(75.54916{max2222022xsxssx}95.1275.65{max22022xssx2f2x247.33s2275.65so可见，只有当02x时，函数2295.1275.65xs才能达到极大值。故有,0*2x222275.65)(ssf33375.54)(ssf5）k=1时)}()({max)500()(2211011111sfxgfsfsx}275.65916{max21150001sxsx)}2.09.0(275.65916{max111150001xsxsx}055.47475.74{max1150001xsx同理，只有当时，函数,0*1x75.373735007475.747475.74)(111ssf01x11055.47475.74xs才能达到极大值。故有（万元）所对应的最优策略分别为：01x时，由状态转移方程kkkxss2.09.014505009.02.09.0112xss由,0*2x且4054509.02.09.0223xss再由3*3sx且5.2834052.04059.02.09.0334xss4*4sx45.1985.2832.05.2839.02.09.0445xss5*5sx15.13845.1982.045.1989.02.09.0556xss第一年初：500辆车全部用于低负荷运输。第二年初：还有450辆完好的车，也全部用于低负荷运输。第三年初：还有405辆完好的车，全部用于超负荷运输。第四年初：还有238.5辆完好的车，全部用于超负荷运输。第五年初：还有198.45辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。实现最大利润74.3)(11sf（亿元）思考：某公司有1000辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆在两种不同的负荷下运输的卡车数量，使在第5年年末剩余的完好卡车数量为500台，并且使在5年内的总利润最大？第1年第2年第3年第4年10001s投x1辆超负荷车状态2s1122.09.0xss2232.09.0xss3342.09.0xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg投x2辆超负荷车投x3辆超负荷车投x4辆超负荷车第5年投x4辆超负荷车)(55xg状态状态5006s4452.09.0xss))(1.01()3.01(1kkkkxsxskkxs2.09.0)(1625)(kkkkkxsxxgkkxs9165,4,3,2,1k第1年第2年第3年第4年10001s投x1辆超负荷车状态2s1122.09.0xss2232.09.0xss3342.09.0xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg投x2辆超负荷车投x3辆超负荷车投x4辆超负荷车第5年投x5辆超负荷车)(55xg状态状态5006s4452.09.0xss逆序递推式为：0)(1,2,3,4,5)()(max)(66110sfksfxgsfkkkksxkkkk第1年第2年第3年第4年10001s投x1辆超负荷车状态2s1122.09.0xss2232.09.0xss3342.09.0xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg投x2辆超负荷车投x3辆超负荷车投x4辆超负荷车第5年投x4辆超负荷车)(55xg状态状态5006s4452.09.0xss1）k=5时)}()({max)(665505555sfxgsfsx（注意到此时=0）)(66sf)}({max55055xgsx}916{max55055xssx5002.09.0556xss25005.455sx225005.56}916{max55525005.455sxssx25005.45*5sx2）k=4时)}()({max)(554404444sfxgsfsx}225005.56916{max544044sxssx}22500)2.09.0(5.56916{max4444044xsxssx}225003.285.66{max44044xssx2250085.664s0*4x2250085.66)(444ssf3）k=3时)}()({max)(443303333sfxgsfsx}2250085.66916{max433033sxssx}22500)2.09.0(85.66916{max3333033xsxssx}2250037.4165.76{max33033xssx不难得到0*3x22500165.76)(333ssf4）k=2时)}()({max)(332202222sfxgsfsx}22500)2.09.0(165.76916{max2222022xsxssx}22500233.65485.84{max22022xssx,0*2x225005485.84)(222ssf5）k=1时)}()({max)1000()(2211011111sfxgfsfsx}225005485.84916{max211100001sxsx}22500)2.09.0(5485.84916{max1111100001xsxsx}225009097.709365.76{max11100001xsx,0*1x65.5359322500100009365.762250009365.76)(111ssf（万元）01x时，由状态转移方程kkkxss2.09.0190010009.02.09.0112xss由,0*2x且8109009.02.09.0223xss再由3*3sx且5678102.08109.02.09.0334xss4*4sx9.3965672.05679.02.09.0445xss25005.45*5sx50079.14221.357)250005.1786(2.021.357)25009.3965.4(2.09.3969.02.09.0556xss第一年初：1000辆车全部用于低负荷运输。第二年初：还有900辆完好的车，也全部用于低负荷运输。第三年初：还有810辆完好的车，全部用于超负荷运输。第四年初：还有567辆完好的车，全部用于超负荷运输。第五年初：还有396.9辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余500辆完好的车。实现最大利润65.53593)(11sf（万元）背包问题一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为a(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量的函数（i=1，2，…n）.问旅行者应如何选择携带物品的件数，以使总价值最大？ia)(iixgix此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：设为第i种物品装入的件数，则背包问题可归结为如下形式的整数规划模型：ixniiixgz1)(max),,2,101nixaxainiii（整数下面从一个例子来分析动态规划建模。例有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？货物编号i123单位重量（t）345单位价值ci456设第种货物装载的件数为ix),3,2,1(ii则问题可表为：321654maxxxxz)3,2,1(,010543321ixxxxi整数阶段k:将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.状态变量：在第k段开始时，背包中允许装入前k种物品的总重量。1ks决策变量：装入第k种物品的件数。kx状