运筹学2010B卷期末考试.doc

河北工业大学期末考试试卷
2010 年 春 季学期
学院名称：
管理学院
班级名称：

姓名：

学号：

河北工业大学期末考试试卷
2010 年 春 季学期
课程名称
运筹学
适用专业
管理学院各专业
A/B卷
B
开/闭卷
闭卷
学院名称
管理学院
班级

姓名

学号

题号
一
二
三
四
五
六
七
八
九
十
十一
十二
总分
分数

阅卷人

一、填空题（每小题3分，共15分）
1. 用单纯形法求解线性规划问题时，单纯形表中的每个解对应的是线性规划问题的一个 ，与图解法上 对应。
2. 在对偶单纯形法中，确定换入变量时采用的最小比值规则，采用该规则的主要目的是是保证对偶问题的解总是 。
3. 用表上作业法解运输规划模型时，作业表应满足的两个基本条件是 。
4. 在动态规划模型中，状态变量表示每个阶段 时所处的自然状况或客观条件，它要满足 的特性。
5. 若解整数规划的单纯形表的最终表中有约束行为：，其中为基变量，则其对应的割平面方程为 。

二、单项选择题（每题3分，共15分）
1、 在用单纯形法求解极大化线性规划问题时，对于所有σj>0来说，选取最大的σj对应的变量作为换入变量，则 。
A、下一步会出现负值 B、肯定需要最多的迭代步骤
C、对迭代过程无影响 D、目标函数值会增长快些
2、 下面哪一个表达式可以作为目标规划的目标函数
A、 B、
C、 D、
3、 当用大M法求解有人工变量的极大化线性规划时，判断原问题无可行解的依据是 。
A、基变量中始终含有人工变量 B、检验数行为非负值
C、非基变量中含有人工变量 D、检验数行有正有负
4、 若原问题有可行解，对偶问题无可行解，则原问题的解为 。
A、唯一最优解 B、无可行解 C、无穷多最优解 D、无界解
5、 设G是一个连通图，不含奇点，则从G中去掉任一条边后，得到的图必定为 。
A、简单图 B、连通图 C、不连通图 D、多重图

三、已知线性规划问题（第一问8分，第二问7分，共15分）

（1） 写出其对偶问题。
（2） 其最优解为，根据对偶性质直接求解对偶问题的最优解。

四、（共20分，其中1、3问各7分，第2问6分） 某厂用两种原材料生产两种产品，已知数据见表1，根据该表列出的数学模型如下，加松弛变量，并用单纯形法求解得最终单纯形表见2表
表1：

产品I
产品II
资源限制
原材料A（kg/件）
2
3
14
原材料B（kg/件）
2
1
9
收入（元 / 件）
3
2

表2：
CB
XB
b
x1
x2
x3
x4
2
x2
5/2
0
1
1/2
-1/2
3
x1
13/4
1
0
-1/4
3/4
cj – zj
0
0
-1/4
-5/4

（1）求c1 的变化范围以使最优解保持不变。
（2）现在市场上原材料B的价格为1元，问是否需要买入原材料B，为什么？
（3）如果需要买入原材料B，最多买入多少？

五、甲、乙两电站供应A、B、C三个城市用电，各电站产量及各城市需电量见下表1，各电站供给各城市单位电价见表2，试求总费用最低的电力分配方案。（共20分，其中初始方案及其检验各占5分，过程及结果各5分）
表2：单位电价
城市
电站

A

B

C
甲
15
18
22
乙
21
25
16
表1：供电量及需求量

电站
日产量
城市
日需电量
甲
400
A
350
乙
450
B
250
C
250

六、用标号法求下图网络从v1到v6的最大流量，图中每弧旁的数字为（cij，fij）。（共15分，其中增广链、过程和结果各占5分）
v1
v2
v3
v4
v5
v6
(4,2)
(3,1)
(4,2)
(2,1)
(1,1)
(2,1)
(3,1)
(3,3)
(4,0)
(2,2)

第4页，共4页