中国矿业大学运筹学(64学时)复习题及答案

1部分习题一、（该题已经讲过了）某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），现要确定总利润最大的生产计划，列出下述线性规划0305434553653max321321321321xxxxxxxxxxxxz，，（原材料）＋＋（劳动力）＋＋＋＋求：（1）线性规划问题的最优解；首先将问题标准化：0,,305434553653max5432153214321321xxxxxxxxxxxxxxxxz，，＋＋＋＋＋＋cj31500iCBXBbx1x2x3x4x500x4x5453063345【5】1001963150005x4x315633/5-14/50110-11/50-300-1最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最优目标值z*=30（2）求对偶问题的数学模型及其最优解；0,05551433363045min2121212121yyyyyyyyyywy1*=0,y2*=1(3)最优解不变的情况下，求产品A的利润允许变化范围；2最优解不变的情况下，3,011cc（4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？有利单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的情况下15302b购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。（5）当可利用的资源增加到60单位时，求最优解。12156045510111'bBbcj31500CBXBbx1x2x3x4x505x4x3-151233/5-14/50110【-1】1/50-300-105x5x3159-36/513/501-11/510-3-20-10最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最优目标值z*=45（6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。521235101121'2PBP3所以最优解不变015215012'2122PBCcB（7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？增加的约束条件，相当于增加了一个约束方程20326321xxxxcj241000CBXBbx1x2x3x4x5x6050x4x3x61562033/52-14/51013100-11/500010-300-10050x4x3x6156233/54/5-14/5-7/5010100-11/5-3/50010-300-10对原问题的最优解无影响，对对偶问题的最优解也无影响。二、考虑下列线性规划MaxZ=2X1+3X22X1+2X2+X3=12X1+2X2+X4=84X1+X5=164X2+X6=12Xj≥0（j=1,2,…6）其最优单纯形表如下：基变量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80σj000-3/2-1/801）当C2=5时，求新的最优解2）当b3=4时，求新的最优解43）当增加一个约束条件2X1+X2≤12，问最优解是否发生变化，如果发生变化求新解？解当C2=5时σ4=－5/2σ5=1/8＞0所以最优解发生变化基变量X1X2X3X4X5X60X30001-1-1/402X1410001/400X64000-21/215X220101/2-1/80σj000-5/21/800X32001－201/22X1210010-1/20X58000-4125X23010001/4σj000-20-1/4最优解为X1=2，X2=3,Z＝192）当b3=4时基变量X1X2X3X4X5X60X33001-1-1/402X1110001/400X6-3000-21/213X25/20101/2-1/80σj000-3/2-1/800X39/20010-1/212X1110001/400X43/20001-1/4-1/23X27/4010001/4σj0000-1/2-3/4此时最优解为X1=1，X2=7/4,Z＝29/43)增加一个约束条件基变量X1X2X3X4X5X6X7X30001-1-1/400X1410001/400X64000-21/210X220101/2-1/800X71221000015σj000-3/2-1/800X30001-1-1/400X1410001/400X64000-21/210X220101/2-1/800X72000－1/2－3/801σj000-3/2-1/800由于X7＝2大于0，所以最优解不变三、用对偶单纯形法求下面问题0,753802..64)(min21212121xxxxxxtsxxxf解：Cj4600min{(zj-cj)/ai*j}CBXBbx1x2x3x4ai*j00x3801(2)10{4,3*}0x4753101OBJ=0zj0000zj-cj4600Cj4600CBXBbx1x2x3x46x2401/211/200x435(5/2)01/21{2/5*,6}OBJ=240zj3630zj-cj1030Cj4600CBXBbx1x2x3x46x233013/51/54x114101/52/5OBJ=254zj4614/52/5zj-cj0014/52/5答：最优解为x1=14，x2=33，目标函数值为254。四、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。已知A、B两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可少供应0－30万吨，乙城市需求须全部满足，丙城市需求不少于270万6吨。试求：将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。产销甲乙丙产量AB152118252216400450销量（T）320250350解：(1)依题意得产销平衡表如下：产销甲’甲’’乙丙’丙’’产量ABC1521M152101825M2216M2216040045070销量（T）2903025027080(2)做初始的调运方案（伏格尔法）产销甲’甲’’乙丙’丙’’产量A1501515250182222400B21212516164501403027010CM0MM07070销量（T）2903025027080（3）用位势法进行检验产销甲’甲’’乙丙’丙’’UA01501501812221222-6B21212516160001007CM0MM0-16M-5-5M-80V2121241616(4)做闭回路调整调整后为：产销甲’甲’’乙丙’丙’’产量A1501515250182222400B212125161645014027040CM0MM0703040销量（T）2903025027080（5）进行进一步检验产销甲’甲’’乙丙’丙’’UA01501501812221222-6B2121251616005100CM0MM0-16M-50M-8M0V2116241616(6)调整后的方案为最优方案最低费用＝150×15＋250×18＋140×21＋270×16＋40×16＋30×0＋40×0＝14650五、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。ABCDE8甲2529314237乙3938262033丙3427284032丁2442362345解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。得效率矩阵为：32202627244523364224324028273433202638393742312925戊丁丙乙甲EDCBA各行减最小值，各列减最小值：得7574171219113078051819717540戊丁丙乙甲EDCBA变换得646316111814077041718718540戊丁丙乙甲EDCBA进一步20023120714001800113001318318100戊丁丙乙甲EDCBA9最有指派方案0010000001100000100000010戊丁丙乙甲EDCBA甲——B，乙——C,D，丙——E，丁——A最低费用＝29＋26＋20＋32＋24＝131六、某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台投资为1个单位，总投资不能超过10个单位；又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？该问题也可如下表表示。（要求用割平面法求解该整数规划问题）甲种炉(x1)乙种炉(x2)限量每台投资/单位2110用电量/单位-122收益/单位64解：设x1,x2为甲乙种炉应建台数，则且为整数,0,22102..46max21212121xxxxxxtsxxz用单纯形法求最优解，见下表。基变量bX1X2X3X4iX31021105X42-1201---z06400X1511/21/2010X4705/21/2114/5-z-3001-3010X118/5102/5-1/5X214/5011/52/5-z-32.800-16/5-2/5最优解为8.32,)0,0,,(x05145180zT确定割平面方程：0)52515425145251432432xxxxxx（取从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。基变量bX1X2X3X4X5X118/5102/5-1/50X214/5011/52/50X5-4/500-1/5-2/51-z-32.800-16/5-2/50基变量bX1X2X3X4X5X14101/20-1/2X2201001X42001/21-5/2-z-3200-30-132z,02,2,04XT，），（。此解为整数解，故计算停止。七、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大。利润投资工厂01千万2千万3千万102.541020358.530269解：K为阶段变量，k=1,2,3Sk:第k阶段所剩的资金数Xk：第k阶段分配给第k个工厂的资金数gk（xk）：将xk分配给第k个工厂的效益11状态转移方程：Sk+1=Sk-xk递推关系：第三阶段，k=3X3=s3)(max)(333333xgsfsxx3s3g3(x3)f3(s3)x*301230000122126623993第二阶段：s3=s2-x2，0s23，0x2s2)}()({max)(2232220222xsfxgsfsxx2s2)}()({max)(2232220222xsfxgsfsxf2(s2)x*2012300+00010+23+02120+63+25+06030+93+65+28.5+090,1第三阶段S1=3S2=s1-x1,0x1s1x1s1)}()({max)(1111111011xsfxgsfsxf1(s1)x*1