安徽大学：《运筹学》课程理论教案（PPT讲稿）第七章 动态规划

第七章 动态规划 多阶段决策过程的实例 动态规划的基本概念和基本原 理 动态规划模型的建立与求解 实用动态规戈划模型应用举例

3 第七章 动 态 规 划 多阶段决策过程的实例 动态规划的基本概念和基本原 理 动态规划模型的建立与求解 实用动态规划模型应用举例

第七章动态规划 在经济管理问题中，存在着大量的分阶段决 策问题，也就是说，一个决策问题，可以分解成 若干个相互联系，又相对独立的阶段，对于每一 个阶段，存在着很多方案可供选择， 我们要对每 个阶段做出一个决策，从而形成一个决策序列 称为策略；而各阶段之间，它们又有密切的联系， 某一个阶段的不同决策，将会对其他阶段的决策 产生重大的影响

4 在经济管理问题中，存在着大量的分阶段决 策问题，也就是说，一个决策问题，可以分解成 若干个相互联系，又相对独立的阶段，对于每一 个阶段，存在着很多方案可供选择，我们要对每 个阶段做出一个决策，从而形成一个决策序列， 称为策略；而各阶段之间，它们又有密切的联系， 某一个阶段的不同决策，将会对其他阶段的决策 产生重大的影响。 第七章 动 态 规 划

第七章动态规划 某个阶段局部的较优方案，未必是整个问题 的最好方案，某个阶段局部的不好方案，也未必 是整个问题的不好方案，我们要寻找的是整个问 题，也就是所有阶段总体的一个最优方案，这就 是本章动态规划所要讨论的问题

5 某个阶段局部的较优方案，未必是整个问题 的最好方案，某个阶段局部的不好方案，也未必 是整个问题的不好方案，我们要寻找的是整个问 题，也就是所有阶段总体的一个最优方案，这就 是本章动态规划所要讨论的问题。 第七章 动 态 规 划

第七章动态规划 动态规划Dynamic Programming)是运筹学 的一个分支，它是解决多阶段决策问题的一种数 学方法。1957年美国数学家贝尔曼Richard Bellman)写出了动态规划的第一本著作“动态规 划”，提出了多阶段决策问题的“最优化原理” 不久又出版了该书的第二版和第三版。以后又有 其他数学家陆续写出了有关动态规划的著作，这 样就逐步形成了运筹学的一个分支

6 动态规划(Dynamic Programming)是运筹学 的一个分支，它是解决多阶段决策问题的一种数 学方法 。 1957 年美 国 数 学家 贝 尔曼 (Richard Bellman)写出了动态规划的第一本著作“动态规 划” ，提出了多阶段决策问题的“最优化原理” 。 不久又出版了该书的第二版和第三版。以后又有 其他数学家陆续写出了有关动态规划的著作，这 样就逐步形成了运筹学的一个分支。 第七章 动 态 规 划

第七章动态规划 随着电子计算机的迅速发展，更为动态规划 的实际应用创造了有利条件 目前动态规划已成功地应用到了经济学、管 理科学、现代控制论、资源理论、网络流及其他 许多领域。 7

7 随着电子计算机的迅速发展，更为动态规划 的实际应用创造了有利条件。 目前动态规划已成功地应用到了经济学、管 理科学、现代控制论、资源理论、网络流及其他 许多领域。 第七章 动 态 规 划

第一节多阶段决策过程的实例 所谓多阶段决策问题是有这样一类决策过程， 它可以划分为若干个相互联系的阶段，在每一阶 段都有若干种方案可供选择，选择哪一种方案需 要做出决策，这样就形成一个决策序列，通常称 为一种策略。不同的策略就产生不同的效果，在 所有可能的策略当中，选择一个效果最好的最优 策略，就是解决多阶段决策问题的主要目的。下 面举几个例子来说明

8 所谓多阶段决策问题是有这样一类决策过程， 它可以划分为若干个相互联系的阶段，在每一阶 段都有若干种方案可供选择，选择哪一种方案需 要做出决策，这样就形成一个决策序列，通常称 为一种策略。不同的策略就产生不同的效果，在 所有可能的策略当中，选择一个效果最好的最优 策略，就是解决多阶段决策问题的主要目的。下 面举几个例子来说明。 第一节 多阶段决策过程的实例

第一节多阶段决策过程的实例 例1（投资决策问题一家公司有三个工厂 每个厂都需要进行扩建。公司用于扩建的资金总 额为400万元。各个厂的投资方案以及扩建后预 期可获得的年利润如表5-1所示（单位：万元）。现 在公司要确定对各厂投资多少才能使公司的总利 润达到最大。 9

9 例1 (投资决策问题)一家公司有三个工厂， 每个厂都需要进行扩建。公司用于扩建的资金总 额为400万元。各个厂的投资方案以及扩建后预 期可获得的年利润如表5-1所示(单位：万元)。现 在公司要确定对各厂投资多少才能使公司的总利 润达到最大。 第一节 多阶段决策过程的实例

第一节多阶段决策过程的实例 投资额（百万元） 厂名 0 1 2 3 4 一厂 38 41 48 60 66 二厂 40 42 50 60 66 三厂 48 64 68 78 76 表7-1例1的数据 10

10 第一节 多阶段决策过程的实例 厂名 投资额（百万元） 0 1 2 3 4 一厂 38 41 48 60 66 二厂 40 42 50 60 66 三厂 48 64 68 78 76 表7-1 例1的数据

第一节多阶段决策过程的实例 解：在这个问题中，因为每个厂 都有几种投 资方案，所以要对每个厂做出一项决策，总共要 做出三个决策。同时，这三个厂的总投资不能超 过4百万元。如果我们依次考虑工厂1，工厂2和工 厂3的投资，把对每个工厂的投资看成是一个阶段， 这就是一个多阶段的决策问题。 11

11 解：在这个问题中，因为每个厂都有几种投 资方案，所以要对每个厂做出一项决策，总共要 做出三个决策。同时，这三个厂的总投资不能超 过4百万元。如果我们依次考虑工厂1，工厂2和工 厂3的投资，把对每个工厂的投资看成是一个阶段， 这就是一个多阶段的决策问题。 第一节 多阶段决策过程的实例

第一节多阶段决策过程的实例 对于工厂3来说，可能的投资数量为0,1,2， 3,4百万元；对于工厂3和2来说，可能的投资数 量为0,1,2,3,4百万元；对于工厂1、2和3来 说，可能的投资数量为0,1,2,3,4百万元。考 虑到投资越多，利润越多，目标是求出最大利润 所以对于工厂1、2和3来说，当总投资额小于4百 万元时不可能获得最优解

12 对于工厂3来说，可能的投资数量为0，1，2， 3，4百万元；对于工厂3和2来说，可能的投资数 量为0，1，2，3，4百万元；对于工厂1、2和3来 说，可能的投资数量为0，1，2，3，4百万元。考 虑到投资越多，利润越多，目标是求出最大利润， 所以对于工厂1、2和3来说，当总投资额小于4百 万元时不可能获得最优解。 第一节 多阶段决策过程的实例