动态规划习题课

1、动态规划习题课动态规划习题课资源分配资源分配问题问题例1某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂，各工厂获得投资后年利润将有相应的增长，一定投资下的利润增长额如下表所示，试确定最优的投资分配方案，使公司年利润增长额最大。 投资投资(百万元) 1 2 3 4 5 甲甲 0.3 0.7 0.9 1.2 1.3 乙乙 0.5 1.0 1.1 1.1 1.1 丙丙 0.4 0.6 1.1 1.2 1.2 例例1的求解的求解按工厂分为三个阶段： 甲 乙 丙 k ： 1 2 3 设sk为第k个工厂至第3个工厂可利用的投资额，xk为第k个工厂获得的投资额，则sk+1=sk - xk。因而有最优

2、指标函数：fk(sk)=maxrk(xk)+fk+1(sk-xk) f4(s4)=0 例例1的求解的求解k =3：f3(s3)=maxr3(x3)+f4(s4)=maxr3(x3)s3 0 1 2 3 4 5 *x3 0 1 2 3 4 4, 5f3(s3) 0 0.4 0.6 1.1 1.2 1.2 k =2：f2(s2)=maxr2(x2)+f3(s2 - x2) 例例1的求解的求解 x2 r2(x2)+f3(s2-x2) s2 0 1 2 3 4 5 f2(s2) *x2 0 0+0 0 0 1 0+.4 .5+0 0.5 1 2 0+.6 .5+.4 1+0 1.0 2 3 0+1.1

3、 .5+.6 1+.4 1.4 2 4 0+1.2 .5+1.1 1+.6 1.1+.4 1.1=0 1.6 1,2 5 0+1.2 .5+1.2 1+1.1 1.1+.6 1.1+.4 1.1+0 2.1 2 例例1的求解的求解k =1：f1(s1)=maxr1(x1)+f2(s1-x1) x1 r1(x1)+f2(s1-x1)s1 0 1 2 3 4 5 f1(s1) *x1 5 0+2.1 .3+1.6 .7+1.4 .9+1.0 1.2+0.5 1.3+0 2.1 0, 2 然后按计算表格的顺序反推算，可得如下两个最优分配方案：1. x1=0 s2=s1-x1=5-0=5 x2=2s3

4、=3x3=3 2. x1=2， x2=2， x3=1 存贮控制问题存贮控制问题例例2 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下一个销售季节各月的需求量预测值为：月 份 10 11 12 1 2 3需求(双) 40 20 30 40 30 20 该鞋店直接从生产商进货，基础进货价为每双4美元。进货批量有10、20、30、40和50双五种规模，对应不同的进货批量享受一定的价格折扣，具体数值如下：批 量 10 20 30 40 50 折扣(%) 4 5 10 20 25 例例2的求解的求解 假设需求是按一定速度均匀发生的，订货不需要时间，但订货只能

5、在月初办理，每次订货的费用为10美元。月存贮费用是按每月底鞋的存量计算的，每双0.2美元。由于订货不需要时间，所以销售季节以外的月份无存货。试确定最佳的进货方案，以使总的销售费用最小。阶段阶段：k = 1, 2, 3, 4, 5, 6状态状态： sk 代表第k月初鞋的存量决策变量决策变量：dk 代表第k月鞋的采购量状态转移律状态转移律： sk+1=sk + dk - dk ，s1 = s7 = 0费用函数费用函数： rk (sk, dk )= (dk)+ 0.2(sk + dk - dk)，其中 (dk)为订货费用，订货费用由两部分构成，一部分是固定的采购费10美元，另一部分是货款， dk=

6、0时 (dk)= 0。最优指标函数最优指标函数： fk (sk )=min (dk) + 0.2(sk + dk - dk)+ fk+1 (sk+1)例例2的求解的求解k=6(三月): s6 0 10 20 *d6 20 10 0f6 (s6 )= (*d6 ) 86 48 0k=5(二月): d5 0 10 20 30 40 50 * d5 f5 (s5 )s5 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4 0 4例例2的求解的求解k=4

7、(一月): d4 0 10 20 30 40 50 * d4 f4 (s4 )s4 0 302 304 40 302 10 282 282 286 30, 40 282 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 126例例2的求解的求解k=3(十二月): d3 0 10 20 30 40 50 * d3 f3 (s3 )s3 0 420 422 414 50 4

8、14 10 388 402 392 384 50 384 20 350 370 372 362 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 例例2的求解的求解k=2(十一月): d2 0 10 20 30 40 50 * d2 f2 (s2 )s2 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 k=1(十月): d1 0 10 20 30 40 50 * d1 f1 (s1 )s1 0 606 608 40 606 例例2

9、的求解的求解利用状态转移律，按上述计算的逆顺序推算，可得如下最优策略：十月份40双 十一月份50双 十二月份0双 一月份40双 二月份50双 三月份0双最小的销售费用为606美元。 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公公斤，设有斤，设有n 种物品可供他选择装入包中。已知每种物品种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/

10、 /件）件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题运输中的货物装载问题、人造卫星内的物品装载问题等。等。例3 背包问题设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下： ). 2 . 1(0max1njxaxaxczjnijjjnjjj 且且为为整整数数用动态规划方法求解，令用动态规划方法求解，令 fx(y) = 总重量不超过总重量不超过 y 公斤，包中只装有

11、前公斤，包中只装有前k 种物品种物品时的最大使用价值。时的最大使用价值。 其中其中y 0， k 1,2, , n 。所以问题就是求所以问题就是求 fn(a) 其递推关系式为：其递推关系式为： nkxayfxcyfkkkkkayxkkk 2)(max)(10 其其中中当当 k=1 时，有：时，有：的的最最大大整整数数表表示示不不超超过过其其中中1111111 , )(ayayayxaycyf例题：求下面背包问题的最优解例题：求下面背包问题的最优解 且且为为整整数数0,55231258max321321321xxxxxxxxxz物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用价值使用价

12、值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5) )55(12max)5(323503333xfxfxax 整整数数 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整数数整整数数 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整整数数整整数数 )0()0(

13、0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整数整数整数整数)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),

14、5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 x（1 . 1 . 0），），最优值为最优值为 z = 13。 练习练习1：某厂生产三种产品，各种产品重量与利：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3重量（吨重量（吨/ /公斤）公斤） 2 3 4 单件利润（元）单件利润（元） 80 130 180最优方案：最优方案：x1 = =（0

15、.2.00.2.0）x2 = =（1.0.11.0.1）z=260=260 例例4 投资问题投资问题 现有资金现有资金5百万元百万元,可对三个项目进行投资可对三个项目进行投资,投资额均投资额均为整数为整数(单位为百万元单位为百万元),其中其中2号项目的投资不得超过号项目的投资不得超过3百万元百万元,1号和号和3号项目的投资均不得超过号项目的投资均不得超过4百万元，百万元，3号号项目至少要投资项目至少要投资1百万元。每个项目投资百万元。每个项目投资5年后年后,预计可预计可获得的收益见下表获得的收益见下表,问如何投资可望获得最大的收益。问如何投资可望获得最大的收益。 0 1 2 3 4 1 0 3

16、 6 10 122 0 5 10 12 - 3 0 4 8 11 15投资额投资额u收益收益wk项目项目k 解解 sk对对1,(k-1)项目投资后剩余的金额项目投资后剩余的金额(状状态变量态变量)uk对对k项目的投资额项目的投资额wk(sk,uk)对对k项目投资项目投资uk后的收益后的收益wk(uk) fk(sk)应用剩余资金应用剩余资金sk对对k,(k+1),n项项 目投资可获得的最大收益目投资可获得的最大收益状态转移方程为状态转移方程为sk+1=sk-uk 为了获得最大收益，必须将为了获得最大收益，必须将5百万元资金全部用于百万元资金全部用于投资，可得下面的递归方程投资，可得下面的递归方程

17、 f4(s4)=0 fk(sk)=maxwk(sk,uk)+fk+1(sk+1) k=3,2,1当当k=3时时 uk=skf3(1)=4 f3(2)=8 f3(3)=11 f3(4) =15当当k=2时时, 有有(注意：注意：项目项目3至少投资至少投资1百万元百万元, 2号项目的投资不得超过号项目的投资不得超过3百万元百万元)s2 1 2 3 4 5d2(sk) 0 0,1 0,1,2 0,1,2,3 0,1,2,3f2(1)=w2(1,0)+f3(1)=4f2(2)=maxw2(2,1)+f3(1)w2(2,0)+f3(2)=max5+40+8=9f2(3)=maxw2(3,2)+f3(1)w2(3,1)+f3(2)w2(3,0)+f3(3)=max10+45+80+11=14f2(4)=maxw2(4,3)+f3(1)w2(4,2)+f3(2)w2(4,1)+f3(3)w2(4,0)+f3(4)=max12+410+85+11 0