运筹学第5章：动态规划

15.2动态规划模型举例5.2.1产品生产计划安排问题例1某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。2例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估计第一阶段，即第4月份初库存的可能状态：s1[0,5]3第一阶段最优决策表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=54第二阶段最优决策表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*)210126039118248110457102666948758705第三阶段最优决策表第四阶段：初始库存量s4=0由状态转移方程：s3=s4+x4-60可知x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下回溯得此表6例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)(4321iiixxxxsxxf7例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)得：8例2生产–库存管理问题(连续变量)第三步：(第二、三、四季度)总效果f2(s2,x2)=0.005x22+s2+f3*(s3)将s3=s2+x2-700代入f2(s2,x2)得：注意：最优阶段总效果仅是当前状态的函数，与其后的决策无关9例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。105.2.2资源分配问题例3某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。31,,3)(min)(321iixxxxdxf解：设分配人员的顺序为市场1,2,3，采用反向阶段编号。设sk为第k阶段尚未分配的人员数，边界条件为s3=9设xk为第k阶段分配的推销人员数；仍采用反向递推，状态转移方程为sk–1=sk–xk目标函数为11例3第一阶段：给第三市场分配s1有0~9种可能，第一阶段最优决策表如下：为什么与例1的第一阶段的表有差别？12例3第二阶段：给第二市场分配s2有0~9种可能，第二阶段最优决策表如下：13例3第三阶段：给第一市场分配由边界条件s3=9，第三阶段最优决策表如下：x3s30123456789x3*f3*92112132182172152082062022012002218得决策过程：x3*=2,x2*=0,x1*=7,f3*=218即市场1分配2人，市场2不分配，市场3分配7人最优解与分配的顺序有关吗？145.2.2资源分配问题例4项目选择问题某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。•上述问题的静态规划模型如下：这是一类0-1规划问题该问题是经典的旅行背包问题(Knapsack)该问题是NP-complete项入选项未入选1030)(maxkkxxwxvxfkkkkkkk15例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、总效益递推公式该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。1617例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=018例4第二阶段(项目C)的选择过程19w3=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)的选择过程205.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%21例5串联机器可靠性问题解：为三台机器分配改造拨款，设拨款顺序为A,B,C，阶段序号反向编号为k，即第一阶段计算给机器C拨款的效果。设sk为第k阶段剩余款，则边界条件为s3=5；设xk为第k阶段的拨款额；状态转移方程为sk-1=sk-xk；目标函数为maxR=(1-PA)(1-PB)(1-PC)仍采用反向递推第一阶段：对机器C拨款的效果R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1)x1s10123x1*R1(s1,x1*)00.800.810.80.910.920.80.90.91,20.930.80.90.90.9430.9440.80.90.90.9430.9450.80.90.90.9430.9422第二阶段最优决策表第二阶段：对机器B,C拨款的效果由于机器A最多只需3万元，故s22递推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)例：R2(3,2)=d2(3,2)R1(1,1)=(1-0.2)0.9=0.72得第二阶段最优决策表x1s1x1*R1(s1,x1*)000.8110.921,20.9330.94430.94530.94x2s20123x2*R2(s2,x2*)20.540.630.6420.6430.5640.630.720.722,30.7240.5640.6580.720.8130.8150.5640.6580.7520.8130.8123第二阶段最优决策表第三阶段：对机器A,B,C拨款的效果边界条件：s3=5递推公式：R3(s3,x3)=d3(s3,x3)R2(s2,x2*)例：R3(5,3)=d3(5,3)R2(2,2)=(1-0.05)0.64=0.608得第三阶段最优决策表x2s2x2*R2(s2,x2*)220.6432,30.72430.81530.81s3x30123x3*R3(s3,x3*)50.5670.6480.6480.6081,20.648回溯：有多组最优解。I：x3=1,x2=3,x1=1,R3=0.80.90.9=0.648II：x3=2,x2=2,x1=1,R3=0.90.80.9=0.648III:x3=2,x2=3,x1=0,R3=0.90.90.8=0.648