管理运筹学课件3.pdf

第6章 动态规划 第6章 动态规划 内容提要 内容提要 Sub title Sub title 第一节 多阶段性决策 第二节 动态规划原理 第三节 逆序求解过程 第四节 动态规划举例 OR:SM OR:SM 第6章 动态规划 第6章 动态规划 • 动态规划Dynamic Programming 研究多阶段决策的最优化问题的方法。 多阶段性决策含有一个描述过程时序或空间演变的阶段变 过程时序 空间演变 量，将复杂问题划分成若干阶段，根据“最优性原理”，逐 段解决而最终实现全局最优。 经济、管理、工业生产、工程技术等领域，许多问题可归 结为多阶段性决策。 一些用线性规划、非线性规划处理有困难的问题，往往可 以用动态规划方便地求解。　 动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提 出的。 OR:SM OR:SM 第一节 多阶段性决策 一、 问题的提出 • 多阶段决策： 经济管理决策中，有些管理决策问题可以按时序或空间演 时序 空间演 变划分成多个阶段，呈现出明显的阶段性； 变 于是可把这类决策问题分解成几个相互联系的阶段，每个 阶段即为一个子问题； 原有问题的求解就化为逐个求解几个简单的阶段子问题； 每个阶段的决策一旦确定，整个决策过程也随之确定，此 类问题称为多阶段性决策。 • 例如： 企业生产物流：可分为物料供应、生产制造、分销零售等 阶段。 最短路问题：可以按空间顺序划分阶段。 OR:SM OR:SM 第一节 多阶段性决策 • 最短路问题 A 1 7 B1 1 4 4 C 2 6 1 3 4 6 Q 4 A2 2 B2 T 3 4 3