PAGE7/NUMPAGES7
《运筹学》期末试卷2答案
得分
一、(2’×6)选择题：
1.A2.C3.D4.C5.D6.C
得分
二、(2’×6)填空题：
1.（0,2）2.03.n+14.多阶段决策5.伏格尔法6.0
得分
三、(12’)考虑线性规划问题：
这里是一个正数。假定给约束条件加上松弛变量使得问题转化为标准形式。
考虑以为基变量的基本解，证明其为基本可行解。
证明（1）中定义的基本解是最优的。
(已知)
解：(1)以为基变量，由约束条件可以得到：
,,,
因此，该基本解是基本可行解。
(2)利用最优性条件，若则为最优解。这里，
，
，，
所以，。
得分
四、(10’)某企业拟生产三种产品，每种产品的单位劳动力和原材料需求量如下：
产品
劳动力（小时/件）
原材料（公斤/件）
1
3
4
2
4
3
3
5
6
三种产品的利润分别为25元/件，30元/件，22元/件。现该企业可在如下两处厂址选择一处，两地的主要区别在于劳动力和原材料的供给能力不同（见下表）。
厂址
可提供的劳动力（小时）
可提供的原材料（公斤）
1
100
100
2
90
120
此外，由于生产机器的特殊性，如果产品3被生产，则其产量不得低于3件。请问该企业应在何处建厂以使总利润最大（建立适当的数学规划模型，不必求解）。
解：设分别为产品1,2,3的生产量，M是一个很大的正数，并引入0-1变量
,
max
s.t.
,
得分
五、(12’)现要在5个工人中确定4个人来分别完成4项工作中的一项。由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项工作所需工时如下表。
工作
工人
A
B
C
D
I
9
4
3
7
II
4
6
5
6
III
5
4
7
5
IV
7
5
2
3
V
10
6
7
4
试找出一个工作分配方案，使总工时最小。
解：本题属于“不平衡”指派问题，故先虚拟一项工作E，设每人完成E所用的时间都是“0”，从而转化为5个人完成5项工作的平衡指派问题。再用匈牙利法求解，得最优解为：I—C，II—A，III—B，IV—D，V—E，即应安排工人I、II、III、IV分别完成工作C、A、B、D，此时总工时最小为3+4+4+3=14。
得分
六、(10’)假设有9个城市之间要架设电缆，已知城市之间的可行线路和费用如下图所示：
v2v88
v2
v8
8
v3
2
5
62754
6
2
7
5
4
v7
v77
5
v1v6
v1
v6
3
3
1334
1
3
3
4
1
1
v5v
v5
v9
v4
41
4
1
试问：
要将所有城市连通，至少需要几条连接边？
试求一个费用最小的架设方案。
解：1）要将所有城市连通，至少需要8条连接边。
2）即求最小支撑树，最小费用为17。
113
1
1
3
4
2
2
3
1
得分
七、(12’)如图给出的是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力。现要求制定一个运输方案，使得从运到的产品数量最多，指出该网络的最大流量和最小割集。
5139
5
13
9
4
6
5
6
4
4
9
10
5
解：用标号法得到的最终结果为：
13(11)9(9)
13(11)
9(9)
4(0)
5(5)
6(6)
5(4)
6(4)
4(3)
4(3)
9(9)
10(8)
5(5)
因此，该网络的最大流量为20，最小割集为。
得分
八、(12’)一项小修计划包括的工作如下表所示。
工作
网络说明
最少工时（d）
正常工时（d）
成本斜率（元）
A
(1,2)
6
9
20
B
(1,3)
5
8
25
C
(1,4)
10
15
30
D
(2,4)
3
5
10
E
(3,4)
6
9
15
F
(4,5)
1
2
40
正常计划工期与最小工期各是多少天？
日常经营费为50元/天，最佳工期应是多少天？列出每项工作的相应工时。
解：
1
1
3
2
4
5
A
B
D
C
E
F
(6,9,20)
(10,15,30)
(5,8,25)
(3,5,10)
(6,9,15)
(1,2,40)
关键路径：1?3?4?5工期19天。首先选择工作E压缩（费用15），可压缩2天。
此时，关键路径为2条：1?4?5和1?3?4?5工期17天。首先选择工作F压缩（费用40），可压缩1天；再选择工作C，E同时压缩（费用45），可压缩1天。
此时，关键路径为3条：1?2?4?5,?4?5和1?3?4?5工期15天。不能继续压缩，因为无论怎样选择都超过了日常经营费为50元/天。
所以，（1）正