动态规划运筹学基础及其应用胡运权第五版1

第五章动态规划2动态规划Dynamicprogramming•五十年代贝尔曼(B.E.Bellman)为代表的研究成果•属于现代控制理论的一部分•以长远利益为目标的一系列决策•最优化原理，可归结为一个递推公式5.1动态规划的最优化原理及其算法5.1.1求解多阶段决策过程的方法例5.1.1最短路问题HLOBIECAFJDGKNPM4352352344771134222548123决策树法ACEHIIFJIFDGJJK可以枚举出20条路径，其中最短的路径长度为164例5.1.1最短路问题•表现为明显的阶段性•一条从A到B的最短路径中的任何一段都是最短的HLOBIECAFJDGKNPM435235234477113422254812161214021457108671189213456阶段HLOBIECAFJDGKNPM435235234477113422254812161214021457108671189213456阶段最优性原理“最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关DADCACAiSdSdSBiSmin则有径的长度点的最短路点到表示由设•因此我们可以从B向回搜索最短路•标记法•如何找出最短路径55.1.2动态规划的基本概念及递推公式•状态(每阶段初始的出发点)–最短路问题中，各个节点就是状态–生产库存问题中，库存量是状态–物资分配问题中，剩余的物资量是状态•控制变量(决策变量)–最短路问题中，走哪条路–生产库存问题中，各阶段的产品生产量–物资分配问题中，分配给每个地区的物资量•阶段的编号与递推的方向–一般采用反向递推，所以阶段的编号也是逆向的–当然也可以正向递推6动态规划的步骤1、确定问题的阶段和编号2、确定状态变量–用Sk表示第k阶段的状态变量及其值3、确定决策变量–用xk表示第k阶段的决策变量，并以xk*表示该阶段的最优决策4、状态转移方程sk-1=g(sk,xk)反向编号sk+1=g(sk,xk)正向编号5、直接效果–直接一步转移的效果dk(sk,xk)6、总效果函数–指某阶段某状态下到终端状态的总效果，它是一个递推公式)),(),,((),(111kkkkkkkkkkxsfxsdhxsf7动态规划的步骤–hk是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有终端的边际效果一般为f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为f0(s0,x0)=1从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段85.2动态规划模型举例5.2.1产品生产计划安排问题例1某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。9例1产品生产计划安排•设xk为第k阶段生产量，则有直接成本dk(sk,xk)=ckxk+2sk•状态转移公式为sk-1=sk+xk-yk•总成本递推公式第一阶段：(即第4月份)由边界条件和状态转移方程s0=s1+x1y1=s1+x16=0得s1+x1=6或x1=6s10估计第一阶段，即第4月份初库存的可能状态：0s1306712=5，所以，s1[0,5]10第一阶段最优决策表s1x1f1(s1,x1)06456153822430833234421605186第二阶段：最大可能库存量7件由状态转移方程：s1=s2+x2120及x210，可知s2[2,7]，minx2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6)=22+8010+456=1260得第二阶段最优决策表，如下s2x25678910x2*f2(s2,x2*)21260*10126031182*11889118241104*111011168110451026*103210381044710266948*95496096697269487870*8768828888949005870s1=0s1=1s1=2s1=3s1=4s1=511第二阶段最优决策表s3x35678910x3*f3(s3,x3*)019081902*1019021183818321826*10182621768176217561750*101750316981692168616801674*1016744162816221616161016041598*101598s2=2s2=3s2=4s2=5s2=6s2=7第三阶段：最大可能库存量4件由状态转移方程：s2=s3+x372及x310，可知s3[0,4]，minx3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8)=21+7210+1104=1826得第三阶段最优决策表，如下s2x2*f2(s2,x2*)2101260391182481104571026669487587012第三阶段最优决策表第四阶段：初始库存量s4=0由状态转移方程：s3=s4+x460可知x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下回溯得此表13例2生产–库存管理问题(连续变量)设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设sk为第k季初的库存量，则边界条件为s1=s5=0设xk为第k季的生产量，设yk为第k季的订货量；sk，xk，yk都取实数，状态转移方程为sk+1=sk+xk-yk仍采用反向递推，但注意阶段编号是正向的目标函数为412,,,1)005.0(min)(4321iiixxxxsxxf14例2生产–库存管理问题(连续变量)第一步：(第四季度)总效果f4(s4,x4)=0.005x42+s4由边界条件有：s5=s4+x4–y4=0，解得：x4*=1200–s4将x4*代入f4(s4,x4)得：f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)总效果f3(s3,x3)=0.005x32+s3+f4*(s4)将s4=s3+x3–500代入f3(s3,x3)得：15例2生产–库存管理问题(连续变量)第三步：(第二、三、四季度)总效果f2(s2,x2)=0.005x22+s2+f3*(s3)将s3=s2+x2700代入f2(s2,x2)得：注意：阶段最优总效果仅是当前状态的函数，与其后的决策无关16例2生产–库存管理问题(连续变量)第四步：(第一、二、三、四季度)总效果f1(s1,x1)=0.005x12+s1+f2*(s2)将s2=s1+x1–600=x1–600代入f1(s1,x1)得：由此回溯：得最优生产–库存方案x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。175.2.2资源分配问题例3某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。31,,3)(max)(321iixxxxdxf解：设分配人员的顺序为市场1,2,3，采用反向阶段编号。设sk为第k阶段尚未分配的人员数，边界条件为s3=9设xk为第k阶段分配的推销人员数；仍采用反向递推，状态转移方程为sk–1=sk–xk目标函数为18例3第一阶段：给第三市场分配s1有0~9种可能，第一阶段最优决策表如下：为什么与例1的第一阶段的表有差别？因为不存在边界条件s0=019例3第二阶段：给第二市场分配s2有0~9种可能，第二阶段最优决策表如下：20例3第三阶段：给第一市场分配由边界条件s3=9，第三阶段最优决策表如下：x3s30123456789x3*f3*92112132182172152082062022012002218得决策过程：x3*=2,x2*=0,x1*=7,f3*=218即市场1分配2人，市场2不分配，市场3分配7人最优解与分配的顺序有关吗？215.2.2资源分配问题例4项目选择问题某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。•上述问题的静态规划模型如下：•这是一类0-1规划问题•该问题是经典的旅行背包问题(Knapsack)•该问题是NP-complete项入选项未入选1030)(maxkkxxwxvxfkkkkkkk22例4项目选择问题解：设项目选择的顺序为A,B,C,D;1、阶段k=1,2,3,4分别对应D,C,B,A项目的选择过程2、第k阶段的状态sk，代表第k阶段初尚未分配的投资额3、第k阶段的决策变量xk,，代表第k阶段分配的投资额4、状态转移方程为sk–1=sk–wkxk5、直接效益dk(sk,xk)=vk或06、总效益递推公式该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。2324例4第一阶段(项目D)的选择过程•s18时，x1只能取0；w1=8,v1=5s1x1d1(s1,x1)s0=s1-w1x1f0(s0,x0*)f1(s1,x1*)条件003003x4=x2=1x3=0005005x4=x3=1x2=00080815005x3=x2=1x4=0001501515705x3=x2=0x4=10018018151005x4=x3=0x2=10020020151205x4=x2=0x3=10030030152205x4=x3=x2=025例4第二阶段(项目C)的选择过程26w3=10v3=8s3x3d3(s3,x3)s2=s3-w3x3f2(s2,x2*)f3(s3,x3*)条件001599*1518508x4=1003014143018201422*x4=0项目决策投资额直接收益vkAx4=000Bx3=1108Cx2=1129Dx1=185总额3022例4第三阶段(项目B)的选择过程w4=15v4=12s4x4d4(s4,x4)s3=s4-w4x4f3(s3,x3*)f4(s4,x4*)条件00302222*3011215921第四阶段(项目A)的选择过程275.2.3串联系统可靠性问题例5有A,B,C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器A,B,C产生次品的概率分别为pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款5万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案1:不拨款，机器保持原状；方案2:加装监视设备，每部机器需款1万元；方案3:加装设备，每部机器需款2万元；方案4:同时加装监视及控制设备，每部机器需款3万元；采用各方案后，各部机器的次品率如下表。ABC不拨款30%40%20%拨款1万元20%30%10%拨款2万元10%20%10%拨款3万元5%10%6%28例5串联机器可靠性问题解：为三台机器分配改造拨款，设拨款顺序为A,B,C，阶段序号反向编号为k，即第一阶段计算给机器C拨款的效果。设sk为第k阶段剩余款，则边界条件为s3=5；设xk为第k阶段的拨款额；状态转移方程为sk-1=sk-xk；目标函数为maxR=(1-PA)(1-