运筹学课件第七章_动态规划.pdf

第七章动 态 规 划 (Dynamic programming) 动态规划的基本概念、基本思想 动态规划模型的建立和求解 动态规划的应用：背包问题；生产 经营问题；设备更新问题；复合系统 工作可靠性问题 2013-5-17 运筹学 第一节 动态规划 动态规划(Dynamic Programming)是用来解决 多阶段决策过程最优化的一种数量方法。其特 点在于，它可以把一个n 维决策问题变换为几个 一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种 方法，是考察问题的一种途径，而不是一种算 法。必须对具体问题进行具体分析，运用动态 规划的原理和方法，建立相应的模型，然后再 用动态规划方法去求解。 2013-5-17 运筹学 决策 决策 决策 状态 状态 状态 状态 1 2  n 一、多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需 求是随时间变化的，因此企业为了获得全年的最佳 生产效益，就要在整个生产过程中逐月或逐季度地 根据库存和需求决定生产计划。 2. 机器负荷分配问题：某种机器可以在高低两 种不同的负荷下进行生产。在高负荷下进行生产 时，产品的年产量g 和投入生产的机器数量u1 的关 系为 2013-5-17 g=g (u ) 运筹学 1 这时，机器的年完好率为a ，即如果年初完好机 器的数量为u ，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量h和投入生产 的机器数量u2 的关系为 h=h(u2) 相应的机器年完好率b, 0 b1。 假定开始生产时完好的机器数量为s 。要求制 1 定一个五年计划，在每年开始时，决定如何重新 分配完好的机器在两种不同的负荷下生产的数 量，使在五年内产品的总产量达到最高。 2013-5-17 运筹学 3. 航天飞机飞行控制问题：由于航天飞机的 运动的环境是不断变化的，因此就要根据航天飞机 飞行在不同环境中的情况，不断地决定航天飞机的 飞行方向和速度（状态），使之能最省燃料和实现 目的（如软着落问题）。 不包含时间因素的静态决策问题（本质上是一 次决策问题）也可以适当地引入阶段的概念，作为 多阶段的决策问题用动态规划方法来解决。 4 . 线性规划、非线性规划等静态的规划问题也 可以通过适当地引入阶段的概念，应用动态规划方 法加以解决。 2013-5-17 运筹学 5 . 最短路问题：给定一个交通网络图如下，其 中两点之间的数字表示距离（或花费），试求从A点 到G点的最短距离（总费用最小）。 C 6 1 1 2 8 D1 E1 3 B1 3 3 5