管理运筹学复习.doc

管理运筹学复习(1）某工厂在计划期内要安排，两种产品的生产。生产单位产品所需的设备台时及A,B两种原材料的消耗以及资源的限制如下表所示：资源限制设备11300台时原料A21400kg原料B01250kg工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元,问工厂应分别生产多少单位产品和产品才能使获利最多?解: max z=50X1+100X2 ；满足约束条件： X1+X2300， 2X1+X2400, X2250，X10,X20。（2）:某锅炉制造厂，要制造一种新型锅炉10台,需要原材料为63.54mm的锅炉钢管，每台锅炉需要不同长度的锅炉钢管数量如下表所示：规格/mm需要数量/根规格/mm需要数量/根2640817704216513514401库存的原材料的长度只有5500mm一种规格，问如何下料，才能使总的用料根数最少?需要多少根原材料？解:为了用最少的原材料得到10 台锅炉，需要混合使用14 种下料方案1234567891011121314264021110000000000177001003221110000165100100102103210144000010010120123合计52804410429140805310519149805072486146504953474245314320剩余2201090120914201903095204286398505477589691180设按14 种方案下料的原材料的根数分别为X1，X2，X3，X4,X5,X6 ,X7,X8,X9,X10，X11,X12,X13,X14, 可列出下面的数学模型:min fX1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14满足约束条件： 2X1X2X3X4 80X23X52X62X7X8X9X10 420X3X62X8X93X11X12X13 350X4X7X92X10X122X133X14 10X1，X2，X3，X4,X5，X6，X7，X8，X9,X10，X11,X12，X13，X14 0(3)某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：B1B2B3产量/件A1646200A2655300销量/件150150200应如何调运，使得总运输费最小？解： 此运输问题的线性规划的模型如下min f =6X11+4X12+6X13+6X21+5X22+5X23约束条件 : X11+X12+X13=200X21+X22+X23=300X11+X21=150X12+X22=150X13+X23=200Xij0(i=1，2；j=1,2，3)（4) 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：B1B2B3产量/件A1646300A2655300销量/件150150200500 600应如何组织运输,使得总运输费为最小?解:这是一个产大于销的运输问题,建立一个假想销地B4，得到产销平衡如下表：B1B2B3B4产量/件A16460300A26550300销量/件150150200100600 600（5）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示：B1B2B3产量/件A1646200A2655300销量/件250200200650 500解：这是一个销大于产的运输问题，建立一个假想销地A3，得到产销平衡如下表：B1B2B3产量/件A1646200A2655300A3000150销量/件250200200650 650(6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。需要供应四个地方的销售，这四地的产品需求分别为400箱、250箱、350箱、200箱.三个分厂到四个销地的单位运价如下表所示：甲乙丙丁1分厂211723252分厂101530193分厂23212022 应如何安排运输方案，使得总运费为最小? 如果2分厂的产量从400箱提高到了600箱,那么应如何安排运输方案，使得总运费为最小? 如果销地甲的需求从400箱提高到550箱，而其他情况都同,那该如何安排运输方案，使得运费为最小?解：此运输问题的线性规划的模型如下minf=21X11+17X12+23X13+25X14+10X21+15X22+30X23+19 X24+23X31+21X32+20X33+22X34 约束条件 : X11+X12+X13 +X14=300X21+X22+X23+X24=400X31+X32+X33+X34=500X11+X21+X31=400X12+X22+X32=250X13+X23+X33=350X14+X24+X34=200Xij0(i=1，2，3;j=1，2，3，4)解：这是一个产大于销的运输问题,建立一个假想销地戊,得到产销平衡如下表：甲乙丙丁戊产量/箱1分厂2117232503002分厂101530190（400)6003分厂232120220500销量/箱4002503502002001400 1400解：这是一个销大于产的运输问题，建立一个假想销地4分厂，得到产销平衡如下表：甲乙丙丁产量/箱1分厂211723253002分厂101530194003分厂232120225004分厂0000150销量/箱5502503502001350 1350（7）整数规划的图解法某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示：货物每件体积/立方英尺每件重量/百千克每件利润/百元甲19542乙273403托运限制1365140甲种货物至多托运4件，问两种货物各托运多少件,可使获得利润最大？解：设X1,X2分别为甲、乙两种货物托运的件数,其数学模型如下所示:max z=2X1+3X2约束条件： 195X1+273X2 1365，4X1+40X2 140，X1 4，X1, X20,X1， X2 为整数。(8）指派问题有四个工人,要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示：问应如何指派工作,才能使总的消耗时间为最少？ABCD甲15182124乙19232218丙26171619丁19212317解：引入01变量Xij ，并令 1，当指派第i人去完成第j项工作时；Xij = 0，当不指派第i人去完成第j项工作时；此整数规划的数学模型为:min z=15X11+18X12+21X13+24X14+19X21+23X22+22X23+18 X24+26X31+17X32+16X33+19X34 +19X41+21X42+23X43+17X44约束条件: X11+X12+X13 +X14=1(甲只能干一项工作）X21+X22+X23+X24=1（乙只能干一项工作）X31+X32+X33+X34=1（丙只能干一项工作）X41+X42+X43+X44=1（丁只能干一项工作）X11+X21+X31+X41=1（A工作只能一个人干）X12+X22+X32+X42=1（B工作只能一个人干）X13+X23+X33+X43=1（C工作只能一个人干）X14+X24+X34+X44=1（D工作只能一个人干）Xij为01变量，(i=1，2，3，4；j=1，2，3,4)（9)有优先权的目标规划的图解法一位投资商有一笔资金准备购买股票，资金总额为90000元,目前可选的股票有A、B两种(可以同时投资于两种股票)，其价格以及年收益率和风险系数如下表所示：股票价格/元年收益/（元/年)风险系数A2030.5B5040.2从表可知：股票A的收益率为（3/20）100=15,股票B的收益率为（4/50）100=8，A的收益率比B大，但同时A的风险也比B大，这符合高风险高收益的规律。试求一种投资方案,使得一年的总投资风险不高于700，且投资收益不低于10000元。X1解：设X1、X2 分别表示投资商所购买的股票A和股票B的数量。1。针对优先权最高的目标建立线性规划4000建立线性规划模型如下:20X1+50X2 900003000 min d1+2000约束条件：20X1+50X2 900001000 0。5X1+0.2X2d1+d1 =700X23X1+4X2d2+d2 =10000010005000400030002000X1 ， X2 ， d1+ , d2 0X12。针对优先权次高的目标建立线性规划0.5X1+0.2X2 =7004000建立线性规划模型如下：3000 min d22000约束条件: 20X1+50X2 9000020X1+50X2 90000 0。5X1+0。2X2d1+d1- =70010003X1+4X2-d2+d2 =10000d1+=0050004000300010002000X1 ， X2 ，d1+ ，d1 ，d2+，d2 03.目标规划模型的标准化对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达: min P1（d1+）+P2（d2-） 约束条件： 20X1+50X2 90000 ， 0。5X1+0.2X2d1+d1- =700，3X1+4X2-d2+d2 =10000,X1 ， X2 ,d1+ ，d1- ,d2+，d2 0。(10）某工厂试对产品A、B进行生产，市场需求并不是很稳定，因此对每种产品分别预测了在销售良好和销售较差时的预期利润，这两种产品都经过甲、乙两台设备加工，已知产品A和B分别在甲和乙设备上的单位加工时间，甲、乙设备的可用加工时间以及预期利润如表所示,要求首先是保证在销售较差时，预期利润不少于5千元,其次是要求销售良好时，预期销售利润尽量达到1万元.试建立目标规划模型.AB可用时间甲4345乙2530销售良好时的预期利润(元/件)86100销售较差时的预期利润（元/件）5550解：设工厂生产 A 产品 X1 件，生产 B 产品X2件。按照生产要求，建立如下目标规划模型:min P1（d1+)+P2（d2）约束条件:4X1+3X2 45 ，2X1+5X2 30 5X1+5X2-d1+d1- =50，8X1+6X2d2+d2 =100,X1 ， X2 ，di+ ，di 0。i=1,2（11)动态规划石油输送管道铺设最优方案的选择问题：如图所示,其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区,其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置,线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？3AED2D1C3C2C1B3B2 B1 6 2 55 3 23 3 4 5 7 4 4 4 4 1 5 4 5 解：第四阶段：D1-E 3;D2E 4；第三阶段：C1D1E 5；C2D2E 8；C3D1-E 8；C3-D2-E 8;第二阶段：B1C1D1E 11；B1C2D2-E 11；B2C1D1-E 8； B3C1-D1E 9 ；B3-C2D2-E 9；第一阶段:AB1C1D1E 14;AB1C2D2E 14； AB2C1-D1E 13；AB3C1D1-E 13；AB3-C2D2E 13;最优解:AB2C1D1E；AB3C1D1E；AB3C2D2E最优值:13(12）最小生成树问题 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，,V7表示7个学院办公室，图中的边为可能联网的途径,边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。584723431031V7V4V5V6V1V2V3G 5847234331V7V4V5V6V1V2V3G1 解：在G中找到一个圈（V1，V7，V6，V1)，并知在此圈上边V1,V6的权数10为最大，在G中去掉边V1，V6得图G1 ，如上图所示 5472343131V7V4V5V6V1V2V3G2 472343131V7V4V5V6V1V2V3G3 在G1中找到一个圈(V3，V4，V5，V7，V3），去掉其中权数最大的边 V4，V5，得图G2 ,如上图所示在G2中找到一个圈（V2，V3,V5，V7，V2），去掉其中权数最大的边 V5，V7，得图G3 ，如上图所示72343131V7V4V5V6V1V2V3G47233131V7V4V5V6V1V2V3G5在G3中找到一个圈（V3，V5,V6，V7，V3)，去掉其中权数最大的边 V5，V6，得图G4 ，如上图所示在G4中找到一个圈（V2,V3， V7，V2），去掉其中权数最大的边 V3,V7，得图G5 ,如上图所示在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。这个最小生成树的所有边的总权数为3+3+3+1+2+7=19（18,3）（13）某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图,图中V1，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间(单位：分钟）（27,5）（25,4）（24,3）（4,1）V4（16,2）（0,S）5V26V26V28V27V22V212V216V218V24V2V1V7（快餐店）（配送中心）V5V3V6V2解：给起始点V1标号为（0，S） I=V1,J= V2，V3,V4，V5,V6 ,V7 ，边的集合Vi,Vj Vi,Vj两点中一点属于I，而另一点属于J= V1，V2， V1，V3，并有 S12=L1+C12=0+4=4 ; S13=L1+C13=0+18=18min （S12,S13)= S12 =4给边 V1，V2中的未标号的点V2 标以（4，1）,表示从V1 到V2 的距离为4，并且在V1到V2的最短路径上V2的前面的点为V1.这时I=V1 ，V2,J=V3，V4，V5，V6 ,V7，边的集合Vi，Vj Vi,Vj两点中一点属于I,而另一点属于J= V1，V3， V2，V3， V2,V4，并有S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min （S23,S24 , S13)= S23 =16给边 V2,V3中的未标号的点V3 标以（16,2)这时I=V1 ，V2 ，V3，J=V4,V5，V6 ,V7,边的集合Vi，Vj Vi,Vj两点中一点属于I，而另一点属于J= V2，V4， V3，V4， V3，V5,并有S34=L3+C34=16+2=18 ; S35=L3+C35=16+6=22 ; S24=L2+C24=4+16=20min (S34,S35，S24)= S34 =18给边 V3，V4中的未标号的点V4 标以（18,3）这时I=V1 ，V2 ，V3 ，V4,J=V5，V6 ，V7，边的集合Vi,Vj Vi，Vj两点中一点属于I,而另一点属于J= V4,V6， V4，V5， V3，V5,并有S46=L4+C46=18+7=25 ; S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24给边 V3,V5中的未标号的点V5 标以(24，3）这时I=V1 ，V2 ,V3 ，V4 ，V5 ，J= V6 ，V7，边的集合Vi,Vj Vi，Vj两点中一点属于I，而另一点属于J= V5，V7, V4,V6 ，并有S57=L5+C57=22+5=27 ；min (S57，S46)= S46 =25给边 V4，V6中的未标号的点V6 标以（25，4）这时I=V1 ,V2 ,V3 ，V4 ，V5 ，V6 ,J= V7，边的集合Vi，Vj Vi，Vj两点中一点属于I，而另一点属于J= V5，V7， V6，V7 ，并有S67=L6+C67=25+6=31 ；min (S57，S67）= S57 =27给边 V5,V7中的未标号的点V7 标以(27，5）此时I=V1 ，V2 ，V3 ,V4 ，V5 ，V6 ，V7，J=空集,边集合Vi,Vj Vi，Vj两点中一点属于I，而另一点属于J=空集，计算结束。得到最短路。从V7 的标号可知从V1 到V7 的最短时间为27分钟。 即：配送路线为： V1 V2 V3 V5 V7（14)最小生成树问题某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图所示，其中V1，,V8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度,单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短 .275623432524V8V7V6V5V4V3V1V2G在图中找到一个圈(V1，V2，V5,V3），并知在此圈上边V1，V2和V3，V5的权数4为最大,在图中去掉边V1，V2 ；在图中找到一个圈（V3，V4，V8 ，V5 ，V3， V1），去掉其中权数最大的边 V4,V8；在图中找到一个圈（V3，V4， V5，V3），去掉其中权数最大的边 V4,V5；在图中找到一个圈（V5,V2，V6，V7 ，V5）,去掉其中权数最大的边 V2，V6；在图中找到一个圈（V5,V7, V8,V5），去掉其中权数最大的边 V5，V8.在图中已找不到任何一个圈了，可知此即为图G的最小生成树。这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18(15）最大流问题某地区的公路网如图所示，图中V1，V6为地点，边为公路，边上所赋的权数为该段公路的流量（单位为千辆/小时）,请求出V1 到V6 的最大流量。 65125641066V6V5V2V4V1V38解：第一次迭代：选择路为V1 V3 V6 。弧（V3 ,V6）的顺流流量为5,决定了pf=5，改进的网络流量图如图所示：第一次迭代后的总流量55555000000V4000065125641066V6V5V2V1V380第二次迭代：选择路为V1 V2 V5 V6 。弧（V1 ,V2)的顺流流量为6，决定了pf=6，改进的网络流量图如图所示：第二次迭代后的总流量111106266655500000V40006512 6466V6V5V2V1V380第三次迭代：选择路为V1V4 V6 。弧（V1 ,V4)的顺流流量为6，决定了pf=6，改进的网络流量图如图所示：第三次迭代后的总流量171706060626665550000V40065646V6V5V2V1V3第四次迭代：选择路为V1V3V4 V2V5V6 .弧（V2 ，V5)的顺流流量为2，决定了pf=2，改进的网络流量图如图所示：第四次迭代后的总流量19193742220880606062666555000V40564V6V5V2V1V34第五次迭代：选择路为V1V3V4V5V6 .弧(V1 ,V3）的顺流流量为3，决定了pf=3，改进的网络流量图如图所示：第五次迭代后的总流量222203111523111474222088060606500V45V6V5V2V1V3在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止.我们已得到此网络的从 V1到V6的最大流量，最大流量为22，也就是公路的最大流量为每小时通过22千辆车。(16） 最小费用最大流问题请求下面网路图中的最小费用最大流,图中弧(Vi ， Vj)的赋权(Cij , bij)，其中Cij为从Vi 到Vj 的流量，bij 为Vi 到Vj 的单位流量的费用。（5，2）（1，2）（2，4）（1，1）（3，3）（4，1）（5，3）（2，4）V6V5V4V3V2V1（1，2）（17)一台机器、n个零件的排序问题某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需要的时间如表所示:零件加工时间/小时零件加工时间/小时11。840。922。051。330.561。5我们应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零件在车间里停留的平均时间为最少？解：对于一台机器n个零件的排序问题，我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少.零件加工时间/小时停留时间零件加工时间/小时停留时间30.50.561.54。240。91.411。86。051.32。722.08（18）两台机器、n个零件某工厂根据合同定做一些零件,这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表所示：零件车床磨床零件车床磨床11.50.541。252。522。00。2550。751。2531.01.75应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少？解：我们应该一方面把在车床上加工时间越短的零件，越早加工,减少磨床等待的时间，另一方面把在磨床上加工时间越短的零件，越晚加工，也就是说把在磨床上加工时间越长的零件,越早加工，以便充分利用前面的时间,这样我们得到了使完成全部零件加工任务所需总时间最少的零件排序方法。等待时间磨床车床5 3 4 1 2 5 3 4 1 2 2（19）在一台车床上要加工7个零件，下表列出它们的加工时间，请确定其加工顺序，以使各零件在车间里停留的平均时间最短。零件1234567Pi1011281465解：各零件的平均停留时间为:由此公式可知，要让停留的平均时间最短,应该让让加工时间越少的零件排在越前面，加工时间越多的零件排在后面。所以，此题的加工顺序为：3，7,6，4,1，2，5(20) 有7个零件,先要在钻床上钻孔,然后在磨床上加工，下表列出了各个零件的加工时间，确定各零件加工顺序，以使总加工时间最短.零件1234567钻床6.72.35。12。39。94.79。1磨床4。93。48。21。26。33。47。4解：此题为两台机器，n 个零件模型,这种模型加工思路为：钻床上加工时间越短的零件越早加工，同时把在磨床上加工时间越短的零件越晚加工.根据以上思路，则加工顺序为：2，3,7，5，1，6，4。（21）根据下表绘制计划网络图ighfjebcdaV5V7V6V4V3V2V1解：V5gfdbecaV6V4V3V1V2（22)对21题,通过调查与研究对完成每个活动的时间作了3种统计，如表所示,请求出每个活动的最早开始时间，最晚开始时间，最早完成时间,最晚完成时间；找出关键工序；找出关键路线；并求出完成此工程项目所需平均时间;如果要求我们以98的概率来保证工作如期完成，我们应该在多少天以前就开始这项工作。活动（工序）乐观时间/天最可能时间/天悲观时间/天a1。523b346c3.556d345.5e2。534f124g245解：显然这三种完成活动所需时间都具有一定概率,根据经验，我们可以假定这些时间的概率分布近似服从分布,这样我们可用如下公式计算出完成活动所需的平均时间:T= 以及方差：2 =2活动T（平均时间）2 （方差)活动T（平均时间）2 （方差）a2.080。07e3.080.07b4.170。26f2。170。26c4。920。18g3。830.26d4。080.18工序安排：工序最早开始时间最迟开始时间最早完成时间最迟完成时间时差是否关键工序a002.082.082.08b004.174。170c4。1759。089。920.83d4。174.178。258.250e4.175.177。258.251f9.089.9211。2512.080。83g8。258.2512。0812。080本问题关键路径是:B-D-G；本工程完成时间是：12.08这个正态分布的均值 E （T ) =12。08其方差为： 2 b2 +d2 +g 2 =0。70 则 0。84当以98的概率来保证工作如期完成时,即:(u ） = 0.98，所以u=2。05此时提前开始工作的时间满足：=2.05所以13。8 14（23）矩阵对策的最优纯策略甲乙乒乓球队进行团体对抗赛，每对由三名球员组成,双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。比赛共赛三局,规定每局胜者得1分,输者得-1分，可知三赛三胜得3分,三赛二胜得1分，三赛一胜得1分，三赛三负得3分。甲队的策略集为S1=1，2，3，乙队的策略集为S1=1，2，3，根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下:A=1 1 11 -1 -33 -1 3 试问这次比赛各队应采用哪种阵容上场最为稳妥.解：甲队的1，2，3 三种策略可能带来的最少赢得，即矩阵A中每行的最小元素分别为: 1,3，1，在这些最少赢得中最好的结果是1,即甲队应采取策略1 ，无论对手采用什么策略，甲队至少得1分。而对乙队来说，策略1，2，3 可能带来的最少赢得，即矩阵A中每列的最大因素（因为两人零和策甲队得分越多,就使得乙队得分越少），分别为： 3，1,3，其中乙队最好的结果为甲队得1分,这时乙队采取2 策略,不管甲队采用什么策略甲队的得分不会超过1分（即乙队的失分不会超过1）。这样可知甲队应采用1 策略，乙队应采取2 策略。把这种最优策略1 和2 分别称为局中人甲队、乙队的最优纯策略。这种最优纯策略只有当赢得矩阵A=(aij）中等式 max min aij = min max aij i j j i成立时，局中人才有最优纯策略,并把（1 ，2）称为对策G在纯策略下的解，又称(1 ，2)为对策G的鞍点。(24)矩阵对策的混合策略5 9 8 6 A=解：首先设甲使用1 的概率为X1,使用2 的概率为X2,并设在最坏的情况下(即乙出对其最有利的策略情况下)，甲的赢得的平均值等于V。这样我们建立以下的数学关系:1.甲使用1 的概率X1和使用2 的概率X2的和为1,并知概率值具有非负性，即X1+ X2=1，且有X10,X20。2。当乙使用1 策略时，甲的平均赢得为：5X1+ 8X2，此平均赢得应大于等于V，即5X1+ 8X2V3。当乙使用2 策略时，甲的平均赢得为：9X1+ 6X2，此平均赢得应大于等于V,即9X1+ 6X2V第二步，我们来考虑V的值，V的值与赢得矩阵A的各因素的值是有关的,如果A的各元素的值都大于零，即不管甲采用什么策略，乙采用什么策略，甲的赢得都是正的。这时的V值即在乙出对其最有利的策略时甲的平均赢得也显然是正的。因为A的所有元素都取正值，所以可知V0。第三步，作变量替换，令Xi =（i=1，2)考虑到V0，这样把以上5个数量关系式变为：X1+ X2 =，X10，X20，5X1+ 8X2 19X1+ 6X2 1对甲来说,他希