物流运筹学试卷运筹学3卷答案.docx

运筹学参考答案及评分细则一、（15分）写出下面线性规划的标准形式和对偶规划令与=f2,X3=Xi-灯，x；，x；AO2分则标准形式为：maxz=3x1-Ix2+6x'3-6xy1分/一与+/_4+/=201分s/3Xj+X3-xj=221分-2xi-x'2+x'i-x+x5=51分x1,Xi,x*,XJ,x4,x501分设对偶变量分别为y”,丫3,则对偶规划为：min=20j1+Ily2+5J32分j1+3j2+2j331分s%J1-J321分y+%一y3=6分J10,J2（）,%无约束3分二、解：首先写出线性规划问题的标准形式maxz=3*1+Sx1+Ixi2x1+x2+2x3+x4=72分s.f.x1+3x2+4x3+x5=6Xl9X29×35x45x5N°CL352000CbXb1）XiX2X3X4X50X47212107/10X561134016/335200（3分）0X455/303/21-1/335X221/314/301/364/30-14/30-5/3（5分）3X3105/23/5-1/55X21016/5-1/52/500-26/5-4/5-7/5（4分）此时，原问题得到最优解为X*=（3,1,0,0,0）maxZ=14（1分）当目标函数系数变为（2,1,3）时，把新系数带入最终单纯型表:Cj一21300CbXbbXiX2X3X4X52Xi3102/53/5-1/515/21X21016/5-1/52/55/6001-10（2分）2Xl8/31-1/302/3-1/33X35/605/61-1/61/30-5/60-5/6-1/3（2分）所以最优解为X*=(83,0,5/6,0,0)maxZ=476三、解：方法一：（1）用最小元素法求得初始解，并计算检验数如下:甲乙丙T产量UiA(1)(2)4370B3(1)1(-1)4-1C(IO)6(12)39-5销量365620Vj29310（初始方案5分，位势2分，检验数2分）（2）因为。24<0,所以此方案不是最优方案，调整的新方案并计算新检验数:甲乙丙T产量UiA(0)(2)5270B3(2)(1)14-2C(9)6(12)39-5销量365620Vj39310（新方案3分，位势1分，检验数1分）因为所有。20,所以此解为最优解，又因为有非基变量检验数3=0,所以该问题有多个最优解。其中一个最优解为：A-丙：5,A-T：2,B-甲：3,B-T：3,C-乙：6,C-T：3；最小运费z=5×3+2×10+3×1+1×8÷6×4+3×5=85<,（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四、解：用“匈牙利法”求解80113、38130列减（3分）10092试指派（6分）J497°,所以最优解为Ul960*J即：丙-*1,甲f2,乙-*3,T-*4此时总时间W=3+5+5+6=l9五、解：1、最小支撑树为：1_3v3v1/V4最小树总权为：7+3+3+3+1+2=192、求最大流：增广链(1) VV4V6V7(2) V,V2V3V5V7(3) VV2V5V7(4) VV3V6V7(5) VV4V3V6V7(6) V,V4V3V5V7(7) ViV4V3V6V5V7Ioo01J(1分)(1分)X2V、(6分)V6(2分)流量调整量431(9分)3111所以最大流量为：4÷3+1+3+1+1+1=14最大流量图为：V.(1,1)点v1;(3,3)Q/)V4V6(1分)76)JxV7(3分)(8,6)(24)XB'(2些/5(18)3AB2-XU(18)所以A到E最长路为26,路径为方法二：(顺序法标号)(2)(1)2义:三力4o77(0)(10分)C34(8)JA->Bj>C->D2->E(5分)15(17)4x铛TlA26)。分)王；E(10)六、解：方法一：(逆序法标号)所以A到E最长路为26,路径为ABCiD2E(5分)