第二讲动态规划讲述.ppt

第二讲 动态规划 讲授：白丹宇 本章内容 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 是运筹学的一个主要分支 是解决多阶段决策过程的最优化的一种方法多阶段决策过程： 动态规划 模型分类 §1多阶段决策过程的最优化 1.多阶段决策过程的最优化 动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。 2.多阶段决策问题举例 属于多阶段决策类的问题很多，例如 1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。 例1：某厂与用户签订了如表所示的交货合同，表中数字为月底的交货量。该厂的生产能力为每月400件，该厂仓库的存货能力为300件。已知每百件货物的生产费用为10000元。在进行生产的月份，工厂还要支付经常费4000元。仓库保管费为每百件货物每月1000元。假设开始时及6月底交货后无存货。 2)设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。 例2：下表给出了某单位的预测数据，现决定考虑到1998年（n=5），试作5年内的设备更新计划 3)连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。 以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。 不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。 4）资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。 例3：某工厂生产A、B、C三种产品，都使用某种原材料，现有原材料4吨。将不同数量的这种原料分配给各种产品时产生的收益如表所示，试确定使总收益最大的分配法。 5）运输网络问题：如图7-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从A至F的最短路线。 这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为5个阶段，而作为多阶段决策问题来研究。 本章内容 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 5.2 动态规划的基本概念 5.3 动态规划的基本思想 课堂练习 用动态规划方法求最短路 先从F开始，因为F是终点。再无后继过程，故可以接着考虑第5阶段上所有可能状态E1，E2的最优后续过程。因为从E1 ,E2到F的路线是唯一的，所以E1，E2的最优决策和最优后继过程就是到F，它们的最短距离分别是4和3。 接着考虑阶段4上可能的状态D1，D2，D3 到F的最优决策和最优后继过程．在状态D1上，到E1是3，到E2是5，综合考虑后继过程整体最优，取最优决策是到E1,最优后继过程是D1→E1→F ，最短距离是7。同理，状态D2的最优决策是至E2 ；D3的最优决策是到E1。 同样，当阶段4上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段3上所有可能状态的最优决策和最优后继过程，如C1的最优决策是到D1,最优路线是C1→D1→E1→F ，最短距离是12…依此类推，最后可以得到从初始状态A的最优决策是到F最优路线是A→B1→C2→D2→E2 →F ，全程的最短距离是17。图7—1中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。 综上所述可见，全枚举法虽可找出最优方案