《运筹学动态规划》PPT课件.ppt

第1页 共64页 第四章 动态规划 Dynamic Programming（DP） 动态规划是运筹学的一个重要分支，是解 决多阶段决策过程最优化问题的一种非常有效 的方法。1951年，美国数学家贝尔曼（R.Bellman） 等人，根据一类多阶段决策问题的特点，把多 阶段决策问题变换为一系列相互联系的单阶段 决策问题，然后分阶段逐个加以解决。 第2页 共64页 动态规划是分析某一类问题的一种途径。它 不像LP那样有一个标准的数学表达式和明确定 义的一组规则，而必须对具体问题进行具体分 析处理。因此，在学习动态规划时，除了对基 本概念和方法正确地理解外，应以丰富的想象 力去建立模型，用创造性的技巧去求解。 第3页 共64页 本章主要研究离散决策过程，介绍动态 规划的基本概念、理论和方法，并通过一些 典型的应用问题说明它的应用。 4.14.1 多阶段决策过程的最优化多阶段决策过程的最优化 4.24.2 动态规划的基本概念及原理动态规划的基本概念及原理 4.34.3 动态规划模型的建立和求解动态规划模型的建立和求解 第4页 共64页 4.1 多阶段决策过程的最优化 一、多阶段决策过程 整个决策过程可按时间或空间顺序分解 成若干相互联系的阶段（“时段”），在每一 阶段都要作出决策，全部过程的决策是一个 决策的序列。 第5页 共64页 某厂有1000台机器，现需作一个五年计划，以 决定每年安排多少台机器投入高负荷生产（产 量大但损耗也大）可使五年的总产量最大，如 图4-1所示。 例4-1 时间阶段示例（机器负荷问题） 图4-1 机器负荷问题 第6页 共64页 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 4 2 1 3 8 2 2 3 3 3 5 5 2 6 6 4 3 例4-2 空间阶段示例（最短路线问题） 给定线路网络图如下，各点间连线上的数字表示 距离，现要从A地向G地铺设一条输油管道，问应选 择什么路线，使总距离最短？ 图4-2 第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段 第7页 共64页 二、多阶段决策过程最优化的目标 生产存储问题 投资决策问题 设备更新问题 三、示 例 达到整个活动过程的总体效果的最优， 而非各单个阶段最优的简单总和。 第8页 共64页 4.2 动态规划的基本概念和基本原理 一、基本概念 1、阶段 2、状态 3、决策和策略 4、状态转移方程 5、指标函数 第9页 共64页 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 4 2 1 3 8 2 2 3 3 3 5 5 2 6 6 4 3 例4-2 最短路线问题 给定线路网络图如下，各点间连线上的数字表示 距离，现要从A地向G地铺设一条输油管道，问应选 择什么路线，使总距离最短？ 图4-2 第10页 共64页 1、阶段（阶段（stagestage） 将所给问题的过程，按时间或空间特征分解 成若干互相联系的阶段，用k表示。如例4-2中， 问题分为AB、BC共6个阶段，k = 6。 2、状态（状态（statestate） 指各阶段开始时过程所处的自然状况或客观条 件。状态应具有“无后效性无后效性”，即当前阶段状态给 定时，这个阶段以后过程的演变与该阶段以前各 阶段的状态无关。 如：S1=A，S2=B1,B2， 第11页 共64页 3、决策（决策（decisiondecision）与策略（）与策略（policy policy） 当某一阶段的状态确定后，可以作出不同的决 定或选择，从而确定下一阶段的状态，这种决定或 选择称为决策。 如：从第二阶段的状态B1出发，可以选择下一阶段 的C1C3，即 D2(B1) = C1,C2,C3 若决定选择C3，则 d2(B1) = C3 一组有序的决策序列构成一个策略，从第k 阶 段至第n 阶段的一个策略称为后部子策略，记为 Pkn （dk，dk+1，dn）。 例4-2 第12页 共64页 4、状态转移方程状态转移方程 系统由一个阶段的一个状态转变到下一个阶 段的另一个状态称为状态转移。其对应状态和决 策的关系称为状态转移方程。记为 第13页 共64页 5、阶段指标阶段指标 衡量在一个阶段某个状态下各决策所对应的 某种数量指标或效果，记为 6、指标函数指标函数 衡量所选策略优劣的数量指标或效果。最优 指标函数表示从第k 个阶段采用最优策略 到 过程终止时的最佳效益值，记为 第14页 共64页 例4-2 最短路线问题 穷举法 动态规划法 得最优线路为： 第15页 共64页 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 5 3 7 6 3 3 4 1 2 3 3 2 6 4 3 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 该点到G点的最短距离 图4-3 上述最短路线的计算过程可用图直观表示(标 号法)，如图4-3所示，结点上方矩形内的数字表 示该点到终点的最短距离。 标号法过程 第16页 共64页 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段 5 3 1 3 6 8 7 6 6 8 3 5 3 4 2 1 3 8 2 2 3 3 3 5 5 2 6 6 4 3 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 图4-4 第17页 共64页 二、最优化原理 Bellman 最优化原理： “一个过程的最优策略具有这样的性质，即无 论开始的状态及初始的决策如何，对先前决策所 形成的状态而言，其以后所有的决策必构成最优 决策后部子过程最优” 第18页 共64页 三、动态规划基本思路 1、将问题划分多个阶段。恰当选择状态变量、决策 变量 及定义最优指标 函数 2、从边界条件开始，逆向或正向逐段递推求 解。 3、各个阶段的最优决策是从全局考虑的，并 非仅考虑本阶段。 其基本方程为 第19页 共64页 建立动态规划的模型，就是分析问题并建 立问题的动态规划基本方程，成功地应用动态 规划方法的关键，在于识别问题本身的多阶段 特征，将问题分解成为可用递推关系式联系起 来的若干子问题。而正确建立基本递推关系方 程的关键又在于正确选择状态变量。 4.3 DP模型的建立与求解 第20页 共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页 共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，3 sk ：第 k 阶段初拥有的资金总量 xk ：项目 k 的投资额，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售价 qk 1 2 3 4 10 9 11 15 12 9 13 17 表4-1 第27页 共64页 问题分4个阶段，即k = 1，2，3，4 sk ：第 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页 逆序递推法 将寻优过程看做连续递推的过程，从最终 阶段开始，逆着实际决策过程的进展方向逐段求 解，在每一段求解中都要利用刚刚求解完那段的 结果，直到初始阶段求出结果回到始点为止。 顺序递推法 从初始阶段向前递推，直到最终阶段为止。 二、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 = 0 k = 1 当 s2 9/2 时 此时，x1 = 0 综上可得 x1 = 0 s2 = 10 9/2 x2 = 0 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 = 2 k = 1 此时，y1 = s1 ，x1 = 0 此时，x2 y2 = H s2 第37页 共64页 综上可得最优决策如下： 库存sk 订购量xk 销售量yk 最大利润为 y1 = s1 ，x1 = 0 x2 y2 = H s2 y3 = s3 ，x3 = H y4 = s4 ，x4 = 0 5005000 00H H H HH H0 第38页 共64页 顺序法与逆序法没有本质的区别。一般来说， 当初始状态给定时，用逆序解法，当终止状态给定 时，用顺序解法。若既给定了初始状态又给定了终 止状态，则两种方法均可使用。如例4-5中终点有 三个，用逆序法求解比较好。 第39页 共64页 一艘货轮在A港装货后驶往F港，中途须靠港加 油、淡水三次，从A港到F港全部可能的航行路线及两港 之间距离如图4-5，F港有三个码头 F1、F2、F3，试求最 合理的停靠的码头及航线，使总路程最短。 例4-5 图4-5 20 30 70 60 45 75 90 120 第40页 共64页 表格求解： 当问题划分的阶段和可供选择的状态较 多时，动态规划可采用表格形式进行求解。 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 6 sk ：第 k 月初的库存 dk ：第k 月的产量 ck ：第k 月的交货量 解： 基本方程为： 0 sk 3 0 dk 4 阶段指标函数 问题描述 第43页 共64页 d6 s6 (4+10d6)( d6 ) + s6 + f7(s7 ) f6(s6) d*6 01 0 14+0 141 1 1+0 10 s601 d610 f6(s6)141 k = 6， s7 =0，c6 =1，则 s6 +d6 1 = 0 d5 s5 (4+10d5)( d5 ) + s5 +f6(s6 ) f5(s5)d*5 0123 0 24+1434+1353 1 15+1425+1262 2 2+1416+1160 3 3+140 k = 5， c5 =2，则 s6 = s5 +d5 - 2 = 0 | 1 0 sk 3 0 dk 4 问题描述 第44页 共64页 d4 s4 (4+10d4)( d4 ) + s4 +f5(s5 ) f4（s4） d*4 01234 0 34+3544+26 693 1 25+3535+2645+16 602 2 16+3526+2636+1646+4 504 3 3+3517+2627+1637+4 380 s50123 d53200 f5(s5)3526164 k = 4， c4 = 3，则 s5 = s4 +d4 - 3 = 0 | 1 | 2 | 3 0 sk 3 0 dk 4 第45页 共64页 d3 s3 (4+10d3)( d3 ) + s3 +f4(s4 ) f3（s3） d*3 01234 1 45+69 1144 2 36+6946+60 1053 3 27+6937+6047+50 962 s40123 d43240 f4(s4)69605038 k = 3， c3 = 5，则 s4 = s3 +d3 - 5 = 0 | 1 | 2 | 3 0 sk 3 0 dk 4 第46页 共64页 d2 s2 (4+10d2)( d2 ) + s2 +f3(s3 ) f2(s2) d*2 01234 0 34+11444+105 1483 1 25+11435+10545+96 1392 2 16+11426+10536+96 1301 3 3+11417+10527+96 1170 s3123 d3432 f3(s3)11410596 k = 2， c2 = 2，则 s3 = s2 +d2 - 2 = 1 | 2 | 3 k = 1， s1 = 0，c1 = 1，则 s2 = d1 - 1 = 0 | 1 | 2 | 3 d1 s1 (4+10d1)( d1 ) + s1 +f2(s2 ) f1(s1) d*1 1234 0 14+14824+13934+13044+117 1614 0 sk 3 0 dk 4 第47页 共64页 综上可得最优决策如下： 库存sk 产量dk 交货量ck 0 3 1 0 0 1 4 0 4 3 3 0 1 2 5 3 2 1 最小费用为 161 千元。 第48页 共64页 某厂生产三种产品，其重量及利润关系表4-5 所示。现将三种产品运往市场出售，运输总重 量不超过6吨。问如何安排运输使总利润最大？ 产品种类重量（吨/件）利润（元/件） 1 2 3 2 4 3 80 180 130 例4-7 背包问题 表4-5 第49页 共64页 方法一 正向递归方法 （见书P110） 方法二 逆向递归方法 第50页 共64页 按装运产品种类，问题分3个阶段 sk ：可用于装载第k种产品的载重量 dk ：装载第k种产品的件数 ak 、ck 分别表示单件第 k 种货物的重量及利润 解： 基本方程为： 0 sk 6 阶段指标函数 第51页 共64页 d3 s3 c3d3 f3(s3) d*3 012 0,1,2 0 00 3,4,5 0130 1301 6 0130260 2602 k = 3， a3 = 3 第52页 共64页 d2 s2 c2d2 + f3(s3) f2(s2) d*2 01 0,1,2 0+0 00 3 0+130 1300 4,5 0+130180+0 1801 6 0+260180+0 2600 k = 2， a2 = 4，s3 = s2 - 4d2 s30，1，23，4，56 d3012 f3(s3)0130260 第53页 共64页 d1 s1 c1d1 + f2(s2) f1(s1) d*1 0123 6 0+26080+180160+0240+0 2600，1 k = 1， a1 = 2，s1 = 6 s20，1，234，56 d20010 f3(s3)0130180260 第54页 共64页 综上可得最优决策如下： 装载能力sk 载重量dk 单位重量ak 6 6 6 0 0 2 2 4 3 最大利润为260元。 装载能力sk 载重量dk 单位重量ak 6 4 0 1 1 0 2 4 3 或 第55页 共64页 产 品 设备量 产 品 1产 品 2产 品 3产 品 4 0 1 2 3 4 5 6 0 20 42 60 75 85 90 0 25 45 57 65 70 73 0 18 39 61 78 90 95 0 28 47 65 74 80 85 例4-8 资源分配问题 某公司新引进6台生产设备，用于4种产品的 生产，投入的设备数量不同利润也不同(见表4- 6)。问应如何分配设备，使总利润最大？ 表4-6（单位：万元） 第56页 共64页 按产品种类顺序，问题分4个阶段。确定对第k个工 厂的投资额看成第k个阶段的决策，k=1,2,3,4。图 示如下： 解： 第57页 共64页 sk ：可分配给第k种产品的设备总量 dk ：分配给第k种产品的设备数量 基本方程为： 0 sk 6 阶段指标函数见表4-6 第58页 共64页 k = 4 时，S4 = 0，1，2，3，4，5，6 d4 s4 v4(s4,d4) f4（s4） d*40123456 0 0 00 1 028 281 2 02847 472 3 0284765 653 4 028476574 744 5 02847657480 805 6 0284765748085 856 利润表 第59页 共64页 d3 s3 v3(s3,d3) + f4(s4) f3(s3) d*30123456 0 0+0 00 1 0+2818+0 280 2 0+4718+2839+0 470 3 0+6518+4739+2861+0 672 4 0+7418+6539+4761+2878+0 893 5 0+8018+7439+6561+4778+2890+0 1083 6 0+8518+8039+7461+6578+4790+2895+0 1263 s40123456 d40123456 f4(s4)0284765748085 k = 3 时，S3 = 0，1，2，3，4，5，6 利润表 第60页 共64页 d2 s2 v2(s2,d2) + f3(s3) f2(s2) d*2 0123456 0 0+0 00 1 0+2825+0 280 2 0+4725+2845+0 531 3 0+6725+4745+2857+0 732 4 0+8925+6745+4757+2865+0 921，2 5 0+108