北京交通大学：《管理运筹学》课程教学课件（讲稿）第8章 动态规划 Dynamic Programming

北京交通大学经济管理学院nics and ManagomentSchool of EconoBaijingJiaotong University第8章动态规划Dynamic Programming华国伟北京交通大学物流管理系

第8章 动态规划 Dynamic Programming 华国伟 北京交通大学物流管理系

北京交通大学经济管理学院内容提要SchoollofEics andManagomentBojingJiaotong University1.多阶段决策过程及实例2.动态规划的基本概念和基本方程3.动态规划的最优性原理和最优性定理4.动态规划和静态规划的关系5.动态规划应用举例北京交通大学1

内容提要 1.多阶段决策过程及实例 2.动态规划的基本概念和基本方程 3.动态规划的最优性原理和最优性定理 4.动态规划和静态规划的关系 5.动态规划应用举例

北京交通大学经济管理学院SctngstEounteaneyfofandMaagoment重点：理解动态规划基本概念、最优化原理和基本方程；通过资源分配、生产与存储和设备更新等问题，学习应用动态规划解决多阶段决策问题重点掌握动态规划模型结构、逆序算法原理、资源分配问题、生产与存储问题难点为动态规划中状态变量、基本方程等的确定北京交通大学1

重点： 理解动态规划基本概念、最优化原理和基本方程; 通过资源分配、生产与存储和设备更新等问题,学习 应用动态规划解决多阶段决策问题; 重点掌握动态规划模型结构、逆序算法原理、资源 分配问题、生产与存储问题. 难点为动态规划中状态变量、基本方程等的确定

北京交通大学经济管理学院SchoollofrsiosandManagomentBoijingJiaotongUniversity动态规划产生于20世纪50年代，美国数学家贝尔曼(R.Bellman)等人提出动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法.必须对具体问题进行具体分析，运用动态规划的原理和方法，划分阶段，建立相应的模型然后再去求解北京交通大学

动态规划产生于20世纪50年代, 美国数学 家贝尔曼(R. Bellman)等人提出. 动态规划是求解某类问题的一种方法,是 考察问题的一种途径,而不是一种算法.必 须对具体问题进行具体分析,运用动态规划 的原理和方法,划分阶段,建立相应的模型, 然后再去求解

北京交通大学经济管理学院SchoolandManagomentBojingJiaotong University动态规划是用来解决多阶段决策过程最优化的一种数量方法.其特点在于，它可以把一个多阶段决策问题变换为几个相互联系的同类型单阶段最优化问题，从而一个一个地去解决北京交通大学

动态规划是用来解决多阶段决策过程最优化 的一种数量方法.其特点在于,它可以把一个 多阶段决策问题变换为几个相互联系的同类 型单阶段最优化问题,从而一个一个地去解决

北京交通大学经济管理学院1．多阶段决策过程及实例schasEtonounanics and Managoment多阶段决策过程（序贯决策过程）决策决策决策状态状态状态状态状态n收益收益收益北京交通大学

1. 多阶段决策过程及实例 多阶段决策过程（序贯决策过程） 1 2 n 决策 决策 决策 状态 状态 状态 状态 状态 收益 收益 收益

2 多阶段决策问题一一举例建模？(1)时间阶段求解?例1机器负荷分配问题1234LS4S5S?S3S,=1000台23541介介介介介X1X2X4X3X5其中：X;各年度不同负荷机器的台数（向量）；-产量V:

2 多阶段决策问题——举例 (1) 时间阶段 例1 机器负荷分配问题 1 x1 v1 S1=1000台 S2 2 x2 v2 S3 3 x3 v3 S4 4 x4 v4 S5 5 x5 v5 其中：xi——各年度不同负荷机器的台数（向量）； vi——产量 建模？ 求解？

(2)空间阶段图中所示为从A到G的路线网络，图中数字表示相应线路的长度，如何求出从A到G的最短路线？6C1231E1D18B1543523F1C25AGE2D2832C36B2F23733E3D38663C4423456（穷举法48条路线）

A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 1 2 3 4 5 6 (2) 空间阶段 图中所示为从A到G的路线网络, 图中数字表示相应 线路的长度, 如何求出从A到G的最短路线？ （穷举法48条路线）

北京交通大学经济管理学院School dt Econonnics and ManagomentBojing Jiaotong University13776C12133E1D1810B1453F1C256A5G9E23D238182C36B2F2>533E316D3863369C44812234156北京交通大学

A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 68 7 6 6 8 3 5338 4 221233 3 55 2 6 6 3 1 2 3 4 5 6 3 75 9 768 13 109 12 13 16 18 4

北京交通大学经济管理学院School dt Econonnics and ManagomentBojing Jiaotong University611136C152317ElD188B154F1C231313A5G10E2D28C3186F2B23733E3D38615623C4154139234156北京交通大学

A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 68 7 6 6 8 3 5338 4 221233 3 55 2 6 6 3 1 2 3 4 5 6 15 13 13 15 11 13 13 68 109 53 18 17 4