1、管理运筹学复习要点管理运筹学复习（1）某工厂在计划期内要安排,两种产品的生产.生产单位产品所需的设备台时及A,B两种原材料的消耗以及资源的限制如下表所示:资源限制设备11300台时原料A21400kg原料B01250kg工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少单位产品和产品才能使获利最多？解： max z=50X1+100X2 ；满足约束条件： X1+X2300， 2X1+X2400， X2250，X10,X20。（2）：某锅炉制造厂，要制造一种新型锅炉10台，需要原材料为63.54mm的锅炉钢管，每台锅炉需要不同长度的锅炉钢管数量如下表所示：规格
2、/mm需要数量/根规格/mm需要数量/根2640817704216513514401库存的原材料的长度只有5500mm一种规格，问如何下料，才能使总的用料根数最少？需要多少根原材料？解：为了用最少的原材料得到10 台锅炉，需要混合使用14 种下料方案1234567891011121314264021110000000000177001003221110000165100100102103210144000010010120123合计52804410429140805310519149805072486146504953474245314320剩余220109012091420190309520
3、4286398505477589691180设按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）某公司从两个产
4、地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，各产地的产量、各
5、销地的销量和各产地运往各销地的每件物品的运费如下表所示：B1B2B3产量/件A1646300A2655300销量/件150150200500 600应如何组织运输，使得总运输费为最小？解：这是一个产大于销的运输问题，建立一个假想销地B4，得到产销平衡如下表：B1B2B3B4产量/件A16460300A26550300销量/件150150200100600 600（5）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示：B1B2B3产量/件A1646200A2655300销量/件250200200650 500
6、解：这是一个销大于产的运输问题，建立一个假想销地A3，得到产销平衡如下表：B1B2B3产量/件A1646200A2655300A3000150销量/件250200200650 650（6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。需要供应四个地方的销售，这四地的产品需求分别为400箱、250箱、350箱、200箱。三个分厂到四个销地的单位运价如下表所示：甲乙丙丁1分厂211723252分厂101530193分厂232120221 应如何安排运输方案,使得总运费为最小?2 如果2分厂的产量从400箱提高到了600箱,那么应如何安排运输方案,使得总运费为
7、最小?3 如果销地甲的需求从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)解：这是
8、一个产大于销的运输问题，建立一个假想销地戊，得到产销平衡如下表：甲乙丙丁戊产量/箱1分厂2117232503002分厂101530190（400）6003分厂232120220500销量/箱4002503502002001400 1400解：这是一个销大于产的运输问题，建立一个假想销地4分厂，得到产销平衡如下表：甲乙丙丁产量/箱1分厂211723253002分厂101530194003分厂232120225004分厂0000150销量/箱5502503502001350 1350（7）整数规划的图解法某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表
9、所示：货物每件体积/立方英尺每件重量/百千克每件利润/百元甲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丁19212
10、317解：引入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+
11、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
12、）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.2X2-d1+d1- =700X23X1+4X2-d2+d2- =10000010005000400030002000X1 , X2 , d1+ , d2- 0X12.针对
13、优先权次高的目标建立线性规划0.5X1+0.2X2 =7004000建立线性规划模型如下：3000 min d2-2000约束条件： 20X1+50X2 9000020X1+50X2 90000 0.5X1+0.2X2-d1+d1- =70010003X1+4X2-d2+d2- =10000d1+=0050004000300010002000X1 ， X2 ，d1+ ，d1- ，d2+，d2- 03.目标规划模型的标准化对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达： min P1(d1+)+P2(d2-) 约束条件： 20X1+50X2 90000 ， 0.
14、5X1+0.2X2-d1+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销售较差时的预
15、期利润（元/件）5550解：设工厂生产 A 产品 X1 件，生产 B 产品X2件。按照生产要求，建立如下目标规划模型:min P1(d1+)+P2(d2-)约束条件：4X1+3X2 45 ，2X1+5X2 30 5X1+5X2-d1+d1- =50，8X1+6X2-d2+d2- =100，X1 ， X2 ，di+ ，di- 0.i=1,2(11)动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为
16、铺设管线所需要的费用，问如何铺设管道才使总费用最小？3AED2D1C3C2C1B3B2 B1 6 2 55 3 23 3 4 5 7 4 4 4 4 1 5 4 5 解：第四阶段：D1E 3；D2E 4；第三阶段：C1D1E 5；C2D2E 8；C3D1E 8；C3D2E 8；第二阶段：B1C1D1E 11；B1C2D2E 11；B2C1D1E 8； B3C1D1E 9 ；B3C2D2E 9；第一阶段：AB1C1D1E 14；AB1C2D2E 14； AB2C1D1E 13；AB3C1D1E 13；AB3C2D2E 13；最优解：AB2C1D1E；AB3C1D1E；AB3C2D2E最优值：13
17、（12）最小生成树问题 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。584723431031V7V4V5V6V1V2V3G 5847234331V7V4V5V6V1V2V3G1 解：在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边V1，V6的权数10为最大，在G中去掉边V1，V6得图G1 ，如上图所示 5472343131V7V4V5V6V1V2V3G2 472343131V7V4V5V
18、6V1V2V3G3 在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的最小生成树
19、。这个最小生成树的所有边的总权数为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，V
20、3，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
21、+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，边的集合
22、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=
23、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）最小生成树问题某电力公司要沿道路
24、为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；在图中找到一
25、个圈（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，改进
