《运筹》教学课件动态规划-应用举例(仅供参考)VIP

8.5动态规划应用举例(此内容仅供学有余力的学生参考）,8.5.1离散动态规划问题,投资额,收益,工厂,例1（资源分配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：,问：对三个工厂如何分配，才能使总收益达到最大？,状态变量sk：,阶段k=1，2，3,决策变量uk：,给工厂k的投资额,在第k阶段时可供工厂k到工厂3分配的资金数,状态转移方程：,sk+1=sk-uk,gk(uk)=给工厂k投资uk（十万元）的收益,指标函数Vk,n,fk（sk）,投资工厂k至工厂3所得的最大总收益,求f1（5）,=在工厂k，可供分配的资金数为sk时，,基本方程：,k=3,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,投资额,收益,工厂,k=2,0,0,0,0,1,0,2,3,0123,8,9,9.5,7.5,2,9.5,4,5,投资额,收益,工厂,sk+1=sk-uk,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,k=1,sk+1=sk-uk,投资额,收益,工厂,5,16,012345,12,1,17,最大总收益：,最优策略：,0,0,0,0,1,0,2,3,0123,8,9,9.5,7.5,2,9.5,4,5,购买新机器的费用机器用了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年内的更新决策，使总收益最大(单位：千元）。,r(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),当k=5时，,1234,3.5,3,3.5,r(0),-v(0),-c(sk),r(sk),-v(sk),效益r(t),维修费v(t),更新费c(t),当k=4时，,1234,3.5,3,3.5,123,6,6.5,6.5,4.5,5.8,5.8,3.25,5.5,5.5,r(0),-v(0),-c(sk),r(sk),-v(sk),效益r(t),维修费v(t),更新费c(t),当k=3时，,123,6,6.5,6.5,4.5,5.8,5.8,3.25,5.5,5.5,12,9.3,9.5,9.5,8,8.8,8.8,r(0),-v(0),-c(sk),r(sk),-v(sk),效益r(t),维修费v(t),更新费c(t),当k=2时，,12,9.3,9.5,9.5,8,8.8,8.8,1,12.3,12.5,12.5,当k=1时，,12,9.3,9.5,9.5,8,8.8,8.8,1,12.3,12.5,12.5,123,6,6.5,6.5,4.5,5.8,5.8,3.25,5.5,5.5,1234,3.5,3,3.5,uk,第k年更新,第k年不更新,8.5.2连续动态规划问题,例3（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数）,方案1：,255220240200255,总费用：,255245245245255,方案2：,总费用：,+200102+200025+20005+200045=190000,200102,解：,阶段1,，状态变量sk第k-1季度聘用人数,决策变量uk第k季度聘用人数,状态转移方程：,sk+1=uk,fk（sk）=第k-1季度聘用人数为sk人时，第k季度到第4季度的最小总费用,220s2255,gkuk255,季度i春夏秋冬春,需用量gk255220240200255,2,3,4,k=1,2,34,s1=255,240s3255,200s4255,已知：每季节超过需用量聘用，每人浪费2000元，聘用和解聘费为200元乘上两个季节聘用人数之差的平方,=min,+fk+1（sk+1）,+2000(ukgk),gkuk255,200(ukuk-1)2,求f1（255）,=min,+fk+1（uk）,+2000(ukgk),gkuk255,200(uksk)2,基本方程：,fk（sk）=,min,+fk+1（uk）,f5（s5）=0,求f1（255）,+2000(ukgk),gkuk255,200(uksk)2,min,f4（s4）=,+2000(u4g4),g4u4255,200(u4s4)2,u*4=255,=200(255s4)2,200s4255,当k=4时,min,f3（s3）=,+f4（u3）,+2000(u3g3),200(u3s3)2,g3u3255,=min,+2000(u3200),200(u3s3)2,200u3255,+200(255u3)2,当k=3时,240s3255,k=4,3,2,1,f3（s3）,=min,+2000(u3200),200(u3s3)2,200u3255,+200(255u3)2,所以f3（s3）=,当k=3时,240s3255,min,min,f2（s2）=,+f3（u2）,+2000(u2g2),200(u2s2)2,g2u2255,fk（sk）=,+fk+1（uk）,+2000(ukgk),gkuk255,200(uksk)2,已知：,f3（s3）,当k=2时,220s2255,=min,+2000(u2240),200(u2s2)2,240u2255,+f3（u2）,=min,240u2255,状态转移方程：,sk+1=uk,f2（s2）,当k=2时,220s2255,=min,240u2255,所以f2（s2）=,min,fk（sk）=,+fk+1（uk）,+2000(ukgk),gkuk255,200(uksk)2,已知：,f2（s2）,当k=1时,，s1=255,min,f1（255）=,+f2（u1）,+2000(u1g1),g1u1255,200(u1s1)2,=min,+2000(u1220),220u1255,200(u1255)2,状态转移方程：,sk+1=uk,f1（255）=185000,f4（s4）=,u*4=255,200(255s4)2,f2（s2）,f1（255）=185000,最优策略：,=245,=247.5,u*4=255,最少总费用：为185000元,状态转移方程：,sk+1=uk,最佳聘用方案：,夏季247.5人，秋季245人，冬季247.5人，春季255人时，,例4(采购与销售问题)某商店在未来的四个月里，准备利用商店的一个仓库来专门经销某种商品，仓库最大容量为这种商品1000单位。假定商店每月只能卖出仓库现有的货物。当商店在某月购货时，下月初才能到货。预测该商店未来四个月的买卖价格如下表，假定商店在1月开始经销时，仓库贮有该商品500单位，试问，如何制定这四个月的订购与销售计划，使获利最大（不计库存费）。,月份（k）,购买单价（ck）,销售单价（pk）,解：,k=1，2，3，4,状态变量sk,xk第k月卖出的货物数量,yk第k月订购的货物数量,状态转移方程：,sk+1=sk+yk-xk,fk（sk）=第k月初库存为时sk，从第k月到第4月末所获得的最大利润,pkxk,+fk+1（sk+1）,0xksk,，求f1（500）,-ckyk,0yk1000-(sk-xk),已知：仓库最大容量为1000单位。商店每月只卖出仓库现有的货物。当商店在某月购货时，下月初才能到货。1月开始经销时，仓库贮有该商品500单位，如何制定四个月的订购与销售计划，使获利最大（不计库存费）。,第k月的购买单价ck,，销售单价pk，,=max,0xksk,0yk1000-(sk-xk),（sk+ykxk）,s1=500,0sk1000,k=2，3，4,决策变量：,第k个月的库存量（含上月的定货）,基本方程：,f5（s5）=0,求f1（500）,k=4，3，2，1,f4（s4）=,=p4s4,=17s4,x*4=s4,y*4=0,当k=4时,当k=3时,f3（s3）=,0s41000,0s31000,当k=3时,f3（s3）=,求maxZ=-4x3+6y3+17s3,0x3s3,0y31000-(s3x3),取Z=-4x3+6y3+17s3,x3s3,-x3+y31000-s3,x3,y30,求maxZ=-4x3+6y3+17s3,0s31000,x*3=s3,y*3=1000,=6000+13s3,x3+x1=s3,-x3+y3+x2=1000-s3,maxZ=-4x3+6y3+17s3,x1,x2,x3,y30,x*3=s3,y*3=1000,最优值Z=6000+13s3,x3s3,-x3+y31000-s3,x3,y30,求maxZ=-4x3+6y3+17s3,标准型：,最优解：,f3（s3）=,x*3=s3,，y*3=1000,6000+13s3,当k=2时,f2（s2）=,0s21000,x*2=0,=11000+8s2,当k=1时,f1（s1）=,s1=500,x*1=500,=17000,，y*1=0,f2（s2）=,x*2=0,11000+8s2,=max4x1,0x1500,-2y1,0y1+x1500,+15000,.,.,.,f1（500）=17000,x*1=500,，y*1=0,f2（s2）=,x*2=0,11000+8s2,，y*2=1000,-s2,f3（s3）=,x*3=s3,，y*3=1000,6000+13s3,f4（s4）=,17s4,x*4=s4,，y*4=0,xk第k月卖出的货物数量,yk第k月订购的货物数量,sk+1=sk+yk-xk,fk（sk）=第k月初库存为时sk，从第k月到第4月末所获得的最大利润,结论：当第1个月初库存为时500时，4个月能获得的最大利润为17000,四个月的订购与销售计划：,第1个月：卖出500个，订购0个,第2个月：卖出0个，订购1000个,第3个月：卖出1000个，订购1000个,第4个月：卖出1000个，订购0个,作业：,1、某公司销售部经理需决定如何在三个地区部署4名推销员。各地区推销员人数与销