运筹学试题库(试卷3).doc
《运筹学试题库(试卷3).doc》由会员分享，可在线阅读，更多相关《运筹学试题库(试卷3).doc（4页珍藏版）》请在冰点文库上搜索。
运筹学试题库（试卷3）
一、填空题：
（10分）
1、在图论中，图的基本要素有两个，它们是和。
2、结点的最早开始时间和时间是同一时间，最早开始是对结点的后接工序而言，
是对结点的紧前工序而言。
3、对需要量供应量的运输问题，求最优解时要先一个供应点。
4、关键路线是从起点到终点所有路中的最路，它的线路时差为。
5、在图论中，为了表示两个队比赛的胜负关系可以用一条带的来表示。
二、选择题（10分）
1、若T是图G的最小支撑树，则（）
A．T必唯一B.G不一定是连通图
C．T中必不含圈D.G中不含圈
3、在网络计划中，进行时间与成本优化时，随工期延长，间接费用将（）。
A．减少B.增加C.不变D.不易估计
4、若线性规划问题的最优解在可行域的两个顶点达到，则最优解（）。
A．有两个B.有无穷多个C.过这两点的直线D.不可能发生
5、在n个产地，m个销地的产销平衡运输问题中，（）是错误的。
A．运输问题是线性规划问题
B．基变量的个数是数字格的个数
C．空格有mn-n-m+1个
D．每一格在运输图中均有一闭合回路
三、判断题（10分）1、用单纯形法求解标准型式的线性规划问题时，与>0对应的变量都可以被选作换入变量。
（）2、对偶问题的对偶一定是原问题。
（）
3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。
（）
4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。
（）
5、求网络最大流的问题可归结为求解一个线性规划模型。
（）
四、规划问题（16分）
已知线性规划问题
（1）写出其对偶问题；
（2）用图解法求对偶问题的解；
（3）利用
（2）的结果及对偶性质求原问题解。
五、运输问题（10分）
某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。
产地销地
B1
B2
B3
B4
产量
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
销量
3
6
5
6
六、支撑树问题（6分）
求下面网络图的最小支撑树：
七、指派问题（10分）
分配甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。
人任务
A
B
C
D
E
甲
12
7
9
7
9
乙
8
9
6
6
6
丙
7
17
12
14
9
丁
15
14
6
6
10
戊
4
10
7
10
9
八、网络最大流问题（10分）
求下图所示容量网络中从～的最大流。
其中每边上的数为。
九、指派问题
有三台设备，可用于五项不同的工程。
但由于设备数有限，只能分给其中的三项工程。
下表给出了不同的工程得到设备后所创的利润，试用匈牙利法确定使总利润最大的设备
分配方案（单位：
万元）。
利润工程
设备
B1
B2
B3
B4
B5
A1
3
7
2
9
11
A2
6
8
10
7
5
A3
9
4
12
5
6
十．动态规划
某公司决定投资60万元（以10万元为单位），以提高三种主要产品A、B、C的产量。
现决定每种产品至少要投资10万元。
各种产品投资不同资金后可获得的期望利润如下：
分配的
投资金额
利润
产品A
产品B
产品C
10
14.5
16.2
15.9
20
16.4
18.4
18.4
30
18.0
19.9
22.6
40
19.6
24.1
24.2
试确定如何安排对各种产品的投资数，可获得最大总期望利润？
十一．整数规划
某公司拟建立4个超市，可选的地址有A、B、C三处。
在不同地址设置不同数量的超市后，每个月的营业利润如下表所示（单位：
万元）：
超市数
地址
1
2
3
4
A
16
20
30
32
B
12
15
20
24
C
10
13
16
17
问这些超市应如何分布，可使公司总的营业利润最高。
十二．指派问题：
用匈牙利算法求解下述指派问题，已知效率矩阵分别如下：
（a）（b）
十三．分配甲、乙、丙、丁四个人去完成五项任务。
每人完成任务的时间如表所示。
由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项。
试确定总花费时间为最少的指派方案。
任务
人
A
B
C
D
E
甲
25
29
31
42
37
乙
39
38
26
20
33
丙
34
27
28
40
32
丁
24
42
36
23
45
十四．求下图的最小生成树和最大生成树：
V16V2
6622
V67V73V3
8343
V51V4
十五．求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。
A
B2
B1
C3
C2
C1
D1
D2
E
5
8
9
6
4
3
5
7
7
10
8
6
9
11
3
5
升级会员 