1、第 8章 动态规划Dynamic Programming华国伟北京交通大学物流管理系内容提要1.多阶段决策过程及实例2.动态规划的基本概念和基本方程3.动态规划的最优性原理和最优性定理4.动态规划和静态规划的关系5.动态规划应用举例重点：理解动态规划基本概念、最优化原理和基本方程 ;通过 资源分配、 生产与存储和设备更新等问题 ,学习 应用动态规划解决多阶段决策问题 ;重点掌握动态规划模型结构、逆序算法原理、资源 分配问题、生产与存储问题 .难点 为动态规划中 状态变量、基本方程 等的确定 .动态规划产生于 20世纪 50年代 , 美国数学家贝尔曼 (R. Bellman)等人提出 . 动态规
2、划是求解某类问题的 一种方法 ,是考察问题的一种 途径 ,而 不是一种算法 .必须对具体问题进行具体分析 ,运用动态规划的原理和方法 ,划分阶段 ,建立相应的模型 ,然后再去求解 .动态规划是用来解决 多阶段决策 过程最优化的一种数量方法 .其 特点 在于 ,它可以把一个多阶段决策问题变换为几个相互联系的同类型单阶段最优化问题 ,从而一个一个地去解决 .1. 多阶段决策过程及实例多阶段决策过程（序贯决策过程）1 2 n决策 决策 决策状态 状态 状态 状态 状态收益 收益 收益2 多阶段决策问题 举例(1) 时间阶段例 1 机器负荷分配问题1x1v1S1=1000台 S22x2v2S33x3v
3、3S44x4v4S55x5v5其中： xi 各年度不同负荷机器的台数（向量）；vi 产量建模？求解？AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266431 2 3 4 5 6(2) 空间阶段图中所示为从 A到 G的路线网络 , 图中数字表示相应线路的长度 , 如何求出从 A到 G的最短路线？（穷举法 48条路线）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526631 2 3 4 5 6375976813109121316184AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526631 2 3 4 5 615131315111313681095318174
