运筹学 动态规划

《运筹学 动态规划》由会员分享，可在线阅读，更多相关《运筹学 动态规划（64页珍藏版）》请在金锄头文库上搜索。

1、第1页 共64页第四章 动态规划 Dynamic Programming（DP）动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化问题的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。第2页 共64页动态规划是分析某一类问题的一种途径。它不像LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。第3页 共64页本章

2、主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过一些典型的应用问题说明它的应用。4.14.1多阶段决策过程的最优化多阶段决策过程的最优化4.24.2动态规划的基本概念及原理动态规划的基本概念及原理4.34.3动态规划模型的建立和求解动态规划模型的建立和求解第4页 共64页4.1 多阶段决策过程的最优化一、多阶段决策过程整个决策过程可按时间或空间顺序分解 成若干相互联系的阶段（“时段”），在每一阶段都要作出决策，全部过程的决策是一个 决策的序列。第5页 共64页某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产 量大但损耗也大）可使五年的总产量最

3、大，如 图4-1所示。 例4-1 时间阶段示例（机器负荷问题）图4-1 机器负荷问题第6页 共64页B1AC3 F2F1E3E2E1D3D2D1C4C2C1B2G531 36876683 5342138223 3355 26643例4-2 空间阶段示例（最短路线问题）给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-2 第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段第7页 共64页二、多阶段决策过程最优化的目标生产存储问题 投资决策问题 设备更新问题三、示 例达到整个活动过程的总体效果的最优，而非各单个阶段最优的简单总和。

4、第8页 共64页4.2 动态规划的基本概念和基本原理一、基本概念1、阶段2、状态3、决策和策略4、状态转移方程5、指标函数第9页 共64页B1AC3 F2F1E3E2E1D3D2D1C4C2C1B2G531 36876683 5342138223 3355 26643例4-2 最短路线问题给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-2第10页 共64页1、阶段（阶段（stagestage）将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，用k表示。如例4-2中，问题分为AB、BC共6个阶段，k = 6。2、状

5、态（状态（statestate）指各阶段开始时过程所处的自然状况或客观条件。状态应具有“无后效性无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。如：S1=A，S2=B1,B2，第11页 共64页3、决策（决策（decisiondecision）与策略（）与策略（policypolicy）当某一阶段的状态确定后，可以作出不同的决定或选择，从而确定下一阶段的状态，这种决定或选择称为决策。如：从第二阶段的状态B1出发，可以选择下一阶段的C1C3，即 D2(B1) = C1,C2,C3若决定选择C3，则 d2(B1) = C3一组有序的决策序列构成一个策略，从第k

6、 阶段至第n 阶段的一个策略称为后部子策略，记为 Pkn （dk，dk+1，dn）。例4-2第12页 共64页4、状态转移方程状态转移方程系统由一个阶段的一个状态转变到下一个阶段的另一个状态称为状态转移。其对应状态和决策的关系称为状态转移方程。记为第13页 共64页5、阶段指标阶段指标衡量在一个阶段某个状态下各决策所对应的某种数量指标或效果，记为 6、指标函数指标函数衡量所选策略优劣的数量指标或效果。最优 指标函数表示从第k 个阶段采用最优策略 到过程终止时的最佳效益值，记为第14页 共64页例4-2 最短路线问题穷举法动态规划法得最优线路为：第15页 共64页B1AC3 F2F1E3E2E1

7、D3D2D1C4C2C1B2G537633412332643437597681310912131618该点到G点的最短距离图4-3上述最短路线的计算过程可用图直观表示(标号法)，如图4-3所示，结点上方矩形内的数字表示该点到终点的最短距离。标号法过程第16页 共64页B1AC3 F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段531 36876683 5342138223 3355 26643437597681310912131618图4-4第17页 共64页二、最优化原理Bellman 最优化原理：“一个过程的最优策略具有这样的性质，即无论开

8、始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优决策后部子过程最优”第18页 共64页三、动态规划基本思路1、将问题划分多个阶段。恰当选择状态变量、决策变量及定义最优指标函数2、从边界条件开始，逆向或正向逐段递推求解。3、各个阶段的最优决策是从全局考虑的，并非仅考虑本阶段。其基本方程为第19页 共64页建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题。而正确建立基本递推关系方程的关键又在于正确选择状态变量。4.3 DP模型的建立与求解第20页

9、 共64页一、DP模型的建立1、正确、明确地划分阶段 k， k =1，2，3，n。2、正确选择并确定状态变量 sk 及状态集合 Sk 。3、确定决策变量 dk 及决策集合 Dk（sk）。4、写出状态转移方程 sk+1 = Tk（sk，dk）。5、定义阶段指标值（函数） vk（sk，dk）。6、定义第 k至 n 阶段的最优指标函数 fk（sk）；7、建立动态规划基本方程（逆序递推方程） 第21页 共64页例4-3 分配投资问题问题的一般描述如下：设有某种资源，总数量为a ，用于生产n种产品；若分配数量 xi 用于生产第i种产 品，其收益为gi(xi)。问应如何分配，使得使总收益最大？ 第22页

10、共64页该类问题可用动态规划进行求解： 第23页 共64页例如：某公司有资金10万元，若投资于项目 k (k = 1,2,3)的投资额为 xk 时，收益分别为 g1(x1) = 4x1， g2(x2) = 9x2， g3(x3) = 2x32 ，问应该如何分配投资数额才能使总收益最大？该问题表面上看与时间无明显关系，其静态模型：第24页 共64页现人为地给它赋予“时段”的概念，将投资项目排序，首先考虑项目1的投资，然后考虑项目2的投资，问题分为3个阶段，每个阶段只决定一个项目的投资金额。第25页 共64页问题分三个阶段，即k = 1，2，3sk ：第 k 阶段初拥有的资金总量xk ：项目 k

11、的投资额，0 xk sk sk+1 = sk - xk Vk(sk,xk) = gk(xk)解：基本方程为：第26页 共64页例4-4 采购与销售问题 P103 例2某商店在未来四个月里，利用一个仓库经销某种商品。仓库最大容量H = 1000件，每月中旬订购商品并于下月初到货。估计未来四个月该商品的购价pk及售价qk如表4-1所示。假定商店在1月初库存500件，每月的需求不限，问应如何计划每月的订购及销售数量，使总利润最大（不考虑库存费用）。月份 k购价 pk售价 qk1 2 3 410 9 11 1512 9 13 17表4-1第27页 共64页问题分4个阶段，即k = 1，2，3，4sk

12、：第 k 月初的库存xk ，yk：第k 月的订购及销售量解：基本方程为：第28页 共64页课堂练习某公司拟将某种高效设备5台分配给所属甲、乙、丙 3厂。各厂获此设备后可产生的效益如表4-2所示。问应如何分配，可使所产生的总效益最大？ 表4-2 效益表第29页 共64页解：阶段k =1,2,3依次表示把设备分配给甲、乙、丙厂的过程； 状态sk表示在第k阶段初还剩有的可分台数； 决策xk表示第k阶段分配的设备台数； 状态转移sk+1 = sk - xk ； 阶段指标vk 表示第k阶段分配后产生的效益； 指标函数：基本方程： 第30页 共64页逆序递推法将寻优过程看做连续递推的过程，从最终阶段开始，

13、逆着实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。顺序递推法从初始阶段向前递推，直到最终阶段为止。二、DP模型的求解P106 例3第31页 共64页sk+1 = sk xk g1(x1)= 4x1 g2(x2)= 9x2 g3(x3)= 2x32 例4-3 分配投资问题的逆序求解基本方程为：第32页 共64页可证明极 大值只可 能在端点 取得k = 3此时，x3 = s3 k = 2此时，x2 = s2 此时，x2 = 0k = 1 当 s2 9/2 时此时，x1 = 0 综上可得x1 = 0 s2 = 10 9/2x2 = 0

14、s3 = 10 x3 = 10 即将全部资金投资于第 3 个项目，可获得最大收益 200 万元。x2 = 0 第34页 共64页sk+1 = sk + xk yk s1 = 500 H = 1000 例4-4 采购与销售问题的逆序求解基本方程为：第35页 共64页k = 4此时，y4 = s4 ，x4 = 0 k = 3此时，y3 = s3 ，x3 = H 第36页 共64页k = 2k = 1此时，y1 = s1 ，x1 = 0 此时，x2 y2 = H s2第37页 共64页综上可得最优决策如下：库存sk 订购量xk 销售量yk最大利润为y1 = s1 ，x1 = 0 x2 y2 = H

15、s2 y3 = s3 ，x3 = H y4 = s4 ，x4 = 0 5005000 00H HHHHH0第38页 共64页顺序法与逆序法没有本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终 止状态，则两种方法均可使用。如例4-5中终点有三个，用逆序法求解比较好。第39页 共64页一艘货轮在A港装货后驶往F港，中途须靠港加油、淡水三次，从A港到F港全部可能的航行路线及两港之间距离如图4-5，F港有三个码头 F1、F2、F3，试求最合理的停靠的码头及航线，使总路程最短。 例4-5图4-520307060457590120第40页 共6

16、4页表格求解：当问题划分的阶段和可供选择的状态较多时，动态规划可采用表格形式进行求解。P107 例4第41页 共64页某厂每月交货量及生产相应费用如表4-3、表4-4所示月份 k1 234 56 交货量(百件)125321例4-6 生产与存储问题 假设1月初和6月末仓库无库存。问该厂应如何安排每月的生产和库存，才能既满足交货需求又使总费用最低？ 最大产 量(百件)最大库 存(百件)生产准备费(千元/批)生产费(千元/百件)库存费 千元/(百件月)434101表4-3表4-4第42页 共64页问题分6个阶段，即k = 1 6sk ：第 k 月初的库存dk ：第k 月的产量ck ：第k 月的交货量解：基本方程为：0 sk 3 0 dk 4 阶段指标函数问题描述第43页 共64页d6 s6(4+10d6)( d6 ) + s6 + f7(s7 )f6(s6