物流运筹学运筹学试卷及答案卷3.docx
O点软O郛题号一二三四五七八九十总分得分评分人课程名称：运筹学一、（15分）写出下面线性规划的标准形式和对偶规划maxz=3xl+2x2+6x3x1+x2+x320s,t.<3x1+x3=222x-%2-35x10,x2O,X3无约束二、（20分）用单纯形法求解：maxz=3x1+5x2+2x32x1+x2÷2x37s.tx1+3x2÷4x36x10,x2O并考虑当目标函数系数变为（2,3尸时最优解的变化情况。三、（15分）求解下列运输问题，表格中间的数字为运价。甲乙丙T产量A3113107B19284C741059销量3656四、（15分）已知让甲、乙、丙、丁四个人中选四个人去完成四项任务，每人完成各项工作的时间如下表，应如何分配使完成任务的总时间最少。甲乙丙J11023152510152315514742015136五、（20分）下图为一网络图：1、若边上数字为边的长度，求该图的最小支撑树；2、若边上数字为容量，求从顶点1到顶点6的最大流。六、（15分）用动态规划的方法求出从点A到点E的最长路。一、（15令叼=则标准形mas.t.设对偶变minSf.二、解：ma>运筹学参考答案及评分细则分）写出下面线性规划的标准形式和对偶规划-X2,X3=Xj-与，X£X：2分式为：xz=3x1-2x'1+6xj-6xj1分X1-Xi+X-+X4=201分3x1+X3Xj=221分-2x1-xi+-Xj+x5=51分X1,Xi，Xj,XJ,X4,X501分量分别为y”丫2,丫3,则对偶规划为：=20j1+22j2+5J32分j1+3j2+2j331分J1-J321分Ji+J2-J3=6分yiO,J20,为无约束3分首先写出线性规划问题的标准形式1.Z=3x1+5x2+2x32x1+x2+2x3+x4=72分x1+3x2+4x3+x5=6X19X29X39X49X5OGT3520OOCbXbbXiX2X3X4X5OX472121O7/1OX56134O16/3352OO（3分）OX455/3O3/21-1/335X221/314/3O1/364/3O-14/3O-5/3（5分）3Xi31O5/23/5-1/55X21O16/5-1/52/5OO-26/5-4/5-7/5（4分）此时，原问题得到最优解为X*=（3,1,0,0,0）maxZ=14（1分）当目标函数系数变为（2,1,3）时，把新系数带入最终单纯型表：GT213OOCbXbbXlX2X3X4X52Xi31O2/53/5-1/515/21X21O16/5-1/52/55/6OO1-1O（2分）2Xi8/31-1/3O2/3-1/33X35/6O5/61-1/61/3O-5/6O-5/6-1/3（2分）所以最优解为X三、解：方法一*=(8/3,0,5/：(1)用最小甲6,0,0）m元素法求得初乙axZ=476J始解，并计拿丙W检验数如下:T产量UiA(1)(2)437OB3(1)1(-1)4-1C(10)6(12)39-5销量365620Vj（初始（2）因为。24<（2方案5分，位），所以此方技甲9势2分，检维3不是最优方场乙3E数2分）口调整的新,丙10方.案并计算新T检验数：产量UiA(0)(2)527OB3(2)(1)14-2C(9)6(12)39-5销量365620Vj（新方因为所有。i最优解。其中一个最彳最小运费Z方法二：用沃格（评分标准：沃四、解：用“包'102510155、2015p（0）0*870*In93案3分，位势20,所以此f尤解为：A-丙=5×3÷2×10尔法（方法略格尔法求得初0牙利法”求女315、152147136>0*112（876眸为5,+3X),始/S匚3、D)I9卜，检验教最优解，A-T：21+1×8+（初始解即:f案10分行减=>（4分）所LIl分）又因为,B-甲5X4+3为最优f检验Z乂最优有非基：3,×5=8蜂。数4分8310、14解为I10变量检验数B-丁：3,C-Z5。,结果1分)O1813O997'OO1O7*=O1、OO=1.：613、O20,0,月,C-列匚试1OOO斤以该问题有多个T：3；（1分）减（3分）=>指派（6分）OOO1J即：丙f I,甲-*2,乙f 3, 丁 一4此时总时间W=3+5+5+6=19Q分）（1分）五、解：1、最小支撑树为:最小树总权为：7+3+3+3+1+2=19（6分）（2分）增广链流量调整量(1) vv4v6v74(2)V V2V3V5V73(3 ) V12NS>V?1(9 分)(4) V1V3V6V73(5) VV4V3V6V71(6) V V4V3V5V71(7) V1 V4 V3 V6 V5 V71所以最大流量为:4+3+1 ÷3+1 + 1 + 1 = 14（1分）最大流量图为：2、求最大流:六、解：方法一：（逆序法标号）（10分）所以A到E最长路为26,路径为A-BlTCl-D2-E所以A到E最长路为26,路径为AtBi-CitDz-E（10 分）（5分）（5分）
