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

1第二章线性规划建模及单纯形法1．将下列线性规划问题化为标准型(1)Maxz=3x1+5x2-4x3+2x40,,95341322318362:.421432143214321xxxxxxxxxxxxxxxts引入松弛变量：33365;,xxxxx令标准型为：4332124453xxxxxMaxz0,,,,,,9533413222318262:.654332143321643321543321xxxxxxxxxxxxxxxxxxxxxxxxts32125inf)2(xxxM0,095326423:.21321321321xxxxxxxxxxxts令32125,xxxMaxzfz则引入松弛变量：3332254,;,xxxxxxx令标准型为：3321225xxxxMaxz0,,,,,953264423:.54332133215332143321xxxxxxxxxxxxxxxxxxxxts4321243inf)3(xxxxM20,0,152342722351232:.421432143214321xxxxxxxxxxxxxxxts令fz4321243xxxxMaxz512324321xxxx72234321xxxx引入松弛变量：;,65xx令33344,xxxxx标准型为：433212443xxxxxMaxz0,,,,,,15233427222351232:.654332143321643321543321xxxxxxxxxxxxxxxxxxxxxxxxts2.求出以下不等式组所定义的多面体的所有基本解和基本可行解（极点）0,,124326332)1(321321321xxxxxxxxx0,,,,1243263325432153214321xxxxxxxxxxxxxA=104320133254321PPPPP3232211PPB4232312PPB0212413PPB1202512PPB4333325PPB0313426PPB1303527PPB0413438PPB31403539PPB10015410PPB312326320xB223121215431xxxxxxxx得的基本解为：令对应即T000323同理对应TB000718762的基本解为对应TB0180063的基本解为对应TB1800034的基本解为同时又为基本可行解对应TB006405的基本解为对应TB060406的基本解为对应TB600207的基本解为同时又为基本可行解对应TB033008的基本解为对应TB402009的基本解为同时又为基本可行解对应TB12600010的基本解为同时又为基本可行解（2）0,,,,123218320,,1232183254321521432132121321xxxxxxxxxxxxxxxxxxxx100320132154321PPPPPA3221211PPB0231312PPB0211413PPB1201514PPB0332325PPB0312426PPB1302527PPB1003538PPB41001549PPB7482730121216543112321820xBxxxxxxxxx得的基本解为：令对应T0000748730同时又为基本可行解同理，TB0008062的基本解为：对应TB00240063的基本解为：对应TB048000184的基本解为：对应同时又为基本可行解TB000403105的基本解为：对应同时又为基本可行解TB00100406的基本解为：对应同时又为基本可行解TB01500407的基本解为：对应TB01206008的基本解为：对应同时又为基本可行解TB012180009的基本解为：对应同时又为基本可行解3.用图解法求解以下线性规划问题X2(1)Maxz=3x1-2x22s.t:x1+x2≤1(A)1x1+2x2≥4(B)x1，x2≥001234x1可行域为空集，无可行解，∴原问题无最优解。AB(2)Minf=x1-3x2X2Ds.t:2x1-x2≤4(A)5Cx1+x2≥3(B)B4x1≤4(C)3Ax2≤5(D)2x1，x2≥01Z*由图可知最优解为A,B两直线的交点即31*3237zT0123456x15(3)Maxz=x1+2x2X2As.t:2x1-x2≤6(A)8C3x1+2x2≤12(B)B7x1≤3(C)6x1，x2≥05从图中可知，最优解为12,60*zT4321(4)Minz=-x1+3x2012345x1s.t:4x1+7x2≥56(A)3x1-5x2≥15(B)x1，x2≥0由于可行域无界，从图中可知，目标函数无界。8E1A0B515x14．以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解Maxz=2x1+x2-x3s.t:x1+x2+2x3≤6x1+4x2-x3≤4x1，x2，x3≥0化为标准形Maxz=2x1+x2-x3s.t:x1+x2+2x3+x4=6x1+4x2-x3+x5=4x1，x2，x3，x4，x5≥0543211014101211PPPPPA4111211PPB1121312PPB0111413PPB1101514PPB1421325PPB0411426PPB1401527PPB0112438PPB61102539PPB10015410PPB共10个基3223201212154314460xBxxxxxxxx得的基本解为：令对应即T00032320同理对应TB000323142的基本解为同时为基本可行解，326z对应TB020043的基本解为同时为基本可行解，8z对应TB200064的基本解为对应TB0009209145的基本解为同时为基本可行解，32z对应TB050106的基本解为同时为基本可行解，1z对应TB2000607的基本解为对应TB0144008的基本解为对应TB703009的基本解为同时为基本可行解，3z对应TB4600010的基本解为同时为基本可行解，0z∴最优解为00032314*x326*z5．用单纯型法求解以下线性规划问题（1）Maxz=3x1+2x2Maxz=3x1+2x20,,,53332:.0,5332:.43214212321212121xxxxxxxxxxtsxxxxxxtsCBXBbˊ3200X1X2X3X400X3X435[2]-310-11011.5--z03200X1X41.56.51-3/21/200-1/21/21-z-4.5013/2-3/207∵a21ˊ与a22ˊ都小于0，∴原问题没有最优解322)2(xxMaxz322xxMaxz0,,1221243:.32132321xxxxxxxxts0,,,1221243:.4321432321xxxxxxxxxxtsCBXBbˊ01-20X1X2X3X400X1X412121[3]4002-1140-z001-2010X2X4441/314/30-2/30-11/31-z-4-1/30-10/304z4040x**最优值最优解为T3212)3(xxxMaxz32122xxxMaxz0,,936212:.32121321321xxxxxxxxxxxts0,,,,,936212:.65432162153214321xxxxxxxxxxxxxxxxxtsCBXBbˊ1-21000X1X2X3X4X5X6000X4X5X61269111100[2]1-1010-130001123--z01-21000010X4X1X6931201/2[3/2]1-1/2011/2-1/201/2007/2-1/201/216---z-30-5/23/20-1/20110X3X1X6661501/312/3-1/3012/301/31/30011/301/31/31-z-120-30-100Tx1500606*X5为非基变量，其检验数为0，∴可能存在无穷多最优解做进一步迭代，令X5为进基8CBXBbˊ1-21000X1X2X3X4X5X6110X3X1X6661501/312/3-1/3012/301/3[1/3]0011/301/31/31-1845-z-120-30-100100X3X5X612189111100320110-130001-z-120-30-100∴此问题有无穷多最优解此无穷多最优解满足条件62123131xxxx其中x2≡0,解得无穷多最优解在线段x1+x3=12（两端点为TT606,1200最优解为12*z4321532inf)4(xxxxM4321532infxxxxM0,,,412432642:.432143143214321xxxxxxxxxxxxxxxts0,,,,,,41232642:.765432174316432154321xxxxxxxxxxxxxxxxxxxxxtsCBXBbˊ21-35000X1X2X3X4X5X6X7000X5X6X76124124-110023-11010101[1]001-124-z021-35000005X5X2X4108422501011[3]-2001-1101100158/3--z-20-31-8000-5015X5X2X414/38/344/3019/301-2/35/31/31-2/3001/3-1/31011001-z-68/3-10/30-22/300-1/3-14/3368*368*31438*00400fzxT6.用大M法及两阶段法求解以下线性规划问题213inf)1(xxM64213,MxMxxxMaxzM法大9