1.4线性规划应用案例

线性规划授课教师：王淑华运筹学课件案例分析1.人力资源分配的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030§1人力资源分配的问题解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0注解该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。♂返回配料问题某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表1，产品规格单价（元/公斤）A原料Ⅰ不少于50%原料Ⅱ不超过25%50B原料Ⅰ不少于25%原料Ⅱ不超过50%35C不限25问如何安排生产使得生产利润最大？原料日最大供应量单价(元/公斤)Ⅰ10065Ⅱ10025Ⅲ6035原料的单价与每天最大供应量如表2配料问题案例问题问题分析模型求解结果分析问题分析变量约束条件目标函数变量生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数，设用于生产第种产品的第种原料数为3,2,1,3,2,1,jixij约束条件规格约束等价于5.0,25.025.0,5.023222121232221211312111113121111xxxxxxxxxxxxxxxx0,0303,0232221232221131211131211xxxxxxxxxxxx资源约束60100100332313322212312111xxxxxxxxx目标函数总产值总成本总利润=总产值-总成本=)(25)(35)(50333231232221131211xxxxxxxxx)(35)(25)(65332313322212312111xxxxxxxxx3331222113121133231332221231211133323123222113121110401030152515)(35)(25)(65)(25)(35)(50xxxxxxxxxxxxxxxxxxxxxxxxx模型3,2,1,3,2,1,060100100003030..10401030152515max33231332221231211123222123222113121113121133312221131211jixxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxij求解model:max=-15*x11+25*x12+15*x13-30*x21+10*x22-40*x31-10*x33;-x11+x12+x13=0;-x11+3*x12-x13=0;-3*x21+x22+x23=0;-x21+x22-x23=0;x11+x21+x31=100;x12+x22+x32=100;x13+x23+x33=60;endGlobaloptimalsolutionfoundatiteration:5Objectivevalue:500.0000VariableValueReducedCostX11100.00000.000000X1250.000000.000000X1350.000000.000000X210.00000015.00000X220.0000000.000000X310.00000045.00000X330.00000010.00000X230.0000000.000000X320.0000000.000000套裁下料问题某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.47.37.27.16.6剩余料头00.10.20.30.8设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。得线性规划模型为：Minx1+x2+x3+x4+x5s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0Matlab程序：C=[1,1,1,1,1]';b1=[0,0,0,0,0]';b2=[100,100,100]';A1=[-1,0,0,0,0;0,-1,0,0,0;0,0,-1,0,0;0,0,0,-1,0;0,0,0,0,-1]';A2=[1,2,0,1,0;0,0,2,2,1;3,1,2,0,3];[x,fv]=linprog(C,A1,b1,A2,b2)求解结果：x=12.330127.669917.669932.33010fv=90.0000用软件计算得出最优下料方案：按方案1下料12根；按方案2下料28根；按方案3下料18根，按方案4下料32根。只需90根原材料就可制造出100套钢架。注意：1.在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。2.目标函数也可用：使剩余料头最少。投资问题某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如右表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？项目风险指数（次/万元）A1B3C4D5.5解：1）确定决策变量：连续投资问题设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx242）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤100xij≥0(i=1、2、3、4、5；j=1、2、3、4）Matlab程序：计算结果（注：变量顺序按行排列）x=170.000059.15620.00004.804733.500030.000027.843822.571830.000080.0000100.0000fv=-341.3500b)所设变量与问题a相同，目标函数为风险最小，有Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下：Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0(i=1、2、3、4、5；j=1、2、3、4）