2016年西安石油大学832管理学综合一之《运筹学教程》考研冲刺密押卷及答案
● 摘要
一、选择题
1． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法
B.Floyd 算法
C.Ford 一Fulkerson 算法
D. 奇偶点作业法
【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
2． 用单纯形法求解线性规划问题时，满足（ ）对应的非基变量xj 可以被选作为换入变量。
A. 检验数σ>0
B. 检验数σ<0
C. 检验数σ>0中的最大者
D. 检验数σ<0中的最小者
【答案】C
【解析】当某些σ>0时，xj 增加则目标函数值还可以增大，这时要将某个非基变量xj 换到基变量中去，为了使目标函数值增加得快，一般选择σ>0中的大者。
二、计算题
3． 用破圈法和避圈法求下图的一个支撑树。
【答案】（l ）用破圈法求解，求解过程如下。
，去掉其中一条边，如e 2=[v1，v 3]; ①取圈（v 1，v 2，v 3）
，去掉其中一条边，如e 7=[v1，v 5]; ②取圈（v 1，v 2，v 5）
，去掉其中一条边，如e 3=[v2，v 3]; ③取圈（v 2，v 3，v 4）
，去掉其中一条边，如e 5=[v2，v 5]; ④取圈（v 2，v 4，v 5）
，去掉其中一条边，如e 10=[v5，v 6]; ⑤取圈（v 4，v 5，v 6）
，去掉其中一条边，如e 15=[v8，v 10]. 这时，剩余的图中不含圈，即得到了⑥取圈（v 8，v 9，v 10）
一个支撑树，如图所示。
图
（2）用避圈法求解，求解过程如下:
①在图10-1中，任取一条边e 1，找一条与e 1不构成圈的边e 4; ②找一条与{el ，e 4}不构成圈的边e 6;
③找一条与{el ，e 4，e 6}不构成圈的边e 8;
④找一条与{el ，e 4，e 6，e 8}不构成圈的边e 9;
⑤找一条与毛{el ，e 4，e 6，e 8，e 9}不构成圈的边e 11;
⑥找一条与{el ，e 4，e 6，e 8，e 9，e 11}不构成圈的边e 12;
⑦找一条与{el ，e 4，e 6，e 8，e 9，e 11，e 12}不构成圈的边e 13; ⑧找一条与{el ，e 4，e 6，e 8，e 9，e 12，e 13}不构成圈的边e 14。这时，剩余的图中不含圈，即得到了一个支 撑树，如图所示。
图
4． 用分支定界法解以下问题。
【答案】在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，化为标准型
先不考虑模型中的整数约束，利用单纯形法求解，过程如表所示。
表
此时的最优解为
记，因为
为可行解，所以 。将原问题分解为两个子问题:
求得B 1的最优解x l =2，x 2=23/9，z 2=41/9。