动态规划作业完整
动态规划作业
1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线？
把A看作终点，该问题可分为4个阶段。
f k（S k）表示从第K阶段点S k到终点A的最短距离。
f4（B l）=20, f4（B2）=40, f4（B 3）=30
f3（C i）=min[d3（C i, B i）+ f4（B i）, d3（C i, B2）+ f4（B2）, d3（C i, B3）+ f4（B3）]=70，U3（C i）= B2 或B3
f3（C 2）=40 ，U3（C2）= B3
f3（CJ=80，U3（C3）= B i 或B2 或B3
f2（D i）=80，U2（D i）= C i
f2（D 2）=70 ，U2（D2）= C2
f i（E）=ii0，U i（E）= D i 或D2
所以可以得到以下最短路线,
E T D I^C I^B 2 / B3TA
E TD 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+i(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
第二阶段：
设将S2个销售点(S2= 0,1,2,3,4)分配给乙丙两个地区时，对每
一个S2值，都有一种最优分配方案，使得最大盈利值为:
f2(S2)= max[ P2(X2)+ f3(S2 - X2)]
其中，X2= 0,1,2,3,4
表2
第一阶段：
设将S1个销售点(S1= 4)分配给三个地区时，则最大利润值为:
f1(S1)= max[ P1(X1)+ f2(4 - X1)]
其中，X1 = 0,1,2,3,4
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)
4
故指标函数为V1,4= ' Vk(Sk，Uk)
k =1
f k(Sk)表示由资源量Sk出发，从第k年开始到第4年结束时所生产的产量最大。
4)递推关系式：f k(Sk)= MAX{20 Uk +15(Sk —Uk)+ f k+1【0?4Uk
5)从第 4 阶段开始，向前逆推计算
当k= 4时，
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
即前三年应把年初全部完好的挖掘设备投入正常负荷下施工，第四年应把年初112台全部完好的挖掘设备投入超负荷下施工，144台投入正常负荷下施工。这样最高产量为22700台。
4、某电视机厂为生产电视机而需生产喇叭，生产以万只为单
位。根据以往记录，一年的四个季度需要喇叭分别是3万、2万、3 万、2万只。设每万只存放在仓库内一个季度的存储费为0.2万元，每生产一批的装配费为2万元，每万只的生产成本费为1万元。问应该怎样安排四个季度的生产，才能使总的费用最小？
再生产点性质，
Ci(Xi) ="0以：=眷=1,2, n hi(xi)= 0.2Xi
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