8.5.1 离散动态规划问题投资额收益工厂 12314.525274.57397.58410.511105121513例1（资源分配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：问：对三个工厂如何分配，才能使总收益达到最大？状态变量sk：阶段k=1，2，3决策变量uk：给工厂k的投资额在第k阶段时可供工厂k到工厂3分配的资金数状态转移方程：sk+1 = sk -ukg k (uk)=给工厂k投资 uk（十万元）的收益指标函数Vk,nfk（ sk ）投资工厂k至工厂3所得的最大总收益求f1（ 5 ）=在工厂k，可供分配的资金数为sk时，基本方程：k=3001122330 57845451013投资额收益工厂 12314.525274.57397.58410.511105121513012345k=200001020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 1212.514.5 1615416投资额收益工厂 12314.525274.57397.58410.511105121513sk+1 = sk -uk001122330 57845451013012345k=1sk+1 = sk -uk投资额收益工厂 12314.525274.57397.58410.511105121513516 0 1 2 3 4 517 16.5 16 15.5 12117最大总收益：最优策略：00001020 15 2050 1 27 7 4.50或1730 1 2 38 9 9.5 7.529.5450 1 2 3 4 10 10 11.512.511312.50 1 2 3 4 513 1212.514.5 1615416购买新机器的费用机器用了t年后的折旧费例2（设备更新问题）问题的提出：已知一台设备已使用了t年，再使用一年的效益为r(t)，维修费为v(t),若在第t+1年更新，则更新费为c(t),现要做一个n年的设备更新计划：每年年初做出决策，是继续使用旧机器还是更换一台新机器，使n年的总收益最大阶段k=1,2, ,n决策变量uk第k年更新状态变量sk=第k年初,机器已使用过的年限第k年不更新状态转移方程：1第k年的收益：r(0)-v(0) -c(sk)r(sk)-v(sk)建模：阶段k=1,2, ,n决策变量uk第k年更新状态变量sk=第k年初,机器已使用过的年限第k年不更新状态转移方程：1第k年的收益：r(0) -v(0) -c(sk)r(sk) -v(sk)基本方程：例 设某台新设备的年收益及年平均维修费、更新费 如下表所示，试作今后5年内的更新决策，使总收 益最大(单位：千元）。使用年限t效益r(t)维修费v(t)更新费c(t)0 1 2 3 4 55 4.5 4 3.75 3 2.50.5 1 1.5 2 2.5 30.5 1.5 2.2 2.5 3 3.5r (0) -v (0) -c (sk)r (sk) -v (sk)基本方程：r (0) -v (0) -c (sk)r (sk) -v (sk)效益r(t)维修费v(t)更新费c(t)使用年限t01234554.543.7532.50.511.522.530.51.52.22.533.5当k=5时，1 2 3 4 3.5 33.52.5 2.32.51.27220.5 1.51.5r (0) -v (0) -c (sk)r (sk) -v (sk)效益r(t)维修费v(t)更新费c(t)使用年限t01234554.543.7532.50.511.522.530.51.52.22.533.5当k=4时，1 2 3 4 3.5 33.52.5 2.32.51.27220.5 1.51.51 2 366.56.54.55.85.83.25 5.55.5r (0) -v (0) -c (sk)r (sk) -v (sk)效益r(t)维修费v(t)更新费c(t)使用年限t01234554.543.7532.50.511.522.530.51.52.22.533.5当k=3时，1 2 366.56.54.55.85.83.25 5.55.51 29.3 9.59.588.88.8r (0) -v (0) -c (sk)r (sk) -v (sk)效益r(t)维修费v(t)更新费c(t)使用年限t01234554.543.7532.50.511.522.530.51.52.22.533.5当k=2时，1 29.3 9.59.588.88.81 12.3 12.512.5当k=1时，1 29.3 9.59.588.88.81 12.3 12.512.51 2 366.56.54.55.85.83.25 5.55.51 2 3 4 3.5 33.52.5 2.32.51.27220.5 1.51.5uk第k年更新第k年不更新8.5.2 连续动态规划问题例例3（季节工问题）某工厂的生产任务随季节波动，为降（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费每季节超过需用量聘用，每人浪费20002000元，聘用或解聘元，聘用或解聘费为费为200200元乘上两个季节聘用人数之差的平方，问厂长元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数）实际工作时间计算，则聘用人数可为分数）方案1： 255 220 240 200 255总费用：+200352200552+200202+200402=1249000255 245 245 245 255方案2：季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255总费用：+200102+200025+20005+200045=190000200102解：阶段1，状态变量sk第k-1季度聘用人数决策变量uk第k季度聘用人数状态转移方程： sk+1 = uk fk（sk）=第k-1季度聘用人数为sk人时，第k季度到 第4季度的最小总费用 ,220s2255gkuk255季度i 春 夏 秋 冬 春需用量gk 255 220 240 200 255234k=1,2,34s1=255,240s3255,200s4255已知：每季节超过需用量聘用，每人浪费2000元，聘用 和解聘费为200元乘上两个季节聘用人数之差的平方=min +fk+1（sk+1）+2000(uk gk)gkuk255200(uk uk-1)2求f1（255） =min +fk+1（uk）+2000(uk gk)gkuk255200(uk sk)2基本方程：fk（sk）=min +fk+1（uk）f5（s5）=0求f1（255）+2000(uk gk)gkuk255200(uk sk)2min f4（s4）=+2000(u4 g4)g4u4255200(u4 s4)2u*4=255=200(255 s4)2,200s4255当k=4时min f3（s3）=+f4（u3）+2000(u3 g3)200(u3 s3)2g3u3255=min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2当k=3时,240s3255k=4,3,2,1f3（s3） =min +2000(u3 200)200(u3 s3)2200u3255+200(255 u3)2所以f3（s3）=当k=3时,240s3255min min f2（s2）=+f3（u2）+2000(u2 g2)200(u2 s2)2g2u2255fk（sk）=+fk+1（uk）+2000(uk gk)gkuk255200(uk sk)2已知：f3（s3）当k=2时,220s2255=min +2000(u2 240)200(u2 s2)2240u2255+f3（u2）=min 240u2255状态转移方程： sk+1 = uk f2（s2）当k=2时,220s2255=min 240u2255所以f2（s2）=min fk（sk）=+fk+1（uk）+2000(uk gk)gkuk255200(uk sk)2已知：f2（s2）当k=1时，s1=255min f1（255）=+f2（u1）+2000(u1 g1)g1u1255200(u1 s1)2=min +2000(u1 220)220u1255200(u1 255)2状态转移方程： sk+1 = uk f1（255）=185000f4（s4）=u*4=255200(255 s4)2f2（s2）f1（255）=185000最优策略：=245=247.5u*4=255最少总费用：为185000元状态转移方程： sk+1 = uk 最佳聘用方案：夏季247.5人，秋季245人，冬季247.5人，春季255人时，例4 (采购与销售问题)某商店在未来的四个月里，准 备利用商店的一个仓库来专门经销某种商品，仓库 最大容量为这种商品1000单位。假定商店每月只能 卖出仓库现有的货物。当商店在某月购货时，下月 初才能到货。预测该商店未来四个月的买卖价格如 下表，假定商店在1月开始经销时，仓库贮有该商 品500单位，试问，如何制定这四个月的订购与销 售计划，使获利最大（不计库存费）。 1 10 12 2 8 9 3 11 13 4 15 17月份（k）购买单价 （ck）销售单价 （pk）解： k=1，2，3，4状态变量skxk第k月卖出的货物数量yk第k月订购的货物数量状态转移方程：sk+1 = sk + yk -xkfk（sk）=第k月初库存为时sk ， 从第k月到第4月末所获得的最大利润 pk xk+fk+1（sk+1）0xk sk ，求f1（500）-ck yk0yk 1000-(sk -xk )已知：仓库最大容量为1000单位。商店每月只卖出仓库 现有的货物。当商店在某月购货时，下月初才能到 货。 1月开始经销 时，仓库贮有该商品500单位，如何制定四个月的订 购与销售计划，使获利最大（不计库存费）。第k月的购买单价ck，销售单价pk，=max ,0xk sk ,0yk 1000-(sk -xk )（ sk + yk xk）s1=500 ,0sk1000 k=2，3，4决策变量：第k个月的库存量（含上月的定货）基本方程：f5（s5）=0求f1（500）fk（sk）= max pk xk 0xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)k=4，3，2，1f4（s4）=maxp4 x4 0x4 s4 -c4 y40y4 1000-(s4 x4 )=p4 s4=17 s4x*4= s4y*4= 0当k=4时当k=3时f3（s3）=maxp3 x3 0x3 s3 -c3 y30y3 1000-(s3 x3 )+f4 （s3+y3-x3)=max13 x3 0x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s3+y3-x3),0s41000 ,0s31000 当k=3时f3（s3）=max13 x3 0x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s3+y3-x3)=max-4 x3 0x3 s3 +6 y30y3 1000-(s3 x3 )+17 s3求maxZ=-4 x3+6 y3 +17s30x3 s3 0y3 1000-(s3 x3 )取Z=-4 x3+6 y3 +17s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3,0s31000 x*3= s3y*3=100 0=6000+13s3x3 + x1 =s3 - x3 +y3 + x2= 1000-s3 maxZ=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2-4 6 0 0Z- 17s3 x1 1 0 1 0s3x2-1 1 0 11000-s3x3 y3 x1 x22 0 0 -6Z-6000-11s3 x1 1 0 1 0s3y3-1 1 0 11000-s3x3 y3 x1 x20 0 -2 -6Z-6000-13s3 x3 1 0 1 0s3y3 0 1 1 11000x*3= s3y*3=100 0最优值 Z=6000+13s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3标准型：最优解：fk（sk）= max pk xk 0xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)f3（s3）=x*3= s3，y*3=100 06000+13s3当k=2时f2（s2）=maxp2 x2 0x2 s2 -c2 y20y2 1000-(s2 x2 )+f3 （s2+y2-x2),0s21000 =max9 x2 0x2 s2 -8 y20y2 1000-(s2 x2 )+6000+13 （s2+y2-x2)=max-4 x2 0x2 s2 +5 y20y2 1000-(s2 x2 )+13 s2+6000x*2= 0=11000+8s2，y*2=1000-s2fk（sk）= max pk xk 0xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)当k=1时f1（s1）=maxp1 x1 0x1 s1 -c1 y10y1 1000-(s1 x1 )+f2 （s1+y1-x1),s1=500 x*1= 500=17000，y*1=0f2（s2）=x*2= 011000+8s2，y*2=1000-s2=max12 x1 0x1 500 -10y10y1 1000-(500 x1 )+11000+8（500+y1-x1)=max4 x1 0x1 500 -2y10y1+ x1 500+15000.0.f1（500）=17000x*1= 500 ，y*1=0f2（s2）=x*2= 011000+8s2，y*2=1000-s2f3（s3）=x*3= s3，y*3=10006000+13s3f4（s4）= 17 s4x*4= s4，y*4= 0xk第k月卖出的货物数量yk第k月订购的货物数量sk+1 = sk + yk -xkfk（sk）=第k月初库存为时sk ， 从第k月到第4月末所获得的最大利润 结论：当第1个月初库存为时500时， 4个月能获得的最大利润为17000 四个月的订购与销售计划：第1个月：卖出500个，订购0个第2个月：卖出0个，订购1000个第3个月：卖出1000个，订购1000个第4个月：卖出1000个，订购0个作业：1、某公司销售部经理需决定如何在三个地区部署4名推销员。各地区推销员人数与销售额（按每日万元计）之间的关系如下表：0 1 2 3 4 A B C5 10 13 15 176 10 14 17 154 9 11 15 18地区人数（1）求销售额最大的推销员配制方案（2）若仅有3名推销员，试求最优配制方案答案（ 1）A地区1名，B地区2名，C地区1名， 销售额33万元（2）A地区1名，B地区1名，C地区1名， 销售额29万元2、 某公司有资金10万元，可投资于项目i（i=1,2,3),若投资项目i的金额为xi，其收益分别为g1 (x1)=4 x1, g2 (x2)=9 x2, g3 (x3)=2x32,问如何分配投资额，使总收益最大？最优策略：把所有资金分配给第3个项目