动态规划作业完整编辑.docx
动态规划作业完整编辑动态规划作业1、 1、 、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路途?把 把 A 看作终点，该问题可分为 4 个阶段。f k (S k ) 表示从第 K 阶段点 S k 点 到终点 A 的最短距离。f 4 (B 1 )=20 ，f 4 (B 2 )=40 ，f 4 (B 3 )=30 f 3 (C 1 )=mind 3 (C 1,B 1 )+ f 4 (B 1 ), d 3 (C 1,B 2 )+ f 4 (B 2 ), d 3 (C 1,B 3 )+ f 4 (B 3 ) =70 ，U 3 (C 1 )= B 2 或 或 B 3 f 3 (C 2 )=40 ，U 3 (C 2 )= B 3 f 3 (C 3 )=80 ，U 3 (C 3 )= B 1 或B 2 或 或 B 3 f 2 (D 1 )=80 ，U 2 (D 1 )= C 1 f 2 (D 2 )=70 ，U 2 (D 2 )= C 2f 1 (E)=110 ，U 1 (E)= D 1 或 或 D 2所以可以得到以下最短路途，E→D 1 →C 1 →B 2/ B 3 →A E→D 2 →C 2 →B 3 →A 2、 习题 42 解：1) 将问题按地区分为三个阶段，三个地区的编号分别为 1、 、2、 、3 ； 2)设 设 Sk 表示为安排给第 k 个地区到第 n 个地区的销售点数， Xk 表示为安排给第 k 个地区的销售点数，S k 1 S k X kPk(Xk) 表示为 Xk 个销售点分到第 k 个地区所得的利润值 fk(Sk) 表示为 Sk 个销售点安排给第 k 个地区到第 n 个地区的最大利润值 3) 递推关系式：fk(Sk) max Pk(Xk)+ f k+1 (S k X k ) k=3,2,1 f4(S4) 0 4 ）从最终一个阶段起先向前逆推计算 第三阶段：将 设将 S3 个销售点（S3 0,1,2,3,4 ）全部安排给第三个地区时，最大利润值为：f3(S3) maxP3(X3)其中 X3 S3 0,1,2,3,4 表 表 1 X 3 S 3P 3 (X 3 ) f 3 (S 3 ) X 3 *0 1 2 3 4 0 0 0 0 11212 1 2 22 22 233636 3 4 47 47 4 其次阶段：将 设将 S2 个销售点（S2 0,1,2,3,4 ）安排给乙丙两个地区时，对每个 一个 S2 值，都有一种最优安排方案，使得最大盈利值为：f2(S2) max P2(X2)+ f3(S2 X2) 其中，X2 0,1,2,3,4 表 表 2 X 2 S 2P 2 (X 2 ) f 3 (S 2 X 2 ) f 2 (S 2 ) X 2 *0 1 2 3 4 0 0 0 0 1 0 12 13 013 1 2 0 22 13 12 24 0 25 1 3 0 36 13 22 24 12 34 036 0,2 4 0 47 13 36 24 22 34 12 42 0 49 1 第一阶段：将 设将 S1 个销售点（S1 4：）安排给三个地区时，则最大利润值为：f1(S1) max P1(X1)+ f2(4 X1) 其中，X1 0,1,2,3,4 表 表 3 X 1 S 1P 1 (X 1 ) f 2 (4 X 1 ) f 1 (4) X 1 *0 1 2 3 4 4 0 49 16 36 28 25 40 13 50 0 53 2,3 然后按计算表格的依次反推，可知最优安排方案有两个：最大总为 利润为 53 1 ）由 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 表示年度，k 1,2,3,4 2 ）设 Sk 表示为安排给第 k 年初拥有的完好挖掘设备数量， Uk 表示为第 k 年初安排在超负荷下施工的挖掘设备数量， Dk (Sk)= Uk|0 ≤Uk ≤Sk Sk Uk 表示为第 k 年初安排在正常负荷下施工的挖掘设备数量。状态转移方程：S k 1 0.4Uk +0.8(Sk Uk) ， S1 500 台3 ）设 vk(sk,uk) 为第 k 年度的产量，则 vk 20Uk +15(Sk Uk) 故 指标函数为 为 V1,4=f k (Sk) 表示由资源量 Sk 动身，从第 k 年起先到第 4 年结束时所生产的产量最大。4）递推关系式：f k (Sk) MAX20 Uk +15(Sk Uk)+ f k+1 0.4Uk +0.8(Sk Uk)k=1,2,3,4 5 ）从第 4 阶段起先，向前逆推计算 当 当 k 4 时 时， ， å=41 k) U , (S V k k kS5=160, 0.4U4 +0.8(S4 U4)=1602S4-U4=400U4=2S4-400 f4(S4) MAX20 U4 +15(S4 U4)+ f50.4U4 +0.8(S4 U4) MAX5 U4 +15S4 =25S4-2000 当 当 k 3 时 时， ， f3(S3) MAX20 U3 +15(S3 U3)+ f40.4U3 +0.8(S3 U3)= 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 ， S2 0.4U1 *+0.8(S1 U1*) 0.8S1 400 S3 0.4U2 *+0.8(S2 U2*) 0.8S2 320 S4 0.4U3 *+0.8(S3 U3*) 0.8S3 256 U4=2S4-400=112 S4-U4=256-112=144 即前三年应把年初全部完好的挖掘设备投入正常负荷下施工，第初 四年应把年初 112 台全部完好的挖掘设备投入超负荷下施工，144 台 台为 投入正常负荷下施工。这样最高产量为 22700 台。4、 某电视机厂为生产电视机而需生产喇叭，生产以万只为单位。依据以往记录，一年的四个季度须要喇叭分别是 3 万、2 万、3万、2 万只。设每万只存放在仓库内一个季度的存储费为 0.2 万元，每生产一批的装配费为 2 万元，每万只的生产成本费为 1 万元。问应当怎样支配四个季度的生产，才能使总的费用最小？ 再生 产点性质， Xi Xi hiXin Xi XiXi Ci 2 . 0 ) (0 0, 2 , 1 2) ( =îíì= +=L C(1,1)=C(3)+h(0)=5 C(1,2)=C(5)+h(2)=7.4 C(1,3)=C(8)+h(5)+h(3)=11.6 C(1,4)=C(10)+h(7)+h(5)+h(2)=14.8 C(2,2)=C(2)+h(0)=4 C(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)=4 f0=0 f1=f0+ C(1,1)=5 j(1)=1 f2=minf0+ C(1,2),f1+ C(2,2)=min0+7.4,5+4=7.4j(2)=1 f3= minf0+ C(1,3),f1+ C(2,3),f2+ C(3,3) =min0+11.6,5+7.6,7.4+5=11.6 j(3)=1 F4= 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.8 j(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、 某工厂生产三种产品，各产品重量与利润关系如下表所示，现将此三种产品运往市场出售，运输实力总重量不超过 6 吨。问如何支配运输使总利润最大。种类 1 2 3 重量 2 3 4 利润 80 130 180 解：( ) ( ) ( ) ( ) 2 180 , 6 0 max3 4 6 3 180 max) 2 130 1 80 max( 3 180 max 62 221 , 0 36 3 43f fx f xx x x fxx+ + =- + =+ + =£ ( ) ( ) ( ) ( ) ( ) 0 1260260 , 210 , 240 max0 260 , 3 130 , 6 0 max2 3 6 2 130 max) 1 80 max( 2 130 max 61 1 112 , 1 , 0 26 2 32=+ + + =- + =+ =£xf f fx f xx x fxx ( ) ( ) ( )1 18022 3 2 2 130 max) 1 80 max( 2 130 max 2110 22 2 32=- + =+ =£xfx f xx x fxx ( ) 1 3 , 0 2 , 1 10 3 , 2 2 , 0 1260 260 , 260 max 63= = = = = =x x xx x xf6 、某工厂在一年进行了 A、B、C 三种新产品试制，由于资金不足，估计在年内这三种新产品研制不胜利的概率分别为 0.40、0.60、0.80，因而都研制不胜利的概率为 0.4×0.6×0.8=0.l92。为了促进三种新产品的研制，确定增援 2 万元的研制费，并要资金集中运用，以万元为单位进行安排。其增援研制费与新产品不胜利的概率如下表所示。试问如何安排费用，使这三秤新产品都研制不胜利的概率为最小。解 解:1) （1 分）将问题品 按产品 A 、B 、C 分为三个阶段，k=1 、2、 、3 ；2) （6 分）设 Sk 表示第 k 阶段可安排给第 k 个产品到第 n 个产品的研制费，S1 2 Xk 设为决策变量，表示第 k 阶段安排给第 k 个产品的研制费。为 状态转移方程为 Sk 1 Sk Xk 允许决策集合：Dk(Sk) Xk 0≤Xk≤Sk ，Xk 为整数 Pk(Xk) 表示为第 k 个产品失败的概率 fk(Sk) 表示为 Sk 万元研制费安排给第 k 个产品到第 n 个产品的最小的失败概率 3) （4 分）递推关系式：f k (Sk) min Pk(Xk)×f k+1 (Sk Xk) k=3,2,1边界条件：f4(S4) 1 4 ）（11 分）从最终一个阶段起先向前逆推计算 第三阶段：将 设将 S3 万元研制费（S3 0,1,2 ）全部安排给 C 产品时，最小的失败概率为：f3(S3) minP3(X3)其中 X3 S3 0,1,2 X 3 S 3P 3 (X 3 ) f 3 (S 3 ) X 3 *0 1 2 0 0.80 0.80 0 10.500.50 1 2 0.30 0.30 2 X3* 表示使得 f3(S3) 为最大值时的最优决策。其次阶段：将 设将 S2 万元研制费（S2 0,1,2 ）安排给 B 、C 产品时，最小的失败概率为：f2(S2) min P2(X2)×f3(S2 X2) 其中，X2 0,1,2 X 2 S 2P 2 (X 2 )×f 3 (S 2 X 2 ) f 2 (S 2 ) X 2 *0 1 2 0 0.60×0.80 0.48 0.48 0 1 0.60×0.50 0.30 0.40×0.80 0.320.30 0 2 0.60×0.30 0.18 0.40×0.50 0.20 0.20×0.80 0.16 0.16 2 第一阶段：将 设将 S1 万元研制费（S1 2 ）分 配给三个产品时，最小的失败概率为：f1(S1) min P1(X1)×f2(S1 X1) 其中，X1 0,1,2 X 1 S 1P 1 (X 1 )×f 2 (S 1 X 1 ) f 1 (2) X 1 *0 1 2 2 0.40×0.16 0.064 0.20×0.30 0.060 0.15×0.48 0.072 0.060 1 5 ）即安排给 A 产品 1 万元，B 产品 0 万元，C 产品 1 万元，可到 使三个小组都失败的概率减小到 0.060 。
