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