样卷
（一）单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2分，共20分）
1. 在线性规划模型中，满足约束条件和非负条件的解称为( )
A．基本解 B．基本可行解 C．可行解 D．最优解
2. 线性规划可行域的顶点一定是( )
A．基本可行解 B．最优解 C．非可行解 D．非基本解
3. X是线性规划的基本可行解则有( )
A．X中的基变量非负，非基变量为零 B．X是最优解
C．X不一定满足约束条件 D．X中的基变量非零，非基变量为零
4. 线性规划最优解唯一是指( )
A．可行解集合无界 B．最优表中存在非基变量的检验数为零
C．可行解集合是空集 D．最优表中非基变量的检验数全大于零
5. 原问题有4个变量3个约束，其对偶问题( )
A．有3个变量4个约束 B．有4个变量3个约束
C．有4个变量3个约束 D．有4个变量4个约束
6. 在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题
( )
A．无最优解 B．有唯一最优解
C．有无穷多个最优解 D．不确定
7. 对偶单纯形法中，若满足( )，则原问题没有可行解。
A．基变量的取值出现负值
B．检验数中出现正数
C．检验数全部小于零
D．存在某个基变量为负数，且其所在行的系数全部大于或等于零
8. 若树T有n个顶点，那么它的边数一定是( )
A．n-1 B．n+1 C．n D．n2
9. 原问题与对偶问题都有可行解，则有( )
A、原问题有最优解，对偶问题可能没有最优解
B、原问题与对偶问题可能都没有最优解
C、可能一个问题有最优解，另一个问题具有无界解
D、原问题与对偶问题都具有最优解
10.用割平面法求解整数规划时，构造的割平面只能切去( )
A．整数可行解 B．整数解最优解 C．非整数解 D．无法确定
（二）填空题（每空格4分，共20分）
1.如果在线性规划模型中变量xj的符号不受限制，即变量xj取正值，取负值或取零都可以，则称xj为 。
2.如果线性规划问题(LP)的基本解又满足非负条件，即有 (i=1,…,m)，则称它为(LP)的一个 。
3.树连通，但不存在 。
4.求解非负赋权图的最短路径问题的较好算法是 。
5.物资调运方案的最优性判别准则是：当 时，当前的方案一定是最优方案。
（三）简答题（共3小题，每题5分，共15分）
1. 线性规划只要有可行解一定有基本可行解。那么，能否确定一定存在最优解？
2. 已知原问题有最优解，那么对偶问题呢？它们的什么是相等的？
3. 为什么说任一运输网络中至少存在一个可行流？
（四）建模题（共2小题，每题10分，共20分）
1. 一个车间要加工3种零件，其需要量分别为4000件、5000件和3500件. 车间内现有4台机床，都可用来加工这3种零件，每台机床可利用的工时分别为1600, 1250, 1800和2000. 机床i#加工零件j#所需工时和成本由表1给出，问如何安排生产，才能使生产成本最低，请列出数学模型，不需要求解。
表1
2. 写出下列线性规划问题的对偶问题：
Max f =3x1 -2x2-5x3-8x5;
s.t. 2x1 +3x2 -3x3- x4 -5x5 ≥-2,
x2 -2x3+3x4 +4x5 =-5,
-x1 +2x3 -2x4 -3x5 ≤-5.
x1 ≤ 0, x2无约束, x3≥ 0, x4≥ 0, x5无约束.
（五）计算题（共5小题，每题15分，共75分）
1. 用单纯形法求解下列线性规划问题：
min f =-5x1 -4x2;
s.t. x1 + 2x2 ≤6,
2x1 -x2 ≤4,
5x1 +3x2 ≤15,
x1 ≥ 0, x2 ≥ 0.
2. 求解表2所给运输问题：
(1) 用西北角法求初始解；
(2) 用位势法求最优解。
表2
3. 用割平面法求解下列整数规划：
min f =-3x1 -4x2;
s.t. 2x1 +5x2 +x3 = 15,
2x1 -2x2 +x4 = 5,
xj ≥ 0, 整数, j=1,2,3,4.
已知相应的(LP)的最优单纯形表如表3所示。
表3
|
XB
|
x1
|
x2
|
x3
|
x4
|
|
|
x2
|
0
|
1
|
1/7
|
-1/7
|
10/7
|
|
x1
|
1
|
0
|
1/7
|
5/14
|
55/14
|
|
r
|
0
|
0
|
1
|
1/2
|
35/2
|
4. 求图1中v1至v10的最短路径和长度。
图1
5. 求运输网络图图2的最大流及最小割。
图2
您现在的位置： 