运筹学第07章.ppt

1第7章动态规划动态规划 2本章内容重点?多阶段决策过程的最优化问题特点?动态规划的基本概念、基本原理和求解思路?离散型动态规划求解方法?连续型动态规划求解方法?动态规划方法应用举例 3 引例一、某运输公司拟将一大型设备从下列交通网络的 A点运输到 F点,试用动态规划求从 A到F的最短路径。 A DDD EE F 123 12 123 12 52 164373 3 325427 10 897 119 12 134 引例二、某企业生产某种产品,每月月初按订货单发货,生产的产品随时入库,仓库最多能够贮存产品 90千件。在 1至6月其生产成本和产品订单的需求数量情况如下表: 已知上一年底库存量为 40千件,要求 6月底库存量仍能够保持 40千件。问:如何安排这6个月的生产量,使既能满足各月的定单需求,同时生产成本最低。 44 67 32 50 63 35 需求量(rk)(千件) 生产成本(ck) (万元/千件) 654321 月份(k) 成本与需求多阶段决策过程特点: 状态 x 1阶段 1T 1决策 u 1状态 x 2决策 u 2阶段 2T 2状态 x 3... 状态 x k决策 u k阶段 kT k状态 x k+1... 状态 x n决策 u n阶段 nT n状态 x n + 多阶段决策问题( Multi-Stage decision process ) . 多阶段决策过程的特点动态规划方法与“时段”关系很密切: “动态”表现在——随着时段过程的发展而决定各时段的决策,产生一个决策序列。?时段可以是客观实际。?在处理与时间无关的静态问题时,也可以通过在问题中人为地引入“时段”因素,将其转化为一个多阶段决策问题。 多阶段决策问题举例 1) 工厂生产过程:由于市场需求是一随着时间而变化的因素,因此, 为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。 多阶段决策问题举例 2) 设备更新问题: 一般用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费。因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。 多阶段决策问题举例 3) 连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。 多阶段决策问题举例实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题, 应用动态规划方法加以解决。