1、1第五章 动态规划多阶段决策过程动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点2资资 源源 分分 配配 问问 题题3 例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题41.阶段k：每投资一个项目作为一个阶段
2、；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-d3x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=11220303
3、0+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584资资 源源 分分 配配 问问 题题6k=2，0d2x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+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
4、=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592资资 源源 分分 配配 问问 题题7k=1，0d1x1，x2=x1-d1x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=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 万元，项目
5、B 投资 0 万元，项目 C 投资 3 万元，最大效益为 60 万吨。资资 源源 分分 配配 问问 题题8背 包 问 题9 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,n，xi为非负整数），背包中物品的价值为z，则 背 包 问 题10则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn为正整数1.阶 段k：第k次 装 载 第k种 物 品（k=1,2,n）2.状
6、态变量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=330max)(max)(3/04433
7、/033333333dxfdcxfwxdwxd列出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
8、4 3 2 1 0 0+0=0 30+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
9、1 4 1 0+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*6
10、5 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=x3-d3=
11、0 即应取第一种物品 2 件,第三种物品 1 件,最高价值为 160 元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到。17生生 产产 库库 存存 问问 题题18 例例5.95.9：一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情 况如下表：月份(k)1 2 3 4 5 6 7 生产成本(ck)11 18 13 17 20 10 15 需求量(rk)0 8 5 3 2 7 4 为了调节生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为 2，要求期末（七月低）库存量为 0。每个月生产的产品在月
12、末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。生生 产产 库库 存存 问问 题题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)
13、=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 d
14、5 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 5-10-10 x x5 5+130+130 d d5 5
15、 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-x5
16、d511-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-x4
17、d412-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)=d3|d30,r4x3-r3+d3H=d3|d30,r4+r
18、3-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)D2(x2)=d2|d20,r3x2-r2+d2H=d2|d
19、20,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+4
20、42 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将以上结果总结成下表：k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 生生 产产 库库 存存 问问 题题31设设 备备 更更 新新 问问 题题32333435
