ljz 运筹学复习题集.docx
《ljz 运筹学复习题集.docx》由会员分享，可在线阅读，更多相关《ljz 运筹学复习题集.docx（14页珍藏版）》请在冰点文库上搜索。
ljz运筹学复习题集
运筹学复习题
1.某一求目标函数极大值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下：
XB
b
X1
X2
X3
X4
X5
X6
X2
X3
X5
ª1
4
10
0
2
a3
1
0
0
0
1
0
0
a4
4
0
0
1
a2
2
3
Cj－Zj
a5
0
0
a6
0
-6
当现行解为唯一最优解时有D。
A.ª1≥0a5＞0a3＞0B.a3≥0a5＝0a6＝0
C.ª2＝0a5≥0a6≥0D.a1≥0a6＜0a5＜0
2.单纯形乘子是指A。
A．
B.
C.
D.
3．在满足下列条件B时，增加资源是有利的。
A．单位资源代价大于资源的影子价格
B．单位资源代价小于资源的影子价格
C．单位资源代价等于资源的影子价格
D．单位资源代价不等于资源的影子价格
4．线性规划的灵敏度分析应在B的基础上，分析系数的变化对最优解产生的影响。
A．初始单纯形表B.最优单纯形表
C.对偶问题初始单纯形表D.对偶问题的最优单纯形表
5．一个图G中,奇点的个数为B。
A.偶奇数B.偶数C.奇数或偶数D.不能确定
6．若运输问题已求得最优解，此时所求出的检验数一定是全部A。
A．大于或等于零B．大于零C．小于零D．小于或等于零
7.线性规划一般模型中，自由变量可以用两个非负变量的B代换。
A．和B．差C．积D．商
8．目标规划中，对于优先级别，则下列说法正确的是C。
A．Pk×Pk+1=0B．Pk<>Pk+1D．Pk=Pk+1
9．求解指派问题的匈牙利方法要求系数矩阵中每个元素都是A。
A．非负的B．大于零C．无约束D．非零常数
10．若运输网络G中发点到收点不存在流f的增广链，则称流f为G的C。
A．最小流B．零流C．最大流D．无法确定
11.运输问题中，闭合回路的数字格分布在每行每列的个数必定为 B 。
A.1B.2C.3D.4
12.目标规划中，以下式子正确的为D。
A.d+≥0,d-≤0B.d+×d-＜0
C.d+×d-＞0 D.d+×d-＝0
13线性规划的原问题与其对偶问题之间关系不存在的是C；
A.对偶问题的对偶问题是原问题；
B.原问题存在最优解，其对偶问题必存在最优解；
C.原问题无可行解，其对偶问题必无可行解；
D.原问题有无界解，其对偶问题无可行解。
14求解整数规划常用的算法有B。
A.单纯形法和分枝定界法B.分枝定界法和割平面法
C.单纯形法和割平面法D.单纯形法和完全枚举法
15含有n个顶点的完全图，其边数有C条。
A.n2B.2nC.
D.2n（n-1）
16用割平面法求解整数规划时，构造的割平面只能切去C。
A．整数可行解B．整数解最优解C．非整数解D．无法确定
1.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。
（√）
2.如果线性规划问题存在最优解，则最优解点不一定在可行域边界上。
（×）
3.单纯形法计算中，如果不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。
（√）
4.可以采用避圈法和破圈法求解网络中的最短路问题。
（√）
5.所有顶点次数之和等于所有边数的2倍。
（√）
6.树图的任意两个顶点间有且只有有一条连通路。
（√）
7.对可行流来说，发点的净流出量,等于收点的净流入量。
（√）
8.割平面法每次切割的都是原问题的非可行整数解。
（√）
9.可以采用避圈法和破圈法求解网络中的最短路问题。
（√）
10.目标规划中的优先因子P1，P2…，Pk中，必定有P1>>P2,…，Pk>>Pk+1,…。
（√）
1.已知A、B、C、D四项任务分别由甲、乙、丙、丁四个人去完成，每人最多承担一项工作，每项工作只能由一个人单独完成。
由于各人的专长不同，他们完成各项任务的时间（h）不相同（如下表），现问该如何分配才能使得四个人完成这四项任务总的时间为最少。
（写出计算过程及最终答案）（8分）
人
任务
甲
乙
丙
丁
A
2
10
9
7
B
15
4
14
8
C
13
14
16
11
D
4
15
13
9
2.已知运输的产销平衡表和单位运价表如下，试采用表上作业法确定运费最少的最佳运输方案，并求出最少费用。
（10分）产销平衡表单位：
t
销地
产地
B1
B2
B3
B4
产量
A1
7
A2
4
A3
9
销量
3
6
5
6
单位运价表单位：
元/t
销地
产地
B1
B2
B3
B4
A1
3
11
3
10
A2
1
9
2
8
A3
7
4
10
5
3.用单纯形表上作业法求解下列线性规划。
写出下列线性规划问题的对偶问题。
（8分）
（1）用闭回路法求检验数（表5-55）
表5-55
B1
B2
B3
B4
Ai
A1
10
5
2
3
70
A2
4
3
1
2
80
A3
5
6
4
4
30
bj
60
60
40
20
（2）用位势法求检验数（表5-56）
表5-56
B1
B2
B3
B4
Ai
A1
9
15
4
8
10
A2
3
1
7
6
30
A3
2
10
13
4
20
A4
4
5
8
3
43
bj
20
15
50
15
某机械厂计划生产甲、乙两种产品，分别在A、B、C三种设备上加工，已知各设备加工不同产品所需的时间和机器的生产能力及其利润情况如下表：
甲
乙
机器生产能力（小时）
A
2
2
12
B
4
0
16
C
0
5
15
利润（元/件）
2
3
该机械厂经营的目标如下：
（1）力求使利润不低于15元；
（2）甲、乙两种产品的常量需保持1：
2的比例；
（3）A为贵重设备，严格禁止超时使用；
（4）设备C可以适当加班，但是要控制；设备B既要充分利用，又尽可能不加班。
且设备的重要性上B是C的3倍。
试建立该问题的目标规划模型。
求下列运输问题的最优解
（1）C1目标函数求最小值；
（2）C2目标函数求最大值
1545204060305040
求解下列最小值的指派问题，其中第
（2）题某人要作两项工作，其余3人每人做一项工作．
（1）
【解】最优解
（2）
【解】虚拟一个人，其效率取4人中最好的，构造效率表为
1
2
3
4
5
甲
26
38
41
52
27
乙
25
33
44
59
21
丙
20
30
47
56
25
丁
22
31
45
53
20
戊
20
30
41
52
20
最优解：
甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165
最优分配方案：
甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9求解下列最大值的指派问题：
（1）
【解】最优解
（2）
【解】最优解
第5人不安排工作。
已知A、B、C、D四项任务分别由甲、乙、丙、丁、戊五个人去完成，每人最多承担一项工作，每项工作只能由一个人来完成。
因各人的专长不同，他们完成各项任务的时间（h）不相同（如下表）。
由于某种原因，丁不愿承担D任务。
现问该如何分配才能使得完成这四项任务总的时间为最少。
（写出计算过程及最终答案）
人
任务
甲
乙
丙
丁
戊
A
10
2
3
15
9
B
5
10
15
2
4
C
15
5
14
7
15
D
20
15
13
6
8
单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的哪一个极点．
用单纯形法求解下列线性规划
网络最短路问题。
求解下列网络图中V1点到V7点之间的最短距离。
要求有求解过程，并将最终路线标示在图上。
如下图所示，给定一个出租汽车的行驶线路网格，两点连线上的数字表示两点间的距离（或费用），试求由A到E的最佳行驶线路，使其距离（运输总费用）最小。
用大M法求解下列线性规划：
求解对偶问题：
求下列运输问题的最优解
（1）C1目标函数求最小值；
（2）C2目标函数求最大值
1545204060305040
求最小部分树。
（a）用破圈法,（b）用生成树法。
6.5某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。
根据勘测，10个村之间修建公路的费用如表6-20所示。
乡镇府如何选择修建公路的路线使总成本最低。
表6-20
两村庄之间修建公路的费用（万元）
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
12.8
10.5
9.6
8.5
7.7
13.8
12.7
13.1
12.6
11.4
13.9
11.2
8.6
7.5
8.3
14.8
15.7
8.5
9.6
8.9
8.0
13.2
12.4
10.5
9.3
8.8
12.7
14.8
12.7
13.6
15.8
9.8
8.2
11.7
13.6
9.7
8.9
10.5
13.4
14.6
9.1
10.5
12.6
8.9
8.8
【解】属于最小树问题。
6.6在图6－42中，求A到H、I的最短路及最短路长。
图6－42
求v1到v10的最大流及最大流量；
升级会员 