重庆大学工商管理学院信息系：《运筹学》第六章 动态规划（熊中楷）

92g 动态规划(1) 运学 狼中J

运筹学 熊中楷教授 动态规划（1）

第六章动态规到(1) 重庆大学 上清寺 解放碑 朝天门 已知重庆大学到朝天门的最短路要经过上清寺和解放碑 证明:上清寺到朝天门的最短路要经过解放碑 运学 熊中描教

运筹学 熊中楷教授 第六章 动态规划（1） 重 庆 大 学 上 清 寺 朝 天 门 解 放 碑 已知重庆大学到朝天门的最短路要经过上清寺和解放碑 证明：上清寺到朝天门的最短路要经过解放碑

第六章动态规到(1) 定理:如果A到F的最短路程是 ABCdef, 那么C到F的最短路程一定是CDEF( Bellman最优化原理) 运学 熊中描教

运筹学 熊中楷教授 定理：如果A到F的最短路程是ABCDEF， 那么C到F的最短路程一定是 CDEF (Bellman最优化原理） 第六章 动态规划（1）

第六章动态规到(1) 动态规划在经济管理中应用: 动态规划应用之一:最优路径问题 动态规划应用之二:资源分配问题 动态规划应用之三:生产计划调度问题 动态规划应用之四:库存问题,采购问题 动态规划应用之五:设备更新问题 动态规划应用之六:生产过程最优控制问题 动态规划应用之七:∴ 运学 熊中描教

运筹学 熊中楷教授 第六章 动态规划（1） 动态规划在经济管理中应用： 动态规划应用之一：最优路径问题 动态规划应用之二：资源分配问题 动态规划应用之三：生产计划调度问题 动态规划应用之四：库存问题，采购问题 动态规划应用之五：设备更新问题 动态规划应用之六： 生产过程最优控制问题 动态规划应用之七： ………

第六章动态规划(1) 动态规划应用之一:最优路径问题:类似P201例题:某 工厂从国外进口一部精密设备,由机器制造厂到出口港有三个港口可供选 择,而进口港又有三个港口可供选择,进口后可以经两个城市到达目的地 其运输成本如图所示,求运费最低的路线 运输成本 BD 40 E ③2 B3 30 国外机器制造厂一出口港 进口港 国内城市 国内某工厂 运学 熊中描教

运筹学 熊中楷教授 动态规划应用之一：最优路径问题：类似P201例题： 某 工厂从国外进口一部精密设备，由机器制造厂到出口港有三个港口可供选 择，而进口港又有三个港口可供选择，进口后可以经两个城市到达目的地， 其运输成本 如图所示，求运费最低的路线 A B3 B2 B1 D2 D1 C3 C2 C1 E 20 40 40 30 20 30 40 10 60 40 70 50 30 30 30 60 40 10 40 30 第六章 动态规划（1） 运输成本 国外机器制造厂 ―出口港 进口港 国内城市 国内某工厂

第六章动态规到(1) 从C1到终点最短路 两点间运输成本 国外机器制造厂一出口港 进口港 国内城市 国内某工厂 运学 熊中描教

运筹学 熊中楷教授 A B3 B2 B1 D2 D1 C3 C2 C1 E 20 40 40 30 20 30 40 10 60 40 70 50 30 30 30 60 40 10 40 30 40 0 30 70 40 80 60 70 110 110 第六章 动态规划（1） 从C1到终点最短路 两点间运输成本 国外机器制造厂 ―出口港 进口港 国内城市 国内某工厂

第六章动态规到(1) 国外机器制造厂一出口港—进口港—国内城市—国内某工厂 1.阶段2状态3决策4策略5状态转移方程6.指标函数和最优值函 数 运学 狼中J

运筹学 熊中楷教授 A B3 B2 B1 D2 D1 C3 C2 C1 E 20 40 40 30 20 30 40 10 60 40 70 50 30 30 30 60 40 10 40 30 40 0 30 70 40 80 60 70 110 国外机器制造厂 ―出口港 进口港 国内城市 国内某工厂 1.阶段 2.状态 3.决策 4.策略 5.状态转移方程 6.指标函数和最优值函 数 第六章 动态规划（1） 110

第六章动态规到(1) 动态规划的基本概念: 1.阶段:把问题分为互相联系有一定次序的阶段 2.状态:每个阶段开始所处自然状况或客观条件,不可控制 3.决策:某个阶段的某个状态决定下一个阶段的状态 4.策略:某个阶段的某个状态所有可能的决策 5.状态转移方程:确定由一个状态转到另一个状态的过程 6.指标函数和最优值函数:衡量过程优劣的数量指标 运学 熊中描教

运筹学 熊中楷教授 动态规划的基本概念： 1. 阶段：把问题分为互相联系有一定次序的阶段 2. 状态：每个阶段开始所处自然状况或客观条件，不可控制 3. 决策：某个阶段的某个状态决定下一个阶段的状态 4. 策略：某个阶段的某个状态所有可能的决策 5. 状态转移方程：确定由一个状态转到另一个状态的过程 6. 指标函数和最优值函数：衡量过程优劣的数量指标 第六章 动态规划（1）

第六章动态规到(1) 动态规划最优性原理与最优性定理: 动态规划与静态规划的关系: 整数规划0-1规划 数字规划静态规线性规划运输问题 非线性规划 动态规划 逆推算法举例:

运筹学 熊中楷教授 动态规划最优性原理与最优性定理： 动态规划与静态规划的关系： 逆推算法举例：                                                − 动态规划 非线性规划 运输问题 整数规划 规划 线性规划 静态规划 数字规划 0 1 第六章 动态规划（1）

第六章动态规划(1) 资源分配问题 引例:某种原料总数为a分配给n种产品,分配数量Xi用于生产第种产品, 效益为g(xi) Max=8(x)+84x)+…+8(x)状态转移方程: Sk +1= Sk-Uk= Sk-Xk X+X2+.+Xn=a 允许决策集合: x≥0 Dk(Sk)={k:0≤Uk=Xk≤Sk} 第种产品原料量第k+1种产晶到第n种产品原料数量 k+1 k+1 第k种产品到第n种产品原料数量

运筹学 熊中楷教授 1.资源分配问题 引例：某种原料总数为a分配给n种产品，分配数量Xi用于生产第i种产品， 效益为gi(xi) 0 ... ( ) ( ) ... ( ) 1 2 1 1 2 2  + + + = = + + + i n n n x x x x a MaxZ g x g x g x 第k种产品原料量 第k +1种产品到第n种产品原料数量 第k种产品到第n种产品原料数量 ( ) { 0 } 1 k k k k k k k k k k k D S U U X S S S U S X =  =  + = − = − ： 允许决策集合： 状态转移方程： 第六章 动态规划（1）