运筹与优化课程教学大纲.doc

运筹与优化课程教学大纲

课程名称：运筹与优化/ Operations and Optimizations
学时/学分：48学时/3学分 （其中课内学时48学时，实验上机0学时）
先修课程：高等代数或线性代数，概率论与数理统计，数值计算方法，算法语言等
适用专业：数学与应用数学，信息与计算科学、计算机科学与技术、软件工程
开课院（系、部、室）：数学与计算机科学学院
一、课程的性质与任务
本课程是信息与计算科学、计算机科学与技术、数学与应用数学和软件工程专业的专业基础课程之一。其任务是使学生从应用角度出发，在理论和实践上掌握数学优化的基本原理和基本方法，培养学生对典型的数学优化模型及基本算法的理解与应用能力。
二、课程内容、基本要求与学时分配
（一）绪论
了解运筹与优化这门科学的产生、发展、现状、应用及相关知识;介绍开设本课程的背景意义、注意之处、与其它课程的相互联系、教学安排、学习方法、相关参考书;介绍本课程的主要内容；介绍相关软件；对学生提出要求等。
（二）线性规划（LP）　　　　　　　　　　　　　 　 4学时
1.理解LP建模及实际背景。
2.掌握LP(二维)的图解法、LP的标准型、LP解的相关基本概念（可行解、可行域、基、基可行解、可行基）。了解LP问题解的几种情况。
3.了解LP的几何意义（可选择其中的结论证明），掌握可行域顶点与基可行解的重要对应关系。
重点：LP(二维)的图解法，LP解的相关基本概念。
难点：可行域顶点与基可行解的重要对应关系。
（三）LP的单纯形法 6学时
1．了解单纯形法原理及运算过程中的基本概念。
2．熟练掌握单纯形法计算方法（特别是表上运算）。
3．掌握LP问题的大M法、两阶段法，了解LP问题的退化情况。
重点：单纯形法计算方法。
难点: 大M法、两阶段法。
（四）LP问题的应用举例 2学时
列举几个典型的LP问题数学模型，培养学生建立LP模型的基本能力。
重点：数学建模思想。
难点：建模方法。
（五）对偶理论 4学时
1．了解单纯形法的矩阵描述及改进单纯形法。
2．了解LP对偶问题提出的背景，会写出一个LP问题的对偶问题。
3．掌握对偶理论的基本性质（特别是互补松驰条件的应用）。
4．了解对偶单纯形法及灵敏度分析。
重点：对偶问题的性质。
难点：互补松驰性。
（六）运输问题 4学时
掌握产销平衡的运输问题的数学模型及表上运算方法，了解产销不平衡情形。
重点：产销平衡的运输问题。
难点：产销不平衡问题。
（七）整数规划 4学时
1．掌握整数规划的常用两种算法之一（分支定界法与割平面法）。
2．掌握0-1规划的隐枚举法。掌握指派问题的解法。
重点：整数规划的分支定界法、指派问题。
难点: 整数规划的割平面法。
（八）非线性规划 8学时
1．了解非线性规划问题提出的意义及一般数学模型与相关概念。
2．掌握多元无约束极值问题的2-3个常用算法（如最速下降法、共轭梯度法、变尺度法、牛顿法等），了解这些算法各自的优缺点。
3．了解约束条件下的极值问题有关基本概念及算法。
重点：无约束极值问题的几种算法。
难点：变尺度法。
（九）动态规划初步 4学时
1. 了解动态规划的基本原理（多阶段决策的动态规划方法）。
2. 通过举例（典型问题）要求学生掌握应用本原理的基本方法。
重点：动态规划的基本原理。
难点：动态规划方法求解方法。
（十）网络优化 4学时
1．掌握最小生成树、最短路、网络最大流算法。了解最小费用最大流问题的算法。了解一些著名网络优化问题。
2．会求关键路线（CPM）。了解GERT（图解评审法）。
重点：最短路、网络最大流算法。
难点：最小费用最大流问题算法。
（十一）排队论 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。

大纲制订者： 刘学飞
大纲审定者：王绍恒