PAGE2/NUMPAGES4
《运筹学》期末试卷1
学号姓名得分
得分
一、(2’×6)选择题：
互为对偶的两个线性规划问题的解存在关系（）
A．原问题无可行解，对偶问题也无可行解
B．对偶问题有可行解，原问题可能无可行解
C．若最优解存在，则最优解相同
D．一个问题无可行解，则另一个问题具有无界解
设线性规划的约束条件，则基本解为（）
A.(0,2,3,2)B.(3,0,,0)C.(0,0,6,5)D.(2,0,1,2)
对偶单纯形法求解最大化线性规划问题时，每次迭代都要求单纯形表中（）
A.列元素不小于零 B.检验数都大于零
C.检验数都不小于零 D.检验数都不大于零
，且为整数，其对应的线性规划最优解是（3.25,2.5），它的整数规划最优解是（）
A.（3,2）B.（4,3）C.（4,1）D.（2,4）
以下各序列哪个能构成某个简单图的各顶点的次的序列（）
A.1，1，2，3，2
B.1，3，2，3，2
C.1，1，2，2，2
D.1，1，2，3，5
设活动的作业时间为，总时差为，节点的最早时间为和，最迟结束时间为和，下列关系式正确的是（）
A.B.
C.D.
得分
二、(2’×6)填空题：
有4个产地5个销地的平衡运输问题，它的基变量有个。
在图中，所有点的次之和是边数的倍。
给一个图，如果图，使及，则称是的一个。
动态规划是解决最优化问题的一种理论和方法。
在分枝定界法中，若选进行分支，则构造的约束条件应为
。
在网络计划中，工序的单时差是指
。
得分
三、(14’)已知下述线性规划问题：
最优解中的基变量为，且已知
请根据上述信息确定三种资源各自的影子价格。
得分
四、(12’)已知运输问题的产销平衡表、单位运价表及最优调运方案如下。
产销平衡表
销地
产地
产量
5
10
15
0
10
15
25
5
5
销量
5
15
15
10
单位运价表
销地
产地
10
1
20
11
12
7
9
20
2
14
16
18
请问从的单位运价在什么范围变化时，上述最优调运方案不变？
得分
五、(12’)某风景区有6个海岛，相互间的距离如下表（单位：哩）。现欲架设海上浮桥，使各岛相连且与陆地相连。已知第1个海岛离海岸最近，为0.3哩，求使架设浮桥长度最短的方案。
2
3
4
5
6
1
1.0
3.0
2.5
5.0
4.0
2
2.6
1.7
4.2
3.2
3
1.0
2.5
1.3
4
2.6
1.8
5
1.3
得分
六、(12’)有甲、乙、丙、丁四人和A、B、C、D、E五项任务，每人完成任务的时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，请确定总时间最少的指派方案。
A
B
C
D
E
甲
15
19
21
32
27
乙
29
28
16
10
23
丙
24
17
18
30
22
丁
14
32
26
13
35
得分
七、(14’)如图所示网络中，有向边旁数字为，表示容量，表示单位流量费用，试求从到的最小费用最大流。请写出最大流量和相应的最小费用。
v
v1
v2
v3
v4
vs
vt
(3,2)
(6,5)
(4,3)
(5,4)
(4,1)
(3,3)
(3,1)
(7,1)
得分
八、(12’)现有某工程的计划网络图如下，括号内数字代表（紧急工期，正常工期，费用率）。
(1) 求正常情况下的总工期；
(2) 如上级要求总工期缩短2天，试求最小追加费用的优化方案，指出缩短工期后的关键路线；
(3) 如上级要求总工期缩短5天，试求最小追加费用的优化方案，指出缩短工期后的关键路线。
1
1
3
2
4
5
(2,3,2)
(2,5,0.5)
(2,5,1)
(4,7,2)
(3,6,0.5)
(5,10,2)
《运筹学》期末试卷1答案
得分
一、(2’×6)选择题：
1.B2.B3.D4.C5.C6.A
得分
二、(2’×6)填空题：
1.82.