《动态规划习题课.ppt》由会员分享，可在线阅读，更多相关《动态规划习题课.ppt（30页珍藏版）》请在三一文库上搜索。
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。因而有最优指标函数： fk(Sk)=maxr
2、k(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, 5 f3(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 .5+.6 1+.4 1.4 2
3、 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=3x3=3 2. x1=2，
4、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的求解,假设需求是按一定速度均匀发生的，订货不需要时间，但订货只能在月初办理，每次订货的费用为10美元。月存
5、贮费用是按每月底鞋的存量计算的，每双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= 0时 (dk)= 0。 最优指标函数： fk (Sk )=min
6、(dk) + 0.2(Sk + dk - Dk)+ fk+1 (Sk+1) ,例2的求解,K=6(三月): S6 0 10 20 *d6 20 10 0 f6 (S6 )= (*d6 ) 86 48 0 K=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(一月): d4 0 10 20 30 40 50 * d4 f4 (S4
7、 ) 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 414 10 388 402 392 384 50 384 20 350
8、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 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,例3 背包问题,设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：,用动态规划方法求解，令 fx(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0，
10、k 1,2, , n 。所以问题就是求 fn(a),其递推关系式为：,当 k=1 时，有：,例题：求下面背包问题的最优解,解：a5 ，问题是求 f3(5),所以，最优解为 X（1 . 1 . 0），最优值为 Z = 13。,练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？,最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260,例4 投资问题 现有资金5百万元,可对三个项目进行投资,投资额均为整数(单位为百万元),其中2号项目的投资不得超过3百万元,1号和3号项目的投资均不得超过4百万
11、元，3号项目至少要投资1百万元。每个项目投资5年后,预计可获得的收益见下表,问如何投资可望获得最大的收益。,解 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百万元资金全部用于投资，可得下面的递归方程,f4(s4)=0 fk(sk)=maxwk(sk,uk)+fk+1(sk+1) k=3,2,1,当k=3时 uk=sk,f3(1)=4 f3(2)=8 f3(3)=11 f
12、3(4) =15,当k=2时, 有(注意：项目3至少投资1百万元, 2号项目的投资不得超过3百万元),f2(1)=w2(1,0)+f3(1)=4,f2(2)=max,w2(2,1)+f3(1) w2(2,0)+f3(2),=max,5+4 0+8,=9,f2(3)=max,w2(3,2)+f3(1) w2(3,1)+f3(2) w2(3,0)+f3(3),=max,10+4 5+8 0+11,=14,f2(4)=max,w2(4,3)+f3(1) w2(4,2)+f3(2) w2(4,1)+f3(3) w2(4,0)+f3(4),=max,12+4 10+8 5+11 0+15,=18,f2(5)=max,w2(5,3)+f3(2) w2(5,2)+f3(3) w2(5,1)+f3(4),=max,12+8 10+11 5+15,=21,当k=1时，有s1=5 D1(s1)=0,1,2,3,4,f1(5)=max,w1(5,4)+f2(1) w1(5,3)+f2(2) w1(5,2)+f2(3) w1(5,1)+f2(4) w1(5,0)+f2(5),=max,12+4 10+9 6+14 3+18 0+21,=21,应用顺序跟踪，可知，最优方案有两个：,方案u1*=0,u2*=2,u3*=3,方案u1*=1,u2*=2,u3*=2,最大收益为21百万元。,练习,