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

运筹学参考答案及评分细则一、（15分）写出下面线性规划的标准形式和对偶规划令M=-X2，、3=叼一与，X£叼NO则标准形式为：maxz'=X-x；+1分x1-X；+xj-xj+X4=221分s.t.3x1Ix1=201分2x1+2x'1+x'3-X；+x5=51分x1,x；,x',X*,x4,x501分设对偶变量分别为y,y2,y3,则对偶规划为：max69=22y+20y2-5y31分y+3%-2%11分>,1+2%+2%-11分=21分y0,为无约束之。1分二、解：首先写出线性规划问题的标准形式maxz'=3工+Ix2x1+x2+X3=4s.Z/-x1+x2+X4=22分6x1+Ix1+X5=18x1,x2,x3,x4,x50CL32O00OCbXbbXiX2X3X4X5OX34111OO4OX42-11O1O-OX51862OO1332OOO（2分）OX31O2/31O-1/63/2OX45O4/3O11/615/43Xi311/3OO1/69¾O1OO-1/2（3分）2X23/2O13/2O-1/40X4300-211/23Xi5/210-1/201/400-3/20-1/4（3分）此时，原问题得到最优解为X*=(52,3/2,0,3,0)maxZ=212(2分)当目标函数系数变为（3,0.5）时，把新系数带入最终单纯型表:Cj30.50000CbXb1）XiX2X3X4XS0.5X23/2013/20-1/410X4300-211/2-3Xl5/210-1/201/4-003/40-5/8（3分）0X3102/310-1/60X4504/3011/63Xi311/3001/60-1/200-1/2（3分）所以新的最优解为X*=(3,0,1,5,O)TmaXZ=9(2分)三、解：方法一：（I）用最小元素法求得初始解，并计算检验数如下:甲乙丙T产量UjA(3)91(7)100B(-1)(0)(1)662C4(4)2282销量493824Vj113-1（初始方案5分，位势2分，检验数（括号中数字）2分）（2）因为。24<0,所以此方案不是最优方案，调整的新方案并计算新检验数:甲乙丙T产量UiA(4)91(7)100B4(0)(1)262C(1)(4)2682销量493824Vj013-1（新方案3分，位势1分，检验数1分）因为所有。/20,所以此解为最优解，又因为有非基变量检验数匹=0,所以该问题有多个最优解。其中一个最优解为：A-乙：9,A-丙：1,B-甲：4,B-T：2,C-丙：2,C-T：6；最小运费z=9X1+1X3+4X2+2Xl+2×5÷6×1=38。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案1。分，检验数4分，结果1分）O1.01.21.50.3'1.00.40.20.70.50.51.50.21.00.90.80.31.50.20.70.30.60.70.60.3行减0.91.0.80.1Q0.31.2/11Af)I21.50.3)0.50.3,0.80.7（2分）U.0VU/1n/八CC4AzlC1yU.2U试指派4分，.4u.J9直线2分四、解：首先变成最小化指派问题。B=（L5-Cij）5×5（2分）0.91.31.50.3-10000-调整0.7(0)X0.40.2010000.21.10.70.6炉=00100（2分）0.6ZX1.4(0)0.500010/0.20.50.3(O)00001再指派2分即：SlfJ1，S2-*J1>S3fJ3,SLJ4,Ss-*Js此时总得分W=I.5+L1+13÷1.3+1.2=6.4（1分）五、解：（I）求最大流：增广链（1） V1V2V4V6V8（2） ViV3V5V7V8所以最大流量为：4+1=5最大流量图为：流量调整量41（4分）（1分）（5分）64（6分）（2分）（6分）所以VI到V8的最短路长为15。路径为：V1V2V5V7V8O（3）求最小树。最小树如下图：六、解:逆序法标号（1分）最小树的权数为：5+5+4+4+4+4+1=27(13)（3分）（标号全对12分）所以A到G最短路长为18,路径为AB1C2-*D1E2F2G