第五章动态规划.doc

第五章 动态规划 动态规划（Dynamic Programming，DP）是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。它产生于五十年代，1951年美国的数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把其变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，提出了解决此类问题的“最优性原理”，并在研究了许多实际问题的基础上，创建了动态规划，1957年出版了动态规划的第一本著作。 动态规划适用范围十分广泛，在工程技术，企业管理，工农业生产及军事部门都有广泛的应用。在企业管理方面，可用来解决诸如运输问题，投资策略，资源分配，生产调度，库存控制，设备更新以及生产中的最优控制等问题。由于它有独特的解题思路，在处理某些优化问题时，比线形规划或非线性规划方法更有效。特别是对于某些变量为离散性的问题，解析数学无法解决，动态规划则显得尤为有效。 与线性规划相比，动态规划不存在一个标准的数学表达式，以及明确定义的一组求解规则。动态规划是解决问题的一类一般性方法，对于每一种具体情况，必须导出具体的算式。这就要求人们在用动态规划解题时，既要对问题有深刻的理解，又要掌握某些解题技巧，而这种能力的获得只能靠对各种动态规划应用问题的了解和熟悉，及对各种情况共性的研究。 本章主要研究离散确定型决策过程（变量取值是离散的）。介绍动态规划的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是动态规划的基本内容。对于连续确定性动态规划问题，通过求解非线性规划问题的例子加以简要介绍。 多阶段决策过程及实例 一、多阶段决策问题 在生产、工程、科学实验中，有这样一类活动，由于它的特殊性，可将过程分为若干个互相联系的阶段，每一个阶段都要做出决策，从而使整个过程达到最佳效果。因此，各阶段的决策既依赖于当前所处于的各个状态，又影响以后的发展。当各阶段的决策确定后，就组成了一个决策序列，从而也就决定了整个过程的一条活动路线。这样一个前后关联且具有链状结构的多阶段过程（如图5-1），就称为多阶段决策过程。 决策 决策 决策 状态 状态 状态 状态 图5-1 多阶段决策过程示意图 在多阶段决策问题中，各阶段做出的决策，一般与时间有关，决策依赖于当前的状态，又随即引起状态的转移，一个决策的序列就是在变化的状态中产生出来的，故有“动态”的含义。但是，一些与时间无关的静态规划问题，只要人为的引入“时段”因素，也可视为多阶段决策过程来处理。 二、多阶段决策问题举例 1.工厂生产过程 由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。 2.设备更新问题 一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。 3.连续生产过程的控制问题 一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。 以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。 4.资源分配问题 便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。 5.运输网络问题 如图5-2所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从起点(sk)至终点的最短路线。 这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。 例1如图5-2所示为一交通线路网络，现在要铺设从A点至E点的线路，中间要经过三个地区B、C、D。地区B和C分别可在区内三个地点设站，地区D可在两个地点设站。图中各