[理学]资源分配问题ppt课件

1、1多阶段决策过程动态规划的根本概念和根本原理动态规划方法的根本步骤动态规划方法应用举例本章内容重点23 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个工程的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题4阶段k：每投资一个工程作为一个阶段；状态变量xk：投资第k个工程前的资金数；决策变量dk：第k个工程的投资；决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vkxk ,dk见表中所示；递推方程：fkxk=maxvkxk ,d

2、k+fk+1xk+1边界条件：f4x4=0资资 源源 分分 配配 问问 题题5x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584资资 源源 分分 配配 问问 题题6x2D2(x2)x3v2(x2,d2)v2(x2,d

3、2)+f3(x3)f2(x2)d2*00000+0=0000100+11=111101313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592资资 源源 分分 配配 问问 题题7x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=

4、58314040+13=534405151+0=51601最优解为 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0， 即项目 A 投资 1 万元，项目 B 投资 0 万元，项目 C 投资 3 万元，最大效益为 60 万吨。 资资 源源 分分 配配 问问 题题89 设有n种物品，每一种物品数量无限。 第i种物品每件重量为wi， 每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包， 使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。 设第i种物品取xi件 （i=1,2,n，xi为非负整

5、数） ，背包中物品的价值为z，则 背 包 问 题10阶 段k： 第k次 装 载 第k种 物 品k=1,2,n状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数；背 包 问 题114. 决策允许集合：Dkxk=dk|0 dkxk/wk，dk为整数；5. 状态转移方程：xk+1=xk-wkdk6. 阶段指标：vk=ckdk7. 递推方程 fkxk=maxckdk+fk+1xk+1 =maxckdk+fk+1xk-wkdk8. 终端条件：fn+1xn+1=0背 包 问 题1230max)(max)(3/04433/033333333dxfdcxfwxdwxd列出

6、f3(x3)的数值表 背 包 问 题13x3 D3(x3) x4 30d3+f4(x4) f3(x3) d3* 0 0 0 0+0=0 0 0 1 0 1 1 0 0+0=0 30+0=30* 30 1 2 0 1 2 2 1 0 0+0=0 30+0=30 60+0=60* 60 2 3 0 1 2 3 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90* 90 3 4 0 1 2 3 4 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120* 120 4 5 0 1 2 3 4 5 5 4 3 2 1 0 0+0=0 3

7、0+0=30 60+0=60 90+0=90 120+0=120 150+0=150* 150 5 14对于k=2 )3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd 列出 f2(x2)的数值表 x2 D2(x2) x3 80d2+f3(x3) f2(x2) d2* 0 0 0 0+f3(0)=0+0=0* 0 0 1 0 1 0+f3(1)=0+30=30* 30 0 2 0 2 0+f2(2)=0+60=60* 60 0 3 0 1 3 0 0+f3(3)=0+90=90* 80+f3(0)=80+0=80 90 0 4 0 1 4 1 0

8、+f3(4)=0+120=120* 80+f3(1)=80+30=110 120 0 5 0 1 5 2 0+f3(5)=0+150=150* 80+f3(2)=80+60=140 150 0 15对于k=1 )2(65max)(max)(11212/02211/01111111dxfdxfdcxfxdwxd 列出f1(x1)的数值 x1 D1(x1) x2 65d1+f2(x2) f1(x1) d1* 0 0 0 0+f2(0)=0+0=0* 0 0 1 0 1 0+f2(1)=0+30=30* 30 0 2 0 1 2 0 0+f2(2)=0+60=60 65+f2(0)=65+0=65*

9、 65 1 3 0 1 3 1 0+f2(3)=0+90=90 65+f2(1)=65+30=95* 95 1 4 0 1 2 4 2 0 0+f2(4)=0+120=120 65+f2(2)=65+60=125 130+f2(0)=130+0=130* 130 2 5 0 1 2 5 3 1 0+f2(5)=0+150=150 65+f2(3)=65+90=155 130+f2(1)=130+30=160* 160 2 16由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得： d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=

10、x3-d3=0 即应取第一种物品 2 件,第三种物品 1 件,最高价值为 160 元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到。 1718月份(k) 1 2 3 4 5 6 7 生产成本(ck) 11 18 13 17 20 10 15 需求量(rk) 0 8 5 3 2 7 4 生生 产产 库库 存存 问问 题题19阶段k：月份，k=1,2,7,8；状态变量xk：第k个月初发货以前的库存量；决策变量dk：第k个月的消费量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dkxk=dk | dk0, rk

11、+1xk+1H =dk | dk0, rk+1xk-rk+dkH ；阶段指标：vkxk ,dk=ckdk；终端条件：f8x8=0,x8=0；生生 产产 库库 存存 问问 题题20对于k=7因为 x8=0有 d7=0递推方程为f7x7=minc7d7+f8x8=0 d7=0生生 产产 库库 存存 问问 题题21生生 产产 库库 存存 问问 题题22对于对于k k=5=5f f5 5x x5 5=min=minc c5 5d d5 5+ +f f6 6x x6 6 d d5 5 D D5 5x x5 5 =min20 =min20d d5 5+110-10+110-10 x x6 6 d d5 5

12、 D D5 5x x5 5 =min20 =min20d d5 5+110-10+110-10 x x5 5- -r r5 5+ +d d5 5 d d5 5 D D5 5x x5 5 =min20 =min20d d5 5+110-10+110-10 x x5 5-2+-2+d d5 5 d d5 5 D D5 5x x5 5 =min10 =min10d d5 5-10-10 x x5 5+130+130 d d5 5 D D5 5x x5 5D D5 5x x5 5 = =d d5 5| | d d5 5 0, 0, r r6 6 x x5 5- -r r5 5+ +d d5 5 H H

13、 = =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生生 产产 库库 存存 问问 题题24生生 产产 库库 存存 问问 题题25 由于 在f4x4的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4x4=-312-x4-20 x4+280 =-17x4+244生生 产产 库库 存存 问问 题题26生生 产产 库库 存存 问问 题题27生生 产产 库库 存存 问问 题题28生生 产产 库库 存存 问问 题题29D D1 1x 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