管理运筹学期末试卷B.doc

一、 填空题（每小题4分,共20分）
1、设原LP问题为则它的标准形和对偶规划问题分别为: 和 。
2、用分枝定界法求整数规划的解时，求得放松问题的解为x1＝18/11， x2 =40/11，则可将原问题分成如下两个子问题
与 求解.
3、右图的最小支撑图是。
4、右边的网络图是标号算法中的图，其中每条弧上的数
表示其容量和流量。该图中得到的可行流的增广链
为： ，在其上可增的最大流量
为 。
5、已知某线性规划问题,最优单纯形表如下：
CB
XB
Cj
xj
1 2 0 0 0
qj

x1 x2 x3 x4 x5
1

2
1 0 1/2 0 —1/2

0

3
0 0 -3/2 1 3/2

2

4
0 1 0 0 1/2

—Z

0 0 -1/2 0 -1/2

则其最优解为： ，最优值 。
二、单项选择题(每小题2分，共10分）
1、下列表格是对偶单纯形表的是（ A ）
A、
CB
XB
Cj
xj
—1 4 5 0 0
qj

x1 x2 x3 x4 x5
—1

—8
1 3 1 0 0
—
0

3
0 0 1/2 1 -1/2
3
-Z
-16
0 -3 —5 0 —1

B、
CB
XB
Cj
xj
5 0 21 0 0
qj

x1 x2 x3 x4 x5
0

2
1 -1 6 1 0
1/3
0

1
1 1 2 0 1
1/2
—Z
0
5 0 21 0 0

C、
CB
XB
Cj
xj
—1 4 5 0 0
qj

x1 x2 x3 x4 x5
—1

-8
1 3 1 0 0
—
0

3
2 2 -3 1 -2
3
-Z
12
0 —3 —5 0 —1

D、
CB
XB
Cj
xj
5 0 21 0 0
qj

x1 x2 x3 x4 x5
0

1/3
1/6 -1/6 1 1/6 0
2
0

2/3
5/6 7/6 0 —1/6 1
4/5
-Z
0
5 0 21 0 0

2、关于线性规划模型的可行域，叙述正确的为（ ）
A、可行域必有界； B、可行域必然包括原点；
C、可行域必是凸的； D、可行域内必有无穷多个点.
3、在运输问题中如果总需求量大于总供应量,则求解时应（ ）
A、虚设一些供应量; B、虚设一个供应点;
C、根据需求短缺量，虚设多个需求点； D、虚设一个需求点。
4、下列规划问题不可用动态规划方法求解的是（ ）
A、背包问题; B、最短路径问题
C、线性规化: D、
5、下列关于图的论述正确地是（ ）
A、有向图的邻接矩阵是对称矩阵；
B、图G是连通的，当且仅当G中的任意两点之间至少存在一条链；
C、任何一个连通图，都存在唯一的最小支撑树;
D、若图是图一个支撑子图，则。
三、判断题(每小题2分，共10分）
（ ）1、若原始问题是利润最大化的生产计划问题，则对偶问题是资源定价问题，对偶问题的最优解称为原始问题中资源的影子价格。影子价格越大说明这种资源越是相对紧缺，影子价格越小说明这种资源相对不紧缺.
( ）2、对max型整数规划，若其松弛问题最优解对应的目标函数值为Zc,而其最优整数解对应的目标值为Zd，那么一定有Zc ≤Zd.
（ ）3、任何一个无圈的图G都是一个树图。
（ ）4、一个可行流满足平衡条件是指：所有中间结点处流出量=流入量，收点流出量=0， 发点流入量=0，收点流入量=发点流出量。
( ）5、恰好有两个悬挂点的树是一条链。
四、求解线性规划：（方法不限）（15分）
五、某食品集团公司下属有甲、乙两个面粉厂供应其下属A、B、C三个食品厂所需面粉,各面粉厂产量及各食品厂所需面粉、各面粉厂到各食品厂的运输距离见下表：

6
5
3
日销量
（需求量吨）
4
2
4
3
乙
10
3
6
3
甲
日产量
（供应量吨）

C

B

A
运距 食品厂
面粉厂

求:(1)用最小元素法求一个初始可行调运方案；
(2)用位势法检验该初始调运方案是否是总运输费最少的最优方案；若是求最少总运输费，若不是，求一次调整新方案。(15分)
六、煤气公司欲从A点往住宅区E送煤气在途中三次加压，全部可能的加压的站点如下图所示，线上数字代表两节点间距离（单位：千米)。
问：（1）如何敷设才能使所用管道最少？
(2)需用管多少？
七、.已知某厂生产A、B两种机型的设备，条件如表所示
工序
型号
每周最大加工能力
A
B
Ⅰ（小时/台）
Ⅱ（小时/台）
4
3
6
2
150
70
利润(元/台)
300
450

如果工厂经营目标的期望值和优先等级如下：
p1: 每周总利润不得低于10000元；
p2： 因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；
p3： 希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。
试建立这个问题的目标规划模型.（10分）
九、某项目工序明细表如下:
工序
工时（d）
紧前工序
工序
工时（d）
紧前工序
A
B
C
D
E
F
3
2
5
4
7
8
－
－
－
A
B
C
G
H
I
J
K
L
6
2
4
5
2
6
D，B
E
G,H
E，F
E,F
I，J
要求:(1）绘制网络图；(2)计算工程的最早完工时间，并指出关键工序.（10分）
.