管理运筹学期末试卷B
一、 填空题（每小题4分，共20分）
1、设原LP 问题为??????
?≥-=++-≥--≤++++-=
,0,5232
4 7
532min 3213213213213
21无约束x x x x x x x x x x x x x x x Z 则它的标准形和对偶规划问题分别为：________________________ 和
________________________。
2、用分枝定界法求整数规划12
12121121min 5 2
56 30
4,0Z x x x x x x x x x x =---≥-??+≤??
≤??≥?且为整数的解时，求得放松问题的解为x 1＝18/11, x 2 =40/11，则可将原问题分成如下两个子问题
与
求解。
3、右图的最小支撑图是。
4、右边的网络图是标号算法中的图，其中每条弧上的数
表示其容量和流量。该图中得到的可行流的增广链
为： ，在其上可增的最大流量 为 。
5、已知某线性规划问题，最优单纯形表如下:
(-3,1) (2,1)
②5(4) ④
①6(6) 6(4) ⑥2(1) 5(1) 7(0 )
③8(6) ⑤(1,1) (-2,2)
(0, ∞) 8(8) 3(2 ) 9(9)(5,1)
则其最优解为：，最优值=
Z。
max
二、单项选择题（每小题2分，共10分）
1、下列表格是对偶单纯形表的是（A ）
A
B
C
D
2、关于线性规划模型的可行域，叙述正确的为（）
A、可行域必有界；
B、可行域必然包括原点；
C、可行域必是凸的；
D、可行域内必有无穷多个点。
3、在运输问题中如果总需求量大于总供应量，则求解时应（）
A、虚设一些供应量；
B、虚设一个供应点；
C、根据需求短缺量，虚设多个需求点；
D、虚设一个需求点。
4、下列规划问题不可用动态规划方法求解的是（ ） A 、背包问题； B 、最短路径问题
C 、线性规化：
???≥≥=++++=0
,01034..max 321
3
32211y x x x x t s x c x c x c Z D 、22
min (,)(2)3(1).. 460,0f x y x y s t xy y x y ?=++-?+
5、下列关于图的论述正确地是（ ）
A 、有向图的邻接矩阵是对称矩阵；
B 、图G 是连通的，当且仅当G 中的任意两点之间至少存在一条链；
C 、任何一个连通图，都存在唯一的最小支撑树；
D 、若图),(
E V G ''='是图),(E V G =一个支撑子图，则E E V V '=?',。
三、判断题（每小题2分，共10分）
（ ）1、若原始问题是利润最大化的生产计划问题，则对偶问题是资源定价问题，
对偶问题的最优解称为原始问题中资源的影子价格。影子价格越大说明这种资源越是相对紧缺，影子价格越小说明这种资源相对不紧缺。
（ ）2、对max 型整数规划，若其松弛问题最优解对应的目标函数值为Z c ，而其
最优整数解对应的目标值为Z d ，那么一定有Z c ≤Z d 。
（ ）3、任何一个无圈的图G 都是一个树图。
（ ）4、一个可行流满足平衡条件是指：所有中间结点处流出量=流入量，收点流
出量=0, 发点流入量=0，收点流入量=发点流出量。
（ ）5、恰好有两个悬挂点的树是一条链。
四、求解线性规划：
???
??≥≤+-≤++++=0,,426 32 max 3
2121321321x x x x x x x x x x x z （方法不限）（15分）
五、某食品集团公司下属有甲、乙两个面粉厂供应其下属A 、B 、C 三个食品厂所需面粉，各面粉
厂产量及各食品厂所需面粉、各面粉厂到各食品厂的运输距离见下表：
求：(1)用最小元素法求一个初始可行调运方案；
(2)用位势法检验该初始调运方案是否是总运输费最少的最优方案；若是求最少总运输费，若不是，求一次调整新方案。（15分）
6 5 3 日销量
（需求量吨）
4
2 4
3 乙 10 3 6 3 甲 日产量 （供应量吨） C B A 运距 食品厂
面粉厂
六、煤气公司欲从A 点往住宅区E 送煤气在途中三次加压，全部可能的加压的站点如下图所示，线上数字代表两节点间距离(
问：(1)(2)需用管多少？
如果工厂经营目标的期望值和优先等级如下：
p 1: 每周总利润不得低于10000元；
p 2: 因合同要求，A 型机每周至少生产10台，B 型机每周至少生产15台；
p 3: 希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。
试建立这个问题的目标规划模型。（10分）
九、某项目工序明细表如下：
要求：（1）绘制网络图；（2）计算工程的最早完工时间，并指出关键工序。（10分）
.
信你自己罢！只有你自己是真实的，也只有你能够创造你自己