运筹学习题集

-1-ChinaUniversityofMiningandTechnology运筹学3.5某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为：A—1500套，B—2000套，C—3000套，D—3500套。有三个城市可供应上述规格服装，各城市供应数量分别为：Ⅰ—2500套，Ⅱ—2500套，Ⅲ—5000套，由于这些城市的服装质量、运价和销量情况不同，预计售出后的利润（元/套）也不同，详见表。请帮助该公司确定一个预期盈利最大的采购方案。习题评讲ABCDⅠⅡⅢ1089523674768-2-ChinaUniversityofMiningandTechnology运筹学解：用10减去利润表上的数字，使之变成一个运输问题，如下表所示。销地产地ABCD产量ⅠⅡⅢ021587436342250025005000销量1500200030003500习题评讲ABCDⅠⅡⅢ1089523674768-3-ChinaUniversityofMiningandTechnology运筹学利用伏格尔法求出初始解。销地产地ABCD产量ⅠⅡⅢ1500500150050025003500250025005000销量1500200030003500习题评讲-4-ChinaUniversityofMiningandTechnology运筹学用位势法求各空格的检验数，如表所示。销地产地ABCDⅠ005040330Ⅱ23843045-1Ⅲ1-170602020540jviu习题评讲-5-ChinaUniversityofMiningandTechnology运筹学表中还有非基变量的检验数小于0，利用闭回路法进行调整。把（Ⅲ,A）格作为调入格，以此格为出发点，作一闭回路，如表所示。销地产地ABCD产量ⅠⅡⅢ1500(-1)(+1)500(+1)1500(-1)50025003500250025005000销量1500200030003500习题评讲-6-ChinaUniversityofMiningandTechnology运筹学(Ⅲ，A)格的调入量θ是选择闭回路上具有（-1）的数字格中的最小者，即θ=min{1500,1500}=1500，然后按照闭回路上的正、负号，加上和减去此值，得到调整方案，如表3-41所示。销地产地ABCD产量ⅠⅡⅢ15002000050025003500250025005000销量1500200030003500用位势法求各空格的检验数。所有非基变量的检验数均为非负，故解为最优解。按照此种方案调运，可得最大盈利72000元。习题评讲-7-ChinaUniversityofMiningandTechnology运筹学3.6甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为：A—400万吨，B—450万吨。由煤矿至各城市的单位运价(万元/万吨)见下表。由于需大于供，经研究平衡决定，甲城市供应量可减少0—30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总运费为最低的调运方案。习题评讲甲乙丙AB152118252216-8-ChinaUniversityofMiningandTechnology运筹学解：甲、乙、丙三个城市每年的煤炭总需求量为：320+250+350=920万吨，A、B两处煤矿年煤炭总供应量为：400+450=850万吨。虚拟一个C煤矿，其供应量为70万吨，其单位运价如表所示习题评讲甲甲′乙丙丙′供应ABC1521M152101825M2216M2216040045070需求2903025027080-9-ChinaUniversityofMiningandTechnology运筹学甲甲′乙丙丙′供应ABC15014030250270107040045070需求2903025027080利用伏格尔法求出初始解，如下表。习题评讲用位势法求各非基变量的检验数，如表所示。-10-ChinaUniversityofMiningandTechnology运筹学销地产地甲甲′乙丙丙′A150150180221222120B2102102511601606CMM-50-5MM-8MM00-101510181010iujv习题评讲-11-ChinaUniversityofMiningandTechnology运筹学习题评讲甲甲′乙丙丙′供应ABC15014030（-1）（[phone]（[phone]需求2903025027080甲甲′乙丙丙′供应ABC15014030250270404040045070需求2903025027080表中所有非基变量的检验数均为非负，故为最优解。按照此种方案调运运费最少，为14650万元。-12-ChinaUniversityofMiningandTechnology运筹学4.1若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确？ddzmax)1(ddzmax)2(ddzmin)3(ddzmin)4(-15-ChinaUniversityofMiningandTechnology运筹学4.3用单纯形法求解以下目标规划问题的满意解。122121mindPdPdPz2,1,0,,,824.621210102212122211121iddxxxxddxxddxxii-16-ChinaUniversityofMiningandTechnology运筹学解：(1)将上述目标规划问题化为如下形式：122121mindPdPdPz3,2,1,0,,,824.621210022132122211121iddxxxxxddxxddxxii其中x3为松驰变量。对于此问题用单纯形法进行计算。习题评讲-17-ChinaUniversityofMiningandTechnology运筹学000P20P1P1P2P101062.481102[2]121001100-1000100-1055.28P1P2-10-1-12-20000010020jcBCBXb1x2x3x1d1d2d2dijjzc1d2d3x-18-ChinaUniversityofMiningandTechnology运筹学0P1052.431/243/21000011/2-6-1/2-1/2[6]1/20100-10-0.46P1P2-40000061-600020jjzc2d3x表4-12x0005.20.42.85/6[2/3]7/61000010-100101/121/6-1/12-1/12-1/61/126.240.62.4P1P200000001001010jjzc2x1d3x习题评讲-19-ChinaUniversityofMiningandTechnology运筹学由表4-1可得为原问题的满意解。2.5,021xx而非基变量的检验数为0，故原问题存在多重解。在表4-1的基础上以为换入变量，为换出变量再迭代一步，得表4-2。1x1x1d习题评讲-20-ChinaUniversityofMiningandTechnology运筹学000P20P1P10004.70.62.10101000015/4-3/27/4-5/43/2-7/4-1/81/4-3/81/8-1/43/8P1P200000001001010jcBCBXb1x2x3x1d1d2d2dijjzc2x1x3x表4-2习题评讲-21-ChinaUniversityofMiningandTechnology运筹学由表4-2可得也为满意解。由线性规划的性质可得：(0.6，4.7)和(0，5.2)这两点之间的线段上的所有点均为原问题的满意解。7.4,6.021xx习题评讲-22-ChinaUniversityofMiningandTechnology运筹学5.3用Gomory切割法解213max)2(xxz整数2121212121,0,521045323xxxxxxxxxx习题评讲-23-ChinaUniversityofMiningandTechnology运筹学解：（2）第一个约束条件左边加入松驰变量x3，第二个约束条件左右两边同时乘以-1，然后左边再减去剩余变量x4，加上人工变量x5；第三个约束条件左边加入松驰变量x6，即可化为标准型，可得习题评讲-24-ChinaUniversityofMiningandTechnology运筹学⑤xxxxxx④xxxxxx③xxx②xxxx①xx,,,,,6,,,,,5210453x236543216543216215421321整数65421003maxxMxxxxz不考虑整数条件，用单纯形法求解，计算结果如表5-6所示习题评讲-25-ChinaUniversityofMiningandTechnology运筹学3-100-M00-M03105[3]52-2411000-10010001125/210M3+5M-1+4M0-M00jcBCBXb1x2x3x4x5x6xiz3x5x6x表5-6习题评讲-26-ChinaUniversityofMiningandTechnology运筹学0-M0153100-2/3[22/3]7/31/3-5/3-2/30-10010001-15/229/75M-301+(22/3)M-1(5/3)M-M00z1x5x6x表5-6习题评讲-27-ChinaUniversityofMiningandTechnology运筹学3-100-M00-1016/1115/2231/221000102/11-5/22-3/22-1/11-3/22[7/22]1/113/227/22001--31/7-81/2200-7/223/22-M-3/220jcBCBXb1x2x3x4x5x6xiz1x2x6x表5-60-1013/79/731/71000101/7-2/7-3/700100-12/73/722/7-30/700-5/70-M-3/7z4x2x1x习题评讲-28-ChinaUniversityofMiningandTechnology运筹学因而相应线性规划问题的最优解,)0,0,731,0,79,713(TX目标函数最优值。730z由最终单纯形表得到变量间的关系式：7137271631xxx797372632xxx731722736543xxxx习题评讲-29-ChinaUniversityofMiningandTechnology运筹学将系数和常数项都分解成整数和非负真分数之和，并移项，则以上三式变为)7271(761631xxx)3775(7216332xxxx)7174(7343636543xxxxxx习题评讲-30-ChinaUniversityofMiningandTechnology运筹学现考虑整数条件，整数条件⑤可由下式代替：0)7271(7663xx即6263xx这就得到一个切割方程，将它作为约束条件，引入松驰变量，得到等式7x62763xxx将这个新的约束方程加到单纯形表中，得表5-7。从表5-7的b列可以看出，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。习题评讲-31-ChinaUniversityofMiningandTechnology运筹学3-100-M00３-10013/79/731/7-6100001001/7-2/7-3/7-1001000-102/73/722/7[-2]0001-30/700-5/70-M-3/70jcBCBXb1x2x3x4