上海电机学院运筹学期末考试试题及答案

1、选择题（共20分，每题2分）1、线性规划模型三个基本要素中不包括（D ）A.决策变量B.目标函数C.约束条件D.基2、使用人工变量法求解极大化线性规划问题时，当所有的检验数/M 0在基变量中仍含有非零的人工变量，表明核线性规划问题（ D ）A.有唯一的最优解B.有无穷多最优解 C.为无界解D .无可行解3、若线性规划的原问题不存在最优解，则对偶问题（ B ）A.可能存在最优解B.不存在最优解C. 一定是无可行解D. 一定是无界解4、若线性规划问题的某个资源常数发生变化，则在最终单纯形表中这一变化 （B ）A.对检验数存在影响B.对b列数存在影响C.对该资源常数所在行的数存在影响D.对所有数都无

2、影响5、在产销平衡运输问题中，设产地为 m个，销地为n个，那么基变量个数 （C ）A.不能大于（m+n-1） B.不能小于（m+n-1）C.等于（m+n-1） D.不确止6、一般讲，对于某一问题的线性规划与该问题的整数规划可行域的关系存在(A )A.前者大于后者B.后者大于前者C.二者相等D.二者无关7、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足(B )A.d* 0 B./=0C.d -0 D.08、对于目标规划问题的求解，在满足一个目标时(B )A.必须同时考虑优先级较低的目标 B.不得违背已经得到满足的优先级更高 的目标C.不必顾虑优先级较高的目标D.无须考虑上述情况9

3、、关于图论中的图，以下叙述不正确的是( C )A.图中点表示研究对象，边或有向边表示研究对象之间的特定关系B.图论中的图，画边时长短曲直无所谓C.图中的边表小研究对象，点表小研究对象之间的特定关系D.图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系10、关于最短路，以下叙述正确的有（A ）A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的B.从起点出发到终点的最短路是唯一的C.从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D.从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上二、填空题（共10 分，每空 1 分）1、线性规划问

4、题如果有无穷多最优解，则单纯形计算表的终表中必然有某一个非基变量的检验数为 0。2、线性规划的解有唯一最优解、无穷多最优解、无界解 和无可行解四种。3、线性规划原问题中的变量个数与其对偶问题中的约束条件 个数相等，因此，当原问题增加一个变量时，对偶问题就增加一个约束条件 ，从而对偶可行域将可能变小 （ 小还是大 ） 。4、“如果线性规划原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错。5、如果某一整数规划：max工二七斗刀工951JT十S1414f 1-2工+三冬王，出之0,11为整数所对应的线性规划（松弛问题）的最优解为10,我们现在要对 进行分枝，应该分为为x 0J =

5、 1,2,3 K. J解：把模型化成标准形式：maxZ = 3Hl +412 +七2Xj +3jc2 +鼻 =1F +2/ +2Xj +r5 =3七 N0jf2,32分单纯形表Cj34100OCBXBbX1X2X3X4X50X41231101/30X53122013/2%3410004X21/32/311/31/301/20X57/3-1/304/3-2/31-%1/30-1/3-4/303X11/213/21/21/200X55/201/23/2-1/210-1/2-1/2-3/209分最优解：X= (1/2, 0, 0, 0, 5/2);最优值 Z=3/212分四、(本题14分)设用单纯形

6、法求解某极大化线性规划问题得到如下的单纯形表cj203/2000CBXBhx1x2x3x4x5x6ax12d-1001-1bx33/20210-12cx40e001-100-100-1/2f(1)试求上述表中的各参数af的值；(2)上表是否给出了最优解，若是则求出最优解;(3)利用对偶关系求出对偶问题最优解、最优值。解：（1） a=2, b=3/2, c=0, d=1, e=0, f=-6分(错一个扣一分)(2)由于所有检验数都非正，因此该表给出最优解，最优解为JC1 = 2,巧=O,JCj =0,工百=0*=25/4(3)利用对偶关系可得对偶问题最优解为M=。，用=1/2g=1,4 =。M，

7、丸=013分825/414分五、(共12分)已知线性规划问题的最终单纯表如下cj3 1 5 0 0CBXBhx1 x2 x3 x4 x535x1x3531-1/3 0 1/3 -1/30 1 1 -1/5 2/50 -3 0 0 -1试分析(1)在什么范围变化，最优解不变？(2)增加一个新的约束条件2玉+39十毛434,原问题最优解是否依然保持？解：（1）由最终单纯形表可知，为保持原最优解不变应有：1R*o仁=.（4 + 2）。L 35 分解不等式组得：3,67 分（2）将原问题的最优解X= （5, 0, 3, 0, 0）代入不等式石十马十434中，不等式仍然成立，故最优解不变。-12 分销地

8、rMB1B2B3B4产量（吨）Al81069250A2127156200A3651012350销量（吨）220180160240800六、（共12分）销地R产妁BAi8S元之 两小素3 3 3 36已知产销量及运价表（见右表）求解此运输问题（要求用沃格尔法求初始调 运方案，用位势法求检验数）。解：（1）由沃格尔法求初始调运方案 产销平衡表二错地产地 8iB,产量Ai5016040250%2002OT小170180350铺必220190ieo540单位运价表的品小元菜之差牛 感6强 J1b |岑】92111（2）用位势法求检验数检验数表情Zf由日工%8I 0g0%7 M21 7（12） 156-3654） 110,112，一一B769（3）因为全体检验数非负，所以初始调运方案即为最优解。12分七、（共10分）用Dijkstra 算法求下图中vi到%的最短路。（可在原图上标号）解：评分标准，表错一个扣一分10分八、（共10分）用图解法找出下面目标规划问题，并写出简要步骤mmZ =片+用(4)十月若而一刍十4一一/；=0 (1)物+2小+d-d；=12 (2) TOC o 1-5 h z 2X1 +3x2+-(/； =12(3)$ 4 4(4)砺 0 (I = 1.23) 1ta 、解:X2d2+(4)d3