D、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应
的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题
通过分支迭代求出最优解。
7、下列变量组是一个闭回路的有（）
A、{x21,x11,x12,x32,x33,x23}
B、{ x11,x12,x23,x34,x41,x13}
C、{x21,x13,x34,x41,x12,x14}
D、{ x12,x22,x32,x33,x23,x21}
8、工序（i,j）的最早开工时间T ES（i,j）等于（）
A、T E（i）
B、max{ T Es（k）+ t ki }
C、T L（i）
D、min{ T L（j）- t ij }
9、对于不确定型的决策，某人采用悲观主义准则进行决策，则应在收益表中（）
A、大中取小
B、大中取大
C、小中取小
D、小中取大
10、以下哪项是决策结果的方法程序（）
A、收集信息-确定目标-提出方案-方案优化-决策
B、确定目标-收集信息-决策-提出方案-优化方案
C、确定目标-收集信息-提出方案-方案优化-决策
D、确定目标-提出方案-收集信息-方案优化-决策
单项选择题答题表
二、判断题，正确打√，错误打×, 并将修改建议简写在对应题号下的改错栏。
（20分，每题2分）
1、线性规划问题的每一个基可行解对应可行域的一个顶点。（√）
2、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（√）
3、线性规划模型中增加一个约束条件，可行区域的范围一般将缩小，减少一个约束条件，
可行域的范围一般将扩大。（√）
4、紧前工序是前道工序，后序工序是紧后工序。( )
5、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。( )
6、旅行售货员问题是遍历每一条边的问题。( )
7、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭
回路。（√）
8、在目标规划模型中，正偏差变量应取正值，负偏差变量应取负值。（×）
9、在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（√）
10、在任何网络中，最大流的值＝最小截集的容量。（√）
中国计量学院200 ~200 学年第学期《运筹学》课程试卷（A ）第2页共6页
中国计量学院200 ~200 学年第 学期《 运筹学 》课程试卷（ A ）第 3 页 共 6页
三、填空计算题（20分，每个填空为2分）
对于如下的线性规划问题
min z = -x 1 + 2x 2
s.t. 2x 1 + 3x 2 ≤
3x 1 + x 2 ≤ 6 (2) -x 1 + 3x 2 ≥ 3 (3) x 1 x 2 ≥ 0
的图解如右图所示。三个约束对应的松弛变量分别为x 3、x 4、x 5
；三个约束条件对应的对偶变量分别
为y 1、y 2、y 3。请填入一个或多个正确的答案于
相应的括号中。
1、这个问题的可行域为（ EFHI ）；该问题的最优解为（ F ）； （填写对应点在图中的标号）
2、这个问题的基础解为（ ABCDEFGHIJ ）；基础可行解为（ EFHI ）； （填写对应点在图中的标号）
3、G 点对应的解中，大于零的变量为（ ），等于零的变量为（ ），小于零的变量为（ ）；（填写变量名称）
4、从E 到F 的单纯形叠代，进基变量为（ ），离基变量为（ ）；（填写变量
名称）
5、 如果约束1的右边常数b 1=12稍有增加（例如，增加0.1），最优目标函数值min z
将分别会（
）。在以下三个备选答案中选择。 （稍有增加）
（不会变化） （稍有减少）
中国计量学院200 ~200 学年第 学期《 运筹学 》课程试卷（ A ）第 4 页 共 6页
四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。
五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。
a ,7 e,10 g,35
② ⑤
④ ⑥ ⑨
C,12 f,24 i,17
③ ⑦ j,34 ⑧
1、 指出项目的关键路线；（5分）
2、 求项目的完工期。（5分）
六、（10分） 求以下网络的最大流的流量（10分）；
7
② ⑤
8 4 3 10 9 8 4
① ③ ⑥ ⑧ 3 2
4 9 6
④ ⑦
Cij
