运筹学大纲.doc

目录

I 考查目标 2
II 考试形式和试卷结构 2
III 考查内容 2
IV. 题型示例及参考答案 3
全国硕士研究生入学统一考试
运筹学考试大纲

I 考查目标
全国硕士研究生入学统一考试《运筹学》考试是为我校招收管理类硕士生而设置的具有选拔性质的考试科目。其目的是科学、公平、有效地测试考生是否具备攻读管理类硕士所必须的基本素质、一般能力和培养潜能，以利用选拔具有发展潜力的优秀人才入学，为国家的经济建设培养具有良好职业道德、法制观念和国际视野、具有较强分析与解决实际问题能力的高层次、应用型、复合型的管理人才。考试要求考生掌握运筹学的基本理论、思想和方法，学会建立简单的运筹学模型，运用运筹学的方法和技巧，为经济、管理问题提供科学的决策方案。要求考生具有综合处理经济管理中定量分析方面问题的能力。
具体来说，要求考生：
1．理解线性规划问题的解的概念，了解线性规划的基本理论，熟练掌握单纯形法求解线性规划问题。
2．理解对偶问题、影子价格；掌握对偶问题解与原问题解之间的关系。
3．理解运输问题的求解原理；掌握运输问题的求解方法。
4．掌握目标规划的建模及其求解方法。
5．理解动态规划基本概念及基本原理；掌握动态规划问题基本求解方法及典型应用问题的求解方法。
6．理解图的基本概念及基本理论；会将实际问题用图的语言表示出来并加以解决；熟悉最小树的求法，熟悉网络最大流的求法；熟悉最短路问题的解法；了解最小费用-最大流问题；了解中国邮递员问题。
7．熟悉存储论的基本理论和方法，掌握循环策略模型、报童模型、（s，S）模型的求解方法。
II 考试形式和试卷结构
一、 试卷满分及考试时间
试卷满分为150分，考试时间180分钟。
二、 答题方式
答题方式为闭卷、笔试。允许使用计算器，但不得使用带有文本存储功能的计算器。
三、 试卷内容与题型结构
考试题型（可能包括但不一定每考试中都出现）有建模题、填空题、判断题、简述题、计算题、证明题。以计算题为主要形式。
III 考查内容
1．运筹学概述
运筹学的内容、目的、进展与现况；运筹学的性质、特点、工作步骤及应用。
要求：了解运筹学的内容、目的、进展与现况，理解运筹学工作过程的各个步骤，理解定量和定性分析相结合解决实际问题的方法。
2．线性规划及单纯形法 
线性规划问题以及数学模型；线性规划的几何意义；单纯形法以及计算步骤；单纯形法的进一步讨论；线性规划建模以及应用。
要求：掌握线性规划数学模型的基本特征和标准形式，以及线性规划问题数学模型的建立方法，学会用图解法求解简单的线性规划问题；理解线性规划问题的解的概念，了解线性规划的基本理论；了解单纯形表的构成，熟练掌握运用单纯形法求解线性规划问题的方法；掌握人工变量法（包括大Ｍ法和两阶段法）的计算步骤。
3．线性规划对偶理论与灵敏度分析
单纯形方法的矩阵描述；线性规划对偶问题；影子价格；对偶单纯形法；线性规划灵敏度分析及其应用。
要求：理解对偶问题、影子价格；掌握对偶问题解与原问题解之间的关系，会对偶单纯形法。了解灵敏度分析的方法和意义，能针对实际问题进行灵敏度分析。
4．运输问题
运输问题的数学模型；产销平衡问题的表上作业法；产销不平衡的运输问题及其求解方法；应用举例。
要求：理解运输问题的求解原理；掌握运输问题的求解方法。
5．整数规划
整数规划的数学模型；掌握割平面法和匈牙利法。
要求：掌握整数规划的建模及其求解方法。
6．图与网络分析 
图的概念；树及最小生成树；最短路问题；网络最大流问题；最小费用-最大流问题  ；欧拉图，中国邮递员问题 ；网络计划。
要求：理解图的基本概念及基本理论；会将实际问题用图的语言表示出来并加以解决；熟悉最小生成树的求法，熟悉网络最大流的求法；熟悉最短路问题的解法；了解最小费用-最大流问题；了解中国邮递员问题。
7．存储论
存储论的基本概念；循环策略模型、报童模型、（s，S）模型的条件和结论。
要求：理解存储论的基本概念；熟悉循环策略模型、报童模型、（s，S）模型的求解。

IV. 题型示例及参考答案
一、（15分）某工厂安排某种生活必需品在以后四个月的生产计划。该产品在这四个月中均可以生产，四个月的生产成本分别为12,10,15,18（元/件）。四个月对该产品的需要量分别为400,700,900,800（件），该工厂平常每月最多能生产700件，但在第二个月可以加班，加班后可增产300件，加班增加的生产成本为3元/件。过剩产品每件每月的存储费为3元，试建立运输问题的表格模型。

二、（15分）已知线性规划问题：

的对偶问题的最优解为Y =（0,1,1），求原问题的最优解。
三、（20分）用单纯形法求解下列线性规划：

四、（15分）求下列运输问题的最优调运方案和最小费用：
运价表
B1
B2
B3
B4
产量
A1
5
5
9
12
40
A2
11
8
13
13
30
A3
15
18
16
20
30
销量
25
15
10
50

五、（16分）已知线性规划问题：

当t1 = t2 =0时，用单纯形法求得最终表如下：

要求：1.（10分）确定c1，c2，c3，b1，b2，a11，a12，a13，a21，a22，a23的值；
2.（3分）当t2＝0时，t1在什么范围内变化上述最优解不变；
3.（3分）当t1＝0时，t2在什么范围内变化上述最优基不变。
六、（15分）求解下列指派问题：

七、（20分）求下图所示网络流的最大流并给出一个最小截集（写出标号过程）：
V5
V1
Vs
V2
V3
V6
V4
Vt
(3,3)
(8,5)
(9,9)
(3,3)
(5,1)
(2,1)
(10,7)
(5,3)
(9,8)
(5,4)
(5,1)
(5,4)
(6,6)
(8,4)
(3,1)

八、（18分）某企业对某种外购件的需求速度为R=36500件/年，订货提前期为零，每次订货费
为50元。该外购件的价格为30元，年存贮费为10元/件.年。如发生供应短缺，可在下批货物
到达时补上，但缺货损失为40元/件。
1.（6分）若允许缺货，试求经济订货批量及全年的最小总费用；
2.（6分）如不允许发生缺货，重新求经济订货批量；
3.（6分）将（1）、（2）的结果进行比较，并解释理由。
九（16分）分别用破圈法和避圈法求下图的最小部分树：
V1
V3
V2
V4
V5
V6
3
4
2
3
6
2
1
1
3
3
3

参考答案
一、可建立5行4列的产销不平衡的运输问题，表格如下：
销售月份
生产月份
一月 二月 三月 四月
产量
一月正常
二月正常
三月正常
四月正常
二月加班
12 15 18 21
M 10 13 16
M M 15 18
M M M 18
M 13 16 19
700
700
700
700
300
需要量
400 700 900 800

二、解：此线性规划的对偶为：

将对偶最优解代入对偶问题的第二个约束条件，可知此约束为松的，故有：x2 = 0；
由原问题的约束条件得：
解此方程组得原问题的最优解为：x1 = 14, x2 = 0, x3 = -12 。

三、 原模型标准化并加入人工变量得如下辅助问题

对辅助问题用大M法求解如下：
CB
XB
b
-3
0
2
0
0
-M
-M
θi
X1
X2
X3
X4
X5
X6
X7
0
X4
4
1
1
1
1
0
0
0
4
-M
X6
1
-1
[1]
-1
0
-1
1
0
1
-M
X7
9
-1
3
1
0
0
0
1
3
-Z
10M
-2M-3
4M
2
0
-M
0
0

0
X4
3
3
0
2
1
1

0
3/2
0
X2
1
-1
1
-1
0
-1

0
—
-M
X7
6
2
0
[4]
0
3

1
3/2
-Z
6M
2M-3
0
4M+2
0
3M

0

0
X4
0
2
0
0
1
-1/2

0
X2
5/2
0
1
0
0
-1/4

2
X3
3/2
1/2
0
1
0
3/4

-Z
-3
0
0
3
0
3/2

最终单纯形表中，所有检验数非正，且人工变量已出基，故最终单纯形表给出了最优解：
；max Z＝3
四、 用最小元素法得初始运输方案如下：
运 量 表（一）

B1
B2
B3
B4
A1
25
15

A2

0
10
20
A3

30
用位势法检验如下表(括弧中的数字为检验数)：

B1
B2
B3
B4
行位势
A1
5
5
(-1)
(2)
0
A2
(3)
8
13
13
3
A3
(0)
(3)
(-4)
20
10
列位势
5
5
10
10

单位运费、位势与检验数表（括弧中数为检验数）
s 33 = -4为最小的负检验数，在运量表（一）中取闭回路调整得如下运量表（二）：
运 量 表（二）

B1
B2
B3
B4
A1
25
15

A2

0

30
A3

10
20
再检验：
单位运费、位势与检验数表（括弧中数为检验数）

B1
B2
B3
B4
行位势Ui
A1
5
5
(3)
(2)
0
A2
(3)
8
（4）
13
3
A3
(0)
(3)
16
20
10
列位势Vj
5
5
6
10

检验数已全非负，故运量表（二）为最优运输方案，最低运费为1150。
五、 1. 由最终表知最优基为B=(P3,P1)，且；
因此

由线性代数知识，最终表中非基变量x2列的系数应为：

因此
由最终表知基本最优解为：

因此
由检验数计算公式得：-4=c2 -(1/2)c3 + (1/2)c1，-4=(-1/2)c3 + (1/6)c1，-2=(-1/3)c1
因此 c1 = 6，c3 = 10，c2 = -2
2. 当t2＝0时，x2，x4，x5的检验数分别为：
-2 -(1/2)*10 + (1/2)*(6+ t1)，(-1/2) *10 + (1/6) *(6+ t1)，(-1/3) *(6+ t1)
要保证最优解不变，上述三个检验数应保持非正，即：
-2 -(1/2)*10 + (1/2)*(6+ t1)£0, (-1/2) *10 + (1/6) *(6+ t1) £0, (-1/3) *(6+ t1)£0;
解此三个不等式得：-6 £ t1 £ 8
3. 当t1 =0时，要保证现有基为最优基，只要 即可；
即
由此解得：15 ³ t2 ³ (-5/3)

六、解：

所以，最优解为：

最优值为。
七、解：（一）（10分）标号过程：
（1），
（2），
（3），
（4），
（5），
（6），
（7），
（8）
（二）调整过程：
经逆向追踪得到增广链：，调整量为3。
调整后的网络流如下图：
V5
V1
Vs
V2
V3
V6
V4
Vt
(3,3)
(8,8)
(9,9)
(3,0)
(5,4)
(2,1)
(10,10)
(5,3)
(9,8)
(5,1)
(5,4)
(5,4)
(6,6)
(8,7)
(3,1)

重新标号得：
（1），
标号过程中断，所以如图所示的网络流即为最大流。
最小截集为：。
八、解：依题意：R=36500，
（1）（件）

（2）（件）
(元)
（3）经过比较可知，允许缺货的总费用低于不允许缺货的总费用。
原因是，使得，从而允许缺货的总费用低于不允许缺货的总费用。
九、解：最小树如下图：
V1
V3
V2
V4
V5
V6
3
2
2
1
1

10