《运筹学》课程教学资源（PPT课件讲稿）第四章 动态规划 4.1 引言与内容框架

第四章动恋规 2

第四章 动 态 规 划

4-1引言及内容框架 本节要点 动态规划的研究对象和特点 静态决策问题的动态处理 动态规划部分内容框架

4-1 引言及内容框架 本节要点 ◼ 动态规划的研究对象和特点 ◼ 静态决策问题的动态处理 ◼ 动态规划部分内容框架

动态规圳的研究对象 多阶段决策问题 1、多阶段决策问题 1)动态决策—将时间作为变量的决策问题称 为动态决策,其基本特点是多次决策。 2)多阶段决策问题是一类特殊形式的动态决策 问题。是指这样一类活动过程:系统的动态 过程可以按照时间进程分为状态相互联系而 又相互区别的各个阶段,而且在每个阶段都 要进行决策,当每一阶段的决策确定以后, 就完全确定了一个过程的活动路线

一、动态规划的研究对象 ─多阶段决策问题 1、多阶段决策问题 1) 动态决策──将时间作为变量的决策问题称 为动态决策，其基本特点是多次决策。 2) 多阶段决策问题是一类特殊形式的动态决策 问题。是指这样一类活动过程：系统的动态 过程可以按照时间进程分为状态相互联系而 又相互区别的各个阶段，而且在每个阶段都 要进行决策，当每一阶段的决策确定以后， 就完全确定了一个过程的活动路线

多阶段决策问题的典型例子: 今企业在生产过程中,由于需求是随着时间变 化的因素,因此企业为了获得全年最佳经济效 益,就要在整个生产过程中逐月或逐季的根据 库存和需求决定生产计划。 某种机器,可以在高、低两种负荷下生产 高负荷下生产的产量多,但每生产一个阶段后 机器的完好率低;低负荷下生产时的情况则相 反。现在需要安排该种机器在多个阶段内的生 产,问应该如何决定各阶段中机器的使用,使 整个计划期内的总产量最大

多阶段决策问题的典型例子： ❖企业在生产过程中，由于需求是随着时间变 化的因素，因此企业为了获得全年最佳经济效 益，就要在整个生产过程中逐月或逐季的根据 库存和需求决定生产计划。 ❖某种机器，可以在高、低两种负荷下生产。 高负荷下生产的产量多，但每生产一个阶段后 机器的完好率低；低负荷下生产时的情况则相 反。现在需要安排该种机器在多个阶段内的生 产，问应该如何决定各阶段中机器的使用，使 整个计划期内的总产量最大

某台设备,例如汽车,刚买来时故障少,耗 油低,出车时间长,处理价值和经济效益高 随着使用时间的增加则变为故障多,耗油高, 维修费用增加,经济效益差。使用时间愈长, 处理价值也愈低。另外,每次更新都要付出 更新费用。因此,应当如何决定设备的使用 年限,使总的效益最佳

❖某台设备，例如汽车，刚买来时故障少，耗 油低，出车时间长，处理价值和经济效益高。 随着使用时间的增加则变为故障多，耗油高， 维修费用增加，经济效益差。使用时间愈长， 处理价值也愈低。另外，每次更新都要付出 更新费用。因此，应当如何决定设备的使用 年限，使总的效益最佳

心化工生产过程包含一系列的过程设备,如 反应器、蒸馏塔、吸收器等等,前一设备的 输出是后一设备的输入。因此,应该如何控 制生产过程中各个设备的输出和输入,使总 立量最大。 发射一枚火箭去击中运动中的目标。由于 目标的行动是不断改变的,因此应如何根据 目标运动情况,不断调整火箭飞行的方向与 速度,使之最快地命中目标,等等

❖化工生产过程包含一系列的过程设备，如 反应器、蒸馏塔、吸收器等等，前一设备的 输出是后一设备的输入。因此，应该如何控 制生产过程中各个设备的输出和输入，使总 产量最大。 ❖发射一枚火箭去击中运动中的目标。由于 目标的行动是不断改变的，因此应如何根据 目标运动情况，不断调整火箭飞行的方向与 速度，使之最快地命中目标，等等

2什么是动态规划? DP是运筹学OR的一个分支,是解决多阶 段决策过程最优化的一种方法或是一种分析多 阶段决策过程的数学方法,这种方法可根据人 们所采取的措施,一步步地控制过程的发展, 以实现预定的要求。 这一运筹学分支最初是由美国数学家 Bellman等人根据一类多阶段决策问题的特性, 提出了解决这类问题的最优化原理,并研究了 许多实际问题而建立起来的

2.什么是动态规划？ DP是运筹学OR的一个分支，是解决多阶 段决策过程最优化的一种方法或是一种分析多 阶段决策过程的数学方法，这种方法可根据人 们所采取的措施，一步步地控制过程的发展， 以实现预定的要求。 这一运筹学分支最初是由美国数学家 Bellman等人根据一类多阶段决策问题的特性， 提出了解决这类问题的最优化原理，并研究了 许多实际问题而建立起来的

3动态规划方法的特点 优点: ①许多问题用动态规划研究求解比线性规 划、非线性规划更有效,特别是离散性问题, 解析数学无用武之地,而动态规划成为得力 工具; ②某些情况下,用动态规划处理不仅能作 定性描述分析,且可利用计算机给出求其数 值解的方法

3.动态规划方法的特点 ☺ 优点： ①许多问题用动态规划研究求解比线性规 划、非线性规划更有效，特别是离散性问题， 解析数学无用武之地，而动态规划成为得力 工具； ②某些情况下，用动态规划处理不仅能作 定性描述分析，且可利用计算机给出求其数 值解的方法

⊙缺点: ①没有统一的处理方法,求解时要根据问 题的性质,结合多种数学技巧。因此,实践 经验及创造性思维将起重要的引导作用。 ②“维数障碍”:当变量个数太多时,由 于计算机内存和速度的限制导致问题无法解 决。有些问题由于涉及的函数没有理想的性 质使问题只能用动态规划描述,而不能用动 态规划方法求解

缺点： ①没有统一的处理方法，求解时要根据问 题的性质，结合多种数学技巧。因此，实践 经验及创造性思维将起重要的引导作用。 ②“维数障碍”：当变量个数太多时，由 于计算机内存和速度的限制导致问题无法解 决。有些问题由于涉及的函数没有理想的性 质使问题只能用动态规划描述，而不能用动 态规划方法求解

靜决策问蕙的动态处嬃 不包含时间因素的决策问题称为静态决策 问题,是一次性决策(如线性规划)。但若 能恰当地人为引入“时段”概念,就可以把 问题转化成一个多阶段决策问题,这样就能 用动态规划去处理了。 这样的例子是大量的(如最短路线问题, 资源分配问题等等)

二、静态决策问题的动态处理 不包含时间因素的决策问题称为静态决策 问题，是一次性决策（如线性规划）。但若 能恰当地人为引入“时段”概念，就可以把 问题转化成一个多阶段决策问题，这样就能 用动态规划去处理了。 这样的例子是大量的（如最短路线问题， 资源分配问题等等）