动态规划 [兼容模式].pdfVIP

动 态 规 划 (Dynamic programming) 动态规划的基本思想 最短路径问题最短路径问题 投资分配问题 背包问题 zhyw 动态规划是用来解决多阶段决策过程最优化 的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而 一个一个地去解决。 需指出需指出：：动态规划是求解某类问题的一种方动态规划是求解某类问题的一种方 法，是考察问题的一种途径，而不是一种算法。 必须对具体问题进行具体分析，运用动态规划 的原理和方法，建立相应的模型，然后再用动 态规划方法去求解。 zhyw 动态决策问题的特点： 系统所处的状态和时刻是进行决策的重要因素； 即在系统发展的不同时刻 （或阶段）根据系统 所处的状态，不断地做出决策； 找到不同时刻的最优决策以及整个过程的最优策略。 多阶段决策问题多阶段决策问题：： 是动态决策问题的一种特殊形式； 在多阶段决策过程中,系统的动态过程可以按照时间 进程分为状态相互联系而又相互区别的各个阶段； 每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。 zhyw 决策 决策 决策 状态 状态 状态 状态 1 2  n 多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需 求是随时间变化的，因此企业为了获得全年的最佳 生产效益生产效益，，就要在整个生产过程中逐月或逐季度地就要在整个生产过程中逐月或逐季度地 根据库存和需求决定生产计划。 2. 机器负荷分配问题：某种机器可以在高低两 种不同的负荷下进行生产。在高负荷下进行生产时， 产品的年产量g 和投入生产的机器数量u 的关系为 1 g=g (u ) 1 zhyw 这时，机器的年完好率为a ，即如果年初完好机 器的数量为u，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量h和投入生产 的机器数量u 的关系为 2 h=h(u ) 2 相应的机器年完好率相应的机器年完好率bb,0,0 bb11。。 假定开始生产时完好的机器数量为s。要求制1 定一个五年计划，在每年开始时，决定如何重新 分配完好的机器在两种不同的负荷下生产的数量， 使在五年内产品的总产量达到最高。 zhyw 3. 航天飞机飞行控制问题：由于航天飞机的 运动的环境是不断变化的，因此就要根据航天飞机 飞行在不同环境中的情况，不断地决定航天飞机的 飞行方向和速度 （状态），使之能最省燃料和实现 目的（如软着落问题）。 不包含时间因素的静态决策问题 （本质上是一 次决策问题）也可以适当地引入阶段的概念，作为 多阶段的决策问题用动态规划方法来解决。 4 . 线性规划、非线性规划等静态的规划问题也 可以通过适当地引入阶段的概念，应用动态规划方 法加以解决。 zhyw 5 . 最