1、第四章第四章 动态规划动态规划Dynamic Programming多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点 多阶段决策过程特点多阶段决策过程特点:状态状态 s1阶段阶段1 1g1决策决策d1状态状态 s2决策决策d2阶段阶段2 2g2状态状态 s3.状态状态 sk决策决策dk阶段阶段k kgk状态状态 sk+1.状态状态 sn决策决策dn阶段阶段n ngn状态状态 sn+1多阶段决策问题(Multi-Stage decision process)上的数字是对应的路上的数字是对应的路长。问：应如何选择行驶路线，才能使从长。问：应如
2、何选择行驶路线，才能使从A A、B B、C C、D D各城市到各城市到E E城市的行驶路城市的行驶路程程按照过程进行的先后，每个阶段的按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，状态可分为初始状态和终止状态，或称输入状态和输出状态，或称输入状态和输出状态，阶段阶段k k的的初始状态记作初始状态记作s sk k，终止状态记为，终止状态记为s sk k+1+1。但为了清楚起见，但为了清楚起见，通常定义阶段的通常定义阶段的状态即指其初始状态状态即指其初始状态。动态规划数学模型由最优指标函数递推表达式、边界条件及状态转移方程构成。动态规划数学模型由最优指标函数递推表达式、边界条件及状态
3、转移方程构成。11()1()(,(),1,2,()0(,)kkkkkkkkkkdDsnnkkkfsOptr sdfsknfssTr sd区区区区店店数数123店店数数1230000312149135441416102710751516112S S3 3f f3 3(S S3 3)d d*3 3S S3 3f f3 3(S S3 3)d d*3 300039314141042725115区区区区店店数数123店店数数1230000312149135441416102710751516112R R2 2(d d2 2)+f f3 3(S S3 3)d d 2 2S S2 2012345f f 2
4、2(S S2 2)d d *2 200-00145-5127910-10239121414-142,3,41014171816-1835111519212016213R R1 1(d d1 1)+f f2 2(S S2 2)d d 1 1S S1 1012345f f 1 1(S S1 1)d d *1 15212121221915223sif1(s1)d1*f2(s2)d2*f3(s3)d3*00000151412102723142,39341831045223213115 生产和存储问题生产和存储问题w假设某厂生产的某种产品，以后四个月的订单如下表所示，合同规定在月底前交货，生产每批产品的
5、固定成本为3千元，每批生产的产品的数量不限。每件产品的可变成本为1千元，每批产品的最大生产能力为5件。产品每件每月的存储费用为0.5千元。设1月初有库存1件，4月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本费用最低。月份1234订货量3324wn=4，w状态变量sk（k=1,2,3,4）为每月初的库存，则 s1=1,s5=0,w决策变量xk，每月生产的产量w状态转移方程sk+1=sk+xk-bkkkkkkkk3x0.5s,0 x5d(s,x)0.5s x0 w阶段损益函数d(sk,xk)为各阶段产品的总成本（库存成本+生产成本）w模型kkkkkkkkk 1k 1xD(s)5
6、5f(s)min d(s,x)f(s),k4,3,2,1f(s)0wK=4wS4的取值范围s4本阶段费用s5f5(s5)d(s4,x4)+f5(s5)f4(s4)x4生产费用存储费d(s4,x4)043+4070077133+30.56.5006.56.5223+21.060066313+11.55.5005.55.5400220022最大：S5=S4+x4 b4 S4=5*3+1-(3+3+2)nK=3nS3的取值范围s3本阶段费用s4f4(s4)d(s3,x3)+f3(s3)f3(s3)x3生产费用存储费d(s3,x3)023+20507121233+30616.512.543+40726
7、1353+50835.513.5最大：6 S4=5*2+1-(3+3)s3本阶段费用s4f4(s4)d(s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)113+10.54.50711.510.523+20.55.516.51233+30.56.52612.543+40.57.535.51353+50.58.54210.5s3本阶段费用s4f4(s4)d(s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)2001.01.0078813+1516.511.523+26261233+3735.512.543+484210s3本阶段费用s4f4(s4)d(
8、s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)3001.51.516.58813+11.55.52611.523+21.56.535.51233+31.57.5429.540022268813+12635.511.523+2274295002.52.535.58813+12.56.5428.5s2本阶段费用s3f3(s3)d(s2,x2)+f3(s3)f2(s2)x2生产费用存储费d(s2,x2)033+306012181643+407110.517.553+5082816123+20.55.501217.515.533+30.56.5110.51743+40.57.
9、52815.553+50.58.53816.5213+115012171523+216110.516.533+317281543+418381653+5194817s2本阶段费用s3f3(s3)d(s2,x2)+f3(s3)f2(s2)x2生产费用存储费d(s2,x2)3001.51.501213.513.513+11.55.5110.51623+21.56.52814.533+31.57.53815.543+41.58.54816.553+51.59.55817.5s1本阶段费用s2f2(s2)d(s1,x1)+f2(s2)f1(s1)x1生产费用存储费d(s1,x1)123+20.55.5
10、01621.521.533+30.56.5115.52243+40.57.521522.553+50.58.5313.522w最优解为x1*=2,x2*=5,x3*=0,x4*=4,f1(s1)=21.5w存在特别的规律：w根据再生点性质，简化求解wC(j,i)wfi资源平行分配问题资源平行分配问题假设有某种原材料数量为假设有某种原材料数量为a a，这种材料可以用来生产，这种材料可以用来生产n n种产品，已知生产每种产品所获的收益与所使用的原种产品，已知生产每种产品所获的收益与所使用的原材料的数量关系为材料的数量关系为V Vi i=g=gi i(x(xi i)，其中，其中x xi i表示用于生
11、产第表示用于生产第i i种产品的原材料的数量。种产品的原材料的数量。目标：总收益最大目标：总收益最大1122nnzg(x)g(x)g(x)满足的条件11n2nna xa xa xa背包问题背包问题货货货货物物物物编编编编号号号号 i i123单单位位重重量量（吨吨）345单单单单位位位位价价价价值值值值 C Ci i456nixWxwxwxwxcxcxcZinnnn,10max22112211且为整数，kkkkkkk+1k+1skkk+1kkkkwf(s)maxc xf(s)maxc xf(sw x),x0,1,2,3333xf(s)max6x 333sD(s)0,1,2,53S0,1,2,1
12、0K=3时 x36x3012f3(s3)x3000010002000300040005066160661706618066190661100612122s35x2+f3(s2-4x2)012f2(s2)x200001000200030004055156560665607656086560961111110121110120 x2s2222sD(s)0,1,2,42S0,1,2,10K=2时 x14x1+f2(s1-3x1)0123f1(s1)x100001000200030441454505646066488276488286108101911108121231012101312132s1k1
13、k2kksskwx0,1,2,(,)aMin资金分配问题资金分配问题w某建筑公司拟建造甲乙丙三类住宅出售，甲类住宅每栋耗费100万元，售价200万元，乙类住宅每栋耗资60万元，售价110万元，丙类住宅每栋耗资30万元，售价70万元。由于某种限制，建造每类住宅不得超过3栋。该公司拥有建房资金350万元，问应当如何安排资金可使该公司的住房收益最大。w阶段:将甲乙丙三种住宅的建造计划视为3个阶段，第一阶段建造甲，第二阶段建造乙，第三阶段建造丙w状态变量：sk表示阶段k公司所拥有的资金的数量w决策变量：xk表示阶段k公司建造的数量w状态转移方程：s2=s1-100 x1，s3=s2-60 x2，s1=
14、350w允许决策的集合D3(s3)=0,1,2,min3,s3/30 D2(s2)=0,1,2,min3,s2/60,D1(s1)=0,1,2,min3,s1/100w最大收益fk(sk)表示当第k阶段拥有的资金为sk时从第k到第3阶段获得的最大收益kkkkk 1k 1x44f(s)max(ba)xf(s)f(s)0 x340 x3f3(s3)x3s4=s3-30 x301230-200000-2030-500404010-2060-80040808020-2090-3500408012012030-260s3K=333333443xxf(s)max(7030)xf(s)max40 x D3(
15、s3)=0,1,2,min3,s3/30 x250 x2+f3(s3)f2(s2)x2s3=s2-60 x201230-200000-2030-500+4040030-5060-800+805080060-8090-1100+12050+40120090-110120-1400+12050+80100+0130160-80150-1700+12050+120100+40170190-110180-2000+12050+120100+80150180260-80210-2300+12050+120100+120150+40220290-110240-2600+12050+120100+12015
16、0+80230360-80270-3500+12050+120100+120150+120270390-110s2K=22222233233xxf(s)max(11060)xf(s)max50 xf(s)D2(s2)=0,1,2,min3,s2/60=0.1.2.3,K=11111122122xxf(s)max(200100)xf(s)max100 xf(s)D1(s1)=0,1,2,min3,350/100=0,1,2,3 x1100 x1+f2(s2)f1(s1)x1s2=s1-100 x101233500+270100+230200+170300+403702150s1*12233x2,
17、s150,x1,s90,x3总获利370万元90设设 备备 更更 新新 问问 题题在企业中，经常遇到设备陈旧或部分损坏需要更新的问题。从经济上分析，一种设备应该使用多少年后进行更新最合算。这就是要研究的问题。一台设备的价格为P，运行寿命为m年，每年的维修费用是设备役龄t的函数，记为C(t)；旧设备出售的价格也是设备役龄t的函数，记为S(t)。新设备的役龄为0。现要用该种设备进行为期n年的生产，在n年末，役龄为t的设备残值为R(t)。在n年的生产过程开始时，有一台役龄为T的设备；以后每年都会面临“继续使用”或“更新”的决策。设备更新问题设备更新问题设具体数据如下：设备更新问题设备更新问题对于 k
18、=6：f6(t6)=-R(t6)f6(1)=-25,f6(2)=-17,f6(3)=-8,f6(4)=0,f6(5)=0,f6(6)=0,f6(7)=0对于 k=5：656*5656*5(0)(5)(1)50 100(25)(5)minmin(5)(6)100035min35,(5)100(0)(6)(1)50 100(25)(6)minmin(6)(7)100035min35,(6)100PCSffCfdRPCSffCfdR 对于 k=4：对于 k=3：对于 k=2：12111112111212*1(0)()(1)()()min()(1)()(0)(2)(1)50 10 21 76(2)mi
19、nmin(2)(3)20 97115min115,(2)117P CS sfd sRf sC sf sd sKP CSffCfdR对于 k=1：两个最优策略 设备更新问题设备更新问题由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。110旅行售货员问题旅行售货员问题Traveling Salesman Problem 设有n个城镇，城镇i到城镇j的距离为dij，现求从城镇1出发，经各城镇一次且仅一次，最后返回城镇1的最短路线。旅行售货员问题旅行售货员问题/货郎担问题货郎担问题阶段阶段设S表示从城镇1出发，目前到达某个城镇前经过的城镇（不包括城镇1和目前到达的城镇）。第k阶段为经过
20、城镇的个数为k个，即S中元素个数为k个。k=0,1,n-1。状态变量状态变量第k阶段状态变量(i,S)：从城镇1出发，经过集合S中的k个城镇，目前到达城镇i。k=0:i2,3,n，S=1 k n-2:i2,3,n，S2,3,nk=n-1:i=1，S=2,3,n决策变量决策变量第k阶段决策变量Pk(i,S)：在从城镇1出发，经过集合S中的k个城镇，到达城镇i的最短路径上，到达城镇i前的一个城镇。Pk(i,S)S状态转移状态转移第k阶段状态为(i,S)，第k阶段决策为Pk(i,S)=j，则第k-1阶段状态为(j,Sj)。递推方程递推方程fk(i,S)=minjS dji+fk-1(j,Sj),k=
21、1,2,n-1f0(i,)=d1i设具体数据如下：旅行售货员问题旅行售货员问题/货郎担问题货郎担问题距离距离dij城镇城镇 j1234城城镇镇i10679280973580846550求解：求解：k=0状态状态(2,)(3,)(4,)f0()679求解：求解：k=1状态状态(2,3)(2,4)(3,2)(3,4)(4,2)(4,3)决策决策 j342423第0阶段状态(3,)(4,)(2,)(4,)(2,)(3,)dji859578f0()796967f1()151415141315决策决策 P1342423求解：求解：k=2状态状态(2,3)(2,4)(3,2)(3,4)(4,2)(4,3)
22、决策决策 j342423第0阶段状态(3,)(4,)(2,)(4,)(2,)(3,)dji859578f0()796967f1()151415141315状态状态(2,3,4)(3,2,4)(4,2,3)决策决策 j342423第1阶段状态(3,4)(4,3)(2,4)(4,2)(2,3)(3,2)dji859578f1()141514131515f2()201822决策决策 P2442求解：求解：k k=3=3状态状态(2,3)(2,4)(3,2)(3,4)(4,2)(4,3)决策决策 j342423第0阶段状态(3,)(4,)(2,)(4,)(2,)(3,)dji859578f0()796967f1()151415141315状态状态(1,2,3,4)决策决策 j234第2阶段状态(2,3,4)(3,2,4)(4,2,3)dji856f2()201822f3()23决策决策 P33最优解最优解P3(1,2,3,4)=3P2(3,2,4)=4P1(4,2)=2最短回路12431，路径长度23
