1、运筹与优化课程教学大纲课程名称：运筹与优化/ Operations and Optimizations学时/学分：48 学时/3 学分 （其中课内学时 48 学时，实验上机 0 学时）先修课程：高等代数或线性代数，概率论与数理统计，数值计算方法，算法语言等适用专业：数学与应用数学，信息与计算科学、计算机科学与技术、软件工程开课院（系、部、室）：数学与计算机科学学院一、课程的性质与任务本课程是信息与计算科学、计算机科学与技术、数学与应用数学和软件工程专业的专业基础课程之一。其任务是使学生从应用角度出发，在理论和实践上掌握数学优化的基本原理和基本方法，培养学生对典型的数学优化模型及基本算法的理解与
2、应用能力。二、课程内容、基本要求与学时分配（一）绪论 了解运筹与优化这门科学的产生、发展、现状、应用及相关知识;介绍开设本课程的背景意义、注意之处、与其它课程的相互联系、教学安排、学习方法、相关参考书;介绍本课程的主要内容；介绍相关软件；对学生提出要求等。（二）线性规划（LP） 4 学时1.理解 LP 建模及实际背景。2.掌握 LP(二维)的图解法、LP 的标准型、LP 解的相关基本概念（可行解、可行域、基、基可行解、可行基） 。了解 LP 问题解的几种情况。3.了解 LP 的几何意义（可选择其中的结论证明） ，掌握可行域顶点与基可行解的重要对应关系。重点：LP(二维)的图解法，LP 解的相关
3、基本概念。难点：可行域顶点与基可行解的重要对应关系。（三）LP 的单纯形法 6 学时1了解单纯形法原理及运算过程中的基本概念。2熟练掌握单纯形法计算方法（特别是表上运算） 。3掌握 LP 问题的大 M 法、两阶段法，了解 LP 问题的退化情况。重点：单纯形法计算方法。难点: 大 M 法、两阶段法。（四）LP 问题的应用举例 2 学时列举几个典型的 LP 问题数学模型，培养学生建立 LP 模型的基本能力。重点：数学建模思想。难点：建模方法。（五）对偶理论 4 学时1了解单纯形法的矩阵描述及改进单纯形法。2了解 LP 对偶问题提出的背景，会写出一个 LP 问题的对偶问题。3掌握对偶理论的基本性质（
4、特别是互补松驰条件的应用） 。4了解对偶单纯形法及灵敏度分析。重点：对偶问题的性质。难点：互补松驰性。（六）运输问题 4 学时掌握产销平衡的运输问题的数学模型及表上运算方法，了解产销不平衡情形。重点：产销平衡的运输问题。难点：产销不平衡问题。（七）整数规划 4 学时1掌握整数规划的常用两种算法之一（分支定界法与割平面法） 。2掌握 0-1 规划的隐枚举法。掌握指派问题的解法。重点：整数规划的分支定界法、指派问题。难点: 整数规划的割平面法。（八）非线性规划 8 学时1了解非线性规划问题提出的意义及一般数学模型与相关概念。2掌握多元无约束极值问题的 2-3 个常用算法（如最速下降法、共轭梯度法、
5、变尺度法、牛顿法等） ，了解这些算法各自的优缺点。3了解约束条件下的极值问题有关基本概念及算法。重点：无约束极值问题的几种算法。难点：变尺度法。（九）动态规划初步 4 学时1. 了解动态规划的基本原理（多阶段决策的动态规划方法） 。2. 通过举例（典型问题）要求学生掌握应用本原理的基本方法。重点：动态规划的基本原理。难点：动态规划方法求解方法。（十）网络优化 4 学时1掌握最小生成树、最短路、网络最大流算法。了解最小费用最大流问题的算法。了解一些著名网络优化问题。2会求关键路线（CPM） 。了解 GERT（图解评审法） 。重点：最短路、网络最大流算法。难点：最小费用最大流问题算法。（十一）排队
6、论 6 学时1了解排队系统模型及基本概念。2了解顾客到达时间和服务时间的分布。3掌握几个常用排队模型（M/M/1、M/M/1/N/ 、M/M/1/ /m）中相关参数的计算。重点是 M/M/1 模型。4了解多服务台排队模型。重点：重点是 M/M/1 模型。难点：模型的有关指标。（十二）机动与总复习 2 学时三、推荐教材和主要参考书1推荐教材：（1）运筹学教材编写组, 运筹学 ,北京：清华大学出版社，1998。2 推 荐 参 考 书 ：（1）张莹，运筹学基础，北京：清华大学出版社，1995。（2）罗荣桂，新编运筹学题解，武汉：华中科技大学出版社，2002。（3）胡运权，运筹学基础及应用，哈尔滨：哈尔滨工业大学出版社，1988。（4）M S Bazarra , J Jarvis . Linear programming and network flows. New York: John Wiley & Sons , Inc.，1977。（5）S Bradley，瞿立林等译，应用数学规划，北京：机械工业出版社，1986。（6）胡运权，运筹学习题集，北京：清华大学出版社，1995。大纲制订者： 刘学飞大纲审定者：王绍恒
