广东人事局-英国驻华大使馆

运筹学期末考试题
一． 判断题（每题两分）
1.每一个问题都用一组决策 变量（X
1
，X
2
，……，Xn）表示某一方案，一般这些变量取值
是非负不连续的。 （ ）
2.任何两个凸集的交集都是凸集。 （ ）
3.若可行域有界，线性规划问题的目标函数不一定可以在其可行域的顶点上达到最优。
( )
4.如线性规划的对偶问题无可行解，则原问题也一定无可行解。 （ ）
5.从每一空格出发一定存在和可以找到很多闭回路。 （ ）
6.表上作业法实质上就是求解运输问题的单纯形法。 （ ）
7.目标约束是指必须严格满足的等式约束和不等式约束。 （ ）
8.分支定界法可用于解纯整数或混合的整数规划问题。 （ ）
9.分支定界法比穷举法优越，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷
举法小。 （ ）
10.任一个图中，奇点的个数为奇数。 （ ）
二.选择题（每题两分）
1.线性规划问题模型是建立在哪几个隐含的重要假设基础上 （ ）
①比例性 ②可加性 ③可分性 ④确定性
A.①②③ B.①②④ C.①③④ D.①②③④
2.下列属于对偶问题基本性质的有 （ ）
①对称性 ②弱对偶性 ③无界性 ④可行解是最优解时的性质 ⑤强对偶性 ⑥互
补松弛性
A.①②④ B.②③④⑤ C.①②③④⑤ D.①②③④⑤⑥
3.下列不是目标规划的目标函数基本形式的为 （ ）
z=f(d+ +d-) z=f(d+) z=f(d-) z=f(d-)
4.下列可称为二进制变量的是 （ ）
A.决策变量 B.0—1变量 C.换入变量 D.松弛变量
5.下列不属于整数线性规划问题的解题方法有 （ ）
A.分支定界法 B.割平面解法 C.单纯形法 D.0—1型整数线性规划
6.下列哪个不属于树的性质 （ ）
A.无界性 B.有且仅有一条链 C.树中任删掉一条链，则不连通 D.边树=点数-1
三．计算题（每题七分）
1.用单纯形法解决下列线性规划问题。
max z=2X
1
+3X
2
-5X
3

X
1
+X
2
+X
3
=7
2X
1
-5X
2
+X
3
≥10
X
1
,X
2
,X
3
≥0

2.写出下列线性规划问题的对偶问题。
max z=X
1
+2X
2
+3X
3
+4X
4

-X
1
+X
2
-X
3
-3X
4
=5 ①
6X
1
+7X
2
+3X
3
-5X
4
≥8 ②
12X
1
-9X
2
-9X
3
+9X4
≤20 ③
X
1
,X
2
≥0,X
3< br>≤0,X
4
无约束
3.试用对偶单纯形法求解下列线性规划问题。
min z=X
1
+X
2

2X
1
+X
2
≥4
X
1
+7X
2
≥7
X
1
,X
2
≥0
4.用表上作业法求下表给出的运输问题的最优解。
加工厂
A
1

A
2

A
3

销量
销地
B
1
B
2
B
3

3 11
1 9
7 4
3 6
B
4

3
2
10
5
产量
10
8
5
6
7
4
9

5.用分支定界法解 max z=X
1
+X
2

X
1
+914X
2
≤5114
-2X
1
+X
2
≤13
X
1
,X
2
≥0
X
1
,X
2
整数
6.有四个工人，要指派他们分别完成4种工作， 没人做各种工作所消耗的时间如下表，问要
指派哪个人去完成哪种工作，可使总的消耗时间为最小？
工人
甲
乙
丙
丁

工种
A
15
19
26
19
B
18
23
17
21
C
21
22
16
23
D
24
18
19
17
四.建模题（每题十二分）
某商标的酒是三种等级的酒兑制而成.若这三种等级的酒每天供应量和单位成本为：
等级
Ⅰ
Ⅱ
Ⅲ
日供应量（kg） 成本（元kg）
1500
1200
1000
6
4.5
3
设该种牌号酒有三种商标（红、黄、蓝），各种商标的酒对原料酒的混合比及售价见下表。
决策者规定 ：首先必须严格按规定比例兑制各商标的酒；其次是获利最大；再次是红商标的
酒每天至少生产2000 kg，是列出数学模型。
商标 兑制要求 售价（元kg)

红
黄
蓝

Ⅲ少于10%，Ⅰ多于
50%
Ⅲ少于70%，Ⅰ多于
20%
Ⅲ少于50%，Ⅰ多于
10%
5.5
5
4.8

运筹学期末考试题
一． 判断题（每题两分）
1.每一个问题都用一组决策变量（X
1
，X
2
，……，Xn）表示某一方案，一般这些变量取值
是非负不连续的。 （ ）
2.任何两个凸集的交集都是凸集。 （ ）
3.若可行域有界，线性规划问题的目标函数不一定可以在其可行域的顶点上达到最优。
( )
4.如线性规划的对偶问题无可行解，则原问题也一定无可行解。 （ ）
5.从每一空格出发一定存在和可以找到很多闭回路。 （ ）
6.表上作业法实质上就是求解运输问题的单纯形法。 （ ）
7.目标约束是指必须严格满足的等式约束和不等式约束。 （ ）
8.分支定界法可用于解纯整数或混合的整数规划问题。 （ ）
9.分支定界法比穷举法优越，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷
举法小。 （ ）
10.任一个图中，奇点的个数为奇数。 （ ）
二.选择题（每题两分）
1.线性规划问题模型是建立在哪几个隐含的重要假设基础上 （ ）
①比例性 ②可加性 ③可分性 ④确定性
A.①②③ B.①②④ C.①③④ D.①②③④
2.下列属于对偶问题基本性质的有 （ ）
①对称性 ②弱对偶性 ③无界性 ④可行解是最优解时的性质 ⑤强对偶性 ⑥互
补松弛性
A.①②④ B.②③④⑤ C.①②③④⑤ D.①②③④⑤⑥
3.下列不是目标规划的目标函数基本形式的为 （ ）
z=f(d+ +d-) z=f(d+) z=f(d-) z=f(d-)
4.下列可称为二进制变量的是 （ ）
A.决策变量 B.0—1变量 C.换入变量 D.松弛变量
5.下列不属于整数线性规划问题的解题方法有 （ ）
A.分支定界法 B.割平面解法 C.单纯形法 D.0—1型整数线性规划
6.下列哪个不属于树的性质 （ ）
A.无界性 B.有且仅有一条链 C.树中任删掉一条链，则不连通 D.边树=点数-1
三．计算题（每题七分）
1.用单纯形法解决下列线性规划问题。
max z=2X
1
+3X
2
-5X
3

X
1
+X
2
+X
3
=7
2X
1
-5X
2
+X
3
≥10
X
1
,X
2
,X
3
≥0

2.写出下列线性规划问题的对偶问题。
max z=X
1
+2X
2
+3X
3
+4X
4

-X
1
+X
2
-X
3
-3X
4
=5 ①
6X
1
+7X
2
+3X
3
-5X
4
≥8 ②
12X
1
-9X
2
-9X
3
+9X4
≤20 ③
X
1
,X
2
≥0,X
3< br>≤0,X
4
无约束
3.试用对偶单纯形法求解下列线性规划问题。
min z=X
1
+X
2

2X
1
+X
2
≥4
X
1
+7X
2
≥7
X
1
,X
2
≥0
4.用表上作业法求下表给出的运输问题的最优解。
加工厂
A
1

A
2

A
3

销量
销地
B
1
B
2
B
3

3 11
1 9
7 4
3 6
B
4

3
2
10
5
产量
10
8
5
6
7
4
9

5.用分支定界法解 max z=X
1
+X
2

X
1
+914X
2
≤5114
-2X
1
+X
2
≤13
X
1
,X
2
≥0
X
1
,X
2
整数
6.有四个工人，要指派他们分别完成4种工作， 没人做各种工作所消耗的时间如下表，问要
指派哪个人去完成哪种工作，可使总的消耗时间为最小？
工人
甲
乙
丙
丁

工种
A
15
19
26
19
B
18
23
17
21
C
21
22
16
23
D
24
18
19
17
四.建模题（每题十二分）
某商标的酒是三种等级的酒兑制而成.若这三种等级的酒每天供应量和单位成本为：
等级
Ⅰ
Ⅱ
Ⅲ
日供应量（kg） 成本（元kg）
1500
1200
1000
6
4.5
3
设该种牌号酒有三种商标（红、黄、蓝），各种商标的酒对原料酒的混合比及售价见下表。
决策者规定 ：首先必须严格按规定比例兑制各商标的酒；其次是获利最大；再次是红商标的
酒每天至少生产2000 kg，是列出数学模型。
商标 兑制要求 售价（元kg)

红
黄
蓝

Ⅲ少于10%，Ⅰ多于
50%
Ⅲ少于70%，Ⅰ多于
20%
Ⅲ少于50%，Ⅰ多于
10%
5.5
5
4.8