动态规划之二--机器负荷问题

1、案例4机器负荷分配问题某机器可以在高、低两种不同的负荷下进行生产。高负荷下生产时，产品年产量s, 8u1，式中u1为投入生产的机器数量，机器的年折损率为a 07，即年初完好的机器数量为U,年终就只剩下u,台是完好的，其余均需维修或报废。在低负荷下生产，产品年 产量S 5u2，式中u2为投入生产的机器数量，机器的年折损率为x, 1000台，要求制定一个五年计划，在每年开始时决定如何重新分配好机器在两种不同负荷下工作的数量，使产品五年的总产量最高。模型分析 设阶段变量k表示年度，状态变量 xk是第k年初拥有的完好机器数量。 k 0时它也是k 1年度末的完好机器数量，决策变量xk规定为第k年度中分配

2、在高负荷下生产的机器数量。于是 Xk Uk是该年度分配在低负荷下生产的机器数量。这里与前面几 个例子不同的是 xk，uk的非整数值可以这样来理解：例如xk =表示一台机器在该年度正常工作时间只占60%； uk=表示一台机器在该年度的 3/10时间里在高负荷下工作。此时状态 转移方程为Xk 10.7Uk0.9( XkUk),k 1, 2,5k阶段的允许决策集合是Dk (Xk )Uk0UkXk 第k年度产品产量是Vk (Xk ,u k )8Uk5(Xk -U k )指数函数是5Vk8Uj5(XjUj)j k最优值函数为fk （Xk）第k年初从Xk出发到第5年度结束产品产量的最大值由最优化原理得递推

3、关系为 fk （xk）mqx、8Uk 5（Xk Uk） fk i0.7Uk 09（Xk uQuk Dk（xk）边界条件是f6（X6）0 ,计算过程如下：k 5时,f5（X5）max8u50 U5 X55(X5 U5)f6【0.7U50.9(x5U5)max8us0 U5 x/ r5(X5U5)max3us0 U5 X55X5因为f5的表示式是u5的单调函数，所以最优决策*U5 = X5，f5 (X5)=8 X5 ；k 4时，f4（X4）max 8U40 U4 X45(X4U4)f5【0.7U409(X4U4)max 8u40 u4 x45(X4U4)80.7u40.9(x4U4)max1.4u

4、40 U4 X412.2X4同理，最优决策u4 :=x4，f4(X4)= X4，依次可以*U3X3,f3（X3）=17.6x3*U20,f2（X2）=20.8x2*U10,f1 (X1)=23.7x1因为 X1=1000，所以 f1（xj=23700 （台）。从上面的计算可知，最优策略是前两年将全部完好机器投入低负荷生产，后3年将全部 机器投入高负荷生产，最高产量是 23700 台。在一般情况下，如果计划是 n 年度，在高、低负荷下生产的产量函数分别是s1 cu1 ，s du2, c 0,d0, c d，年折损率分别为a和b, 0 a b 1，则应用上例相似的办法可以求出最优策略是， 前若干年

5、全部投入低负荷下生产。 由此还可看出， 应用动态规 划可以在不求出数量值解的情况下确定最优策略的结构。终端状态固定的情形。如果要求在第 5 年末完好的机器数量是 500 台，即 x6 =500，于 是由状态转移方程得x60.7u6 0.9(x5 u5) 500即u5 4.5x5 2500这时允许决策集合 D5(x5) 退化为一个点，第5 年度投入高负荷生产的机器数只能由式(3-29 )作出一种决策，所以f 5(x5)max8u5 5(x5 u5)max3u5 5x50 u5 x50 u5 x5=3( x5)+5 x5=x5利用递推关系， k 4 时，f4( x4) max8u4 5(x4 u4

6、) f5(x5)0 u4 x4max8u4 5(x4 u4) 1 8.5 0.7u4 0.9( x4 u4) 75000 u4 x4max21.654x4 0.7u4 75000 u4 x4显然有最优策略：u4 =0， f 4 (x4 )=x4x4 依次相似可得*u3*0,f3(x3)=24.5x 3 -7500*u2*0,f 2(x 2 )= 27.1x 2-7500*u1*0,f 1(x 1) =29.4x1 -7500由此可见为满足第 5 年度末完好机器为 500 台的要求，而又要使产品产量最高，则前 4 年 均应全部在低负荷下生产，而在第 5 年又将部分机器投入高负荷生产。经过计算 x5=656，