动规 Dynamic Programming(DP 第七章 动态规划
1 动态规划 Dynamic Programming（DP） 第七章 动态规划
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化 的一种非常有效的方法。1951年,美国数学家贝尔曼(R Bellman)等人,根据一类多阶段决策问题的特点,把多阶段决策 问题变换为一系列相互联系的单阶段决策问题,然后分阶段逐个加 以解决。贝尔曼等人在研究和解决了大量实际问题之后,提出了解 决这类问题的—所谓“最优性原理”,通常称为“贝尔曼最优化 原理”,从而创建了解决最优化问题的一种新的方法——动态规 划—( Dynamic Programming)。贝尔曼的名著《动态规划》 于1957年出版,这成了动态规划的第一本著作
2 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化 的一种非常有效的方法。1951年，美国数学家贝尔曼（ R . Bellman ）等人，根据一类多阶段决策问题的特点，把多阶段决策 问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加 以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解 决这类问题的——所谓“最优性原理”，通常称为“贝尔曼最优化 原理”，从而创建了解决最优化问题的一种新的方法 —— 动态规 划 ——（Dynamic Programming ）。贝尔曼的名著《动态规划》 于1957年出版，这成了动态规划的第一本著作
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 动态规划的方法,在工程技术、企业管理、工农业生产及军事 等部门中有着广泛的应用,并且获得了显著的效果。在经济管理方 面,动态规划可以用来解决最优路径问题、资源分配问题、生产调 度问题、库存问题、装载问题、排序问题、设备更新问题、生产过 程最优控制问题等等,他是现代企业管理中的一种重要的决策方法。 许多实际问题采用动态规划方法去处理,常比线性规划或非线 性规划更加有效。特别对于离散性的问题,由于解析数学无法施展 其术,而动态规划的方法就成为一种非常有效的工具
3 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 动态规划的方法，在工程技术、企业管理、工农业生产及军事 等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方 面，动态规划可以用来解决最优路径问题、资源分配问题、生产调 度问题、库存问题、装载问题、排序问题、设备更新问题、生产过 程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。 许多实际问题采用动态规划方法去处理，常比线性规划或非线 性规划更加有效。特别对于离散性的问题，由于解析数学无法施展 其术，而动态规划的方法就成为一种非常有效的工具
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 应特别指出的是,动态规划是解决某一类问题的一种方法,是 分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算 法)。因而,它不象线性规划那样有一个标准的数学表达式和明确 定义的一组规则,而必须对具体问题进行具体分析处理。因此,在 学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富 的想象力去建立模型,用创造性的技巧去求解。正如贝尔曼本人所 说:“由于动态规划的最优化原理仅仅是一种基本原理,正是它的 某种不确定性为你提供了发挥你创造性思维的巨大空间 本部分我们主要研究离散决策过程,介绍动态规划的基本概念、 理论和方法,在通过一些典型的应用问题来说明它的应用
4 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 应特别指出的是，动态规划是解决某一类问题的一种方法，是 分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算 法）。因而，它不象线性规划那样有一个标准的数学表达式和明确 定义的一组规则，而必须对具体问题进行具体分析处理。因此，在 学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富 的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所 说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它的 某种不确定性为你提供了发挥你创造性思维的巨大空间 ! 本部分我们主要研究离散决策过程，介绍动态规划的基本概念、 理论和方法，在通过一些典型的应用问题来说明它的应用
动规 Dynamic Programming(DP 动态规划 Dynamic Programming 多阶段决策过程的最优化 多阶段决策过程: 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段 每一阶段都需作出决策,全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标: 达到整个活动过程的总体效果最优,而非各单个阶段最优的简 单总和。 Page199例1、2、3 请看如下典例—最短路线问题
5 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 多阶段决策过程的最优化 多阶段决策过程： 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段， 每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简 单总和。 Page 199 例1、2、3 请看如下典例——最短路线问题