2010运筹动态.ppt

第八章 动态规划 小结 1、具体问题具体分析（无确定模型） 2、无后效性有局限性 3、可以处理非线性、离散问题 * 游戏：捡火柴 桌上放有30根火柴，一次可以取1-3根，谁捡最后一根谁输。怎么选择，保证你能赢？ 29—25—21---17—13—9—5---1 研究多阶段决策问题 R.E.Bellman 1951年提出动态规划。 1957年出版Dynamic Programming 应用：最优调度、资源分配 最优路径、最优控制 设备更新、库存问题 最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质： 对于最优策略过程中的任意状态而言，无论其过去 的状态和决策如何，余下的诸决策必构成一个最优子 策略。 该原理的具体解释是，若某一全过程最优策略为： 则对上述策略中所隐含的任一状态而言，第k子过程上对应 于该状态的最优策略必然包含在上述全过程最优策略p1*中， 即为 四大要素，一个方程 动态规划求解非线性规划问题 例： *