第六章动态规到(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）