物流运筹学试卷及答案卷4.docx
课程名称：运筹学题号一二三四五七八九十总分得分评分人一、（10分）写出下面线性规划的标准形式和对偶规划:minz=x1-X2-2x3X1+X2+X322s.t.<3x1+2x2=202x÷2x2一当-5X1O,x20,无约束二、（20分）用单纯形法求解maxz=3xl+2x2xl+x24«X÷X226x1+2x218x1O,x2O并考虑若目标函数的系数变为C=（3,0.5）T后，最优解的变化情况。三、（15分）运用表上作业法求解下列运输问题，表格中间的数字为运价。甲乙丙T产量A413610B23616C37518销量4938四、（15分）有5个工人，要指派去做5项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得分最大？业务工人JlJ2J3J.J5S11.50.50.301.2S20.51.11.30.81.0S31.001.30.50.6S40.71.201.30.8S51.20.90.80.91.2五、（25分）下图为一网络图，边上数字为边的容量或者长度：（1）求从顶点1到顶点8的最大流（10分）；（2）用Dijkstra算法求解从顶点1到顶点8最短路（8分）；（3）画出最小生成树（7分）。六、在如下的网络中，从起点A到终点G分六个阶段，每个阶段各有若干条可选择的道路，每条道路的长度如下图所示。试确定从A点到G点的最短路线。（15分）运筹学参考答案及评分细则一、（15分）写出下面线性规划的标准形式和对偶规划令x；=一、2，3="，一2O则标准形式为：maxz,=-xl-Xj+Ix5-2xj1分X1-Xi+xj-x3+x4=221分sJ.3x1-2x,2=201分2xi+2x'2+x'3-X；+x5=51分xi,x2,x3,xx4,x501分设对偶变量分别为y,y2,y3,则对偶规划为：max69=22>,1+IOy2-5y31分俨+3%-2%11分sJ.'yi+2y2+2y3-11分=21分M0,为无约束,月NO1分二、解：首先写出线性规划问题的标准形式maxz,=3x1+Ix2x1+x2+x3=4s.t.'-x1+x2+X4=22分6xi+Ix2+X5=18x1,x2,x3,x4,X50GT32OOOOCbXbbXiX2X3X4X5OX34111OO4OX42-11O1O-OX51862OO1332OOO（2分）OX31O2/311O-1/63/2OX45O4/3O11/615/43X1311/3OO1/69O1OO-1/2（3分）2X23/2O13/2O-1/4OX43OO-211/23X15/21O-1/2O1/46jIOlOl32014（3分）此时，原问题得到最优解为X*=（52,3/2,0,3,0）maxZ=212（2分）当目标函数系数变为（3,0.5）时，把新系数带入最终单纯型表：G一30.5000CbXbbXi×2×3X4X50.5X23/2013/20-1/4I0X4300-211/2-3Xi5/210-1/201/4-003/40-5/8（3分）0X3102/310-1/60X4504/3011/63X1311/3001/60-1/200-1/2（3分）所以新的最优解为X*=（3,0,1,5,0）maxZ=9（2分）三、解：方法一：（1）用最小元素法求得初始解，并计算检验数如下：甲乙丙T产量UiA(3)91(7)100B(-1)(0)(1)662C4(4)2282销量493824Vj113-1（初始方案5分，位势2分，检验数（括号中数字）2分）（2）因为。24<0,所以此方案不是最优方案，调整的新方案并计算新检验数：产量Uj甲乙丙TA(4)91(7)100B4(0)(1)262C(1)(4)2682销量493824Vj（新方0案3分，位势11分，检验类3【1分）-1因为所有。口20,所以此解为最优解，又因为有非基变量检验数31=0,所以该问题有多个最优解。其中个最优解为：A-乙：9»A-丙：1fB甲：4,B-丁：2,C-丙：2,C丁：6；最小运费z=9X1+1X3+4X2+2X1+2X5+6X1=38。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四、解：首先变成最小化指派问题。B=（L5-Cij）5×5（2分）'O1.01.21.50.3"-00.91.21.50.3'1.00.40.20.70.5行减0.80.100.50.30.51.50.21.00.9=>0.31.200.80.70.80.31.50.20.7（2分）0.601.300.50.30.60.70.60.300.20.40.30试指派4分，划直线2分-O）0.91.31.50.3"-10000调整0.7（0）XZ0.40.2010000.21.10.70.6X*二00100（2分）0.6ZX1.4（0）0.500010/0.20.50.3（O）00001再指派2分即：SlfJI，S2->J1>S3fJ3,SLJ4,S5-*J5此时总得分W=1.5+1.1+1.3+1.3+1.2=6.4（1分）五、解：（1）求最大流：流量调整量4I（4分）（1分）增广链（1） VV2V4V6V8（2） V1V3V5V7V8所以最大流量为：4+1=5最大流量图为：（5分）所以VI到V8的最短路长为15。路径为：V1V2V5V7V8O（2分）（3）求最小树。最小树如下图：最小树的权数为：5+5+4+4+4+4+1=27（1分）六、解：逆序法标号（13）（标号全对12分）所以A到G最短路长为18,路径为ABiC2DiE2F2G（3分）
