交大运筹学2套往年试卷及答案包含各题型期末考试绝对有用.doc

北 京 交 通 大 学 考 试 试 题 答 案（A卷）——运筹学A

一、单选题

5分，每题1分。
二
1．设甲、乙产品的产量分别为x1，x2件，线性规划模型为：
max z=3x1+2x2
s.t. 2x1+4x2£160
3x1+2x2£180
x1 , x2³0
标准型及单纯形计算如下：
max z=3x1+2x2
s.t. 2x1+4x2+x3=160
3x1+2x2+x4=180
x1 , x2, x3, x4³60

XB
B-1b
x1
x2
x3
x4
x3
x4
160
180
2
3
4*
2
1
0
0
1

0
3
2
0
0
X3
X1
40
60
0
1
8/3
2/3
1
0
-2/3
1/3

-180
0
0
0
-1
x2
x1
15
50
0
1
1
0
3/8
-1/4
-1/4
1/2

-180
0
0
0
-1
最优方案为甲生产50件，乙生产15件，或甲生产60件，乙生产0件，或上述两种方式的凸组合。最大利润为180。
15分，模型5分，标准型与初始表5分，计算3分，结论2分。
2．影子价格分别为0和1
4分，各2分，计算错误扣1分。
3．产品丙的检验数为－1，不值得生产。
5分，公式2分，计算2分，结论1分。
4．原料B的灵敏度范围0-240，最多应购买60千克。
6分，公式2分，计算3分，结论1分。

三、（15分）

B1
B2
B3
虚拟

A1
6
4
6
0
300
A2
6
M
5
0
300

150
150
200
100

①正确列出运价表如右：7分
②最小元素法方案3分

B1
B2
B3
虚拟

A1
50
150
×
100
300
A2
100
×
200
×
300

150
150
200
100

③位势法求检验数4分
④给出正确的调运方案1分

B1
B2
B3
虚拟

A1

+1

300
A2

M-4

0
300

150
150
200
100

四、（10分）分配甲、乙、丙三个人去完成A、B、C、D四项任务，每个人完成各项任务的时间如表所示。其中任务D必须完成，且每个人只能完成一项任务，每项任务只能由一个人完成。试确定最优分配方案，使完成任务的总时间最少。
①正确列出效益表如右：5分
②匈牙利法计算结果3分
③给出正确的分配方案2分
任务
人
A
B
C
D
甲
20
28
30
41
乙
35
39
26
20
丙
30
27
28
40
虚拟
0
0
0
M

1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0

0
8
10
21
15
19
6
0
3
0
1
13
0
0
0
M

第五题
定义状态：s1=x1+s2 s2=x2+s3 s3=x3 故 s1<=8（3分）
k=3时f3(s3)=Max {4*x3} ，此时 0<=x3<=s3
即x3=s3时 f3(s3)=4＊s3（3分）
k=2时f2(s2)=Max {3*x2+f3(s3)}= Max {3*x2+4*(s2-x2)} 0<=x2<=s2
即x2=0时 f2(s2)=4＊s2（3分）
k=3时f1(s1)=Max {x1*x1+ f2(s2)}=Max{x1*x1-4*x1+4*s1} ，此时 0<=x1<=s1
由于s1<=8，故x1=s1＝8时 f1(s1)=64（3分）
因此，x1=8, x2=0, x3=0时z取得最大值，最大值为64。（3分）

第六题
用最小数问题求解（3分）。理由：将各区域作为点，各区域间的连线作为边，不可以包含圈，目标位所修路纵长最短，最短路问题能解决这一种问题。（2分）
用避圈法求解可得1－5－4, 2－3－8－7－6为最佳修路方案，总长5.2. （5分）

第七题

（6分）
工序
最早可以开工时间
最晚必须完工时间
A
0
5
B
0
4
C
5
12
D
5
7
E
2
7
F
7
14
G
7
14
H
7
10
I
10
14
（5分）
关键工序：A-D-H-I（3分），总工期14（1分）。

北 京 交 通 大 学 考 试 试 题（A卷）
专业： 班级： 学号： 姓名：
课程名称：管理运筹学（A）2006—2007学年第2学期 出题教师：丁静之
题号
一
二
三
四
五
六
七
总分
得分

签字

一、 单选题（每题2分，共10分，答案一律写在答题纸上，否则无效）。
1. 存贮论研究对象包括（ ）。A
A．订货时间和订货数量 B．订货数量和订货人员
C．订货品种和订货数量 D．订货人员和订货费用

2. 下列有关图解评审法（GERT）说法正确的是（ ）。D
A．GERT适用于确定型网络计划 B．GERT中不包含回路
C．GERT中各事项有严格的时间先后关系 D．GERT只有一个总开工事项

3. 经济订购批量＝（2×单次订货费×单位时间需求量／单位时间单位数量物资存贮费）1／2，这一结论的产生基于一定的假设，这些假设不包括（ ）。C
A．不允许缺货 B．存储费率不变
C．以特定的速度生产来补充库存 D．需求是连续均匀的

4. 存贮论模型可按不同方式进行分类，但一般不包括（ ）。B
A．确定型存贮模型与随机型存贮模型 B．简单存贮模型与复杂存贮模型
C．单品种存贮模型与多品种存贮模型 D．单周期存贮模型与多周期存贮模型

5.下列说法正确的是（ ）。D
A．动态规划求解的问题可以无后效性，也可以有后效性。
B．图论中，最大流问题实质是一种非线性规划问题。
C．割平面解法可以求解纯整数规划问题，也可以求解混合整数规划问题。
D．线性规划中，当约束条件系数矩阵中不含有单位矩阵时，可以采用大M法求解，也可以采用两阶段法求解，但求解结果一定是相同的。

二、（共30分）某厂用A、B两种原料生产甲、乙两种产品，生产消耗参数如下。根据生产安排，甲产品每天至少生产3吨，乙产品每天至少生产1吨。两种原料都需要采购，每吨A原料需2万元，每吨B原料需3万元。每吨A原料可生产1吨甲产品和2吨乙产品，1吨B原料和1吨乙产品可生产2吨甲产品。
产品
原料
甲
（吨）
乙
（吨）
采购费
（万元／吨）
A
1
2
2
B
2
－1
3
产量（吨）
3
1

（1）如何安排两种原料采购（采购的材料都用于生产），使该厂采购总额最小？请建立线性规划模型并用图解法求解；
（2）请用对偶单纯形法求解上述模型并指出最小采购总额时两种原料采购数量。
（3）假设市场上原料C的价格为4万元／吨，每吨C原料可生产2吨甲产品和2吨乙产品。是否应采购C原料？请说明理由。

三、（共10分）已知某运输问题的产销平衡表如下。产量和销量单位均为：件；运价单位为：元/件。
销地
单位运价
产地
B1
B2
B3
产量
A1
A2
8
7
4
5
6
5
22
30
销量（件）
25
15
20

（1）用最小元素法求出初始调运方案？
（2）位势法进行检验，并找到最优运输方案。

四、（共10分）派五人去做五项工作，各人做各项工作的能力评分见表。如何分派，总的得分最大？
评分 工作
人员
B
B
B
B
B
A
1.3
0.8
0
0
1.0
A
0
1.2
1.3
1.3
0
A
1.0
0
0
1.2
0
A
0
1.05
0
0.2
1.4
A
1.0
0.9
0.6
0
1.1

五、（共15分）现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位为百万元）。其中2#项目的投资不得超过3百万元，1#和3#项目的投资均不得超过4百万元，3#项目至少要投资1百万元。每个项目投资五年后，预计可获得的收益如下表所示。如何投资可望获得最大收益？请用动态规划方法求解。
投资额
项目
0
1
2
3
4
5
1#
0
3
6
10
12
－
2#
0
5
10
12
－
－
3#
－
4
8
11
15
18

六、（共15分）某高校在某地区有五个不同的校区，包括一个主校区和四个分校区。学校决定在各校区之间铺设光缆以形成校园网。主校区与各分校区之间都要保持光缆连接畅通。四个分校区之间距离较近，可以直接铺设光缆。但主校区与四个分校区距离较远。学校请示相关主管部门后得知，主校区可通过四个中转点铺设光缆然后与分校区2相连接，进而再与其它三个分校区保持连接。各校区、各中转点之间的距离如下图所示，单位为公里。没有线条相连接的节点之间不能铺设光缆。为使所消耗的光缆总长度最小，请用图论的知识指出最优铺设方案并说明理由。至少需要多少公里长度的光缆？

七、（共10分）某工程项目的工序清单如下（工时单位：天）：
工序代号
紧前工序
工时
工序代号
紧前工序
工时
A
B
C
D
E
—
—
A
A
B
15
12
12
12
13
F
G
H
I
C
D,E
D,E
H
12
15
13
14
（1）绘制双代号网络图；
（2）计算工序的最早可能开始时间和最迟必须完成时间；
（3）指出关键工序和总工期。
（4）要将总工期压缩2天，应该如何做？

2007年本科试题（A）——64学时
A卷

一、选择题。每题2分，共10分。 ADCBD
二、
（1）设A原料采购量为x1, B原料采购量为x2。模型如下（8分）：
Min Z= 2 X1+3X2
X1+2X2≥3
2X1- X2≥1
X1,X2≥0
图解法（7分）可知：X1＝1，X2＝2，此时 Z取得最小值，最小值为5。即采购A、B原料各1套，最小采购额为5万元。

（2）（10分）上述模型可化为:
Max W= －2 X1－3X2
－X1－2X2＋X3 ＝－3
－2X1＋ X2 ＋X4＝－1
X1,X2，X3,X4≥0

－2
－3
0
0
CB
XB
b
X1
X2
X3
X4
0
X3
－3
－1
－2
1
0
0
X4
－1
－2
1
0
1

－2
－3
0
0
－3
X2
3／2
1／2
1
－1／2
0
0
X4
－5／2
－5／2
0
1／2
1

－1／2
0
－3／2
0
－3
X2
1
0
1
－2／5
1／5
－2
X1
1
1
0
－1／5
－2／5

0
0
－8／5
－1／5
最优解为X1＝1，X2＝2，此时 Z取得最小值，最小值为5。
（3）（5分）设C原料的采购量为X5，则P5＝（－2，－2）T
C5＝－4 CB＝（－3，－2） B－1＝
Ô5 ＝ C5－CB B－1 P5＝－2／5 <0 故不应该采购C原料。

加入一个虚设的产地，转化为供需平衡的运输问题，有虚设的产地到销地的运费为在各销地寻找货源所多花的费用。供需平衡表如下。（4分）

B1
B2
B3
产量（件）
A1
8
4
6
22
A2
7
5
5
30
A3
1
2
2
8
销量（件）
25
15
20
60
用最小元素发法求的初始运输方案。（2分）

B1
B2
B3
产量（件）
A1
7
15

22
A2
10

20
30
A3
8

8
销量（件）
25
15
20
60
上述方案的位势法检验。 位势表

B1
B2
B3
vj
A1
8
4

8
A2
7

5
7
A3
1

1
ui
0
-4
-2

检验数表（2分）

B1
B2
B3
vj
A1

0
8
A2

2

7
A3

5
3
1
ui
0
-4
-2

由检验数可知，上述方案是最优运输方案。
（2分）即由A1运往B1： 7件，运往B2：15件；
A2运往B1： 10件，运往B3：20件；
B1有8件的需求尚未满足，需要在当地寻找货源。
总运费56+70+60+100=286元

四、原效益矩阵
转化成最小问题（2分）
划线覆盖全部的零元素（2分）

调整（2分） 分派（2分）

（2分）最优分配方案：A1-B1,A2-B3,A3-B4
A4-B5,A5-B2, 最大的得分：1.3+1.3+1.2+1.5+0.9=6.2

五、（6分）按投资项目划分3个阶段，sk表示从k阶段到第三阶段可以用于投资的资金，xk为第k个项目的投资金额。则状态转移方程为，基本方程为：

（2分）k=3
x3
s3
g3(x3)
f3(s3)
x3
1
2
3
4
1
2
3
4
5
4

8

11

15
15
4
8
11
15
15
1
2
3
4
4

（2分）k=2
x2
s2
g2(x2)+ f3(s3)
f2(s2)
x2
0
1
2
3
1
2
3
4
5
0+4
0+8
0+11
0+15
0+15

5+4
5+8
5+11
5+15

10+4
10+8
10+11

12+4
12+8
4
9
14
18
21
0
1
2
2
2

（2分）k=1
x1
s1
g1(x1)+ f2(s2)
f1(s1)
x1
0
1
2
3
4
5
0+21
3+18
6+14
10+9
12+4
21
0,1

（3分）最优方案两个：项目1不投资，项目投资2百万，项目3投资3百万；项目1投资1百万，项目投资2百万，项目3投资2百万；最大收益为21。

六、解题思路（5分）：要保持主校区与各分校区之间光缆的畅通，必须使得这五个节点之间保持连通。图中，主校区与分校区2之间距离较远，其中可通过几个中转点进行连接，但这些中转点不是必须都纳入保持连通。因此，可将四个分校区作为一部分（四个分校区作为四个点，它们相互间的连线作为边，各边的距离作为该边的权），求它们的最小树。然后将主校区、分校区2和四个中转点作为一部分（主校区、分校区2和四个中转点作为六个点，它们相互间的连线作为边，各边的距离作为该边的权），求主校区到分校区2的最短路。最小树、最短路中所包含的边即为铺光缆的路径，最小树的权与最短路长之和为光缆的总长度。

（4分）V0至V2间的最短路为：V 0——V 6——V 8——V2，路长为85公里。

（4分）最小树为：V1V2，V2V3，V1V4，权为6公里。
（2分）所以光缆铺设路径为：主校区——中转站2——中转站4——分校区2——分校区1——分校区4和分校区2——分校区3，共需要光缆91公里。

七、（1）（5分）
1
3
2
B
A
5
C
D
E
4
F
G
H
6
7
15
12
12
12
13
12
15
13
I
14

（2）（2分）
工序代号
ES
LF
工序代号
ES
LF
A
B
C
D
E
0
0
15
15
12
15
14
42
27
27
F
G
H
I
27
27
27
40
54
54
40
54

（3）（2分）关键工序A、D、H、I，总工期是54天。
（4）（1分）应在关键工序上压缩2天。

第 14 页 共 14 页