物流运筹学试卷及答案卷5.docx
课程名称:运筹学考试时间:第周星期(月0)题号一二三四/1.六七八九总分得分评分人一、(15分)写出下面线性规划的标准形式和对偶线性规划。minz=-3x1+4x22x3+5x44x1-x2+2x3x4=2s.tx1+x2+3x3x4142x1+2x2x3+2x42XnX2O,X3O,X4无约束二、(20分)已知线性规划问题maxZ=2X+3X2+X3'X1÷X2+X35-X1+2X24X1,X2,X30(1)用单纯形法求出最优解。(2)若C=4时,最优解如何改变。三、(15分)求解下列运输问题,表格中间的数字为运价。BiB2B3B4产量Ai123410A2876520A391011930销量8221218四、(15分)求解如下最小化指派问题。2823113182224292214150202416237628162223152217五、(20分)下图为一网络图:(1)若不考虑方向时,边上数字为边的长度,求该图的最小支撑树;(7分)(2)若边上数字为容量,求从顶点Vl到顶点V8的最大流。(10分)(3)求最小割(3分)课程名称:运筹学考试时间:年月日(第周星期一(15分)解:令芍=一X3,X4=与一0则标准形式为:max!=3x-4x2-2xj-5x+5x;-4x1+x2+2芯+芍-K=2sjxl+x2-3与-x,4+X5=14-2x1+2x2+Xj+2x4-2芍-X6=2阳,X2,芍,芍,芍,5,工60l>l71/分分分分分11221/(Zv/|/(/(设对偶变量分别为y”y2,y3,则对偶规划为:max=-21+14y2+2y34Ji+y2-2>,3一3-y1÷y2+2y34s,t.2%+3%一打-2-%-+2%=5必无约束,乃«°,为N°,7!/)zXJ/!/分分分分分分UHH«nlz(z(z(xz(xz(二(20分)解:(1)首先写出线性规划问题的标准形式maxz=2x1+3x2+xixi+x2+x3+x4=5sJ.<-xl+2x2+x5=4x1,x2,x3,x4,x5OCj231O0OCbXbbXiX2X3X4XsOX451111O5/1OX54-I2OO14/2Oi231OO(2分)OX433/2O11-1/223X22-1/21OO1/2一i5/2OOO-3/2(3分)2Xl21O2/32/3-1/33X23O11/31/31/3OO-4/3-7/3-1/3(2分)此时,原问题得到最优解为X*=(2,3,O,O,O)TmaXZ=13(2)若C=4时,代入最终单纯型表:Cj43100CbXbbXiX2X3X4Xs4Xi2102/32/3-1/323X23011/31/31/3300-8/3-11/31/3(5分)4Xi5I111020X59031110-1-3-40(3分)所以最优解改变,X*=(5,0,0,0,9)r,Z*=20(2分)三(15分)解:方法一:(1)用最小元素法求得初始解,并计算检验数如下:BiB2B3B4产量UiAi82(0)(2)100A2(4)(2)218203A3(0)2010(-1)308销量8221218Vj123(初始:2方案5分,位势2分,佥验数2分)(2)因为。34<0,所以此方案不是最优方案,调整的新方案并计算新检验数:BB2B3B4产量UjAi82(1)(3)100A2(3)(1)128204A3(0)20(1)10308销量8221218Vj122(新71斤案3分,位:务1分,;佥验数1分)因为所有。u20,所以此解为最优解,又因为有非基变量检验数3=0,所以,该问题有多个最优解。其中一个最优解为:Ai-Bi:8,A1-B2:2,A2-B3:12,A2-B4:8,A3-B2:20>A3-B4:10;最小运费z=8×l+2×2+12×6+8×5+20×10+10X9=414。(1分)方法二:用沃格尔法(方法略),初始解即为最优解。(评分标准:沃格尔法求得初始方案10分,检验数4分,结果1分)四(15分)解:-2823113182224292214150202416237628162223152217矩阵变换"1315316110151I(4分)0U20171UIO1(0)15I0QSv/0,(试指派4分,划直线1分)"1214215G-10000调整©94X01000=>8(0)201717所以L=00100(2分)101151100010JXz87300001(再指派2分)此时最大值W=33+19+41+35+19=147五(20分)解:(1)求最小树。最小树如下图:最小树的权数为:5+5+5+4+4+4÷4=31(2)增广链流量调整量(1)V1V2V4V6V84(2)VV3V5V7V86所以最大流量为:4+6=10(3)最小割为:(5,5)=(vi,v2),(vi,v3)(1分)(1分)(6分)(1分)(3分)(3分)(1分)(3分)(3分)六(15分):分54个阶段,k=l,2,3A5K=5时,f5(El)=if5(E2)=2K=4时,A(R)=min<'4+5(E)2+加刈>=mn<4+12÷2Dl>E2>6+(1)6+1(DJ=min<51,=min4=7,D2E.429+八(当)9+2(1分)(1分)(1分)Z1(D3)=min-7+启用)、5+启3,»=min<'7+”15+2J>=7,DI->E2(1分)K=3时,力(Cl)=min'"(八)5÷A(2).8+(1)»=min-'1+4'5+7-8+4'=5,C1Dl.(1分)K=2时,力(C2)=mh力(C3)=mh4+。2)6+X(D3)4+(2)'2+4(D3)9+(C1)l»=min<»=min<4+76+74+7'2÷79+5=11,>=9,C2d2.C32(1分)(1分)1(5)=IniIb5+(C2)4+(G)'=min-5+114+51=14,B1C1.(1分)Z2(B2)=min(3)=min-3+(C2)5+(C3)i+(C2)'7÷(Q).3+2(B1),=min-=min*3+114+91+117÷93+1二9,>=12,4'B2C2.B3C1.(1分)(1分)K=I时,fl(八)=max-所以,A到E最短翳路径为AB5+力(坊)4+(¾号为142C2D2=miaEF5+9=14,4+12A>B2.(1分)(1分)(3分)