《上海电机学院运筹学期末考试试题及答案.docx》由会员分享，可在线阅读，更多相关《上海电机学院运筹学期末考试试题及答案.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、选择题（共20分，每题2分）1、线性规划模型三个基本要素中不包括（A.决策变量B.目标函数C.2、使用人工变量法求解极大化线性规划问题时,1、线性规划模型三个基本要素中不包括（A.决策变量B.目标函数C.2、使用人工变量法求解极大化线性规划问题时,约束条件 D.当所有的检验数bj0,。8、对于目标规划问题的求解，在满足一个目（B）标时B,不得违背已经得到满足的优先级更高的目标A.必须同时考虑优先级较低的目标C.D .无须考虑上述情况不必顾虑优先级较高的目标C ）9、关于图论中的图，以下表达不正确的选项是（A .图中点表示研究对象，边或有向边表示研究对象之间的特定关系B 图论中的图，画边时长
2、短曲直无所谓C .图中的边表示研究对象，点表示研究对象之间的特定关系D ,图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系 A10、关于最短路，以下表达正确的有（ A ）A.从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的B.从起点出发到终点的最短路是唯一的C.从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D.从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上二、填空题（共10分，每空1分）1、线性规划问题如果有无穷多最优解，那么单纯形计算表的终表中必然有某一个非基变量的检验数为02、线性规划的解有唯一最优解、无穷多最优解、无界解
3、和无可行解四种。3、线性规划原问题中的变量个数与其对偶问题中的加约束条件个数相等，因此，当原问题增一个变量时，对偶问题就增加一个约J送f,从而对偶可行域将可能变小-（小还是大）。4、“如果线性规划原问题存在可行解，那么其对偶问题一定存在可行解”，这句话对还是错?2/6max z = X + Xj 2951XI + X 兰25、如果某一整数规划：1414所对应的线性规划（松弛问题）的最优解为St*- 2 为 +X2 2 0 2j = _2= i_x_L_6、对于Max型整数规划问题，假设其松弛问题的最优单纯形表中有一行数据为：X|)bX,2x：，）XX3/410-1/41/4那么对应的割平面方程
4、为那么对应的割平面方程为“3-1X4 3 或二 X3.1X4+X5 - 3 0444 4447、求最小生成树问题，常用的方法有：避圈法和破圈法（共12分）用单纯形法求如下线性规划的最优解、最优值。maxZ =3% +4x +X232x +3xx 0, j =1,2,3j解：把模型化成标准形式：maxZ =3% +4x +X232x +3X +X +Xi 234 =1文为 +2X + 2X +X* 为 235 =3X 0, j =1,2,3j单纯形表3341009XbbXIX2X3X4X50X41231101/30X53122013/2bj3410004X21/32/311/31/301/20X
5、57/3-1/304/3-2/31-bj1/30-1/3-4/303XI1/213/21/21/23/60X55/201/23/2-1/214/60-1/2 -1/2-3/209分12分巧上表是否给出了最优解，假设是那么求出最优解;出对偶问题最优解、最优值。利用对偶关系求6分（错一个扣一分）7分最优解：X二（1/2, 0, 0, 0, 5/2）;最优值 Z = 3/2 四、（此题14分）设用单纯形法求解某极大化线性规划问题得到如下的单纯形表Cj203/2000xBbXiX2X3X4X5X6aXi2d-1001-1bX33/20210-12cX40e001-100-100-1/2f（1）试求上述
6、表中的各参数的值; 解：（1） a=2, b=3/2, c=0, d=l, e=0, f=-l（2）由于所有检验数都非正，因此该表给出最优解，最优解为X =2, X =0, X =3/2, X =0, X =0, X =0i 23456Z* =25/4利用对偶关系可得对偶问题最优解为分14分分14分y =0, y T/2, y T,，0, yT,Z* =25/4五（共12分）Z* =25/4五（共12分）i2313K知线性规划问题的最终单纯表如下C.i31500CbXbbXiX2X3X4X53Xi51-1/301/3-1/35X33011-1/52/50-300-1试分析（1） %在什么范围变
7、化，最优解不变?（2）增加一个新的约束条件2石+3X2 +% 34,原问题最优解是否依然保持?解：（1）由最终单纯形表可知，为保持原最优解不变应有：=1 一（/G +5）031 /T-G -1X031T G +2) 0 35/6解不等式组得：（2）将原问题的最优解X二（5,0, 3, 0, 0）代入不等式X1+X2 + 3x3 34中，不等式仍然成立，故最优解不变。12分八、（共12分）己知产销量及运价表（见右表） 求解土运输问题（要求用沃格尔法求 初始调运方案，用位势法求检验数）肖地 产地、Bib2BB&产量（吨）A81069250127156200A651012350销量（吨）220180
8、160240800o解：（1）由沃格尔法求初始调运方案产销平衡表地虽03B4产量Ai5016040250A2200200170130350销量220180160240销地 产地、1 1 BlB2 z 上门B4Ai0 1b (扪9 * Aj.12皆才-eh-L26- -L2-54041 23-.两最小元22113素之差1 12$；31 12ii3两最小元素之差 TTa 4a1 1 1 K II (2)10分12分用位势法求检验数检验数表rIBlB：6,Al -0匹690A2(7)(3) Li6-3如65阻陛8769（3）因为全体检验数非负，所以初始调运方案即为最优解。 七、（共10分）6/6用Dijkstra算法求下列图中匕到Vg的最短路。（可在原图上标号）解：评分标准，表错一个扣一分。（共10分）io分八、 用图解法找出下面目标规划问题，并写出简要步骤。mi nZ =Rd3+P2 （di+dj + F3drxx +dr-d =02x2x +dr-cT = 1222x + 3x +d f-d + = 12 123% 4(4x 3)八八 2x/0, d/, drO (I =1. 2. 3)i解:解：如上图，可行域为图中剖面线局部；RdJ：4分满意解在AB以上，即三角形ABE6分R(di+d。：满意解在线段CD；8分P3d2：满意解在线6C以下，即最优解为C点;；10分8/6