北京理工大学：《运筹学》课程PPT教学课件（Operations Research）第5章 动态规划

第五章动态规判 本章内容重点 多阶段决策过程的最优化 动态规判的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例

2 第五章 动态规划 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例 本章内容重点

,多阶段决耽过程的最化 一、多阶段决策同题 动态规划是把多阶段决策问题作 为研究对象。所谓多阶段决策问题 是指这样一类活动过程,即根据冋 题本身的特点。可以将其求解的全 过程判分为若干个相互联系的阶段 (即将问题划分为许多个相互联系的 子问题),在它的每一阶段都需要作 出决策。并且在一个阶段的决策确 定以后再转移到下一个阶段

3 1.多阶段决策过程的最优化 一 、多阶段决策问题 动态规划是把多阶段决策问题作 为研究对象。所谓多阶段决策问题， 是指这样一类活动过程，即根据问 题本身的特点，可以将其求解的全 过程划分为若干个相互联系的阶段 (即将问题划分为许多个相互联系的 子问题)，在它的每一阶段都需要作 出决策，并且在一个阶段的决策确 定以后再转移到下一个阶段

录阶段夹菜过程的提花化 往往前一个阶段的决策要影响 到后一个阶段的决策,从而影响整 个过程。人们把这样的决策过程称 做多阶段决策过程⑩ulti- Stagedecision process)o 各个阶段所确定的决策就构 成了一个决策序列,称为一个策略。 般來说,由于每一阶段可供选择 的决策往往不止一个,因此,对于 整个过程,就会有许多可供选择的 策略。 4

4 1.多阶段决策过程的最优化 往往前一个阶段的决策要影响 到后一个阶段的决策，从而影响整 个过程。人们把这样的决策过程称 做多阶段决策过程(Multi-Stagedecision process)。各个阶段所确定的决策就构 成了一个决策序列，称为一个策略。 一般来说，由于每一阶段可供选择 的决策往往不止一个，因此，对于 整个过程，就会有许多可供选择的 策略

,多阶段决耽过程的恍化 若对应于一个策略.可以由一 个量化的指标來确定这个策略所对 应的活动过程的效果.那么,不同 的策略就有各自的效果。在所有可 供选择的策略中,对痖效果最好的 策略称为最优策略。把一个问题划 分成若千个相互联系的阶段选取其 最优策略,这类问题就是多阶段决 策问题

5 1.多阶段决策过程的最优化 若对应于一个策略，可以由一 个量化的指标来确定这个策略所对 应的活动过程的效果，那么，不同 的策略就有各自的效果。在所有可 供选择的策略中，对应效果最好的 策略称为最优策略。把一个问题划 分成若干个相互联系的阶段选取其 最优策略，这类问题就是多阶段决 策问题

,多阶段决耽过程的恍化 多阶段决策过程最优化的目标是要 达到整个活动过程的总体效果最优。由 于各段决策间有机地联系着,本段决策 的执行将影响到下一段的决策,以至于 影响体效果,所以决策者在每段决策 时不应仅考虑本阶段最优,还应考虑对 最终目标的影响,从而作出对全局来讲 是最优的决策。动态规划就是符合这种 要求的一种决策方法

6 1.多阶段决策过程的最优化 多阶段决策过程最优化的目标是要 达到整个活动过程的总体效果最优。由 于各段决策间有机地联系着，本段决策 的执行将影响到下一段的决策，以至于 影响总体效果，所以决策者在每段决策 时不应仅考虑本阶段最优，还应考虑对 最终目标的影响，从而作出对全局来讲 是最优的决策。动态规划就是符合这种 要求的一种决策方法

,多阶段决耽过程的恍化 由上述可知,动态规划方法与 “时间”关系很密切,随着时间过 程的发展而决定各时段的决策。产 生一个决策序列,这就是“动态” 的意思。然而它也可以处理与时 无关的静态问题。只要在问题中人 为地引入“时段”因素,就可以将 其转化为一个多阶段决策问题。在 本章中将介绍这种处理方法

7 1.多阶段决策过程的最优化 由上述可知，动态规划方法与 “时间”关系很密切，随着时间过 程的发展而决定各时段的决策，产 生一个决策序列，这就是“动态” 的意思。然而它也可以处理与时间 无关的静态问题，只要在问题中人 为地引入“时段”因素，就可以将 其转化为一个多阶段决策问题。在 本章中将介绍这种处理方法

,多阶段决耽过程的最化 二、多阶段决草问题举例 属于多阶段决策类的问题很多 例如 1)工厂生产过程:由于市场需求是 随着时间而变化的因素,因此。为了 取得全年最佳经济效益,就要在全年的 生产过程中。逐月或者逐季度地根据库 存和需求情况决定生产计划安排

8 1.多阶段决策过程的最优化 二、多阶段决策问题举例 1)工厂生产过程：由于市场需求是 一随着时间而变化的因素，因此，为了 取得全年最佳经济效益，就要在全年的 生产过程中，逐月或者逐季度地根据库 存和需求情况决定生产计划安排。 属于多阶段决策类的问题很多， 例如：

多阶段决对程的最龙化 2)设备更新问题:一般企业用于生 活动的设备,刚买来时故障少,经济效益 高,即使进行转让,处理价值也高,随着 使用年限的增加,就会逐渐变为故障多 维修费用增加,可正常使用的工时藏少, 加工质量下降,经济效益差,并且,使用 的年限越长、处理价值也越低。自然,如 果卖去旧的买新的,还需要付出更新 费,因此就需要综合权衡决定设备的使用 年限,使总的经济效益最好

9 1.多阶段决策过程的最优化 2)设备更新问题：一般企业用于生产 活动的设备，刚买来时故障少，经济效益 高，即使进行转让，处理价值也高，随着 使用年限的增加，就会逐渐变为故障多， 维修费用增加，可正常使用的工时减少， 加工质量下降，经济效益差，并且，使用 的年限越长、处理价值也越低，自然，如 果卖去旧的买新的，还需要付出更新 费．因此就需要综合权衡决定设备的使用 年限，使总的经济效益最好

,多阶段决耽过程的最化 3连焕生产过程的控制问题 般化工生产过程中,常包含 系列完成生产过程的设备,前 工序设备的输出则是后一工序设 备的输入,因此,应该如何根据 各工序的远行工况,控制生产过 程中各设备的输入和输出,以使 总产量最大

10 1.多阶段决策过程的最优化 3)连续生产过程的控制问题： 一般化工生产过程中，常包含一 系列完成生产过程的设备，前一 工序设备的输出则是后一工序设 备的输入，因此，应该如何根据 各工序的运行工况，控制生产过 程中各设备的输入和输出，以使 总产量最大

1多阶段决过程的最优化 以上所举问题的发展过程都与时间因 傃素有关,因此在这类多阶段决策问题中, 阶段的划分常取时间区段来表示,并且各 个阶段上的决策往往也与时间因素有关 这就使它具有了“动态”的含义。所以把 处理这类动态问题的方法称为动态规划方 法。不过,实际中尚有许多不包含时间因 素的一类“静态”决策问题,就其本质而 言是一次决策冋题,是非动态决策冋题 但是也可以人为地引入阶段的概念当作多 阶段决策问题。应用动态规划方法加以解 决

11 1.多阶段决策过程的最优化 以上所举问题的发展过程都与时间因 素有关，因此在这类多阶段决策问题中， 阶段的划分常取时间区段来表示，并且各 个阶段上的决策往往也与时间因素有关， 这就使它具有了“动态”的含义，所以把 处理这类动态问题的方法称为动态规划方 法。不过，实际中尚有许多不包含时间因 素的一类“静态”决策问题，就其本质而 言是一次决策问题，是非动态决策问题， 但是也可以人为地引入阶段的概念当作多 阶段决策问题，应用动态规划方法加以解 决