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

一、选择题（共20分，每题2分）

1、线性规划模型三个基本要素中不包括（ D ）

A.决策变量 B.目标函数 C. 约束条件 D.基

2、使用人工变量法求解极大化线性规划问题时，当所有的检验数?j?0在基变量中仍含有非零的人工变量，表明该线性规划问题（ D ）

A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 3、若线性规划的原问题不存在最优解，则对偶问题（ B ）

A．可能存在最优解 B．不存在最优解 C．一定是无可行解 D．一定是无界解 4、若线性规划问题的某个资源常数发生变化，则在最终单纯形表中这一变化（ B ） A．对检验数存在影响 B．对b列数存在影响 C．对该资源常数所在行的数存在影响 D．对所有数都无影响

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. d?0 C. d?0 D. d?0,d?0

???8、对于目标规划问题的求解，在满足一个目标时 （ B ）

A．必须同时考虑优先级较低的目标 B．不得违背已经得到满足的优先级更高的目标 C．不必顾虑优先级较高的目标 D．无须考虑上述情况 9、关于图论中的图，以下叙述不正确的是（ C ）

A．图中点表示研究对象，边或有向边表示研究对象之间的特定关系 B．图论中的图，画边时长短曲直无所谓

C．图中的边表示研究对象，点表示研究对象之间的特定关系

D．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系 10、关于最短路，以下叙述正确的有（ A ）

A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的 B．从起点出发到终点的最短路是唯一的

C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上

二、填空题（共10分，每空1分）

1、线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有某一个非基变量的检验数为 0 。 2、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 3、线性规划原问题中的变量个数与其对偶问题中的 约束条件 个数相等，因此，当原问题增加一个变量时，对偶问题就增加一个约束条件 ，从而对偶可行域将可能变小 (小还是大)。 4、“如果线性规划原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错。

1 / 6

maxz?x1?x2951?x?x??114214?5、如果某一整数规划：?所对应的线性规划（松弛问题）的最优解为1s.t.??2x1?x2?3??x1,x2?0,且为整数??x1?310，x2?，我们现在要对x1进行分枝，应该分为为 x1?1 和 x1?2 。 23XB x1 则对应的割平面方程为?6、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

b 3/4 x1 1 x2 0 x3 -1/4 x4 1/4 313313x3?x4?? 或?x3?x4?x5??。 4444447、求最小生成树问题，常用的方法有：避圈法和 破圈法 。

三、（共12分）

用单纯形法求如下线性规划的最优解、最优值。

maxZ?3x1?4x2?x3 ??2x1?3x2?x3?1?x1?2x2?2x3?3?x?0,j?1,2,3?j

解：把模型化成标准形式：

maxZ?3x1?4x2?x3?2x1?3x2?x3?x4?1 ??2分 ?x?2x?2x?x?3?1235?x?0,j?1,2,3?j单纯形表 Cj CB 0 0 XB X4 X5 b 3 4 [3] 2 4 1 0 0 3/2 1/2 1 1 2 1 1/3 4/3 -1/3 1/2 3/2 2 / 6

0 X4 1 0 0 1/3 -2/3 -4/3 1/2 -1/2 X1 X2 X3 2 1 3 ? X5 0 0 1 0 0 1 0 0 1 1/3 3/2 0 1/2 1 3 ?j 4 0 X2 X5 1/3 7/3 [2/3] -1/3 1/3 - ?j 3 0 X1 X5 1/2 5/2 1 0 ?j 0 -1/2 -1/2 -3/2 0 ??9分 最优解：X=（1/2，0，0，0，5/2）；最优值Z＝3/2 ??12分

四、（本题14分）

设用单纯形法求解某极大化线性规划问题得到如下的单纯形表

cj CB a b c XB x1 x3 x4 ?j 2 0 x2 -1 2 0 -1 3/2 x3 0 1 0 0 0 x4 0 0 1 0 0 x5 1 -1 -1 -1/2 0 x6 -1 2 0 f b 2 3/2 0 x1 d 0 e 0 (1) 试求上述表中的各参数a~f的值；

(2) 上表是否给出了最优解，若是则求出最优解； (3) 利用对偶关系求出对偶问题最优解、最优值。 解：（1）a=2, b=3/2, c=0, d=1, e=0, f=-1 ??6分(错一个扣一分) （2）由于所有检验数都非正，因此该表给出最优解，最优解为 ??7分

x1?2,x2?0,x3?3/2,x4?0,x5?0,x6?0 ??8分

z*?25/4 ??9分

（3）利用对偶关系可得对偶问题最优解为

y1?0,y2?1/2,y3?1,y4?0,y5?1,y6?0 ??13分

z*?25/4 ??14分 五、（共12分）

已知线性规划问题的最终单纯表如下 cj CB 3 5 XB x1 x3 ?j 3 1 5 0 0 b 5 3 x1 x2 x3 x4 x5 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5 0 -3 0 0 -1 试分析（1）c1在什么范围变化，最优解不变？

（2）增加一个新的约束条件2x1?3x2?x3?34 ，原问题最优解是否依然保持？ 解：（1）由最终单纯形表可知，为保持原最优解不变应有：

1???1?(?C1?5)?0?23?1????(C1?1)?0 -------5分 ?43?1????(?C1?2)?0?53? 3 / 6

解不等式组得：C1??3,6? -------7分 （2）将原问题的最优解X=（5，0，3，0，0）代入不等式x1?x2?3x3?34中，不等式仍然成立，故最优解不变。 --------12分

六、（共12分）

已知产销量及运价表（见右表）求解此运输问题（要求用沃格尔法求初始调运方案，用位势法求检验数）。

销地 B1 产地 Al A2 A3 8 12 6 B2 10 7 5 180 B3 6 15 10 160 B4 9 6 12 240 产量（吨） 250 200 350 800

解：（1）由沃格尔法求初始调运方案

销量（吨） 220 产销平衡表

单位运价表

??5分

（2）用位势法求检验数

检验数表

??10分

（3）因为全体检验数非负，所以初始调运方案即为最优解。 ??12分

七、（共10分）

4 / 6