管理运筹学作业答案(韩大卫)MBA

1、运筹学作业答案-1-第 1 章线性规划基本性质P47 1 1 (2)解：设每天从i煤矿i =1,2运往j城市j =1,2,3的煤为Xj吨，该问题的 LP 模型为:min，= CijXij =9xn7x1210X138x216.5x228x23i 4 j JX11+ X12+ X13= 200+x21=100s.t.x12+x22= 150X13 +X23= 200Xj-0i =1,2;j =1,2,3P48 1 2( 2)max z = % x2X x20(1) st3x1x2兰-3(2)X , x2X 0解：；R1R2= ；：J，则该 LP 问题无可行解。x22x23二250运筹学作业答案-

2、2-P48 1 2 ( 3)min z = 2x1-10 x2% -x2- 0(1)st. % 5x2z 5(2)%,x2A0广X| _X2=0$15X2= -5P48 1 2( 4)解：目标函数等值线与函数约束（ 2）的边界线平行，由图可知则该LP 问题为多重解（无穷多最优解）。* _5 V14,4z*- -10（射线 QP 上所有点均为最优点）X2=54运筹学作业答案-3-min z - -IO% -11x23xi+4x2兰105xi+2x2玄8(2) st.Xi- 2x2 2(3)Xi,X2-0则x：6,1329P48 1 3 (2)解：由图可知 Q 点为最优点。少+4x2=10Xr+2

3、x2=8运筹学作业答案-4-min z = 3xj4x22x3x4Sxj+x2+x3兰74Xr+ x2+6X3Z 6nst.-Xi - X2 X3 . X4 = 4x -1,x2- 0解：把_1 看作一函数约束 令自由变量 X3二 X；-XX4二 x4X：m a 龙二 -3 捲 - 4x2- 2x32x(- x4x?- / /3x1x2x3-x3x5= 74 捲 + x2+ 6X3- 6x(-X6= 6s.tJxH x2- x3 +x3/-x4 +X4= 4/X1,X2,X3,X3,X4,X4,X5,X6,X7P49 1 5解：可行域的极点与基本可行解是一一对应的。(1)对于X2= (9,7,

4、0,0,8j，不满足约束条件4洛+ 7x2- x32x4- x5= 85，即X2=(9,7,0,0,8不是可行解，也就不是基本可行解，故不是该可行域的极点。(2)对于X1二5,15,0,20,0T，是可行解。此时基变量为X1.X2.X4，由此得到的基矩阵为2 1 013-1=0，所以X1=(5,15,0,20,0不是基本解，也就不是基本可行解，故不是该472可行域的极点。(3)对于X3=(15,5,10,0,0T，是可行解。此时基变量为X1,X2, X3，由此得到的基矩阵为21 -11 30 =0，所以X3=(15,5,10,0,0$不是基本解，也就不是基本可行解，故不是该可4 7-1行域的极

5、点。P50 1 812345678A(2.9)11120000100运筹学作业答案-5-B(2.1)12001023100C(1.2)20314620100余料00.30.90.40.50.20.81.1解：设按第j种截法下料Xjj =1,2 - ,8根，该问题的 LP 模型为:min= Xix2x3x4x5x6x7x8X +x2+x3+2x4A100 xi +2x2+x5+2x7+3x8Z100s.t.2xi+3x3+x4+4x5+6xg+2x7K100Xj Z0(j =1,2，,8)第 2 章单纯形法P70 2 1( 2)maxz = 2x1x25x2+x3=15解：标准化为6为+2x2+

6、 x4= 24，容易得s.t.124% X2X5= 5X1,X2,X3,X4,X5-0X。二0,0,15,24,5T,z。=0第一次迭代时：max2,V = 2 =1则x1为进基变量（此时x2仍为非基变量）X3=15X3=15一06x1x4= 24二x4= 24 - 6x1_ 0IX1X5=5X5=5- 为0则X4为进基变量，6 为主元5x2+x31Xr+ X232 1=15z = 2xi+x2此时：1=2 4 x2一36x81x1X433X1二4,0,15,0,1T,Z1 =8；x2一：X46X5 =1运筹学作业答案1-6-（图解法略）注意由方程组形式求的每个基本可行解与图解法求得的可行域的

7、极点之间的一一对应关系。第二次迭代:0则X2为进基变量X3“ x1X5=15 -5X2- 01=4 x2_ 032=1X2亠032一则X5为进基变量，一为主元35x2+x3=151 1 xi + x2+ x4= 431X2X4、4632X5r51515X3+X X5 :=-422117*+X4 一X5 =4221丄33X2 X4十二X5 =422此时:C11z =8x2X333117 11X5X4X4X5232 427 32,/ 2j&0,0乙P70 2 2（ 1）解：化标准形为:maxz = 2x12x23 354V 1- - 2 2 2XXX3 2=8X2此时；j _0，则X运筹学

8、作业答案-7-X1X2X3= 1st.* -0.5x1+X2 + X4=2,X2,X3,X4AO运筹学作业答案-8-Cj22000iCBXBbX1X2X3X40X31-11100X42-0.5101aj2200TT丁耳=2A0,而它所对应的系数列向量 旳=(1,0.5) c(0,0)则该LP问题无最优解(无界解)。补充作业：max z = 6% - 3x23x3lx! + x2+ x3兰60求解下列 LP 问题：2x,2x2+4x3兰20s.t.3x3x2-3x3乞60X!,X2,X3一0解：标准化后求解过程如下:Cj6-33000dCBXBbX1X2X3X4X5X60X46031110020

9、0X510(1)_12010100X62011_ 1001206_ 330000X43004_51-3030/4运筹学作业答案-9-6XI101-120100X6100（2）-30-11503-90-600X4100011-1-26XI15101/201/21/2-3X2501-3/20-1/21/200-9/20-9/2-3/2*T*-0，则最优解为：X二15,5,0 ,z =75P70 2 2 (4)m axz=一2捲一3X2-x3-MX6-MX7x*4X22X3X4X6=8s.t.W +2X2- x5+ x7= 2X1,X2,X3,X4,X5,X6,XO5-2_3-100-M-MCBXB

10、bXIX2X3X4X5X6X7-MX681（4）2-10102-MX763200-10134m 26m-32m-1-m-m00-3X221/411/2-1/401/408_MX72（5/2）0-11/2-1-1/214/5解：建立该 LP 问题的大 M 法辅助问题如下:运筹学作业答案-10-5m51 m 2m33m 3_斗624024-m240-3X29501（3/5）-3/101/103/10-1/10-2Xi4510-2/51/5-2/5-1/52/5000-1/2-1/2-1X3305/31-1/21/61/2-1/6-2Xi212/300 1/301/3000-1 /2 1/2X；二5

11、，I，0，X；二2,0,3 -15 5丿则最优解为：X嘗TM 2,03T3-3由于出现非基变量的检验数为0,故该 LP 问题有多重解。运筹学作业答案-11-P71 2 2 ( 5)解：目标函数化标准形为：max z = -2捲x2 x3x4函数约束添加人工变量x5, x6,x7，拟采用两阶段法求解。第一阶段：两阶段法辅助问题目标函数为：max Z = _x5_ x6_ x7Cj0000-1-1-1e.iCBXBb片xX3X4X5X6X7-1X52(1)-12-11002-1X6621-310103-1X7711110017aj41010000X121-12-1100运筹学作业答案-12-1X6

12、20（3）-73-2102/3-1X7502-12-1015/205-85-3000X18/310-1/301/31/300X22/301-7/31-2/31/30-1X711/300（11/3）01/3-2/31160011/30-2/3-5/300X1310004/113/111/110X230101-5/11-1/117/110X3100101/11-2/113/1160000-1-1-1由第一阶段最终单纯形表可得z/=0，故原 LP 问题存在可行基，转入第二阶段继续求解。第二阶段：求解原 LP 问题。5-2-1116iiCBXBbX1X2X3X4-2X131000-1X23010（1）

13、31X310010aj0002-2X131000运筹学作业答案-13-1X4301011X310010aj0-200*T*此时-j 0,故原 LP 问题的最优解为：X = 3,0,1,3 , =2补充作业：maxz =2捲x2x3宓+2x2+2x3工4求解下列 LP 问题：2x,+4x2兰20s.tA4X!+8x2+2x3兰16x1,x2,x0maxz二2x1x2x3_ Mx74為+ 2x2十2x3_ x4十x7= 4解:建立大M法的辅助问题如下：2捲+ 4x2+ X5= 20st.4x18x22x3x6= 16Xi,X2,X3,X4,x5,X6,X7- 0Cj211000-M日.iCBXBb

14、X1X2X3X4X5X6X7-MX74（4）22100110X5202400100100X61648200104aj4m +22m + 12m+1-m0002X1111/21/2-1/4001/40X51803-11/210-1/236运筹学作业答案-14-0X612060（1）01-112运筹学作业答案-15-60001/2001m22X1412（1/2）001/4080X51200-101-1/200X412060101-1aj0-3000-1/2-m1X38241001/200X52024001000X412060101-160-3000-1/2-m*T *T该 LP 问题有多重解。X1

15、= 4,0,0 ,X2= 0,0,8*TT最优解为：X=収1+（1 卩X2=円4,0,0）+（1卩10,0,8 ） = 0（0兰卩兰1）,*z =8第 3 章对偶原理P92 3 1 （ 1）（ 2）（4）X1- X2X3- -1 s.t.x12x2-x3- 1X1,X2,X3-0maxz = 2yy2y3”3% +2 +3兰60* m22y3汨0 s.t.y1y2- y 20y1, y2, y3- 0（1）max z = 4% 3x26x3x2x3空60s.t. 2x12x23x3- 40XX2,X3-0mi n = 60y140 y23yrH2y4=+1*2y2 X3s.t.13y2- 6y

16、,y2（2）min = 60 x110 x220 x3运筹学作业答案-16-maxz = x13X22x3x12x24X3=10s.t.*?% +5x2+3X3=15XX2,X33 0min =10y115y2y2y1二2% +5y2K3s.t.4% 3y2一2y1, y2为自由变量P92 3 2 ( 6)maxz = 2x13x26x3x43為+4x2+4X3+7X4= 21(6)2捲+7x2+3x3+8X418二s.t.X1- 2x25x3- 3x4_ 4X1_ 0, X2_ 0,X4- 0P93 3 6 ( 1)用对偶单纯形法求解 LP 问题max z = -2x2_ X1 2x?+ X

17、3= 4解：捲+X4=5s.t.143xi x?+ X5= 6X1,X2X3,X4,X0Cj_1_ 2000CBXBbX1X2X3X4X50X3_4_1_ 2100min - 21y118y24y3g +2y?+ y3Z24y1+7 y22y3兰3s.t.* 4y|+3y2+5y3= 67力+8y?_3y3启1y2乞0,y3- 0运筹学作业答案-17-0X4510010运筹学作业答案-18-0X5-6(-3)-1001-1-20001/320X3-205()310130X43013011/3-1X1211/30013053001-311-2X26/5010(1/5)0X417/5001512/

18、5-1X18/5101/502500-1000X5605-3010X410-1110-1X1412-10000-100最优解为:*z =4该 LP 问题有多重解。X,8 6丫 ,“cT肩6丿兀=（4,0）x= % 十(1卜X2=卩-65 丿包小1一运筹学作业答案-19-P93 3 7解：（1 ）设甲、乙、丙三种产品每月的产量分别为X1,X2,X3件，建立 LP 模型为:max z = 3为2x2x3为2x2x3二400s.t.2x1+x2+2x3兰500 xK, X3A 0Cj32100日iCBXBbX1X2X3X4X5运筹学作业答案-20-0X440012110400运筹学作业答案-21-0

19、X5500(2)12012506321000X41500(3/2)01-1/21003X125011/2101/250001/2-20-3/22X21000102/3-1/33X1200101-1/32/300-2-1/3-4/3- -43x13x2 _ -1st#12XiAOx1, x2为整数03其松弛问题的最优解为与Xi一0相矛盾则原 IP 问题无可行解。运筹学作业答案-27-P172 6 54184 23079847 7540（q84663T5136576 2435e543h443广00711、2401321310T13520430ID 1000100100即解矩阵为00001解：此题满

20、足标准指派问题的三个条件，直接用匈牙利法求解如下:31、0071r332401330T2 1310=（bj）401352020J4300z0 0712、240141020002410J4300丿指派方案为：机床 1 加工零件 2，机床 2 加工零件 3，机床 3 加工零件 5,机床 4 加工零件 1, 机床 5 加工零件 4，总加工费用为：z*=1 4 3 6 17（元）运筹学作业答案-28-P173 6 7解：（1）该指派问题要求目标函数最大化，根据匈牙利法适用的标准指派问题三必要条件应先化为最小化问题，记 M = TOO。二 MID001000100即解矩阵为0000 10100 0000

21、00?指派方案为： 甲翻译德文，乙翻译日文，丙翻译法文，丁翻译俄文，戊翻译英文,总翻译效率为：z =800 - 900 - 800 - 800 - 1000 =4300（印刷符号/小时）（2）由于甲不能胜任翻译德文，乙不能胜任翻译日文，效益矩阵变化为：巾64M5、053M4、040M325M0425M0424M0313752T02641T013406241551304500030 57420 57420 444b001000 0 0 1 0即解矩阵为0000 10100 0 s 3 2，路长为 6Sr 3，路长为 2s 3 2 4，路长为 8运筹学作业答案-33-Sr35，路长为 6Sr6，路长为 3P234 8 9052 o o即：S 2,1 2,2 4,3 1,4 t,t t最短路最短距离ST 2T4Tt31T 2T4Tt52T4Tt13T1T2T4Tt34Tt4t- t0解: 距离矩阵为W =(1)各点到点t的取短路052O0Q00、0043Q00Q040O0-3Q00-2501Q0Q0Q04204Q000-200 ,0043O0040OC-3C0-2501Cod42040O0O02O00丿330O0555Q0T1T1T1T10553344444010 ,10,10,i0运筹学作业答案-34-(2 )点 S 到各点的