管理运筹学讲义-第6章动态规划.pptVIP

第6章动态规划;第6章动态规划;一、多阶段决策问题

在生产经营活动中，某些问题决策过程可以划分为假设干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响下一阶段的开展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。;二、多阶段决策问题举例;例2设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费。因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。;以上所举问题的开展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。;例3资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。;第一节多阶段决策;特别注意：

动态规划求解的多阶段决策问题的特点：

适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的开展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。比方国家政策的制定。;第二节动态规划原理;第二节动态规划原理;第二节动态规划原理;第二节动态规划原理;第二节动态规划原理;小结:;解多阶段决策过程问题，求出;第二节动态规划原理;第三节逆序求解过程;第三节逆序求解过程;第三节逆序求解过程;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;第四节动态规划举例;某种机床，可以在上下不同的负荷下生产，在高负荷下生产时，产品的年产量与年初投入机床数量u1的关系为8u1，年终机床完好台数为0.7u1。在低负荷下生产时，产品的年产量和投入机床数量的关系为5u2，年终机床完好台数将为0.9u2。假设某厂开始有1000台完好的机床，现要制定一个五年生产方案，问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为最高。;2.状态变量：用sk表示第k年度初拥有的完好机床台数。;4．状态转移方程为：;6．条件最优目标函数递推方程;下面采用逆序递推计算法,从第5年度开始递推计算．;K=4时有：;K=3时有：;此时，当u2*=0时有最大值，即f2(s2)=20.8s2,其中s2=0.7u1+0.9(s1-u1);按照上述计算顺序寻踪得到下述计算结果：;上面所讨论的最优决策过程是所谓始端状态固定，终端状态自由．如果终端也附加上一定的约束条件，那么计算结果将会与之有所差异．例如，假设规定在第五个年度结束时，完好的机床数量为500台(上面只有278台)，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？;有;显然，只有取u4*=0,有最大值f4(s4)=21.7s4-7500;当k=3时有:;当k=2时有:;当k=1时有:;;某公司拥有资金10万元，假设投资于工程i(i＝1，2，3)的投资额为xi时，其收益分别为g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资数额才能使总收益最大?;满足;2.状态变量：用sk表示已经对第1至第k-1个工程投资后的剩余资金；即第k段初拥有的可以分配给第k到第3个工程的资金额〔单位：万元〕。;6.根本方程为：;当k=3时：;