一、选择题（共20分，每题2分）
1、线性规划模型三个基本要素中不包括（ D ）
A.决策变量
B.目标函数
C. 约束条件
D.基
2、使用人工变量法求解极大化线性规划问题时，当所有的检验数0≤j σ在基变量中仍含有非零的人工变量，表明该线性规划问题（ 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. 0d +
> B. 0d +
= C. 0d -
= D. 0,0d d -+
>>
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、“如果线性规划原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错。

5、如果某一整数规划：⎪⎪⎪
⎩⎪⎪
⎪⎨⎧≥≤
+-≤++=且为整数,0,31
21451149..max 2121212
1x x x x x x t s x x z 所对应的线性规划（松弛问题）的最优解为231=
x ，3
102=x ，我们现在要对1x 进行分枝，应该分为为 11≤x 和 21≥x 。

6、对于Max
则对应的割平面方程为43414343-≤--
x x 或4
3
4143543-=+--x x x 。

7、求最小生成树问题，常用的方法有：避圈法和 破圈法 。

三、（共12分）
用单纯形法求如下线性规划的最优解、最优值。

123
123123max 34231223
0,1,2,3j
Z x x x x x x x x x x j =++⎧++≤⎪
++≤⎨⎪≥=⎩
解：把模型化成标准形式：
123
12341235max 34231
2230,1,2,3j
Z x x x x x x x x x x x x j =++⎧+++=⎪
+++=⎨⎪≥=⎩ ……2分
9分 最优解：X=（1/2，0，0，0，5/2）；最优值Z ＝3/2 ……12分
四、（本题14分）
设用单纯形法求解某极大化线性规划问题得到如下的单纯形表
(1) 试求上述表中的各参数a~f 的值；
(2) 上表是否给出了最优解，若是则求出最优解； (3) 利用对偶关系求出对偶问题最优解、最优值。

解：（1）a=2, b=3/2, c=0, d=1, e=0, f=-1 ……6分(错一个扣一分) （2）由于所有检验数都非正，因此该表给出最优解，最优解为 ……7分
0,0,0,2/3,0,2654321======x x x x x x ……8分
4/25*=z ……9分
（3）利用对偶关系可得对偶问题最优解为
0,1,0,1,2/1,0654321======y y y y y y ……13分
4/25*=z ……14分 五、（共12
分）
试分析（1）1c 在什么范围变化，最优解不变？
（2）增加一个新的约束条件1232334x x x ++≤ ，原问题最优解是否依然保持？ 解：（1）由最终单纯形表可知，为保持原最优解不变应有：
2
14
15
111(5)03
1(1)031(2)03C C C σσσ⎧
=--+≤⎪⎪
⎪
=--≤⎨⎪
⎪
=--+≤⎪⎩
-------5分
解不等式组得：1C []3,6∈ -------7分 （2）将原问题的最优解X=（5，0，3，0，0）代入不等式123334x x x ++≤中，不等式仍然成立，故最优解不变。

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

解：（1）由沃格尔法求初始调运方案
产销平衡表
单位运价表
……5分
（2）用位势法求检验数
检验数表
……10分
（3）因为全体检验数非负，所以初始调运方案即为最优解。

……12分
七、（共10分）
用Dijkstra 算法求下图中1v 到8v 的最短路。

（可在原图上标号）
解：评分标准，表错一个扣一分。

……10分
八、（共10分）
用图解法找出下面目标规划问题，并写出简要步骤。

⎪⎪
⎪⎪
⎩
⎪⎪⎪⎪⎨
⎧=≥≥≤≤=-++=-++=-+-+++=-
++-+
-+-++--)3.2.1( 0,,0)5(3 )4(4)3(12 32 )2(12 2 2 )1(0)(min 2,1213321222111212
311231l d d x x x d d x x d d x x d d x x d P d d P d P Z l l 解：
X （3
0 4 6 X1
解：如上图，可行域为图中剖面线部分；……4分P1d3-:满意解在AB以上，即三角形ABE；……6分P2(d1-+d1+):满意解在线段CD上；……8分P3d2+:满意解在线6C以下，即最优解为C点；……10分。