动态规划作业完整

1、1、动态规划作业1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地,其间的运输成本如图中所标的数字,试求运费最低的路线？把A看作终点，该问题可分为4个阶段。fk（Sk）表示从第K阶段点Sk到终点A的最短距离。f4（Bl）=20, f4（B2）=40, f4（B3）=30d3（Cl, B3）+f3（Ci）=mind3（Ci, Bi）+ f4（Bi）, d3（Ci, B2）+ f4（B2）,f4（B3）=70, U3（Ci）= B2 或 B3f3（C2）=40，U3（C2）= B3f3（C3）=80，U3（C3）=

2、Bi 或 B2 或 B3f2（Di）=80，U2（Di）= Cif2（D2）=70，U2（D2）= C2fi（E）=110，Ui（E）= Di 或 D2所以可以得到以下最短路线,精品文库EtD -iC -iB 2 / B3A2、习题4 2欢迎下载103；解：1)将问题按地区分为三个阶段，三个地区的编号分别为1、2、2) 设Sk表示为分配给第k个地区到第n个地区的销售点数,Xk表示为分配给第k个地区的销售点数，Sk +1 = Sk XkPk(Xk)表示为Xk个销售点分到第k个地区所得的利润值fk(Sk)表示为Sk个销售点分配给第k个地区到第n个地区的最大利润值3) 递推关系式:fk(Sk)= m

3、ax P k(Xk)+ fk+i(Sk Xk) k=3,2,1f4(S4)= 04) 从最后一个阶段开始向前逆推计算第三阶段:设将S3个销售点(S3= 0,1,2,3,4)全部分配给第三个地区时，最大利润值为:f3(S3)= maxP3(X3) 其中 X3 = S3= 0,1,2,3,4表1X3S3P3(X3)f3(S3)*X3012340000112121222222336363447474第二阶段:设将S2个销售点（S2= 0,1,2,3,4）分配给乙丙两个地区时，对每一个S2值，都有一种最优分配方案，使得最大盈利值为:f2(S2)= max P 2(X2)+ f3(S2 X2)其中，X2

4、= 0,1,2,3,4表2S2P2(X2)+ f3(S2 X2)f2(S2)*X201234000010 + 1213+ 013120 + 2213+ 1224+ 025130 + 3613+ 2224+ 1234+ 0360,240 + 4713+ 3624 + 2234+ 1242+ 0491第一阶段:设将S1个销售点（S1= 4）分配给三个地区时，则最大利润值为:f1(S1)= max P 1(X1)+ f2(4 X1)其中，X1 = 0,1,2,3,4表3P 1(X1) + f2(4 X1)f1(4)X1*0123440 + 4916+ 3628 + 2540+ 1350+ 0532,

5、3然后按计算表格的顺序反推，可知最优分配方案有两个：最大总 利润为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台设备保持完好，并使产

6、值最 高。试求出四年内使得产值最高的施工方案和产值数。解：1)该问题分成四个阶段，k表示年度，k= 1,2,3,42) 设Sk表示为分配给第k年初拥有的完好挖掘设备数量,Uk表示为第k年初分配在超负荷下施工的挖掘设备数量,Dk (Sk)= Uk|0 Uk x2zQ,1,2FaxS + f1 13 0+ f1 260+ 仏）=max240,210,260= 260x1 = 0f2（2 ）= maxi 130x2 + max（80x1） =max130x2+ f1（2-3x2） x2T=f r （2 ）=80x1 = 1f3（6）= max260,260 = 260x1 = 0,x2 = 2,x3

7、 = 0x1 = 1, x2 = 0, x3 = 16、某工厂在一年进行了 A、B、C三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功的概率分别为0.40、0.60、0.80，因而都研制不成功的概率为0.4X 0.6X 0.8=0.192。为了促进三种新产品的研制，决定增援2万元的研制费，并要资金集中使用，以 万元为单位进行分配。其增援研制费与新产品不成功的概率如下表所示。试问如何分配费用，使这三秤新产品都研制不成功的概率为最小。新产品1不成功 ffi 率研制费5A3c0OJO(UO0血1OJO020.15OJO0.30解:1) ( 1分)将问题按产品A、B、C分为三个阶段，k=

8、1、2、3；2) ( 6分)设Sk表示第k阶段可分配给第k个产品到第n个产品的研制费，S1 = 2Xk设为决策变量，表示第k阶段分配给第k个产品的研制费。状态转移方程为 Sk+1 = Sk Xk允许决策集合：Dk(Sk) = Xk I 0 Xk Sk Xk为整数Pk(Xk)表示为第k个产品失败的概率fk(Sk)表示为Sk万元研制费分配给第k个产品到第n个产品的最小的失败概率3) (4分)递推关系式:fk(Sk) = min Pk(Xk) fk+i(Sk Xk) k=3,2,1边界条件：f4(S4)= 14) (11分)从最后一个阶段开始向前逆推计算第三阶段:设将S3万元研制费(S3= 0,1,

9、2)全部分配给C产品时，最小的失败概率为:f3(S3)= minP3(X3) 其中 X3 = S3= 0,1,2X3P3(X3)f3(S3)X3*01200.800.80010.500.50120.300.302X3*表示使得f3(S3)为最大值时的最优决策。第二阶段:设将S2万元研制费(S2= 0,1,2)分配给B、C产品时，最小的失败概率为:f2(S2)= min P2(X2) f3(S2-X2)其中，X2= 0,1,2P2(X2)ff3(S2- X2)f2(S2)*X201200.60 0.800.480.48010.60 0.500.300.40 0.800.320.30020.60 0.300.180.40 0.500.200.20 0.800.160.162第一阶段:设将S1万元研制费(S1= 2)分配给三个产品时，最小的失败概率为:f1(S1)= min P1(X1) f