浙江师范大学硕士研究生入学考试初试科目
考 试 大 纲
|
科目代码、名称: |
运筹学 |
|
|
适用专业: |
0812z2 智能交通技术 |
|
一、考试形式与试卷结构
（一）试卷满分 及 考试时间
本试卷满分为150分，考试时间为180分钟。
（二）答题方式
答题方式为闭卷、笔试。
试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。
（三）试卷题型结构
单选题：10小题，每小题2分，共20分
填空题：7小题，每空2分，共20分
简答题：3小题，每小题5分，共15分
建模题：2小题，每小题10分，共20分
计算题：5小题，每小题15分，共75分
二、考查目标（复习要求）
全日制攻读硕士学位研究生入学考试运筹学科目考试内容包括线性规划、整数规划、运输问题、网络规划、动态规划等内容，要求考生系统掌握相关学科的基本知识、基础理论和基本方法，并能运用相关理论和方法分析、解决生产实践中的实际问题。
三、考查范围或考试内容概要
第一章 线性规划
1．线性规划问题数学模型的三个要素（决策变量、约束条件、目标函数）
2．线性规划问题的解的几种可能情况（无可行解、有无界解、有唯一最优解、有无穷多最优解）。
3．线性规划问题的建模方法。
4．线性规划问题数学模型的一般形式及标准形式。
5．线性规划问题的基、基本解、可行解、基本可行解的概念及它们之间的关系。
6．凸集的概念。
7．图解法的步骤及几何意义。
8．单纯形法的基本原理及几何意义。
9．单纯形法的思路与图解法的思路的相同之处。
10．单纯形法的计算步骤及实际运用。
第二章 线性规划的对偶理论与灵敏度分析
1．线性规划的对偶问题。
2．对偶问题的性质（对偶性定理、松弛互补定理）。
3．对偶单纯形算法的计算步骤及实际应用。
4．灵敏度分析的概念。
5．利用单纯形表进行常用的几种灵敏度分析。
第三章 运输问题
1．运输问题及其数学模型。
2．用表上作业法求解产销平衡的运输问题（西北角法、最小元素法、位势法）。
3．会将产销不平衡的运输问题转化成产销平衡问题并用表上作业法求解。
第五章 整数规划
1．整数规划的概念、特点和数学模型。
2．割平面法、分支定界法的思想。
3．会用割平面法求解纯整数规划问题。
4. 会用分支定界法求解简单的纯整数规划问题。
5. 会用匈牙利算法求解最优分配问题（即指派问题）。
第六章 网络规划（图论）
1．图的基本概念。
2．树的定义及几种等价定义。
3．会用狄克斯特拉算法求解最短路径问题。
4. 最小生成树的概念及求解最小生成树的方法。
5. 运输网络及其相关概念。
6. 会求运输网络的最大流及最小割。
第八章 动态规划
1．多阶段的决策问题
2．动态规划的基本概念（包括阶段、状态、决策、允许决策集合、状态转移方程、递归方程等）。
3．动态规划的逆序解法。
4．动态规划的应用：会使用动态规划求解最优路径问题、投资问题、0-1背包问题等。
参考教材或主要参考书：
1．《运筹学方法与模型》傅家良 主编 复旦大学出版社，2007.02
2．《运筹学教程第三版》胡运权 主编 清华大学出版社，2008.06
四、样卷
（一）单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2分，共20分）
1. 在线性规划模型中，满足约束条件和非负条件的解称为( )
A．基本解 B．基本可行解 C．可行解 D．最优解
2. 线性规划可行域的顶点一定是( )
A．基本可行解 B．最优解 C．非可行解 D．非基本解
3. X是线性规划的基本可行解则有( )
A．X中的基变量非负，非基变量为零 B．X是最优解
C．X不一定满足约束条件 D．X中的基变量非零，非基变量为零
4. 线性规划最优解唯一是指( )
A．可行解集合无界 B．最优表中存在非基变量的检验数为零
C．可行解集合是空集 D．最优表中非基变量的检验数全大于零
5. 原问题有4个变量3个约束，其对偶问题( )
A．有3个变量4个约束 B．有4个变量3个约束
C．有4个变量3个约束 D．有4个变量4个约束
6. 在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题
A．无最优解 B．有唯一最优解
C．有无穷多个最优解 D．不确定
7. 对偶单纯形法中，若满足( )，则原问题没有可行解。
A．基变量的取值出现负值
B．检验数中出现正数
C．检验数全部小于零
D．存在某个基变量为负数，且其所在行的系数全部大于或等于零
8. 若树T有n个顶点，那么它的边数一定是( )
A．n-1 B．n+1 C．n D．n2
9. 原问题与对偶问题都有可行解，则有( )
A、原问题有最优解，对偶问题可能没有最优解
B、原问题与对偶问题可能都没有最优解
C、可能一个问题有最优解，另一个问题具有无界解
D、原问题与对偶问题都具有最优解
10.用割平面法求解整数规划时，构造的割平面只能切去( )
A．整数可行解 B．整数解最优解 C．非整数解 D．无法确定
（二）填空题（每空格2分，共20分）
1. 线性规划解的情形有唯一最优解、 、 和无可行解。
2. 如果在线性规划模型中变量xj的符号不受限制，即变量xj取正值，取负值或取零都可以，则称xj为 。
3. 如果线性规划问题(LP)的基本解又满足非负条件，即有(i=1,…,m)，则称它为(LP)的一个 。
4. 线性规划问题的标准形式的特点为目标函数求最小值、 、 和右端常数项都非负。
5. 树连通，但不存在 。
6. 如果某一整数规划：
Min Z=-7X1-9X2
-X1 +3X2 ≤ 6
7X1 + X2 ≤ 35
X1, X2 ≥ 0且均为整数
所对应的线性规划（松弛问题）的最优解为X1=9/2，X2=7/2，Min Z=-63，我们现在要对X1进行分枝，应该分为 和 。
7. 求解非负赋权图的最短路径问题的较好算法是 。
（三）简答题（共3小题，每题5分，共15分）
1. 线性规划只要有可行解一定有基本可行解。那么，能否确定一定存在最优解？
2. 已知原问题有最优解，那么对偶问题呢？它们的什么是相等的？
3. 为什么说任一运输网络中至少存在一个可行流？
（四）建模题（共2小题，每题10分，共20分）
1. 一个车间要加工3种零件，其需要量分别为4000件、5000件和3500件. 车间内现有4台机床，都可用来加工这3种零件，每台机床可利用的工时分别为1600, 1250, 1800和2000. 机床i#加工零件j#所需工时和成本由表1给出，问如何安排生产，才能使生产成本最低，请列出数学模型，不需要求解。
2. 写出下列线性规划问题的对偶问题：
Max f =3x1 -2x2-5x3-8x5;
s.t. 2x1 +3x2 -3x3- x4 -5x5 ≥-2,
x2 -2x3+3x4 +4x5 =-5,
-x1 +2x3 -2x4 -3x5 ≤-5.
x1 ≤ 0, x2无约束, x3≥ 0, x4≥ 0, x5无约束.
（五）计算题（共5小题，每题15分）
1. 用单纯形法求解下列线性规划问题：
min f =-5x1 -4x2;
s.t. x1 + 2x2 ≤6,
2x1 -x2 ≤4,
5x1 +3x2 ≤15,
x1 ≥ 0, x2 ≥ 0.
2. 求解表2所给运输问题：
(1) 用西北角法求初始解；
(2) 用位势法求最优解。
3. 用割平面法求解下列整数规划：
min f =-3x1 -4x2;
s.t. 2x1 +5x2 +x3 = 15,
2x1 -2x2 +x4 = 5,
xj ≥ 0, 整数, j=1,2,3,4.
已知相应的(LP)的最优单纯形表如表3所示。
表3
|
XB |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
0 |
1 |
1/7 |
-1/7 |
10/7 |
|
x1 |
1 |
0 |
1/7 |
5/14 |
55/14 |
|
r |
0 |
0 |
1 |
1/2 |
35/2 |
4. 求图1中v1至v10的最短路径和长度。
5. 求运输网络图图2的最大流及最小割。
