课 制作:北景狸工夫吴新泉奇 器因翻 数学术
运筹学课件 制作：北京理工大学 吴祈宗等
第五章动态规为 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例
2 第五章 动态规划 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例 本章内容重点
1阶段决敢过程的量优化 多阶段决策问题 (Multi-Stage decision process) 多阶段决策过程特点: 决草L 决草L 决 决un 状态价段1 状态阶段2 状状~阶救k态状阶殷n/张走 →● Xk Xk+1 m+1 Tn
3 一 、多阶段决策问题 (Multi-Stage decision process) 多阶段决策过程特点: 状态 x1 阶段1 T1 决策u1 状态 x2 决策u2 阶段2 T2 状态 x3 ...状态 xk 决策uk 阶段k Tk 状态 xk+1 ...状态 xn 决策un 阶段n Tn 状态 xn+1 1.多阶段决策过程的最优化
身要阶段来求过程的艇戏化 动态规划方法与“时间”关系 很密切,随着时间过程的发展而决 定各时段的决策,产生一个决策序 列,这就是“动态”的意思。然而 它也可以处理与时间无关的静态后 题。只要在问题中人为地引入“时 段”因素,就可以将其转化为一个 多阶段决策问题。在本章中将介绍 这种处理方法
4 1.多阶段决策过程的最优化 动态规划方法与“时间”关系 很密切，随着时间过程的发展而决 定各时段的决策，产生一个决策序 列，这就是“动态”的意思。然而 它也可以处理与时间无关的静态问 题，只要在问题中人为地引入“时 段”因素，就可以将其转化为一个 多阶段决策问题。在本章中将介绍 这种处理方法
身要阶段来求过程的艇戏化 二、多阶段决策问题举例 属于多阶段决策类的问题很多 例如: 1)工厂生产过程:由于市场需求是 一随着时间而变化的因素·因此.为了 取得全年最佳经济效益,就要在全年的 生产过程中,逐月或者逐季度地根据库 存和鼎求情况决定生产计划安排
5 1.多阶段决策过程的最优化 二、多阶段决策问题举例 属于多阶段决策类的问题很多， 例如： 1)工厂生产过程：由于市场需求是 一随着时间而变化的因素，因此，为了 取得全年最佳经济效益，就要在全年的 生产过程中，逐月或者逐季度地根据库 存和需求情况决定生产计划安排
项多阶段决歌过程的圾优化 2)设备更新问题:一般企业用于生产 活动的设备,刚买来时故障少,经济效益 高,即使进行转让,处理价值也高,随着 使用年限的增加,就会逐渐变为故障多 维修费用增加,可正常使用的工时减少 加工质量下降,经济效益差,并且。使用 的年限越长、处理价值也越低,自然,如 果卖去旧的买新的,还翕要付出更新 费,因此就需要综合权衡决定设备的使用 年限,使总的经济效益最好
6 1.多阶段决策过程的最优化 2)设备更新问题：一般企业用于生产 活动的设备，刚买来时故障少，经济效益 高，即使进行转让，处理价值也高，随着 使用年限的增加，就会逐渐变为故障多， 维修费用增加，可正常使用的工时减少， 加工质量下降，经济效益差，并且，使用 的年限越长、处理价值也越低，自然，如 果卖去旧的买新的，还需要付出更新 费．因此就需要综合权衡决定设备的使用 年限，使总的经济效益最好
身要阶段来求过程的艇戏化 3)连续生产过程的控制问题: 般化工生产过程中,常包含 系列完成生产过程的设备,前 工序设备的输出则是后一工序设 备的输入,因此,应该如何根据 各工序的远行工况,控制生产过 程中各设备的输入和输出,以使 总产量最大
7 1.多阶段决策过程的最优化 3)连续生产过程的控制问题： 一般化工生产过程中，常包含一 系列完成生产过程的设备，前一 工序设备的输出则是后一工序设 备的输入，因此，应该如何根据 各工序的运行工况，控制生产过 程中各设备的输入和输出，以使 总产量最大
1多阶殷决过程的录龙化 以上所举问题的发展过程都与时j 因素有关,因此在这类多阶段决策问题 中,阶段的划分常取时间区段来表示, 并且各个阶段上的决策往往也与时间因 素有关,这就使它具有了“动态”的含 义,所以把处理这类动态问题的方法称 为动态规判方法。不过,实际中尚有许 多不包含时间因素的一类“静态”决策 问题。就其本质而言是一次决策问题 是非动恋决策问题。但是也可以人为地 引入阶段的概念当作多阶段决萆问题 应用动态规划方法加以解决
8 1.多阶段决策过程的最优化 以上所举问题的发展过程都与时间 因素有关，因此在这类多阶段决策问题 中，阶段的划分常取时间区段来表示， 并且各个阶段上的决策往往也与时间因 素有关，这就使它具有了“动态”的含 义，所以把处理这类动态问题的方法称 为动态规划方法。不过，实际中尚有许 多不包含时间因素的一类“静态”决策 问题，就其本质而言是一次决策问题， 是非动态决策问题，但是也可以人为地 引入阶段的概念当作多阶段决策问题， 应用动态规划方法加以解决
1多阶殷决过程的最龙化 4)资源分配问题:便属于这类静态 问题。如:某工业部门或公司,拟对其 所属企业选行稀缺资源分配,为此需要 制定出收益最大的资源分配方案。这种 问题原本要求一次确定出对各企业的资 源分配量,它与时间因素无关,不属动 态决策,但是,我们可以人为地规定 个资源分配的阶段和顺序,从而使其变 成一个多阶段决策问题(后面我们将详细 讨论这个问题)
9 1.多阶段决策过程的最优化 4）资源分配问题：便属于这类静态 问题。如：某工业部门或公司，拟对其 所属企业进行稀缺资源分配，为此需要 制定出收益最大的资源分配方案。这种 问题原本要求一次确定出对各企业的资 源分配量，它与时间因素无关，不属动 态决策，但是，我们可以人为地规定一 个资源分配的阶段和顺序，从而使其变 成一个多阶段决策问题(后面我们将详细 讨论这个问题)
身要阶段来求过程的艇戏化 5)运输网络问题:如图5-1所示的 运输网络,点间连线上的数字表示两地 距离(也可是运费、时间等),要求从 f(S)至的最短路线。 这种运输网络冋题也是静态决葉冋 题。但是,按照网络中点的分布,可以 把它分为4个阶段,而作为多阶段决策 问题来研究
10 1.多阶段决策过程的最优化 5）运输网络问题：如图5-1所示的 运输网络，点间连线上的数字表示两地 距离(也可是运费、时间等)，要求从 fk(sk)至v10的最短路线。 这种运输网络问题也是静态决策问 题。但是，按照网络中点的分布，可以 把它分为4个阶段，而作为多阶段决策 问题来研究