资源分配问题.ppt

《资源分配问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章动态规划多阶段决策过程动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点1资源分配问题2例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资源分配问题3阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0≤dk≤xk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；递推方程：f

2、k(xk)=max{vk(xk,dk)+fk+1(xk+1)}边界条件：f4(x4)=0资源分配问题4k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3资源分配问题5k=2，0≤d2≤x2，x3=x2-d2资源分配问题6k=1，0≤d1≤x1，x2=x1-d1资源分配问题7背包问题8背包问题9则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn为正整数阶段k：第k次装载第k种物品（k=1,2,…,n）状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数

3、；背包问题104.决策允许集合：Dk(xk)={dk

4、0dkxk/wk，dk为整数}；5.状态转移方程：xk+1=xk-wkdk6.阶段指标：vk=ckdk7.递推方程fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.终端条件：fn+1(xn+1)=0背包问题11例5.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5用动态规划求解f4(x4)=0对于k=3背包问题1213141516生产库存问题17例5.9：一个工厂生产某种产品,1-7月份生产成本和

5、产品需求量的变化情况如下表：生产库存问题18阶段k：月份，k=1,2,…,7,8；状态变量xk：第k个月初（发货以前）的库存量；决策变量dk：第k个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)={dk

6、dk0,rk+1xk+1H}={dk

7、dk0,rk+1xk-rk+dkH}；阶段指标：vk(xk,dk)=ckdk；终端条件：f8(x8)=0,x8=0；生产库存问题19递推方程：fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}dkDk(xk)=min{ckdk+fk+1(xk-rk+dk)}

8、dkDk(xk)对于k=7因为x8=0有d7=0递推方程为f7(x7)=min{c7d7+f8(x8)}=0d7=0生产库存问题20对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=min{c6d6+f7(x7)}d6=11-x6=10d6=10(11-x6)=110-10x6生产库存问题21对于k=5f5(x5)=min{c5d5+f6(x6)}d5D5(x5)=min{20d5+110-10x6}d5D5(x5)=min{20d5

9、+110-10(x5-r5+d5)}d5D5(x5)=min{20d5+110-10(x5-2+d5)}d5D5(x5)=min{10d5-10x5+130}d5D5(x5)D5(x5)={d5

10、d50,r6x5-r5+d5H}={d5

11、d50,r6+r5-x5d5H+r5-x5}={d5

12、d50,9-x5d511-x5}生产库存问题22因为x5H=9，因此9-x50，决策允许集合可以简化为D5(x5)={d5

13、9-x5d511-x5}递推方程成为f5(x5)=min{10d5-10x5+130}9-x5d511-x5=1

14、0(9-x5)-10x5+130=220-20x5d5*=9-x5生产库存问题23对于k=4f4(x4)=min{c4d4+f5(x5)}d4D4(x4)=min{17d4+220-20x5}d4D4(x4)=min{17d4+220-20(x4-r4+d4)}d4D4(x4)=min{17d4+220-20(x4-3+d4)}d4D4(x4)=min{-3d4-20x4+280}d4D4(x4)生产库存问题24D4(x4)={d4

15、d40,r5x4-r4+d4H}={d4

16、d40,r5+r4-x4d4H+r4-x4}={d4

17、d

18、40,5-x4d412-x4}={d4

19、ma