1、第第1页页 共共64页页第四章第四章 动态规划动态规划 Dynamic Programming（DP）动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化问题的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。第第2页页 共共64页页 动态规划是分析某一类问题的一种途径。它不像LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的
2、技巧去求解。第第3页页 共共64页页 本章主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过一些典型的应用问题说明它的应用。第第4页页 共共64页页4.1 4.1 多阶段决策过程的最优化多阶段决策过程的最优化一、多阶段决策过程一、多阶段决策过程 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段（“时段”），在每一阶段都要作出决策，全部过程的决策是一个决策的序列。第第5页页 共共64页页 某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大，如图4-1所示。例4-1 时间阶段示例（机器负荷问题）图4-1 机器
3、负荷问题第第6页页 共共64页页B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643例4-2 空间阶段示例（最短路线问题）给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-2第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段第第7页页 共共64页页二、多阶段决策过程最优化的目标二、多阶段决策过程最优化的目标生产存储问题投资决策问题设备更新问题三、示三、示 例例 达到整个活动过程的总体效果的最优，而非各单个阶段最优的简单总和。第第8页页 共共64页页4.2 4.
4、2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、基本概念一、基本概念1、阶段2、状态3、决策和策略4、状态转移方程5、指标函数第第9页页 共共64页页B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643例4-2 最短路线问题 给定线路网络图如下，各点间连线上的数字表示距离，现要从A地向G地铺设一条输油管道，问应选择什么路线，使总距离最短？图4-2第第10页页 共共64页页1、将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，用k表示。如例4-2中，问题分为AB、BC共6个阶段，k=6。2、指各阶段开始
5、时过程所处的自然状况或客观条件。状态应具有“”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。如：S1=A，S2=B1,B2，第第11页页 共共64页页3、当某一阶段的状态确定后，可以作出不同的决定或选择，从而确定下一阶段的状态，这种决定或选择称为决策。如：从第二阶段的状态B1出发，可以选择下一阶段 的C1C3，即 D2(B1)=C1,C2,C3 若决定选择C3，则 d2(B1)=C3 一组有序的决策序列构成一个策略，从第k 阶段至第n 阶段的一个策略称为后部子策略，记为 Pkn（dk，dk+1，dn）。第第12页页 共共64页页4、系统由一个阶段的一个状态转变到下
6、一个阶段的另一个状态称为状态转移。其对应状态和决策的关系称为状态转移方程。记为),(1kkkkdsTs 第第13页页 共共64页页5、衡量在一个阶段某个状态下各决策所对应的某种数量指标或效果，记为 ),(kkkdsv6、衡量所选策略优劣的数量指标或效果。最优指标函数表示从第k 个阶段采用最优策略 到过程终止时的最佳效益值，记为)()(,knkkksVoptsf*,nkP第第14页页 共共64页页例4-2 最短路线问题穷举法动态规划法间管道线路的长度间管道线路的长度到到：从：从)(),(kkkkkksdsdsv短短管管道道长长度度按按最最佳佳线线路路铺铺设设时时的的最最出出发发到到终终点点：从从
7、G)(kkkssf3)(4)(2616 FfFf73543min)(),()(),(min)(262151611515 FfFEvFfFEvEf115)(FEd 得最优线路为：GFEDCBA22121第第15页页 共共64页页B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G537633412332643437597681310912131618该点到G点的最短距离图4-3 上述最短路线的计算过程可用图直观表示(标号法)，如图4-3所示，结点上方矩形内的数字表示该点到终点的最短距离。第第16页页 共共64页页B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第二阶段
8、第三阶段第四阶段第五阶段第六阶段531368766835342138223335526643437597681310912131618图4-4第第17页页 共共64页页二、最优化原理二、最优化原理Bellman 最优化原理：“一个过程的最优策略具有这样的性质，即无论开始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优决策后部子过程最优”第第18页页 共共64页页三、动态规划基本思路三、动态规划基本思路1、将问题划分多个阶段。恰当选择状态变量、决策变量 及定义最优指标函数2、从边界条件开始，逆向或正向逐段递推求解。3、各个阶段的最优决策是从全局考虑的，并非仅考虑本阶
9、段。其基本方程为 0)()()(,()(1111)()(nnkkkkkksDsdkksfsfsdsvoptsfkkkk第第19页页 共共64页页 建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题。而正确建立基本递推关系方程的关键又在于正确选择状态变量。4.3 DP4.3 DP模型的建立与求解模型的建立与求解第第20页页 共共64页页一、一、DP模型的建立模型的建立1、正确、明确地划分阶段 k，k=1，2，3，n。2、正确选择并确定状态变量 sk 及状态集合 Sk。3、确定决
10、策变量 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
11、 时，收益分别为 g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32，问应该如何分配投资数额才能使总收益最大？该问题表面上看与时间无明显关系，其静态模型：010.294max313212321xxxxtsxxxz第第24页页 共共64页页 现人为地给它赋予“时段”的概念，将投资项目排序，首先考虑项目1的投资，然后考虑项目2的投资，问题分为3个阶段，每个阶段只决定一个项目的投资金额。第第25页页 共共64页页问题分三个阶段，即k=1，2，3sk：第 k 阶段初拥有的资金总量xk：项目 k 的投资额，0 xk sk sk+1=sk-xk Vk(sk,xk)=gk(xk)解：基本方程
12、为：0)()()(max)(44110sfsfxgsfkkkksxkkkk第第26页页 共共64页页例4-4 采购与销售问题 P103 例2 某商店在未来四个月里，利用一个仓库经销某种商品。仓库最大容量H=1000件，每月中旬订购商品并于下月初到货。估计未来四个月该商品的购价pk及售价qk如表4-1所示。假定商店在1月初库存500件，每月的需求不限，问应如何计划每月的订购及销售数量，使总利润最大（不考虑库存费用）。月份 k购价 pk售价 qk123410911151291317表4-1第第27页页 共共64页页问题分4个阶段，即k=1，2，3，4sk：第 k 月初的库存xk，yk：第k 月的订
13、购及销售量解：基本方程为：kkkkkysHxHssy 00,0k即即 0)(00)(max)(5511sfysHxsysfxpyqsfkkkkkkkkkkkkkkkkkxyss1状态转移方程为kkkkkkkkxpyqyxsv),(阶段指标函数：第第28页页 共共64页页课堂练习 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如表4-2所示。问应如何分配，可使所产生的总效益最大？表4-2 效益表第第29页页 共共64页页解：阶段k=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；状态sk表示在第k阶段初还剩有的可分台数；决策xk表示第k阶段分配的设备台数；状态转
14、移sk+1=sk-xk；阶段指标vk 表示第k阶段分配后产生的效益；指标函数：基本方程：第第30页页 共共64页页逆序递推法 将寻优过程看做连续递推的过程，从最终阶段开始，逆着实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。顺序递推法 从初始阶段向前递推，直到最终阶段为止。二、二、DP模型的求解模型的求解P106 例3第第31页页 共共64页页sk+1=sk xkg1(x1)=4x1 g2(x2)=9x2 g3(x3)=2x32 例4-3 分配投资问题的逆序求解基本方程为：0)()()(max)(44110sfsfxgsfkkkks
15、xkkkk第第32页页 共共64页页可证明极可证明极大值只可大值只可能在端点能在端点取得取得k=32max)(2303333xsfsx 232s 此时，此时，x3=s3 k=229max)(23202222sxsfsx 此时，此时，x2=s2)(29max2222022xsxsx otherssss,22/9,92222此时，此时，x2=0k=1当当 s2 9/2 时24max)(22101111sxsfsx )(24max2111011xsxsx 2002,4max211 ss此时，此时，x1=0 综上可得x1=0 s2=10 9/2x2=0 s3=10 x3=10 即将全部资金投资于第 3
16、 个项目，可获得最大收益 200 万元。x2=0 第第34页页 共共64页页sk+1=sk+xk yks1=500 H=1000 例4-4 采购与销售问题的逆序求解基本方程为：0)(00)(max)(5511sfysHxsysfxpyqsfkkkkkkkkkkkkk第第35页页 共共64页页k=41517max)(44004444444xysfsyHxsy 417s 此时，此时，y4=s4，x4=0 k=3)(1113max)(4433003333333sfxysfsyHxsy )(171113max33333yxsxy 4617max333yxs 3136sH 此时，此时，y3=s3，x3=
17、H 第第36页页 共共64页页k=2k=1)(1012max)(2211001111111sfxysfsyHxsy )(9101012max11111yxsHxy 11210sH 此时，此时，y1=s1，x1=0)(99max)(3322002222222sfxysfsyHxsy )(13699max22222yxsHxy 44136max222yxsH 2910sH 此时，此时，x2 y2=H s23910max111yxsH 第第37页页 共共64页页综上可得最优决策如下：库存sk 订购量xk 销售量yk 最大利润为y1=s1，x1=0 x2 y2=H s2y3=s3，x3=H y4=s4
18、，x4=0 500500000HHHHHH01600012101 sH第第38页页 共共64页页 顺序法与逆序法没有本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。如例4-5中终点有三个，用逆序法求解比较好。第第39页页 共共64页页 一艘货轮在A港装货后驶往F港，中途须靠港加油、淡水三次，从A港到F港全部可能的航行路线及两港之间距离如图4-5，F港有三个码头 F1、F2、F3，试求最合理的停靠的码头及航线，使总路程最短。例4-5图4-520307060457590120第第40页页 共共64页页表格求解
19、：当问题划分的阶段和可供选择的状态较多时，动态规划可采用表格形式进行求解。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 月的交货量解：基本方程为
20、：0,0)(3040)(),(min)(717711sssfcdsdsfdsvsfkkkkkkkkkkkkkkkcdss1:状态转移方程 0040104),(kkkkkkkkdsdsddsv0 sk 3 0 dk 4 阶段指标函数第第43页页 共共64页页 d6s6(4+10d6)(d6)+s6 +f7(s7)f6(s6)d*601014+014111+010s601d610f6(s6)141k=6，s7=0，c6=1，则，则 s6+d6 1=0 d5s5(4+10d5)(d5)+s5+f6(s6)f5(s5)d*50123024+1434+1353115+1425+126222+1416+1
21、16033+140k=5，c5=2，则，则 s6=s5+d5-2=0|10 sk 3 0 dk 4 第第44页页 共共64页页 d4 s4(4+10d4)(d4)+s4+f5(s5)f4（s4）d*401234034+3544+26693125+3535+2645+16602216+3526+2636+1646+450433+3517+2627+1637+4380s50123d53200f5(s5)3526164k=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
22、）d*301234145+691144236+6946+601053327+6937+6047+50962s40123d43240f4(s4)69605038k=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*201234034+11444+1051483125+11435+10545+961392216+11426+10536+96130133+11417+10527+961170s3123d3432f3(s3)11410596k=2，c2=2，则，则 s
23、3=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*11234014+14824+13934+13044+11716140 sk 3 0 dk 4 第第47页页 共共64页页综上可得最优决策如下：库存库存sk 产量产量dk 交货量交货量ck 031001404 330125321最小费用为 161 千元。第第48页页 共共64页页 某厂生产三种产品，其重量及利润关系表4-5所示。现将三种产品运往市场出售，运输总重量不超过6吨。问如何安排运输使总利润最大？产品种类产品种类重量（吨
24、重量（吨/件）件）利润（元利润（元/件）件）12324380180130例4-7 背包问题 表表4-5第第49页页 共共64页页方法一 正向递归方法（见书P110）方法二 逆向递归方法 第第50页页 共共64页页按装运产品种类，问题分3个阶段sk：可用于装载第k种产品的载重量dk：装载第k种产品的件数ak、ck 分别表示单件第 k 种货物的重量及利润解：解：基本方程为：6,0)()(max)(14411ssfsfdcsfkkkkkkkkkkdass1:状态转移方程kkkkkdcdsv),(0 sk 6 阶段指标函数第第51页页 共共64页页 d3s3c3d3 f3(s3)d*30120,1,2
25、0003,4,501301301601302602602k=3，a3=3第第52页页 共共64页页 d2s2c2d2 +f3(s3)f2(s2)d*2010,1,20+00030+13013004,50+130180+0180160+260180+02600k=2，a2=4，s3=s2-4d2s30，1，23，4，56d3012f3(s3)0130260第第53页页 共共64页页 d1s1c1d1 +f2(s2)f1(s1)d*1012360+26080+180160+0240+02600，1k=1，a1=2，s1=6s20，1，234，56d20010f3(s3)0130180260第第54
26、页页 共共64页页综上可得最优决策如下：装载能力装载能力sk 载重量载重量dk 单位重量单位重量ak666002243最大利润为260元。装载能力装载能力sk 载重量载重量dk 单位重量单位重量ak640110243或或第第55页页 共共64页页产产 品品设备量设备量产产 品品 1 1产产 品品 2 2产产 品品 3 3产产 品品 4 401234560204260758590025455765707301839617890950284765748085例4-8 资源分配问题 某公司新引进6台生产设备，用于4种产品的生产，投入的设备数量不同利润也不同(见表4-6)。问应如何分配设备，使总利润最
27、大？表表4-6（单位：万元）（单位：万元）第第56页页 共共64页页按产品种类顺序，问题分4个阶段。确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：解：第第57页页 共共64页页sk：可分配给第k种产品的设备总量dk：分配给第k种产品的设备数量基本方程为：6,0)(,1,0)(),(max)(15511ssfsdsfdsvsfkkkkkkkkkkkkdss1:状态转移方程0 sk 6),(kkkdsv阶段指标函数见表4-6第第58页页 共共64页页k=4 时，时，S4=0，1，2，3，4，5，6 d4 s4v4(s4,d4)f4（s4）d*4012345600001
28、02828120284747230284765653402847657474450284765748080560284765748085856第第59页页 共共64页页 d3 s3v3(s3,d3)+f4(s4)f3(s3)d*3012345600+00010+2818+028020+4718+2839+047030+6518+4739+2861+067240+7418+6539+4761+2878+089350+8018+7439+6561+4778+2890+0108360+8518+8039+7461+6578+4790+2895+01263s40123456d40123456f4(s4
29、)0284765748085k=3 时，时，S3=0，1，2，3，4，5，6 第第60页页 共共64页页 d2 s2v2(s2,d2)+f3(s3)f2(s2)d*2012345600+00010+2825+028020+4725+2845+053130+6725+4745+2857+073240+8925+6745+4757+2865+0921，250+10825+8945+6757+4765+2870+0114160+12625+10845+8957+6765+4770+2873+01342s30123456d30002333f3(s3)028476789108126k=2 时，时，S2=
30、0，1，2，3，4，5，6 第第61页页 共共64页页 d1 s1v1(s1,d1)+f2(s2)f1(s1)d*1012345660+13420+11442+9260+7375+5385+2890+01340，1，2s20123456d200121,212f2(s2)028537392114134k=1 时，时，S1=6 第第62页页 共共64页页综上可得最优决策如下：设备总数sk 投资设备数dk 66410231最大利润为134万元。或设备总数sk 投资设备数dk 65411131或设备总数sk 投资设备数dk 64312121或设备总数sk 投资设备数dk 64222202第第63页页
31、共共64页页最大总利润（万元）产品1 产品2产品3产品4方案10台2台3台1台134方案21台1台3台1台134方案32台1台2台1台134方案42台2台0台2台134即第第64页页 共共64页页0204260758590025455765707301839617890950284765748085s1=6s2=0s3=0s3=1s3=2s3=3s3=4s3=5s3=6s4=0s4=1s4=2s4=3s4=4s4=5s4=6s5=090s2=1s2=2s2=3s2=4s2=5s2=6857560422000284765748085028476789108126028537392114134134或或 问题问题最短路径问题最短路径问题
