物流运筹学试卷及答案卷6.docx
课程名称:运筹学题号一二三四五七八九十总分得分评分人(一、（10分）设有如下线性规划问题:3x1 +4x2 +x3 5X2 x3 = 2x1 0,x2 O,X3自由maxz=2x1-x2+x32x1-x2+3x32（1）写出其对偶问题；（2）利用对偶问题的性质证明原问题目标函数值z6°二、（15分）用顺序法或逆序法，求解A到E的最长路问题。三、（15分）运用表上作业法求解下列运输问题，表格中间的数字为运价。甲乙丙T产量A9181109B116818IOC14122166销量4975七、（15分）下图为一网络图：1、若不考虑方向时，边上数字为边的长度，求该图的最小支撑树；（5分）2、若边上数字为容量，求从顶点Vl到顶点V8的最大流。（7分）3、求最小割（3分）课程名称：运筹学一（10分）解：（1）设对偶变量分别为y”y2,y3,则对偶规划为：min=2yl+5y2+2y32%+3），22s.tA-yi+4%+y3-1.3y1+2-y3=1y0,y20,无约束（min1分，目标函数系数1分，右端向量1分，约束系数矩阵1分，变量取值范围1分）（2）证明：令y=（l,0,2）,易证满足上述对偶问题的所有约束条件所以y=（l,0,2）是对偶问题的一个可行解，（可行解3分）代入对偶问题的目标函数得w=2X1+5X0+2X2=6由弱对偶性得：原问题目标函数值ZWw=6.得证（弱对偶性2分）路径为 ABiCD2E 方法二：分4个阶段，k= 1,2,3,4二（15分）方法一：（逆序法标号）(12分)(1分)(2分)K=3时，力(C)=max<'7+l(3)5+/。2),=miax<7+1'5+4>=9,C1d2.i(C2)=max<1+f式DJ,1÷(2)J»=micxt'7+1'1+4=8,C2->Z).力(C3)=max<3÷()4+)。2).»=miax*3+14+4»=8,C3D2K=4 时，K(R) = IK(D2)= 4(15分)(15分)(15分)K=2时，f2(Bi)=max<15+(C1)'13÷(Q).=miax<'15+913+8>=24,B1C1.(15分)7+(c1)7+9Z2(B2)=max<10+(Q)>=miax<10+8>=18,B2-C2,(15分)5+(C3)5+8(1.5分)K=I时,力(8J=maxfl（八）=max-P10+(CJ110+8-=18,=26,83C2AB,.(15分)(15分)6÷4(C3)2÷(1)'5+f2(B2)J+(¾).-=niax<>=miax<6+82+24'5+18J+18所以，A到E最长路为26路径为AB1CD2E(1分)(2分)四（15分）W：首先变成最小化指派问题。B=(41-Cij)5x5-282311318'"1315316D2215240292022241416矩阵变换I10151r>O<201/16232272361528221617/B分)IU1必151)8（3分）（试指派3分，划直线1分）调整N'12©14918(衽21415CXX100100000'0I,>810X20OX工指派17151分)17113所以X*=000000100100001Q分)(2分)此时最大值W=33+I9+4I+35+19=147（1分）三（15分）解：由最小元素法得初始运输方案如下表所示：（初始解4分，检验数4分）甲乙内-产量UiA29(14)1871(-1)1090B11196(5)8(5)18102C114(3)12(-4)251665销量4975Vj94111因为。H,o33<0,所以该方案不是最优方案。进行调整：（调整2分，新检验数2分）甲乙内产量UiA39(14)1861(-5)1090BI1196(5)8(1)18102C(4)14(7)121251661销量4975Vj94115因为。MVo,所以该方案不是最优方案，再调整。新方案如下：（再调整I分，检验数I分）1乙丙产量UiA39(14)181151090B11196(5)8(6)18IO2C(4)14(7)1262(5)1661销量4975Vj94110因为O,所以该方案是最优方案。总运费为155o（1分）五（10分）解：图解法见下图由图知目标规划的满意解为线段AB,A（2,4）,B（103,10/3）,即满意解为：（2,4）+2（103,103）=（2a+103a2,4a+103a2）其中0a,oi2l,ai+a2=1（坐标系：1分，绝对约束1分，三个目标约束2分义3=6分，结果2分）六（20分）解：（1）当Cl变为13时，代入最终单纯型表得：Cj135000CbXbbXiX2X3X45X23/2015/14-3/1410/213Xi110-1/72/7-Oj001/14-31/14（4分）0X321/5014/51-3/513Xi8/51201/5Oj0-1/50-2/5（4分）因为。.WO,所以X*=(8/5,0,21/5,0)r,Z*=1042(2分)（2）当右边向量b变为（8,9）T时，X'B=,=/5/14-3/14Y811/72/713/1410/7>0所以X*=（10/7,13/14,0,0）,Z*=26514七（15分）解：（1）求最小树。最小树如下图：最小树的权数为：5+5+5+4+4+4+4=31（2）增广链流量调整量（1）V1V2V4V6V84(2)V1V3V5V7V86所以最大流量为：4+6=10(3)最小割为：(5,5)=(vi,v2),(v1,v3)（8分）（2分）（4分）（1分）（2分）（2分）（1分）（2分）（3分）
