运筹第07章-OR.ppt

课堂练习 若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？ 课堂练习 (载货问题) 现有载重量为20吨的卡车，装用3种不同的货物．已知这3种货物的单件重量和装载收费如表所示，又规定2号货物和3号货物都至多装两件．问如何装载这3种货物，可使该车一次运输的货物收费最多? 3.动态规划方法的基本步骤 (3)决策变量uk，表示第k年度中分配于高负荷下生产的机床台数。于是sk- uk便为该年度中分配于低负荷下生产的机床台数． 这里sk与uk均取连续变量，当它们有非整数数值时．可以这样理解：如sk＝0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.4时，就表示一台机床在 k年度只有4/10的时间于高负荷下工作． 2．状态转移方程为 k=1，2，…,6 3.动态规划方法的基本步骤 3．允许决策集合,在第k段为 4．目标函数。设gk(sk,uk)为第k年度的产量，则gk(sk,uk)=8uk+5(sk-uk),因此，目标函数 为 k＝1,2,．．．,5 5．条件最优目标函数递推方程。 令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第5年度结束这段时间的产品产量，根据最优化原理有以下递推关系： k=1,2,3,4,5 3.动态规划方法的基本步骤 6.边界条件为 下面采用逆序递推计算法,从第5年度开始递推计算。 k=5时有 显然，当u5*=s5时，f5(s5)有最大值，相应的有f5(s5)=8s5 k=4时有 3.动态规划方法的基本步骤 k=3 时有 可见，当u3*=s3时，f3(s3)有最大值f3(s3) =17.55s3. k=2 时有 = + = 此时，当取u2*=0时有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1) 3.动态规划方法的基本步骤 k=1时有 + = 当取u1*=0时, f1(s1)有最大值，即f1(s1)=23.7s1,因为s1=1000,故f1(s1)=23700个产品． 按照上述计算顺序寻踪得到下述计算结果： 3.动态规划方法的基本步骤 上面所讨论的最优决策过程是所谓始端状态s1固定，终端状态s6自由．如果终端也附加上一定的约束条件，那么计算结果将会与之有所差别．例如，若规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？ 3.动态规划方法的基本步骤 解：由状态转移方程 有 得 显而易见，由于固定了终端的状态s6，第五年的决策变量U5的允许决策集合U5(s5)也有了约束，上式说明U5(s5)已退化为一个点，即第五年投入高负荷下生产的机床数只能由式U5=4.5s5-2500作出一种决策，故 3.动态规划方法的基本步骤 当k=5时有 当k=4时有 显然，只有取u4*=0 ，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理类推 3.动态规划方法的基本步骤 k=3时有 可知,当u3*=0时,f3(s3)有最大值f4(s4)=24.5s3-7500. k=2时有 此时,当u2*=0时有最大值,即 f2(s2)=27.1s2-7500 3.动态规划方法的基本步骤 k=1时有 只有取u1*=0时,f1(s1)有最大值，即 f1(s1)=29.4s1-7500 。 由此可见，为了使下一个五年计划开始的一年有完好的机床500台，其最优策略应该为：在前4年中，都应该把全部机床投人低负荷下生产，在第5年，只能把部分完好机投入高负荷下生产。根据最优策赂，从始端向终端递推计算出各年的状态，即算出每年年初的完好机床台数，因为s1＝1000台，于是有 3.动态规划方