物流运筹学试卷运筹学5卷答案.docx
课程名称：运筹学考试时间：年月日（第周星期一（15分）解：令x'3=-x3,x4=x;-X4,xX40则标准形式为：l X17 l l 分分分分分 112 2 1 Zlx z( z( z( z(max z, = 3x1 - 4x2 - 2x,2t - 5x; ÷ 5局=24x + % + 2巧 + x；-芍S.I.*x1 + x2 - 3%3 -芍+ 芍 + X5=142x + 2x> ÷ xj ÷ 2招- Xft=2xl,x2,xx'4,xx5,xb 0设对偶变量分别为y, y2, y3,则对偶规划为: maxty = -2yl + 14y2 + Iy3/ -7 Xlfz x)z 7 Xuz 分分分分分分 11 H 11 114必+为-2%-3s.t.<一必+为+ 2%42y +3y2-y3-2-M - + 2%=5必无约束,为«0，为N °，二（20分）解：（1）首先写出线性规划问题的标准形式maxz2xl+3x2+X31+X2+X3+X4=5s,t.<-x1+2x2+x5=4x1,x2,x3,x4,x5OGT231OOCbXbbXiX2X3X4X5OX451111O5/1OX54-1OO14/2¾231OO（2分）OX433/2O11-1/223X22-1/21OO1/2¾5/2OOO-3/2（3分）2Xi2102/32/3-1/33X230I1/31/31/300-4/3-7/3-1/3（2分）此时，原问题得到最优解为X*=（2,3,0,0,0）maxZ=13（1分）（2）若C=4时，代入最终单纯型表:cj431000CbXbbXiX2×3X4Xs4Xi2102/32/3-1/323X23011/31/31/3300-8/3-11/31/3（5分）4XI51111020X5903111¾0-1-3-40（3分）所以最优解改变，X*=(5,O,O,0,9),Z*=20(2分)三（15分）解：方法一：（1）用最小元素法求得初始解，并计算检验数如下:BiB2B3B4产量UiAi82(0)(2)100A2(4)(2)218203A3(0)2010(-1)308销量8221218Vj(2)因为Oa1i<0,所以此)Bi2了案不是最优,B23（初始二H案,调整的B32斤案5分，位新方案并计算B4势2分，新检验数产量检验数2分）UiAi82(I)(3)100A2(3)(1)128204A3(0)20(1)10308销量8221218Vj122(三1案3分，位势1分，佥验数1分）因为所有。仃20,所以此解为最优解，又因为有非基变量检验数M=O,所以，该问题有多个最优解。其中一个最优解为：Ai-Bi：8,Ai-B2:2,A2-B3:12,A2-B4:8,A3-B2:20,A3-B4:10；最小运费z=8X1+2X2+12X6+8X5+20X10+10X9=414。(1分)方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四（15分）解:-282311318一2224292214矩阵变换15020241623762816（4分32223152217-1214215调整TK©914XX8(?)201717（2分）101O)15118X'©3_（再指派2分）此时最大值W=33+19+41+35+19=1471315316Q110151z彳/8'<0201716uIG)15IO00z)zv4.-（试指派4分，划直线1分）10000OlOOO所以X*二00100(1分)0001000001（1分）五（20分）解：（1）求最小树。最小树如下图:最小树的权数为：5+5+5+4+4+4+4=31（2）增广链流量调整量（6分）（1分）（3分）（3分）（1分）(1)VV2V4V6V84(2)VV3V5V7V86所以最大流量为：4+6=10（3）最小割为：（5,5）=（%,匕），（匕，匕）（3分）（3分）六（15分）：分54个阶段，k=l,23A5（1分）K=5时，")=1力32)=2K=4时，t(Dl)=min<4+(),2+启马)=min<r4+l、=4,IE”(1分)2+2-j(D2)=minZ1(D3)=min-6+人(4)、9+(¾7+f5(Ely5÷(¾)J=min->=min<f6+l、9+2卜7，D2Ei.(1分)r7+ll.=7,D1E2.(1分)5+2K=3时，力(G)=min<,1+九(2)、5+2»=min1+4、"5,C1D,.(1分)5+73(C2)=min<8+f4(Dl)'4+4(2)>=min<8+4'4+7卜11,C2D2.(1分)力(G)=min.16+九（。3）,'4+九（2）、2÷A（D3）»=mi'6+74+7、$=9,C.D,.(1分)2+7K=2时，人(4)=min,Z2(B2)=min<,9+AG)5÷(QZ+AG)'3+(C2)=min*=min<9+5八5+1J=14,B1Ci.(1分)4+5'3+lB=9,B2C2.(1分)i(B3)=min-5+(C3),1+(C2)'7÷(C3).=min-4+91+11、5=12,B.C.(1分)7+9一K=I时，1（八）=max<3+2(Bi),5+2(B2)>=mia"3+14(5+9=14,AB2.(1分)所以,A到E最短且路径为AB4+2(B3号为142-C2>D?-»E1F4+12（1分）（3分）
