运筹学第三版(刁在筠著高等教育出版社)课后答案

运筹学课厉习题参考答案第二章线性观划1、解：模型为：min55xu+30xl2+40xl3+50xl4+40xI5+35x2I+30x22+100入,+45x24+60x25+40xu+60兀32+95x33+35心+30x15xh+xi2+a:I3+xh+x15=4O心1+“22+X2^+X24+“2$=2°xyi+X32+勺3+x34+x3S=40xH+x21+x3l=25<X12+*22+心=10X]3+X23+X33=2（）X]4+心厶+x”=30+X2$=I5xl}0J=1.2.3.7=1・2・3・4.52•提示：标准问题就是收发平衡问题。min工仑內max£cjXjj=i3•解：\s.t.Wni=\2・・nixy>0max工>1其标准形式为:・M工®®+g=lii=12其标准形式为:；=lXj>0.x/l+/>0,j=\=1.2•….tn•标准形式为:min+(x4-1)-2x3s.t.x{・2(x4-1)+3xy-x5=62x{+(x4-1)-x3+x6=30<x,<30<x4<7x.>0,y=3.5.65•提示：建立直角坐标系.用约束方穆把对行域描述出來，在通过目标直线找到最优解’6•提示：用凸集的定义。提示：(1)用数学归纳法先证明两个凸集的交集是凸集，再证明任意多个凸集的交仍是凸集。⑵例{(x9y)\x2+y2<l}o{(x,y)|U+02+rSi}略9•不能构成可行基，因为此时对应的基木解为*=(0,-2,0,6)'「o10」1•略12•解：--^+%2+-%5=311-x{+x3+-x4+-x5=5257一了為一4兀一才“+x6=一39x.>0,j=L2••…613•提示：14解：首先求出该问题对应的标准形式:minz=_2召-x2s.t.2X]+5x2+=60x{+x2+x4=183x{+x2+xs=44©y12345写出对应的单纯形表:XIX2X3X4X5RHSZ210000X32510060X41101018X53100144选取x3x4x5为基变量，此时检验数最人的对应xl,做出基入基变换得到下表

XIX2X3X4X5RHSz01/300-2/3-88/3X3013/310-2/332/3X402/301-1/310/3XI11/300-/344/3在经过一次出基入基变换得到:XIX2X3X4X5RHSZ000-1/21/2-31X3001-13/23/2-11X20103/2-1/25XI1001/21/213所以，原问题的最优解为x*=(l3,5)\®优值为：z*=-31o15•略。16.(1)解原问题的标准形式为:Minz=一2舛一兀2+兀3S.t.3召+x2+x3+x4=60X]-x2+2兀3+xs=10S.t.+尤2_x3+x6=20Xjnoj=12345,6对应的单纯型表为:x{x2x3x4x5x6RHS21-1000031110060r-120101011-100120经过i次旋转变换之肩得到：兀3X、兀6RHS035()20-2004•51•30301•120101002*-3/20-1/21/210在经过一次旋转变换得到：X2屯兀4“兀6RHS00-1/20-1/2-3/2-35

0011・1-210101/201/21/21501-3/20-1/21/25故最优解为F=(I5.5.O)r,最优值为/=-35°(2)原问题C经是标准形式，莫对应的单纯形表为:XIX2X3X4RHSZ-3・1-I-10X3-22104X431016山于基变杲对应的第零行元索非零.故不是检验数，整理得到XIX2X3X4RHSZ-220010X3-22104X431016进行一次旋转变换得到^RHS召花“兀乙00・106-111/202£40•114此时U经是检验数都是非正数，故己得到最优解和最优值.最优解为：x*=(0.2,0.4)7\最优值为芒=6。(3)解：原问题已经是标准形式,其对应的单纯形表为:XIX2X3X4X5X6X7RHSZ•111-10-1100X500301106X2012•100010X310000・100X400100116山于基变呈对应的第零行元索注零，故不是检验数.整理得到XIX2X3X4X5X6X7RHSZ•110-31-110-10X500301106X2012-100010X310000•100X400100116由于检验数x4所对应的列元索均为非正数.故此问题无界。17.(I)解：先将问题标准化,得到:minz=3片+4x2+2x3s.t.X]+x2+x^+x4+x5=30“3x{+6x2+x3一2x4+x6=0x2-x7=4Xj>0,j=1.2.3•….7故先求辅助问题：min&=农S.t.X[+X?+兀+兀+X5=30“3x(+6x2+x3一2x4+x6=0花_心+兀=4xi>0,j=1.2.3••…8其对应的单纯形为XIX2X3X4X5X6X7X8RHSG0000000・10Z-3-4-2000000X51111100030X6361201000X8010000-114经过计算可得辅助问题的最优单纯形表为:XIX2X3X4X5X6X7X8RHSG000000010Z-10-3/2-4/302/300-12X55/203/2011/24-414X2010000・114X4-3/20-1/210-1/2-3312得到了原问题的一个基木可行解，去掉辅助问题，再去掉添加的人工变呈，应用单纯形方法得到原问题的最优解和最优值为：%*=(0,4,—)\z*=—o333解：先将原问题标准化.得到：minz=2x{+4x2sX.2Xj一3x2一X3=2-x,+x2-x4=3a;.>0J=1.23.4应川两阶段法求解.需耍先求解以下辅助问题ming=x5+x65J.2X]—3x2一X3+禺=2-x)+x2-x4+x6=®>0,7=12345.6

XIX2X3X4X5X6RHSG0000•I10Z2400000X52•1-10102X6-1101013应用单纯形方法，得到辅助问题对应的最优单纯形表为:XIX2X3X4X5X6RHSG0000•1•10Z0026-2-6-22XI10-I-1115X201-1-2128得到了原问题的一个基木可行解，去掉辅助问题，再去掉添加的人工变氐应用单纯形方法求解原问题，得到：XIX2X3X4RHSZ0026-22XI10-115X201•I•28故原问题无解。解：Minz=^x{+x23x{+x2=3xpx2,x3,x4xpx2,x3,x4>0研究辅助问题：Ming=x5+x63x{+x2+x5=34xi+3x2-x5+x6=6o.l.“ccx{+2x2+x4=3X.>0,J=1,2,3,4,5,6辅助问题对应的单纯型表为：X]x2xx4x5x6RHS-4-10000000001-10310010343-100161201003计算辅助问题的最优值:

・4・10000074-1000931001034300161201003%RHS经过一次旋转变换得到:““兀抵竝RHS01/3001/30405/3・10-7/30211/3001/30105/3•10-4/31205/301-1/302再次进行旋转变换得到:RHS001/503/5-1/518/50000•1•10101/503/5-1/53/5011/50-4/151/52/500111-10去抻辅助问题，得到原问题的一•个基木可行解，应用单纯型方法得:000-1/518/510003/501002/500110x4RHS得到原问题的最优解为：（3/5,2/5厂最优值为：f=18/5.（4）解:先将原问题标准化,得到:rminz=一2若+4x2一5x3+6x4s.r.X]+4x2-2“+8x4=2・X]+2x2+3x3+4x4=1>0,J=1.2.3.4故所求问题的辅助问题为：ming=x5+x6s.t.X[+4x2一2x,+8x4+xs=2-X,+2x2+3xa+4x4+x6=Ix->0,j=1.23.4.5.6其对应的单纯形表为:XIX2X3X4X5X6RHSG0000•1・10Z2-45-6000X51斗-28102X6•1234011应用单纯形方法求出辅助问题的最优单纯形表为:XIX2X3X4X5X6RHSG0000•1・10Z0-123/30-1/623/2X510-8/301/310X601/21/1211/1201/4得到了原问题的i个基本可行解•去抻辅助问题.再去掉添加的人工变推.应用单纯形方法求解原问题，得到原问题的域优解和最优值为：a*=(8,0,3,0)\z*=31o1&(1)max5叫+3vv2+2vr3+4vv4s.t.5+w2+w3+Sw4=102W|+4w2+3w3+2w4=10Wj>0,y=123.4(2)max2W|+3叫一5叫sJ・2w[+2w2一wy<13W|+Wy-3叫<24vVj+6vv2—5w\=2吗>0,vv3>0,叫无约束(3)jnnmax工昭+工也r=i；=i5.0+0H无约束mincTx19•证明：给定一个一般形式的线性规划问题：\sj.Ax=bx>0maxb1y其对应的对偶问题为:<s.t.ATy=cy>0则所给规划的11其对应的对偶问题为:20(1)将原问题化为标准型:min兀|+兀3SJ.片+2x2+x4=5咕0J=l,2,3,4其对应的单纯形表为:XIX2X3X4RHSZ•10•I00X312015XI01/2103经过计算可得最优单纯形表为:XIX2X3X4RHSZ-5/400-5/47/4X21/2101/25/2XI-1/401-1/47/4577故故优解和故优值为：x*=(O?-，4),z*=4244对偶问题为：max一5叫+6wys.t.一W]<1一2⑷]+w2<02叫<1吗>0,无约束TOC\o"1-5"\h\z一2函+“=011T互补松紧条件为'-，所以泸=。2w.=14221•解：