运筹课后题答案

作业题答案第二章单纯形法3.两阶段法求解:解：引入松弛变量x3，x4}0，人工变量x5，x630，得第一阶段模型:Minz=4x+6x根据第一阶段最优单纯形表得:Minz=4x+6x根据第一阶段最优单纯形表得:Minz=x+xs.t.5x13x16+2x-x +x =802 3 5+x -x +x =752 4 6求解过程如下表：x1,xXXX,X302, 3, 4 5' 6Cj000011CbXbx〔x.x々x』x5乂巴X；802-101175310-101Zj43-1-111Cj-Zj-4-31100目标函数求minZ，根据min(-4,-3)=-4得x1为换入变量，。=min{80/1,75/3}=25得到x6为换出变量。在(2,1)处进行线性行变换，得：Cj000011C b X b——bx1x2x3—x—x5x61X 5——5505/3-11/31-1/30X 1 2511/30-1/301/3Zj.05/3-11/31-1/3Cj-Zj0-5/31-1/304/3min(-5/3，-1/3)=-5/3,得x2为换入变量，。=min{55/(5/3),25/(1/3)}=33得到x5为换出变量。在(1,1)处进行线性行变换，得：Cj000011CbXbbx〔xox々x“x5乂点3301-3/51/53/5-1/50X,14101/5-2/5-1/52/5Zj000000Cj-Zj000011所有Cj-Zj30，取得最优解，人工变量x5=x6=0，故有最优解，转入第二阶段:目标函数变为

6X 2——3301-3/51/54X 1 14101/5-2/5Zj46-14/5-2/5Cj-Zj0014/52/5所有检验数非负，故已取得最优解(X1,x2,x3,x4)=(14,33,0,0),MinZ=4*14+6*33=254.4、M法求解，并讨论解：引入松弛变量x4和x5,x6,人工变量x7,得到线性规划标准形：maxz=10x1+15x2+12x3-Mx7s.t.5x1+3x2+乂3+乂4=9-5x1+6x2+15乂3 +乂5=152x1+x2+太3 小6+x7=5x1,x,2,乂3 乂4 乂5 乂6X730构造初始单纯形表:Cj101512000-MCbX b—bx1 x3 —x— x5 x6 X70X 4—953110000X 5—15-56150100-MX 7 521100-11Zj-2M-M-M00M-MCj-Zj10+2M15+M12+M00-M0Max(Cj-Zj)=(10+2M，15+M，12+M)=10+2M，选择乂］做换入变量，根据最小比值法则gmin{9/5,5/2}=9/5,选择x4做换出变量，在(1，1)处进行基变换得：Cj101512000-MCbX b—b—x—x2 x3 气 x5 x6 X710X 1—9/513/51/51/50000X52409161100-MX 7 7/50-1/53/5-2/50-11Zj106+1/M2-3M/52+2M/50M-MCj-Zj09-1/M10+3M/5-2-2M/50-M0Max(cj-Zj)=(10+3M/5)>0，选择x3做换入变量，根据最小比值法则0=min{(9/5)/(1/5),24/16,(7/5)/(3/5)}=3/2,选择x5做换出变量，在(2，3)处进行基变换得:Cj101512000-MX b-b—x— x —x——x —x— x6 X710X——1—3/2139/8003/16-1/800012X33/209/1611/161/1600-MX 1/20-43/800-7/16-3/80-11Zj1093/8+34M/801221/8+7M/165/8+3M/80M-MCj-Zj027/8-43M/800-21/8-7M/16-5/8-3M/80-M0所有检验数M0，所以已得最优解。注意到人工变量x7^0，故没有可行解。第三章线性规划建模1、解设i=D,E,F；j=A,B,C。则x..表示成品糖i中含有原料糖j的数量。从而有：目标函数： yMaxZ=(xda+xdb+xdc)+技(xea+xeb+xec)+技(xfa+xfb+xfc)-°-8(xda+xea+Xfa)-0.6(xdb++xeb+xfb)-°5(xdc+xec+xfc)约束条件：A:Xda+Xea+Xfa<1000B:Xdb+Xeb+Xfb<1200C:Xdc+Xec+Xfc<900D:(Xda+XDB+XDC)/(XDA+XDB+XDC+XEA+XEB+XEC+XFA+XFB+XFC)^2E：XEA/(XEA+XEB+XEC)^°-1XEB/(XEA+XEB+XEC)^°-1XEC/(XEA+XEB+XEC)^°-1(Xea+XEB+XEC)/(XDA+XDB+XDC+XEA+XEB+XEC+XFA+XFB+XFC)^0*25F:XFA/(Xfa+Xfb+Xfc)N°・2XEB/(XfA+XFB+XFC)<°.22.解：设各月销售量xi1，购入量xi2(i=1,2,3,4)。贝U目标函数：maxZ=45x-4°x+42x-38x+39x-4°x+44x-42xJ__L _LA A_L AA 。。A _L约束条件：第一月X11<2°°X12+2°°-x11<6°°第二月X21<X12+2°°-X11乂22+*12+2°°小11小21<6°°第三月X31<X22+X12+2°°-X11-X21X+X+x+2°°-x-x-x<6°°乙乙_L乙 _L_L乙_L L第四月X41<X32+X22+X12+2°°-X11-X21-X31Xm+Xm+X“+X]c+2°°-X]-x-x-x<6°°42 32 22 12 11213141i1— i2'非负约束：xi1>°,xi2>°(i=1,2,3,4)i1— i2'4.解：1 1

设车间i加工的A为XiA，B为XiB，(i=l,2,3)则约束条件2X1A+X1B<100X2A+2X2B<120L5X3A+1.5X3B<100根据题意，2单位A和1单位B构成1单位成品。所以令成品数量y,则有Y=min{(XY=min{(X1A+X2A+X3A)/2,X1B+X2B+X3B}，所以y<0.5(X/+X2A+X3A)y<X1B+X2B+X3B上述两个不等式作为约束条件，目标函数为MaXZ=y第五章对偶问题及对偶单纯形法1.写出对偶问题(1)将第2约束变为：-X1-X2N-20,则对偶问题为：MaXW=100y1-20y22y1-y2<204y「y2<305y1<40y1,y2,y3^0o(3)根据约束，知道％为自由变量，X>0,X<0。令x=x'-x'',*=—x，则目标函数和约1 2 3 1113 3束条件变为：Minz=4(x;--x'')1-3X2-8x'X1=X'—x1113-2-X1=—x'1+x”13-6X234-X23-14X3=—xx33-12-x3=xx338(x',1x，X2，x330)故可得对偶问题为：MaxW=-2y1-6y2+4y3-14y4-12y5+8y6y*4-y^zy,"-3、6京（yi，y2,y3,y4,y5,尸6^0）2.用对偶单纯形法求解(1)在各约束中分别引入剩余变量x4,x5,X6,原问题化为:minZ=7x+4x+12x—2x—x—x+x=—63x一2x一x+x=-10TOC\o"1-5"\h\z< 1 2 3 5—x—x—x+x=—312 3 6x.>0,j=1,6迭代过程如下表:Cj7412000CbXbbX]X2X3X4X5XA-6-2-100X-103-2-10100-3-1-1-1001Zj000000Zj-Cj-7-4-12000由于所有检验数非正，说明解是最优解。换入变量根据min{b•/b'<0}=min(-6,-10,-3)iiTOC\o"1-5"\h\z=-10取X，换出变量根据min{E一C/a'<0}=min{-4/-2,-12/-1}=2可知取x。在a处5 a' 可 2 22进行基变换得下表：Cj7412000X b—b—X1_ X —X——X——X5_ X6 0X——4--1-7/20-1/21-1/204X——2—5-3/211/20-1/200X G_2-5/20-1/20-1/21Zj~-6420-20Zj-Cj-130-100-20继续变换:Cj7412000

X——b—bx 1 ^ x 3 x 4 —x5_x 6——7X 1-2/7101/7-2/71/704X——2—38/7015/7-3/7-2/700X 6_19/700-1/7-5/7-1/71Zj7427/7-26/7-1/70Zj-Cj00-57/7-26/7-1/70得最优解：x1=2/7,x2=38/7,x3=0.Z=7*2/7+4*38/7=23+5/76.解原问题对偶问题为maxW=10y+20y'3yi+2y2+y3-52y+3y-20TOC\o"1-5"\h\z〈1 2y1+4y2-y3-8、y1-0,y2>0,y3自由变量略原问题的最优解等于上述对偶问题松弛变量的机会费用(x1=z4,x2=z5,x3=z6)；略。第六章运输问题1、求初始基本可行解1）西北角法销地产地、•••、B1B2B3B4B5产量A1(20)XXXX20A2(5)10(15)(10)12XX30A3XX(25(15)20X40A4X13 XX(30)14(30)60销量2515354530解为x11=20，x21=5，x22=15，x23=10，x33=25，x34=15，x44=30，x45=30。Z=20*6+10*5+15*6+10*12+25*9+15*20+30*14+30*3=14152）最小元素法'••.（肖地产地B1B2B3B4B5产量A1XX(20XX20

4A210xX12 X(30)X30A3X(15)(10(15)20X40A4(25)13 X(5)14 X(30)60销量2515354530Z=4*20+8*30+5*15+9*10+20*15+2*25+6*5+3*30=9553）差值法第一轮差值如下表最大差值在第一列（4）,选择该列最小运费所在位置c41取最大运量x41=25。第二轮差值如下表最大差值在第3行（4），选择该列最小运费所在位置c32取最大运量x32=25。第三轮差值如下表

695A2X10X6128X730A3X6(15)5920X940A4(25)2X13614(30)360销量2515354530103最大差值在第4行（3）,选择该列最小运费所在位置c45取最大运量x45=30。X销地产地、B1B2B3B4B5产量A1X6X948X520A2X10X6128X730A3X6(15)5(25)9X20X940A4(25)2X13614(30)360销量2515354530第四轮差值如下表行差值20列差值44118最大差值在第3行（11），选择该列最小运费所在位置c33取最大运量x33=25。同理，继续用差值法可得最终解:行差值 8 0"X销地产地、B1B2B3B4B5产量列差值44A1X6X9(5)4(15)8X520A2X10X6X12(30)8X730A3X6(15)5(25)9X20X940A4(25)2X13(5)614X(30)360销量2515354530Z=4*5+8*15+8*30+5*15+9*25+2*25+6*5+3*30=850

J••销.地产地B1B2B3产量A1(2)3X1042A213X(3)43A33X-3X4)(4A4(1)4(2)矿:5)(6A5（虚拟）-5X1X-4销量75719ui0-4-22-24.解：1）差值法求得初始最优解如下表。位势法求检验数如下:vj 2 7 3所以，存在负的检验数，尚未得到最优解。选择x52作为换入变量，构造闭回路：X52-x51-x41-x42,如图线条表示。所以调整量=min{c51,c42}=min{4,2}=2故x52=0+2=2，x51=4-2=2，x41=1+2=3，x42=2-4=0，x42成为换出变量。调整如下表:vj 2 2 3、销地产地B1B2B3产量A1(2)8X1042A28X(3)1X-3A33X2X4)(4ui01-2

A4：(酊一4 !111i 5X--9——(3)5 :6A5（虚拟）F-0 /广01X04销量757192-2存在负的检验数，尚未得到最优解。选择x53作为换入变量，构造闭回路：X53-x51-x41-x43,如图线条表示。所以调整量=min{c51,c43}=min{2,3}=2故x53=0+2=2，x51=2-2=0，x41=3+2=5，x43=