第06篇：动态规划.ppt

动态规划是贝尔曼(Bellman)在五十年代为解决多级决策过程而提出来的。它可以解决很多领域中的问题，如生产过程的决策，收益和投资问题，有多级反应器的化工装置的设计，多级轧钢机的最速轧制问题，资源分配、机器负荷分配、生产计划编制，特别是控制工程问题。 6.1 多级决策的例子——最短时间问题 图6-1 按最短时间的路径选择 （一）穷举法 路 线 行车时间（小时） 13 11 14 13 12 9 这里每条路线由四段组成，也可以说是四级决策。 为了计算每条路线所花时间，要做三次加法运算，为了计算六条路线所花的时间要作3×6=18次运算。这种方法称为“穷举法”。 显然当段数很多时，计算量是很大的。这种方法的特点是从起点站往前进行，而且把这四级决策一起考虑。应注意从到 下一站 所花的时间为1，而到 所花时间为3，但最优路线却不经过 。 这说明只看下一步的“眼前利益”来作决策是没有意义的。 （二）动态规划法 1 （倒数第一段）  2（倒数第二段） 3（倒数第三段） 4（倒数第四段） 6.2 最优性原理 图6-2 最优性原理示意图 最优性原理可表示为 6.3 用动态规划解资源分配问题 这些性质构成了以后解题的边界的条件。 例1-1 同理，当可取值3，2，1，0时可求得 再考虑3个产品的资源分配，可得这三个产品投入资源的单元数为1，2，3，4时的，最优值如下 6.4 用动态规划求离散最优控制 例6-2 6.5 连续系统的动态规划 （6-25）或（6-28）称为哈密顿—雅可比—贝尔曼方程，边界条件是（6-22）式。哈密顿—雅可比—贝尔曼方程在理论上很有价值，但它是 的一阶偏微分方程并带有取极小的运算，因此求解是非常困难的，一般情况得不到解析解，只能用计算机求数值解。对于线性二次问题，可以得到解析解，而且求解结果与用极小值原理或变分法所得结果相同。这时，哈密顿——雅可比——贝尔曼方程可归结为黎卡提方程。在实际计算线性二次问题时，一般用直接求解黎卡提方程来求最优控制。 6.6 动态规划与极小值原理 下面由动态规划法来推出协态方程。 6.7 小结 用动态规划求解的结果已在上节中得到，现在归纳一下：在动态规划中协态变量 满足 哈密顿—雅可比—贝尔曼方程（6-28）本身说明了哈密顿函数在最优控制上取极值的条件，故等同于上面极小值原理所得的条件5，不过（6-28）还多给出了一点信息，即 。 由（6-27） （6-4） 取最大，其中满足约束 （6-5） （6-6） 写成数学形式，即要使 上面的问题可以用动态规划求解。为了说明问题简单起见，这里只考虑单资源分配问题，即如何将一种资源分配给 种产品，使总收益最大。设这种资源的总数为 ，分配给第 种产品的数量为 ，则性能指标为 （6-7） 取最大，约束条件是 （6-8） 为了用动态规划求解，引进一个函数 ，它表示将资源量 分配给第1至第 种产品时所能得到的最大收益。显然 表示将总资源 分配到所有 种产品上所得到的最大收益，即 （6-9） 容易看出，函数 有下列性质 即没有资源投入时收益为零。 这表明将资源量只用于生产一种产品时的总收益，就是这种产品本身收益。 即不生产产品时收益为零。 现在来推导 所应满足的关系式。已知投入前 种产品的资源量为 。如果投入第 种产品的资源量为 ，则投入前（ ）种产品的资源量为 。 如果把 种产品的资源分配看成是 步决策，则 表示 步决策的指标最优值， 表示用决策量 时第