物流运筹学试卷及答案卷5.docx

《物流运筹学试卷及答案卷5.docx》由会员分享，可在线阅读，更多相关《物流运筹学试卷及答案卷5.docx（8页珍藏版）》请在优知文库上搜索。

1、课程名称：运筹学考试时间：第周星期（月0）题号一二三四/1.六七八九总分得分评分人一、（15分）写出下面线性规划的标准形式和对偶线性规划。minz=-3x1+4x22x3+5x44x1-x2+2x3x4=2s.tx1+x2+3x3x4142x1+2x2x3+2x42XnX2O,X3O,X4无约束二、（20分）已知线性规划问题maxZ=2X+3X2+X3X1X2+X35-X1+2X24X1,X2,X30（1）用单纯形法求出最优解。（2）若C=4时，最优解如何改变。三、（15分）求解下列运输问题，表格中间的数字为运价。BiB2B3B4产量Ai123410A2876520A391011930销量82

2、21218四、（15分）求解如下最小化指派问题。2823113182224292214150202416237628162223152217五、（20分）下图为一网络图：（1）若不考虑方向时，边上数字为边的长度，求该图的最小支撑树；（7分）（2）若边上数字为容量，求从顶点Vl到顶点V8的最大流。（10分）（3）求最小割（3分）课程名称：运筹学考试时间：年月日（第周星期一（15分）解：令芍=一X3,X4=与一0则标准形式为:max!=3x-4x2-2xj-5x+5x;-4x1+x2+2芯+芍-K=2sjxl+x2-3与-x,4+X5=14-2x1+2x2+Xj+2x4-2芍-X6=2阳，X2,芍

3、，芍，芍，5，工60ll71/分分分分分11221/(Zv/|/(/(设对偶变量分别为y”y2,y3,则对偶规划为:max=-21+14y2+2y34Ji+y2-2,3一3-y1y2+2y34s,t.2%+3%一打-2-%-+2%=5必无约束,乃，为N，7!/)zXJ/!/分分分分分分UHHnlz(z(z(xz(xz(二（20分）解：（1）首先写出线性规划问题的标准形式maxz=2x1+3x2+xixi+x2+x3+x4=5sJ.-xl+2x2+x5=4x1,x2,x3,x4,x5OCj231O0OCbXbbXiX2X3X4XsOX451111O5/1OX54-I2OO14/2Oi231OO（

4、2分）OX433/2O11-1/223X22-1/21OO1/2一i5/2OOO-3/2（3分）2Xl21O2/32/3-1/33X23O11/31/31/3OO-4/3-7/3-1/3（2分）此时，原问题得到最优解为X*=（2,3,O,O,O）TmaXZ=13（2）若C=4时，代入最终单纯型表:Cj43100CbXbbXiX2X3X4Xs4Xi2102/32/3-1/323X23011/31/31/3300-8/3-11/31/3（5分）4Xi5I111020X59031110-1-3-40（3分）所以最优解改变，X*=(5,0,0,0,9)r,Z*=20(2分)三（15分）解：方法一：（1

5、）用最小元素法求得初始解，并计算检验数如下:BiB2B3B4产量UiAi82(0)(2)100A2(4)(2)218203A3(0)2010(-1)308销量8221218Vj123（初始:2方案5分，位势2分，佥验数2分）（2）因为。34A3-B4：10；最小运费z=8l+22+126+85+2010+10X9=414。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四(15分)解：-2823113182224292214150202416237628162223152217矩阵变换1315316110151I(4分)0U

6、20171UIO1(0)15I0QSv/0,（试指派4分，划直线1分)1214215G-10000调整94X01000=8(0)201717所以L=00100（2分）101151100010JXz87300001（再指派2分）此时最大值W=33+19+41+35+19=147五（20分）解：（1）求最小树。最小树如下图:最小树的权数为：5+5+5+4+4+44=31（2）增广链流量调整量（1）V1V2V4V6V84(2)VV3V5V7V86所以最大流量为：4+6=10(3)最小割为:(5,5)=(vi,v2),(vi,v3)（1分）（1分）（6分）（1分）（3分）（3分）（1分）（3分）（3分

7、）六(15分)：分54个阶段,k=l,2,3A5K=5时，f5(El)=if5(E2)=2K=4时,A(R)=min=mnE26+(1)6+1(DJ=min51，=min4=7,D2E.429+八(当)9+2（1分）（1分）（1分）Z1(D3)=min-7+启用)、5+启3,=min=7,DI-E2（1分）K=3时，力(Cl)=min（八）5A(2).8+(1)=min-1+45+7-8+4=5,C1Dl.（1分）K=2时,力(C2)=mh力(C3)=mh4+。2)6+X(D3)4+(2)2+4(D3)9+(C1)l=min=min=9,C2d2.C32（1分）（1分）1(5)=IniIb5+(C2)4+(G)=min-5+114+51=14,B1C1.（1分）Z2(B2)=min(3)=min-3+(C2)5+(C3)i+(C2)7(Q).3+2(B1),=min-=min*3+114+91+11793+1二9,=12,4B2C2.B3C1.（1分）（1分）K=I时，fl（八）=max-所以，A到E最短翳路径为AB5+力(坊)4+(号为142C2D2=miaEF5+9=14,4+12AB2.（1分）（1分）（3分）