运筹学自测题(含答案).doc

运筹学复习题（A）
一、单项选择（将唯一正确答案前面的字母填入题后的括号里。正确得 2 分，
选错、多选或不选得0 分。共30 分）
1、在线性规划模型中，没有非负约束的变量称为 （C ）
A 多余变量 B 松弛变量 C 自由变量 D 人工变量
2、约束条件为AX=b，X≥0 的线性规划问题的可行解集是 （B ）
A 补集 B 凸集 C 交集 D 凹集
3、线性规划问题若有最优解，则一定可以在可行域的 （C ）上达到。
A 内点 B 外点 C 极点 D 几何点
4、对偶问题的对偶是 （D ）
A 基本问题 B 解的问题 C 其它问题 D 原问题
5、若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变
量的 （C ）
A 值 B 个数 C 机会费用 D 检验数
6、若运输问题已求得最优解，此时所求出的检验数一定是全部 （ A）
A 大于或等于零 B 大于零 C 小于零 D 小于或等于零
7、设V 是一个有n 个顶点的非空集合，V={v1，v2，……，vn}，E 是一个有m
条边的集合，E={e1，e2，……em}，E 中任意一条边e 是V 的一个无序元素对
[u，v]，（u≠v），则称V 和E 这两个集合组成了一个 （D ）
A 有向树 B 有向图 C 完备图 D 无向图
8、若开链Q 中顶点都不相同，则称Q 为 （B ）
A 基本链 B 初等链 C 简单链 D 饱和链
9、若图G 中没有平行边，则称图G 为 （A ）
A 简单图 B 完备图 C 基本图 D 欧拉图
11、若Q 为f 饱和链，则链中至少有一条后向边为f （B ）
A 正边 B 零边 C 邻边 D 对边
12、若f 是G 的一个流，K 为G 的一个割，且Valf=CapK，则K 一定是 （A ）
A 最小割 B 最大割 C 最小流 D 最大流
13、对max 型整数规划，若最优非整数解对应的目标函数值为Zc，最优整数解
对应的目标值为Zd，那么一定有 (D)
A Zc ∈Zd B Zc =Zd C Zc ≤Zd D Zc ≥Zd
14、若原问题中xI 为自由变量，那么对偶问题中的第i 个约束一定为 （ A）
A 等式约束 B “≤”型约束 C “≥”约束 D 无法确定
15、若f*为满足下列条件的流：Valf*=max{Valf |f 为G 的一个流}，则称f*为G
的 （C ）
A 最小值 B 最大值 C 最大流 D 最小流
二、多项选择题（每题至少有一个答案是正确的。选对得2 分；多选、少选或
不选得0 分。共10 分）
1、就课本范围内，解有“≥”型约束方程线性规划问题的方法有 （ABE ）
A 大M 法 B 两阶段法 C 标号法 D 统筹法 E 对偶单纯型法
2、线性规划问题的一般模型中可以出现下面几种约束 （ ABC）
A = B ≥ C ≤ D ⊕ E ∝
3、线性规划问题的主要特征有 （ABCD ）
A 目标是线性的 B 约束是线性的 C 求目标最大值 D 求目标最小值
E 非线性
4、图解法求解线性规划问题的主要过程有 （ABCE ）
A 画出可行域 B 求出顶点坐标 C 求最优目标值
D 选基本解 E 选最优解
5、就课本内容，求解0-1 规划常用的方法有 （AB ）
A 全枚举法 B 隐枚举法 C 单纯型法 D 位势法 E 差值法
三、简答题（每道题 5 分。共20 分）
1、何谓线性规划问题的基础解？何谓基础可行解？
解：

设B为A中的一个基，令Ax=b，中所有的非基变量（n-m个）为0，得出的解x，称为是B的基础解。
满足变量非负条件（1-6）的基础解称为基础可行解。
2、当线性规划数学模型中引用人工变量数时，分别采用哪两种方法迭代出基变量？在何种情况下采用？
在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加入的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解。
对于无初始可行解的问题可用大M法求解。方法：化为标准型的同时，将>以及=的约束条件中，加入人工变量(虚拟变量)，将目标函数中虚拟变量的稀疏设定为M。
但是大M法如在计算机上运作，M就只能用很大的数来代替，这样可能会出现错误。此时需要两阶段法求解。
3、什么是线性规划问题的灵敏度分析？
线性规划模型的确定是以 为已知常数作为基础的，但在实际问题中，这些数据本身不仅很难准确得到，而且往往还要受到诸如市场价格波动，资源供应量变化，企业的技术改造的因素的影响，因此，很自然地要提出这样的问题，当这些数据有一个或多个发生变化时，对已找到的最优解或最优基会产生怎样的影响；或者说这些数据在什么范围内变化，已找到的最优解或最优基不变；以及在原最优解或最优基不在是最优基时，如何用最简单的方法求出新的最优解或最优基。这就是线性规划问题的灵敏度分析。

4、什么是整数规划？并写出其数学模型？

四、计算题 （共40 分）

1、（6 分）化为标准型

解：令Z’=- Z，x1’=- x1, x3= x4- x5,其中x4 ≥0，x5≥0，则问题的标准形式为：
max Z’=-2x1’+x2-2x4+2x5
x1’+x2+x4-x5 =4
s.t． x1’+x2-x4+x5+x6=6
x1’,x2,x4,x5,x6≥0
≤
2、（10 分）某厂生产甲、乙、丙三种产品，已知有关数据如下表所示：

求使该厂获利最大的生产计划。
解：设生产甲、乙、丙三种产品的数量各为x1，x2，x3，依题意得，
max Z=4x1+x2+5x3
6x1+3x2+5x3≤45
s.t． 3x1+4x2+5x3≤30
x1,x2,x3≥0
对该方程求解得， x1=5.3
x2=0
x3=5.3
所以，最优生产计划为生产甲、丙各5.3公斤，不生产乙产品。
3、（8 分）目标函数为max Z =28x4+x5+2x6，约束形式为“≤”，且x1，x2，
x3 为松弛变量,表中的解代入目标函数中得Z=14，求出a~g 的值，并判断是否最优解

解：由图表可知，表中的解为x4=0,x5=0,x6=a。
由题意，表中的解带入目标函数得Z=14,可得
max Z =28x0+0+2xa=14
解之得，a=7.
另由图表知，最终的基向量为x6,x2,x4.故c=g=0,d=1,e=0.
因x1,x2,x3是虚拟变量，故计算可得b=-6，f=1/3.
将所求得的值带入表格中，验证可得，x4=0,x5=0,x6=7是线性规划的最优解。
4、（7 分）根据所给的表和一组解判断是否最优解，若不是，请求出最优解。
（x13, x14, x21, x22, x32, x34）=（5，2，3，1，5，4）

解：该解不是最优解。下面运用最小元素法求解。
销地
产地
B1
B2
B3
B4
产量
A1
3
11
5 3
2 10
7
ƒ
A2
3 1
9
1 2
8
4

A3
7
6 4
10
3 5
9
ƒ
销量
3
6
5
5
‚

最优解为（x13, x14, x21, x22, x32, x34）=（5，2，3，1，6，3）

5、（9 分）用标号法求图所示的网络中从vs 到vt 的最大流。

解：依题意得

最大流值为5