动态规划作业完整

.动态规划作业1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择， 而进口港又有三个可供选择，进口后可经由两个城市到达目的地， 其间的运输成本如图中所标的数字，试求运费最低的路线 ?把 a 看作终点，该问题可分为4 个阶段。fk(sk)表示从第 k 阶段点 sk 到终点 a 的最短距离。f4(b1)=20，f4(b2)=40， f4(b3)=30f3(c 1)=mind3(c1,b1)+f4(b1),d3(c1,b2)+f4(b2),d3(c1,b3)+ f4(b3) =70， u3(c 1)= b2 或 b3f3(c 2)=40，u3(c2)= b3f3(c 3)=80，u3(c3)= b1 或 b2 或 b3 f2(d 1)=80，u2(d1)= c1f2(d 2)=70，u2(d2)= c2f1(e)=110，u1(e)= d 1 或 d2所以可以得到以下最短路线，;.ed1c1b2 / b3a ed2c2b3a2、习题 4 2解：1)将问题按地区分为三个阶段， 三个地区的编号分别为1、2、3；2) 设 sk 表示为分配给第k 个地区到第 n 个地区的销售点数， xk 表示为分配给第k 个地区的销售点数， sk 1 sk xk pk(xk) 表示为 xk 个销售点分到第k 个地区所得的利润值fk(sk)表示为 sk 个销售点分配给第k 个地区到第n 个地区的最大利润值3) 递推关系式：fk(sk) max pk(xk)+ f k+1(sk x k) k=3,2,1 f4(s4)04）从最后一个阶段开始向前逆推计算第三阶段：设将 s3 个销售点（ s3 0,1,2,3,4）全部分配给第三个地区时，最大利润值为：f3(s3)maxp3(x3)其中 x3 s30,1,2,3,4表 1x 3p3(x 3)s301234f 3(s3)x *30000112121222222336363447474第二阶段：设将 s2 个销售点（ s2 0,1,2,3,4）分配给乙丙两个地区时，对每一个 s2 值，都有一种最优分配方案，使得最大盈利值为：f2(s2)max p2(x2)+ f3(s2 x2) 其中， x2 0,1,2,3,4表 2x 2p2(x 2) f3(s2 x2)01234000010 1213 013120 2213 1224 025130 3613 2224 1234 0360,240 4713 3624 2234 1242 0491s2*f 2(s2)x 2第一阶段：设将 s1 个销售点（ s1 4）分配给三个地区时， 则最大利润值为：f1(s1)max p1(x1)+ f2(4 x1) 其中， x1 0,1,2,3,4表 3f1(4)x *1400 49116 36228 25340 13450 0532,3x 1p1(x 1) f2(4 x 1)s1然后按计算表格的顺序反推，可知最优分配方案有两个：最大总利润为 531） 由 x1* 2， x2* 1， x3* 1。即得第一个地区分得2 个销售点，第二个地区分得1 个销售点，第三个地区分得1 个销售点。2） 由 x1* 3， x2* 1， x3* 0。即得第一个地区分得3 个销售点，第二个地区分得1 个销售点，第三个地区分得0 个销售点。3、某施工单位有500 台挖掘设备，在超负荷施工情况下，年产值为 20 万元/台，但其完好率仅为0.4，在正常负荷下，年产值为15 万元/台，完好率为 0.8。在四年内合理安排两种不同负荷下施工的挖掘设备数量， 使第四年年末仍有160 台设备保持完好， 并使产值最高。试求出四年内使得产值最高的施工方案和产值数。解： 1）该问题分成四个阶段，k 表示年度， k1,2,3,42）设 sk 表示为分配给第k 年初拥有的完好挖掘设备数量， uk 表示为第 k 年初分配在超负荷下施工的挖掘设备数量， dk (sk)= uk|0 uk sk skuk 表示为第 k 年初分配在正常负荷下施工的挖掘设备数量。状态转移方程： sk 10.4uk +0.8(sk uk)， s1 500 台 3）设 vk(sk,uk)为第 k 年度的产量，则vk 20uk +15(skuk)4故指标函数为v1,4=kvk(sk, uk) 1fk(sk)表示由资源量 sk 出发，从第 k 年开始到第 4 年结束时所生产的产量最大。4）递推关系式： fk(sk) max20uk+15(skuk)+f k+10.4uk+0.8(sk uk)k=1,2,3,45）从第 4 阶段开始，向前逆推计算当 k 4 时，s5=160, 0.4u4 +0.8(s4 u4)=1602s4-u4=400u4=2s4-400 f4(s4) max20 u4 +15(s4 u4)+ f50.4u4 +0.8(s4u4) max5 u4 +15s4=25s4-2000当 k 3 时，f3(s3) max20 u3 +15(s3 u3)+ f40.4u3 +0.8(s3u3)= max5u3+15s3+25(0.8s3-0.4u3)-2000 max-5u3 +35s3-2000故得最大解 u3* 0所以 f3(s3)35 s3-2000依次类推，可求得：u2* 0， f2(s2)43s2-2000 u1* 0， f1(s1)49.4s1-2000因为 s1 500 台，故 f1(s1) 22700 台最优策略为 u1* 0， u2* 0，u3* 0， u4* 112已知 s1 500，s20.4u1 *+0.8(s1 u1*) 0.8s1 400 s30.4u2 *+0.8(s2 u2*) 0.8s2 320 s40.4u3 *+0.8(s3 u3*) 0.8s3 256u4=2s4-400=112s4-u4=256-112=144即前三年应把年初全部完好的挖掘设备投入正常负荷下施工，第四年应把年初 112 台全部完好的挖掘设备投入超负荷下施工，144 台投入正常负荷下施工。这样最高产量为22700 台。4、某电视机厂为生产电视机而需生产喇叭，生产以万只为单位。根据以往记录，一年的四个季度需要喇叭分别是3 万、 2 万、3万、2 万只。设每万只存放在仓库内一个季度的存储费为0.2 万元，每生产一批的装配费为2 万元，每万只的生产成本费为1 万元。问应该怎样安排四个季度的生产，才能使总的费用最小？再生产点性质，ci ( xi)2xi0xixi1,2,0nhi ( xi)0.2xic(1,1)=c(3)+h(0)=5c(1,2)=c(5)+h(2)=7.4 c(1,3)=c(8)+h(5)+h(3)=11.6c(1,4)=c(10)+h(7)+h(5)+h(2)=14.8c(2,2)=c(2)+h(0)=4c(2,3)=c(5)+h(3)=7.6 c(2,4)=c(7)+h(5)+h(2)=10.4 c(3,3)=c(3)+h(0)=5c(3,4)=c(5)+h(2)=7.4 c(4,4)=c(2)+h(0)=4f0=0 f1=f0+ c(1,1)=5 j(1)=1f2=minf0+ c(1,2),f1+ c(2,2)=min0+7.4,5+4=7.4j(2)=1f3= minf0+ c(1,3),f1+ c(2,3),f2+ c(3,3)=min0+11.6,5+7.6,7.4+5=11.6j(3)=1f4= minf0+ c(1,4),f1+ c(2,4),f2+ c(3,4), f3+ c(4,4)=min0+14.8,5+10.4,7.4+7.4,11.6+4=14.8j(4)=1,3当 j(4)=1 ，x1=d1+d2+d3+d4=10,x2=0,x3=0,x4=0当 j(4)=3,x3=d3+d4=5,x4=0,x1=d1+d2=5,x2=0 。5、某工厂生产三种产品， 各产品重量与利润关系如下表所示，解：f 3 6max4 x 3 6max 180x3x 3 0, 1180 x3max(80x1130 x2)f 2 64x3max 0f 26 ,180f26max3 x 2 6max 130x2x 2 0 ,1, 2f22130x2max(80x1) f1 63x2max 0f1 6 ,130f1 3 ,260f1 0max 240,210,260260x10现将此三种产品运往市场出售，安排运输使总利润最大。运输能力总重量不超过6 吨。问如何种类123重量234利润80130180f 2 2max130x2max(80x1)3 x 2 2max130x2f1 23x2f1 280x11x 2 0f3 6max260,260260x10, x2x11, x22, x300, x316、某工厂在一年进行了a、b、c 三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功的概率分别为0.40、0.60、0.80，因而都研制不成功的概率为0.40.6 0.8=0.l92。为了促进三种新产品的研制，决定增援2 万元的研制费，并要资金集中使用，以万元为单位进行分配。 其增援研制费与新产品不成功的概率如下表所示。试问如何分配费用， 使这三秤新产品都研制不成功的概率为最小。解:1)（ 1 分）将问题按产品a、b、c 分为三个阶段， k=1、2、3；2)（ 6 分）设 sk 表示第 k 阶段可分配给第k 个产品到第 n 个产品的研制费， s12xk 设为决策变量，表示第k 阶段分配给第k 个产品的研制费。00.800.80010.500.50120.300.302状态转移方程为sk1 sk xk允许决策集合： dk(sk) xk 0xks，kxk 为整数 pk(xk) 表示为第 k 个产品失败的概率fk(sk)表示为 sk 万元研制费分配给第k 个产品到第n 个产品的最小的失败概率3)（ 4 分）递推关系式：fk(sk)min pk(xk)fk+1(skxk) k=3,2,1边界条件：f4(s4) 14）（ 11 分）从最后一个阶段开始向前逆推计算第三阶段：设将 s3 万元研制费（ s3 0,1,2）全部分配给 c 产品时，最小的失败概率为：f3(s3)minp3(x3)x 3s3其中 x3 s30,1,20p3 (x3)1*2f3(s3)x 3x3* 表示使得 f3(s3)为最大值时的最优决策。第二阶段：设将 s2 万元研制费（ s2 0,1,2）分配给 b、c 产品时，最小的失败概率为：f2(s2)min p2(x2)f3(s2 x2) 其中， x2 0,1,2x 2s200.60 0.800.480.60 0.500.300.60 0.300.18p2(x 2) f3(s2 x2 )12f2(s2)x 2*00.48010.40 0.800.320.40 0.500.200.30020.2