第五章动态规划

1、第五章 动态规划动态规划(Dynamic Programming, DP)是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。 它产生于五十年代， 1951 年美国的数 学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，把其变换 为一系列互相联系的单阶段问题,然后逐个加以解决。与此同时,提出了解决 此类问题的“最优性原理” ，并在研究了许多实际问题的基础上，创建了动态 规划， 1957年出版了动态规划的第一本著作。动态规划适用范围十分广泛，在工程技术，企业管理，工农业生产及军事 部门都有广泛的应用。 在企业管理方面， 可用来解决诸如运输问题， 投资策略， 资源分配

2、，生产调度，库存控制，设备更新以及生产中的最优控制等问题。由 于它有独特的解题思路， 在处理某些优化问题时， 比线形规划或非线性规划方 法更有效。特别是对于某些变量为离散性的问题，解析数学无法解决，动态规 划则显得尤为有效。与线性规划相比， 动态规划不存在一个标准的数学表达式， 以及明确定义 的一组求解规则。 动态规划是解决问题的一类一般性方法， 对于每一种具体情 况，必须导出具体的算式。这就要求人们在用动态规划解题时，既要对问题有 深刻的理解， 又要掌握某些解题技巧， 而这种能力的获得只能靠对各种动态规 划应用问题的了解和熟悉，及对各种情况共性的研究。本章主要研究离散确定型决策过程(变量取值

3、是离散的) 。介绍动态规划 的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是 动态规划的基本内容。 对于连续确定性动态规划问题， 通过求解非线性规划问 题的例子加以简要介绍。第一节多阶段决策过程及实例、多阶段决策问题在生产、工程、科学实验中，有这样一类活动，由于它的特殊性，可将过 程分为若干个互相联系的阶段，每一个阶段都要做出决策，从而使整个过程达 到最佳效果。因此，各阶段的决策既依赖于当前所处于的各个状态，又影响以 后的发展。当各阶段的决策确定后，就组成了一个决策序列，从而也就决定了 整个过程的一条活动路线。这样一个前后关联且具有链状结构的多阶段过程（如图5-1），就称为

4、多阶段决策过程。状态决策决策决策状态._状态图5-1多阶段决策过程示意图在多阶段决策冋题中，各阶段做出的决策，一般与时间有关，决策依赖于 当前的状态，又随即引起状态的转移，一个决策的序列就是在变化的状态中产 生出来的，故有“动态”的含义。但是，一些与时间无关的静态规划问题，只 要人为的引入“时段”因素，也可视为多阶段决策过程来处理。、多阶段决策问题举例1. 工厂生产过程由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定 生产计划安排。2. 设备更新问题一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进

5、行 转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用 增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年 限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费.因 此就需要综合权衡决定设备的使用年限，使总的经济效益最好。3. 连续生产过程的控制问题一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控 制生产过程中各设备的输入和输出，以使总产量最大。以上所举问题的发展过程都与时间因素有关， 因此在这类多阶段决策问题 中，阶段的划分常取时间区段来表示， 并且各个阶段上

6、的决策往往也与时间因 素有关，这就使它具有了 “动态 ”的含义，所以把处理这类动态问题的方法称为 动态规划方法。不过，实际中尚有许多不包含时间因素的一类 “静态 ”决策问题， 就其本质而言是一次决策问题， 是非动态决策问题， 但是也可以人为地引入阶 段的概念当作多阶段决策问题，应用动态规划方法加以解决。4. 资源分配问题便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺 资源分配， 为此需要制定出收益最大的资源分配方案。 这种问题原本要求一次 确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序， 从而使其变成一个多阶段决策

7、 问题（ 后面我们将详细讨论这个问题 ）。5. 运输网络问题如图 5-2 所示的运输网络，点间连线上的数字表示两地距离 （ 也可是运费、 时间等 ） ，要求从起点 （sk） 至终点的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以 把它分为 4 个阶段，而作为多阶段决策问题来研究。例 1 如图 5-2 所示为一交通线路网络，现在要铺设从 A 点至 E 点的线路， 中间要经过三个地区B、C、D。地区B和C分别可在区内三个地点设站，地区 D 可在两个地点设站。 图中各点之间的连线表示两点间可铺路， 连线上的数 字表示两点间的距离。要求选择一条 A 点至 E 点的最短路线。

8、此类问题可用穷举法求解， 即列出从 A 点至 E 点的所有线路， 并计算每条 线路的长度，比较后就可找出最短线路。本例共有 12 条不同的路线，每条线 路需相加 3 次，共需相加 36次。当面临的选择方案较多时，计算量就相当大，甚至无法实现。最短路线问题具有如下重要性质：若已经给定从始点S到终点T的最短路 线，如图5-3中的实线所示，则从其上任一中间点P到终点T的部分路线也必 然是P点到终点T的所有可选择的路线中的最短路线。该性质的成立是显然的, 可用反证法加以证明。因为如果不是这样，则从点P到T必然有另一更短的路 线（如图中虚线所示），把它和原来最短路线上由始点 S到P点那部分连接起来，将得

9、到一条新路线，它比原来那条最短路线还要短，这显然与前提条件相 矛盾，所以是不可能的。图5-3最短路线示意图根据最短路线问题的这一重要性质，我们可以从最后一个阶段开始，由终 点向始点方向逐阶段递推，寻找各点到终点的最短路线，当递推到始点时，就 找到了始点到终点的最短路线。这种由后向前逆序递推的方法，正是动态规划 通常采用的寻优途径。第二节 逆序递推法面介绍用逆序递推的方法求解例 1 的最短路线问题。首先把从 A 到 E 的全过程分成4个阶段，用K表示阶段变量，第1阶段，有一个初始状态A，三 条可供选择的支路ABi、AB2、AB3；第2阶段，有三个初始状态Bi、B2、B3, 它们各有三条可供选择的

10、支路,。 我们用dk(Sk，Sk+1)表示在第K阶段由初始d3(C2， D1) = 2。用 fk(sk) 表示从第 K 阶段的 sk f3(C1) 表示从第 3 阶段的 C1 到终点 E 的最短距状态sk到下阶段的初始状态Sk+1的支路的距离。例如，d3(C2, Di)表示在第3 阶段，由C2到Di的距离，即 到终点 E 的最短距离。例如， 离。 f3(C1) = 7。A，终点是E。所谓逆序递推就是逆着过程的行图 5-2 中，过程的始点是进方向，由终点到始点，一个阶段随着一个阶段地递推。1. 阶段 K = 4第 4 阶段有两个初始状态 D1 和 D2， A 到 E 的全过程最短路线在第 4 阶

11、段经过哪个点，目前还不能确定，只能考虑到所有选择，分别得到 D1 和 D2 到终 点 E 的最短距离 f4(D1) = 3 和 f4(D2) = 4。2. 阶段 K =3设全过程最短路线在第3阶段经过Ci点，而Ci点至下一阶段只有一条路, 所以f3(C1) = d3(C1， D1) + f4(D1) = 4+3 = 7 类似地，设全过程最短路线在第 3 阶段经过 C2 点，而 C2 点至下一阶段有 两条路，所以f3(C2) = min d 3(C2， D1) + f4(D1)， d3(C2， D2) + f4(D2) = min(5 ，7) = 5即由C2到E的最短路是C2 7Di 7E,最短

12、距离是5。设全过程最短路线在第3阶段经过C3点，则有f3(C3) = min d 3(C3， D1) + f4(D1)， d3(C3， D2) + f4(D2) = min(9 ，9) = 9则由C3到E的最短路有两条：C3 7Di 7E， C3 7D2 f E，最短距离都3. 阶段K = 2类似以上作法，可计算f2（Bl）、以B2）、f2（B3）如下:f2(Bi) = min d 2(Bi ,Ci)+ f3(Ci),d2(Bi,C2)+f3(C2)=min(14 ,12) = 12f2(B2)= min d 2(B2, Ci) + f 3(Ci), d2(B2, C2) + f 3(C2),

13、 d2(B2,C3) + f3(C3)=mi n(11, 10, 15) = 10f2(B3)= min d 2(B3, C2) + f3(C2), d2(B3, C3) + f3(C3) = min(10 ,12) = 10因此，由B1到E的最短路有一条：B1f C2f D1f E ,最短距离是12;由B2到E的最短路有一条：B2 C2fD1 f E,最短距离是10；由B3到E的最短路有一条：B3 f C2fD1 f E,最短距离是10。4. 阶段K = 1计算f1（A）如下:f1(A) = min d 1(A, B1) + f2(B1),d1(A , B2) + f2(B2),d1(A , B3) +f2(B3)=mi n(15, 16, 14) = 14因此，A到E的全过程最短路线为Af B3f C2 f D1f E,如图5-4中双线所示，最短距离是14。图5