动态规划作业
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 )=min[d 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 2
f 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、 习题 4－2 解：1) 将问题按地区分为三个阶段，三个地区的编号分别为 1、 、2、 、3 ； 2)设 设 Sk 表示为分配给第 k 个地区到第 n 个地区的销售点数， Xk 表示为分配给第 k 个地区的销售点数，S k ＋ 1 ＝ ＝S k － －X k
Pk(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) ＝max[P3(X3)]
其中 X3 ＝S3 ＝0,1,2,3,4 表 表 1 X 3 S 3
P 3 (X 3 ) f 3 (S 3 ) X 3 *
0 1 2 3 4 0 0
0 0 1
12
12 1 2
22
22 2
3
36
36 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 2
P 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 ＋0
13 1 2 0 ＋22 13 ＋12 24 ＋0
25 1 3 0 ＋36 13 ＋22 24 ＋12 34 ＋0
36 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 1
P 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) ＝MAX{20 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 k
S5=160, 0.4U4 +0.8(S4 －U4)=160
2S4-U4=400
U4=2S4-400 f4(S4) ＝MAX{20 U4 +15(S4 －U4)+ f5[0.4U4 +0.8(S4 －U4)]}
＝MAX{5 U4 +15S4}
=25S4-2000 当 当 k ＝3 时 时， ， f3(S3) ＝MAX{20 U3 +15(S3 －U3)+ f4[0.4U3 +0.8(S3 －U3)]}
= MAX{5U3+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) ( 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)=5
C(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=min{f0+ C(1,2),f1+ C(2,2)}=min{0+7.4,5+4}=7.4
j(2)=1 f3= min{f0+ C(1,3),f1+ C(2,3),f2+ C(3,3)} =min{0+11.6,5+7.6,7.4+5}=11.6
j(3)=1 F4= min{f0+ C(1,4),f1+ C(2,4),f2+ C(3,4), f3+ C(4,4)} =min{0+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 xf
6 、某工厂在一年进行了 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) ＝min[P3(X3)]
其中 X3 ＝S3 ＝0,1,2 X 3 S 3
P 3 (X 3 ) f 3 (S 3 ) X 3 *
0 1 2 0 0.80
0.80 0 1
0.50
0.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 2
P 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.32
0.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 1
P 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 。
