运筹学习题参考解答机械2版

1第二章线性规划建模及单纯形法1将下列线性规划问题化为标准型1MAXZ3X15X24X32X40,95341322318362421432143214321XXXXXXXXXXXXXXXTS引入松弛变量33365,XXXXX令标准型为4332124453XXXXXMAXZ0,9533413222318262654332143321643321543321XXXXXXXXXXXXXXXXXXXXXXXXTS32125INF2XXXM0,09532642321321321321XXXXXXXXXXXTS令32125,XXXMAXZFZ则引入松弛变量3332254,XXXXXXX令标准型为3321225XXXXMAXZ0,95326442354332133215332143321XXXXXXXXXXXXXXXXXXXXTS4321243INF3XXXXM20,0,152342722351232421432143214321XXXXXXXXXXXXXXXTS令FZ4321243XXXXMAXZ512324321XXXX72234321XXXX引入松弛变量,65XX令33344,XXXXX标准型为433212443XXXXXMAXZ0,15233427222351232654332143321643321543321XXXXXXXXXXXXXXXXXXXXXXXXTS2求出以下不等式组所定义的多面体的所有基本解和基本可行解（极点）0,1243263321321321321XXXXXXXXX0,1243263325432153214321XXXXXXXXXXXXXA104320133254321PPPPP3232211PPB4232312PPB0212413PPB1202512PPB4333325PPB0313426PPB1303527PPB0413438PPB31403539PPB10015410PPB312326320XB223121215431XXXXXXXX得的基本解为令对应即T000323同理对应TB000718762的基本解为对应TB0180063的基本解为对应TB1800034的基本解为同时又为基本可行解对应TB006405的基本解为对应TB060406的基本解为对应TB600207的基本解为同时又为基本可行解对应TB033008的基本解为对应TB402009的基本解为同时又为基本可行解对应TB12600010的基本解为同时又为基本可行解（2）0,123218320,1232183254321521432132121321XXXXXXXXXXXXXXXXXXXX100320132154321PPPPPA3221211PPB0231312PPB0211413PPB1201514PPB0332325PPB0312426PPB1302527PPB1003538PPB41001549PPB7482730121216543112321820XBXXXXXXXXX得的基本解为令对应T0000748730同时又为基本可行解同理，TB0008062的基本解为对应TB00240063的基本解为对应TB048000184的基本解为对应同时又为基本可行解TB000403105的基本解为对应同时又为基本可行解TB00100406的基本解为对应同时又为基本可行解TB01500407的基本解为对应TB01206008的基本解为对应同时又为基本可行解TB012180009的基本解为对应同时又为基本可行解3用图解法求解以下线性规划问题X21MAXZ3X12X22STX1X21A1X12X24BX1，X2001234X1可行域为空集，无可行解，原问题无最优解。AB2MINFX13X2X2DST2X1X24A5CX1X23BB4X14C3AX25D2X1，X201Z由图可知最优解为A,B两直线的交点即313237ZT0123456X153MAXZX12X2X2AST2X1X26A8C3X12X212BB7X13C6X1，X205从图中可知，最优解为12,60ZT43214MINZX13X2012345X1ST4X17X256A3X15X215BX1，X20由于可行域无界，从图中可知，目标函数无界。8E1A0B515X14以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解MAXZ2X1X2X3STX1X22X36X14X2X34X1，X2，X30化为标准形MAXZ2X1X2X3STX1X22X3X46X14X2X3X54X1，X2，X3，X4，X50543211014101211PPPPPA4111211PPB1121312PPB0111413PPB1101514PPB1421325PPB0411426PPB1401527PPB0112438PPB61102539PPB10015410PPB共10个基3223201212154314460XBXXXXXXXX得的基本解为令对应即T00032320同理对应TB000323142的基本解为同时为基本可行解，326Z对应TB020043的基本解为同时为基本可行解，8Z对应TB200064的基本解为对应TB0009209145的基本解为同时为基本可行解，32Z对应TB050106的基本解为同时为基本可行解，1Z对应TB2000607的基本解为对应TB0144008的基本解为对应TB703009的基本解为同时为基本可行解，3Z对应TB4600010的基本解为同时为基本可行解，0Z最优解为00032314X326Z5用单纯型法求解以下线性规划问题（1）MAXZ3X12X2MAXZ3X12X20,533320,533243214212321212121XXXXXXXXXXTSXXXXXXTSCBXBB3200X1X2X3X400X3X4352310110115Z03200X1X4156513/21/2001/21/21Z45013/23/207A21与A22都小于0，原问题没有最优解3222XXMAXZ322XXMAXZ0,122124332132321XXXXXXXXTS0,12212434321432321XXXXXXXXXXTSCBXBB0120X1X2X3X400X1X412121340021140Z0012010X2X4441/314/302/3011/31Z41/3010/304Z4040X最优值最优解为T32123XXXMAXZ32122XXXMAXZ0,93621232121321321XXXXXXXXXXXTS0,93621265432162153214321XXXXXXXXXXXXXXXXXTSCBXBB121000X1X2X3X4X5X6000X4X5X61269111100211010130001123Z0121000010X4X1X6931201/23/211/2011/21/201/2007/21/201/216Z305/23/201/20110X3X1X6661501/312/31/3012/301/31/30011/301/31/31Z12030100TX1500606X5为非基变量，其检验数为0，可能存在无穷多最优解做进一步迭代，令X5为进基8CBXBB121000X1X2X3X4X5X6110X3X1X6661501/312/31/3012/301/31/30011/301/31/311845Z12030100100X3X5X612189111100320110130001Z12030100此问题有无穷多最优解此无穷多最优解满足条件62123131XXXX其中X20,解得无穷多最优解在线段X1X312（两端点为TT606,1200最优解为12Z4321532INF4XXXXM4321532INFXXXXM0,412432642432143143214321XXXXXXXXXXXXXXXTS0,41232642765432174316432154321XXXXXXXXXXXXXXXXXXXXXTSCBXBB2135000X1X2X3X4X5X6X7000X5X6X76124124110023110101011001124Z02135000005X5X2X4108422501011320011101100158/3Z203180005015X5X2X414/38/344/3019/3012/35/31/312/3001/31/31011001Z68/310/3022/3001/314/33683683143800400FZXT6用大M法及两阶段法求解以下线性规划问题213INF1XXM64213,MXMXXXMAXZM法大90,16482632332121212121XXXXXXXXXXTS0,16482632338765432182172165214321XXXXXXXXXXXXXXXXXXXXXXTSCBXBB310M0M00X1X2X3X4X5X6X7X8MM00X4X6X7X836816131100002300110021000010410000013344Z9M3M31M0M0003M00X1X6X7X83024131100000922001005220010013440001011Z90109M2M33M3M0003000X1X3X7X8302413/2001/21/20009/2111/21/2000400111001500220108/311Z907/20M3/2M3/200最优解为TX039Z9F两阶段法第一阶段64XXZMAX0,16482632338765432182172165214321XXXXXXXXXXXXXXXXXXXXXTSCBXBB00010100X1X2X3X4X5X6X7X81100X4X6X7X836816131100002300110021000010410000013344Z930101000100100X1X6X7X83024131100000922110005220010013440001011Z0092310000000X1X3X7X8302413/2001/21/20009/2111/21/2000400111005002201Z000010100第二阶段CBXBB310000X1X2X3X5X7X83000X1X3X7X8302413/201/20009/211/200040110050201Z907/203/200最优解TX039Z9F321432XXXMAXZ0,13217313233213213221XXXXXXXXXXTS大M法632143MXXXXMAXZ0,13217313236543216321532421XXXXXXXXXXXXXXXXTSCBXBB13400MX1X2X3X4X5X600MX4X5X613171332010001301021100113/313/2Z3M12M3M4M0001110MX1X5X613/31713/312/301/30001301001/312/30117/313/3Z13M/313/307/3M/34M1/32M/300104X1X5X613/3413/312/301/30002301021/3100113/22Z65/3011/307/30M4134X1X2X33251001/31/3101011/23/20011/31/61/2Z290004/311/63/2MTX52329Z两阶段法第一阶段6XZMAX0,13217313236543216321532421XXXXXXXXXXXXXXXXTSCBXBB000001X1X2X3X4X5X6001X4X5X613171332010001301021100113/313/21X5X613/31713/312/301/30001301001/312/30117/313/3Z13/3000X1X5X313/341312/301/3000202132/3112/301Z0000001第二阶段CBXBB13400X1X2X3X4X5104X1X5X313/3413/312/301/300202101/312/3013/2212Z65/3011/307/30134X1X2X33251001/31/301011/20011/31/6Z290004/311/6TX52329Z32123XXXMAXZ0,4322482321321321321XXXXXXXXXXXXTS大M法73212MXXXXMAXZ0,432248276543217632153214321XXXXXXXXXXXXXXXXXXXXTSCBXBB211000MX1X2X3X4X5X6X700MX4X5X782411210004110100231001184/3Z4M22M13M1M00M0001X4X5X220/310/34/31/305/3101/31/314/302/3011/31/32/311/3001/31/32010/142Z4/38/302/3001/3M1/3021X4X1X245/75/76/70012/711/145/145/14101/703/141/141/14013/701/72/72/75Z4/7002/704/70M1/7011X4X3X2105/753120015/21/21/270103/21/21/231001/21/21/2Z2200010MTX5302Z13两阶段法第一阶段7XZMAX0,432248276543217632153214321XXXXXXXXXXXXXXXXXXXXTSCBXBB0000001X1X2X3X4X5X6X7001X4X5X782411210004110100231001184/3Z42310010000X4X5X220/310/34/31/305/3101/31/314/302/3011/31/32/311/3001/31/3Z00000001第二阶段CBXBB211000X1X2X3X4X5X6001X4X5X220/310/34/31/305/3101/314/302/3011/32/311/3001/32010/142Z4/38/302/3001/3021X4X1X245/75/76/70012/711/145/14101/703/141/14013/701/72/75Z4/7202/704/71/7011X4X3X2105/753120015/21/270103/21/231001/21/2Z22000103213INF4XXXM0,4522332132121321XXXXXXXXXXXTS大M法14753213MXMXXXXMAXZ0,45223876543218321762154321XXXXXXXXXXXXXXXXXXXXXTSCBXBB1310M0M0X1X2X3X4X5X6X7X8MM0X5X7X8324111110001200011015100001314/5Z5M13M31MM0M00MM3X5X7X211/52/54/56/504/511001/53/502/500112/511/511/500001/511/6Z512513M5853M05852MM0M05353MCBXBB1310M0M0X1X2X3X4X5X6X7X81M3X1X7X811/63/27/6102/35/65/6001/60001/21/2111/2011/31/61/6001/611/47/2Z31623M008/3234M234MM0232M1M3X3X7X211/42/34/53/2015/45/4001/40001/21/2111/21/2101/41/4001/4Z223M400022MM021M原问题无最优解两阶段法第一阶段75XXZMAX0,45223876543218321762154321XXXXXXXXXXXXXXXXXXXXXTS15CBXBB1310M0M0X1X2X3X4X5X6X7X8110X5X7X8324111110001200011015100001314/5Z513110100110X5X7X211/52/54/56/504/511001/53/502/500112/51/511/500001/511/6Z13/53/502/510103/5010X1X7X811/63/27/6102/35/65/6001/60001/21/2111/2011/31/61/6001/6Z3/20001/21/2101/2原问题无最优解7解设星期一至星期五工作的有X1人，星期二至星期六工作的有X2人；星期三至星期日工作的有X3人，星期四至星期一工作的有X4人；星期五至星期二工作的有X5人，星期六至星期三工作的有X6人；星期日至星期四工作的有X7人。7654321INFXXXXXXXM0,28283119252415765432176543654325432174321763217652176541XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXTS解得36,051101208FXT8解31M25M17M剩根数方法121003X1方法220111X2方法303015X3方法412009X4方法502206X5方法601314X6方法71120X7方法800505X8方法910308X91698765432180500416090511130INFXXXXXXXXXM0,300352321002232002298765432198765276543197421XXXXXXXXXXXXXXXXXXXXXXXXXXTS解得0,00200000000FXT另外一个线性规划模型987654321INFXXXXXXXXXM0,30035232100223200229876543219876527654317421XXXXXXXXXXXXXXXXXXXXXXXXXTS解得160,060000000100FXT9解设IX1表示I个零件在A上的加工数；设IX2表示第I个零件在B上的加工数；I1,2,3,415010070405090100803050INF24142313221221111XXXXXXXXM900150705010030388010040908050332FF4,3,2,10,3333212414231322122111IXXXXXXXXXXTSII解得850,030330302423222114131211FXXXXXXXXX另外一种整数规划模型为设启动，不启动，AAY101启动，不启动，BBY10221241423132212211115010070405090100803050INFYYXXXXXXXXM17为一个大正数MJIXMYXXXXMYXXXXXXXXXXXXTSIJ,4,3,2,1,2,103333224232221114131211241423132212211110设IJX为第I年生产，地J年交货，XIJ表示第I年加班生产，第J年交货333323232222131312121111560500690630660600302620560590530560500MINXXXXXXXXXXXXF3,123,2,10,322533544333323222322131211131211333323231313222212121111JIXXXXXXXXXXXXXXXXXXXXXXXXXXTSIJIJ第三章线性规划问题的对偶与灵敏度分析1写出下列问题的对偶规划21531XXMAXZ2125INFYYM0,252212121XXXXXXTS0,5232212121YYYYYYTS32122XXXMAXZ2168INFYYM无符号限制，,6328232132121XXXXXXXXTS无符号限制2122121,132212YYYYYYYTS1843214323XXXXMAXZ3211085INFYYYM无符号限制4231432143214321,0,1067912857653XXXXXXXXXXXXXXXXTS0,4653372971126321321321321321YYYYYYYYYYYYYYYTS无符号限制5432187523INF4XXXXXM25510252223326432143143215432XXXXXXXXXXXXXTS变形为5432187523INFXXXXXM2551025222332643221143143215432XXXXXXXXXXXXXXXTS对偶规划为7654321255102526YYYYYYYMAXZ0,847235232332754321132132176215432YYYYYYYYYYYYYYYYYYYYYTS无符号限制5161INF5IJIJIJXCM5115INIIIIIYBYAMAXZ1962,152,106,2,152,15161JIXJBXIAXTSIJIJIJJIIJ无限制JIJIJIYYJICYYTS,01165,15JJJXCMAXZ616IIIYBM101INF610516161JXBXAIBXATSJJIJIJJIJIJ无符号限制10651061101101JYIYJICYATSJIIJIIJ2使用对偶理论讨论下列原问题与他们的对偶问题是否有最优解21221XXMAXZ212INFYYM对偶问题，0,122321321321XXXXXXXXXTS0,022221212121YYYYYYYYTS原问题有可行解TX000，但对偶问题无可行解原问题无最优解3212INF2XXXM2164YYMAXZ对偶问题，0,624232121321XXXXXXXXTS无符号限制2112121,01212YYYYYYYTS原问题有可行解TX006对偶问题有可行解TY10原问题有最优解3考虑如下线性规划4321INFXXXXM200,7865432143322141XXXXXXXXXXXXTS（1）写出如下对偶规划43217865YYYYMAXZ0,1111432141433221YYYYYYYYYYYYTS（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解CBXBB56870000Y1Y2Y3Y4Y5Y6Y7Y80000Y5Y6Y7Y811111001110001100011100001000010000111568700000800Y5Y3Y7Y81101100111100110000110100110000000010152070800CBXBB56870000Y1Y2Y3Y4Y5Y6Y7Y80870Y5Y3Y4Y81101100111110100001010000111001100011550001705870Y1Y3Y4Y811001001111001000010100101110011000100005170原规划的最优解为T071521（3）说明这样做比直接求解原规划的好处避免引入人工变量，进而避免用大M法或两阶段法求解、简化计算。4通过求解对偶问题，求下面不等式组的一个解0,253423123221212121XXXXXXXX令目标函数为1INFXM并将不等式变为3212412YYYMAXZ0,052313320,253423123232132132121212121YYYYYYYYYTSXXXXXXXX对偶规划用单纯形表求解该对偶规划CBYBB124200Y1Y2Y3Y4Y500Y4Y51023323510011/3_12420040Y2Y51/32/32/313/310131/32/301_2/928/3024/3042Y2Y35/92/919/913/910015/92/91/31/358/90016/92/3由上表可知原不等式组的一个可行解为16/9,2/3T。应用对偶性质，直接给出下面问题的最优目标值MIN1231045FXXXST12357350XXX123,0XXX其对偶规划为MAX150ZYST1510Y174Y22135Y10Y求解对偶规划的约束条件可知3/5,01Y，所以，3/2503/550Z，利用对偶性质得3/250ZF。6有两个线性规划1MAXTZCX（2）MAXTZCXSTAXBSTAXB0X0X已知线性规划（1）有最优解，求证如果规划（2）有可行解，则必有最优解。解（1）的对偶规划为（2）的对偶规划为MINTFBYMINTFBYSTTTAYCSTTTAYCY无非负限制Y无非负限制（1）有最优解，（1）的对偶规划有可行解。又（2）的对偶规划与（1）的对偶规划的约束条件相同，（2）的对偶规划有可行解。又（2）有可行解，（2）有最优解。7用对偶单纯形法求解下列问题MIN123524FXXX变形得MAX123524ZXXXST123324XXXST1234324XXXX12363510XXX123563510XXXX123,0XXX12345,0XXXXXCBXBB52400X1X2X3X4X500X4X54103613251001524000X42/3101/311/3232X210/3215/301/3102/302/352X1X22/3210011/31121/31001/311/3所以，最优值为3/22Z，即3/22F。最优解为TX0,2,3/2。2MAX12323ZXXX变形为MAX12323ZXXXST12324XXXST123424XXXX12328XXX123528XXXX232XX2362XXX123,0XXX123456,0XXXXXXCBXBB123000X1X2X3X4X5X6000X4X5X6482210111121100010001123000100X1X5X62621001/23/211/23/211/21/2001000105/25/21/200所以，Z2，X2,0,0,0,6,2T。1分别对C1，C进行灵敏度分析C1C1A140即3/2C1005C1A1501/8C11/40解之得C11/2即C1在3/2，）变化时，保持最优解不变。C1C2A240即3/2C21/205C2A2501/8C21/80解之得3C21,亦即0C2C24所以，当C2在0，4范围内变化时，保持最优解不变。（2）对B3进行灵敏度分析11130,0,0TBBXXBBBBBBB241132323333343401/441/4041/221/8BBBBBB解得8B30即8B3B316所以，当B3在8，16的范围内变化时，保持最优基不变。（3）当C25时，求新的最优解当C25时，超出了0，4的保持最优解不变的范围，最优解将发生变化，通过下面的单纯形表求解CBXBB250000X1X2X3X4X5X60205X3X1X6X204420100000110001021/21/41/41/21/80010_168_0005/21/800205X3X1X5X22283010000011000214000101/21/221/4000201/4此时，最优解为X2，3，2，0，8，0T，最优值Z19。（4）当B34时，求新的最优解当B34时超出了8，16的范围，最优解将发生变化。CBXBB230000X1X2X3X4X5X60203X3X1X6X23127/20100000110001021/21/41/41/21/80010_170003/21/800203X3X1X4X24113010000011000001001/41/401/201/21/400001/23/4此时，最优解为X1，3，4，1，0，0T，最优值Z11。（5）增加一个约束2X124X212引入松弛变量2X124X2X71225CBXBB2300000X1X2X3X4X5X6X702030X3X1X6X2X704421201002000124100001021/201/41/41/21/80001000000102030X3X1X6X2X70442080100000010100001021/2121/41/41/21/80200100000010003/21/80002030X3X1X6X2X51325/240100000010100001/23/255/4600001001005/45/45/25/850003/4005/8所以，当增加该约束时，最优解变为X3，5/2，1，0，4，2，0T，最优值Z27/2。（6）确定保持当前最优解不变的P4的范围00,8/1,2/3,00044342414444AAAAPYCT9（1）如何充分发挥设备能力，使工厂获利最大解设XI为生产AI产品的数量MAX1233229ZXXXST12312312381610304105840021310420XXXXXXXXX123,0XXX标准化为MAX1233229ZXXXST12341235123681610304105840021310420XXXXXXXXXXXX123456,0XXXXXX26CBXBB3229000X1X2X3X4X5X6000X4X5X63044004208102165131081010001000136402103229000300X1X5X6364034810021595/49/215/21/85/41/4010001040853/800所以，生产A1产品36单位，可使工厂获利最大为336108（千元）。（2）若为了增加产量，可借用别的工厂的设备甲，每月可借用60台时，租金18万元。问是否合算由上表可知，设备甲的影子价格为3/8千元/台时，则租60台时设备价不应高于3/860千元，即225万元。而18万元的租金小于225万元，所以合算。（3）设新产品A4、A5的产量分别为X7、X8；单位利润为21、187；取新产品的加工实践作为列向量P712,5,10T计算检验数77712213/8,0,05214524010TCYP所以不影响原最优解，故不宜生产A4产品。对于A5P84,4,12T88841873/8,0,0418715037012TCYP故应该生产产品A5。（4）增加乙设备的台时，不会使企业的总利润进一步增加，因为其影子价格为0。101B1由20变为45，求新的最优解110BBBBXXXB201025202545104101010090将此结果代入最优单纯形表中CBXBB551300X1X2X3X4X550X2X54590116103214010025027513X2X390452381001523/21/2160011013X4X318923/56/51/52/501103/101/10103/51/50013/10所以最优解为X0，0，9，18，0T，最优值Z117。（2）B2由90变为95，求新的最优解120BBBXXXBB201002002001041510515所以最优基保持不变，最优解为X0，20，0，0，15T，最优值不变Z100。（3）C3由13变为8，是否影响最优解若影响，将新的最优解求出。因为C3为非基变量X3对应的目标函数的系数，所以3352570，故不影响最优解。（4）C2由5变为6，因为C2为基变量X2对应的目标函数的系数，所以对非基变量的检验数会产生影响。对1的影响111112210111TBCCBPCA对3的影响332232135CA对4的影响442245116CA因为10，所以对最优解产生影响。CBXBB561300X1X2X3X4X50X2X52010116103214011056065X2X1165/85/8011023/81/83/41/41/161/160039/823/41/16所以最优解变为X5/8，165/8，0，0，0T。（）增加变量X6，6162610,3,5,CAA对最优解是否有影响63,5TP1666663105,0505TTBCCBPCYP，所以对最优解没有影响。28（）增加一个约束条件12323550XXX，求新的最优解。CBXBB5513000X1X2X3X4X5X600X2X5X62010501162103325140010001500X2X5X620101011651003241430100010025005013X2X5X3125152511/427/25/21000015/45/23/40103/41/21/45/2007/201/2所以最优解变为X0，125，25，0，15，0T，最优值为Z95。第四章运输问题11分别用西北角法和最小元素法求初始基本可行解。1用西北角法销地1B2B3B4B产量/T产地1A511867503504002A1019710210201903A9141315600340260销量/T3504205302601560注左上角为运费，右下角为从AI运往BJ的数量（I1,2,3；J1，2，3，4）。以后的运输表格中的数据，如不作特殊说明，所表示的意思与上表相同。2用最小元素法销地1B2B3B4B产量/T产地1A5118675035021402602A101971021061121053A914131560014201804销量/T3504205302601560注左下角为非基变量的检验数。以后如不作特殊说明，运输表格中左下角都表示非基变量的检验数。292在上面最小元素法求得的初始基本可行解基础上，用两种方法求各非基变量的检验数。A闭回路法121213333211813142CCCC2121111323105876CCCC2222323323191413711CCCC2424231314107865CCCC3131111333958131CCCC34343313141513864CCCCB位势法1132135148UVUVUV2333147136UVUVUV10U令123015UUU12345986VVVV12121211092CUV21212110156CUV222222191911CUV24242410165CUV3131319551CUV34343415564CUV（3）进一步求解这个问题销地1B2B3B4B产量/T产地1A5118675017063202602A101971021011021053A914131560018042015销量/T3504205302601560求检验数301132135148UVUVUV233114796UVUVUV10U令123014UUU123451086VVVV121212110101CUV21212110156CUV2222221911010CUV24242410165CUV33333313481CUV34343415465CUV因为检验数均大于0，所以得到最优解如上表所示，最优值为13940百元。2用表上作业法求解下列运输问题（1）销地1B2B3B4B产量/T产地1A84729010802A583510070303A772912010110销量/T705011080310121421425UVUVUV223233872UVUVUV10U令123043UUU12341412VVVV计算检验数1111118017CUV2323233410CUV3131317313CUV2424245421CUV311313137018