资源分配问题.pptx

1第五章 动态规划多阶段决策过程动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点2资资 源源 分分 配配 问问 题题3 例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题41.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0dkxk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)8.边界条件：f4(x4)=0资资 源源 分分 配配 问问 题题5k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3资资 源源 分分 配配 问问 题题6k=2，0d2x2，x3=x2-d2资资 源源 分分 配配 问问 题题7k=1，0d1x1，x2=x1-d1资资 源源 分分 配配 问问 题题8背 包 问 题9背 包 问 题10则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn为正整数1.阶 段k：第k次 装 载 第k种 物 品（k=1,2,n）2.状态变量xk：第k次装载时背包还可以装载的重量；3.决策变量dk：第k次装载第k种物品的件数；背 包 问 题114.决策允许集合：Dk(xk)=dk|0 dkxk/wk，dk为整数；5.状态转移方程：xk+1=xk-wkdk6.阶段指标：vk=ckdk7.递推方程 fk(xk)=maxckdk+fk+1(xk+1)=maxckdk+fk+1(xk-wkdk)8.终端条件：fn+1(xn+1)=0背 包 问 题12 例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解 f4(x4)=0 对于k=3背 包 问 题1314151617生生 产产 库库 存存 问问 题题18 例例5.95.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情 况如下表：生生 产产 库库 存存 问问 题题19w阶段k：月份，k=1,2,7,8；w状态变量xk：第k个月初（发货以前）的库存量；w决策变量dk：第k个月的生产量；w状态转移方程：xk+1=xk-rk+dk；w决策允许集合：wDk(xk)=dk|dk0,rk+1xk+1H =dk|dk0,rk+1xk-rk+dkH；w阶段指标：vk(xk,dk)=ckdk；w终端条件：f8(x8)=0,x8=0；生生 产产 库库 存存 问问 题题20递推方程：fk(xk)=minvk(xk,dk)+fk+1(xk+1)dkDk(xk)=minckdk+fk+1(xk-rk+dk)dkDk(xk)w对于k=7w因为 x8=0w有 d7=0w递推方程为wf7(x7)=minc7d7+f8(x8)=0 d7=0生生 产产 库库 存存 问问 题题21对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7)d6=11-x6=10d6=10(11-x6)=110-10 x6生生 产产 库库 存存 问问 题题22对于对于k k=5=5f f5 5(x x5 5)=min)=minc c5 5d d5 5+f f6 6(x x6 6)d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10+110-10 x x6 6 d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10(+110-10(x x5 5-r r5 5+d d5 5)d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10(+110-10(x x5 5-2+-2+d d5 5)d d5 5 D D5 5(x x5 5)=min10 =min10d d5 510-10 x x5 5+130+130 d d5 5 D D5 5(x x5 5)D D5 5(x x5 5)=)=d d5 5|d d5 5 0,0,r r6 6 x x5 5-r r5 5+d d5 5 H H =d d5 5|d d5 5 0,0,r r6 6+r r5 5-x x5 5 d d5 5 H H+r r5 5-x x5 5 =d d5 5|d d5 5 0,9-0,9-x x5 5 d d5 5 11-11-x x5 5 生生 产产 库库 存存 问问 题题23因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5|9-x5d511-x5递推方程成为f5(x5)=min10d5-10 x5+130 9-x5d511-x5 =10(9-x5)-10 x5+130 =220-20 x5 d5*=9-x5生生 产产 库库 存存 问问 题题24对于k=4f4(x4)=minc4d4+f5(x5)d4D4(x4)=min17d4+220-20 x5 d4D4(x4)=min17d4+220-20(x4-r4+d4)d4D4(x4)=min17d4+220-20(x4-3+d4)d4D4(x4)=min-3d4-20 x4+280 d4D4(x4)生生 产产 库库 存存 问问 题题25D4(x4)=d4|d40,r5x4-r4+d4H=d4|d40,r5+r4-x4d4H+r4-x4=d4|d40,5-x4d412-x4=d4|max0,5-x4d412-x4 由于 在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280=-17x4+244生生 产产 库库 存存 问问 题题26对于k=3f3(x3)=min c3d3+f4(x4)d3D3(x3)=min 13d3+244-17x4 d3D3(x3)=min 13d3+244-17(x3-r3+d3)d3D3(x3)=min-4d3-17x3+329 d3D3(x3)D3(x3)=d3d30,r4x3-r3+d3H=d3|d30,r4+r3-x3d3H+r3-x3=d3|d30,8-x3d314-x3=d3|max0,8-x3d314-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273,d3*=14-x3生生 产产 库库 存存 问问 题题27对于k=2f2(x2)=minc2d2+f3(x3)d2D2(x2)=min18d2+273-13x3 d2D2(x2)=min18d2+273-13(x2-r2+d2)d2D2(x2)=min18d2+273-13(x2-8+d2)d2D2(x2)=min5d2-13x2+377 d2D2(x2)D2x2)=d2|d20,r3x2-r2+d2H=d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2生生 产产 库库 存存 问问 题题28因为 13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377=-18x2+442,d2*=13-x2生生 产产 库库 存存 问问 题题29对于k=1f1(x1)=minc1d1+f2(x2)d1D1(x1)=min11d1+442-18x2 d1D1(x1)=min11d1+442-18(x1-r1+d1)d1D1(x1)=min11d1+442-18(x1-0+d1)d1D1(x1)=min-7d1-18x1+442 d1D1(x1)D D1 1(x x1 1)=)=d d1 1|d d1 1 0,0,r r2 2 x x1 1-r r1 1+d d1 1 H H =d d1 1|d d1 1 0,0,r r2 2+r r1 1-x x1 1 d d1 1 H H+r r1 1-x x1 1 =d d1 1|d d1 1 0,8-0,8-x x1 1 d d1 1 9-9-x x1 1 生生 产产 库库 存存 问问 题题30根据题意 x1=2所以 D1(x1)=d1|6d17由此 d1=7f1(x1)=-7d1-18x1+442=-77182442=357将以上结果总结成下表：生生 产产 库库 存存 问问 题题31设设 备备 更更 新新 问问 题题32333435