2020年浙江师范大学888运筹学硕士研究生入学考试初试科目考试大纲.docx

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