《运筹学》教学大纲 课程编码:1512106802 课程名称:运筹学 学时/学分:36/2 先修课程:《数学分析》、《高等代数》、《概率论与数理统计》 适用专业:信息与计算科学 开课教研室:应用数学教研室 、课程性质与任务 1.课程性质:本课程为专业必修课,学位课程。 2.课程任务:《运筹学》是一门广泛应用现有的科学技术知识和数学工具,以定性与定 量相结合的方法研究和解决管理、经济和工程技术中提出的实际问题,为决策者选择最优决 策提供定量依据的一门决策科学。运筹学的理论内容丰富,它的时间背景和应用范围涉及到 工业、农业、军事、经济管理科学、计算机科学等领域,它具有鲜明的实践性和经济性,许 多问题的解决丰富了数学理论和方法的发现,甚至产生了应用数学的多个新的分支 开设本课程的目的是让学生熟悉一些运筹学的基本模型及其求解原理、方法技巧,掌握 运筹学整体优化的思想和若干定量分析的优化技术,同时能够运用常用软件(如 Lindo, Lingo, Matlab等)求解运筹学问题,从而使学生正确应用各类模型分析、解决不十分复杂 的实际问题。 二、课程教学基本要求 1.要求正确理解运筹学方法论,掌握运筹学整体优化思想。 2.掌握线性规划、整数规划、非线性规划、动态规划等基本模型的功能和特点,熟悉 其建模条件、步骤及相应的技巧,能根据实际背景抽象岀适当的运筹学模型。 3.熟练掌握各种模型特别是确定性模型的求解方法,并能对求解结果作简单分析 4.掌握与基本模型有关的基本概念及基本原理,做到思路清晰、概念明确 5.具有初步运用运筹学思想和方法分析、解决实际问题的能力和创新思维与应用能力 成绩考核形式:期终成绩(闭卷考试)(70%)+平时成绩(平时测验、作业、课堂提问、 课堂讨论等)(30%)。成绩评定采用百分制,60分为及格。 三、课程教学内容 第一章绪论 1.教学基本要求
《运筹学》教学大纲 课程编码：1512106802 课程名称：运筹学 学时/学分：36/2 先修课程：《数学分析》、《高等代数》、《概率论与数理统计》 适用专业：信息与计算科学 开课教研室：应用数学教研室 一、课程性质与任务 1．课程性质：本课程为专业必修课，学位课程。 2．课程任务：《运筹学》是一门广泛应用现有的科学技术知识和数学工具，以定性与定 量相结合的方法研究和解决管理、经济和工程技术中提出的实际问题，为决策者选择最优决 策提供定量依据的一门决策科学。运筹学的理论内容丰富，它的时间背景和应用范围涉及到 工业、农业、军事、经济管理科学、计算机科学等领域，它具有鲜明的实践性和经济性，许 多问题的解决丰富了数学理论和方法的发现，甚至产生了应用数学的多个新的分支。 开设本课程的目的是让学生熟悉一些运筹学的基本模型及其求解原理、方法技巧，掌握 运筹学整体优化的思想和若干定量分析的优化技术，同时能够运用常用软件（如 Lindo， Lingo，Matlab 等）求解运筹学问题，从而使学生正确应用各类模型分析、解决不十分复杂 的实际问题。 二、课程教学基本要求 1．要求正确理解运筹学方法论，掌握运筹学整体优化思想。 2．掌握线性规划、整数规划、非线性规划、动态规划等基本模型的功能和特点，熟悉 其建模条件、步骤及相应的技巧，能根据实际背景抽象出适当的运筹学模型。 3．熟练掌握各种模型特别是确定性模型的求解方法，并能对求解结果作简单分析。 4．掌握与基本模型有关的基本概念及基本原理，做到思路清晰、概念明确。 5．具有初步运用运筹学思想和方法分析、解决实际问题的能力和创新思维与应用能力。 成绩考核形式：期终成绩（闭卷考试）（70%）＋平时成绩（平时测验、作业、课堂提问、 课堂讨论等）（30％）。成绩评定采用百分制，60 分为及格。 三、课程教学内容 第一章 绪 论 1.教学基本要求
本章首先介绍运筹学的概况,包括运筹学的由来和发展、运筹学的性质与特点、运筹学 的主要内容和运筹学的发展趋势。然后,通过几个例子分别介绍运筹学中线形规划、随机规 划和网络分析的数学模型。 2.教学重点和难点 教学重点:运筹学的由来和发展、运筹学的性质与特点、运筹学的主要内容和运筹学的 发展趋势。 教学难点:运筹学中线形规划、随机规划和网络分析的数学模型。 3教学内容 第一节运筹学的概况 1.运筹学的由来和发展 2.运筹学的性质与特点 3.运筹学的主要内容 4.运筹学的发展趋势 第二节运筹学的数学模型 1.线性规划模型 2.随机规划模型 3.网络规划模型 第二章线性规划 1.教学基本要求 了解运筹学的内容、目的、发展与现况;了解单纯形表的构成,熟练掌握运用单纯形法 求解线性规划问题。了解改进单纯法的计算步骤。熟练人工变量法(包括大M法和两阶段法) 的计算步骤。 2.教学重点和难点 教学重点:线性规划各种解的概念。 教学难点:求解各种类型线性规划(标准化过程、大M法、两阶段法) 3教学内容 第一节线性规划问题 1.线性规划问题举例 2.线性规划模型 第二节可行区域与基本可行解 1.图解法
本章首先介绍运筹学的概况，包括运筹学的由来和发展、运筹学的性质与特点、运筹学 的主要内容和运筹学的发展趋势。然后，通过几个例子分别介绍运筹学中线形规划、随机规 划和网络分析的数学模型。 2.教学重点和难点 教学重点：运筹学的由来和发展、运筹学的性质与特点、运筹学的主要内容和运筹学的 发展趋势。 教学难点：运筹学中线形规划、随机规划和网络分析的数学模型。 3.教学内容 第一节 运筹学的概况 1．运筹学的由来和发展 2．运筹学的性质与特点 3．运筹学的主要内容 4．运筹学的发展趋势 第二节 运筹学的数学模型 1．线性规划模型 2．随机规划模型 3．网络规划模型 第二章 线性规划 1.教学基本要求 了解运筹学的内容、目的、发展与现况；了解单纯形表的构成，熟练掌握运用单纯形法 求解线性规划问题。了解改进单纯法的计算步骤。熟练人工变量法（包括大Ｍ法和两阶段法） 的计算步骤。 2.教学重点和难点 教学重点：线性规划各种解的概念。 教学难点：求解各种类型线性规划（标准化过程、大 M 法、两阶段法）。 3.教学内容 第一节 线性规划问题 1．线性规划问题举例 2．线性规划模型 第二节 可行区域与基本可行解 1．图解法
2.可行区域的几何结构 3.基本可行解及线性规划的基本定理 第三节单纯形方法 1.单纯形方法 2.单纯形表 第四节初始解 1.两阶段法 2.关于单纯形方法的几点说明 第五节对偶性及对偶单纯形法 1.对偶线性规划 2.对偶理论 3.对偶单纯形法 第六节灵敏度分析 1.改变价值向量 2.改变右端向量 第三章整数线性规划 1.教学基本要求 掌握分枝定界法和割平面法的计算步骤。掌握一般0-1型规划的求解方法-隐枚举法。 了解指派问题数学模型的特点,熟悉匈牙利方法的步骤,掌握运用匈牙利方法求解指派问题。 2.教学重点和难点 教学重点:分枝定界法和割平面法的计算步骤 教学难点:匈牙利方法求解指派问题 3教学内容 第一节整数线性规划问题 1.整数线性规划问题举例 2.解整数线性规划问题的困难性 第二节 Gomory翻平面法 1. Gomory割平面法的基本思想
2．可行区域的几何结构 3．基本可行解及线性规划的基本定理 第三节 单纯形方法 1．单纯形方法 2．单纯形表 第四节 初始解 1．两阶段法 2．关于单纯形方法的几点说明 第五节 对偶性及对偶单纯形法 1．对偶线性规划 2．对偶理论 3．对偶单纯形法 第六节 灵敏度分析 1．改变价值向量 2．改变右端向量 第三章 整数线性规划 1.教学基本要求 掌握分枝定界法和割平面法的计算步骤。掌握一般 0－1 型规划的求解方法--隐枚举法。 了解指派问题数学模型的特点，熟悉匈牙利方法的步骤，掌握运用匈牙利方法求解指派问题。 2.教学重点和难点 教学重点：分枝定界法和割平面法的计算步骤 教学难点：匈牙利方法求解指派问题 3.教学内容 第一节 整数线性规划问题 1．整数线性规划问题举例 2．解整数线性规划问题的困难性 第二节 Gomory 割平面法 1．Gomory 割平面法的基本思想
2. Gomory割平面法计算步骤 第三节分枝定界法 1.分枝定界法的基本思想 2.分枝定界法的计算步骤 第四章非线性规划 1.教学基本要求 掌握非线性规划基本形式和求解模式:掌握凸函数和凸规划的概念及性质:掌握0.618 法、 Newton法,了解 Goldstein法和 Armijo法;掌握无约束最优化问题的最优性质,熟练 运用最速下降法和共轭方向法求解无约束最优化问题;掌握约束最优化问题的最优性质,熟 练运用简约梯度法和惩罚函数法求解约束最优化问题。 2.教学重点和难点 教学重点:0.618法、 Newton法,无约束最优化问题的最优性质,最速下降法和共轭方 教学难点:约束最优化问题的求法。 3教学内容 第一节基本概念 1.非线性规划问题 2.非线性规划方法概述 第二节凸函数和凸规划 1.凸函数及其性质 2.凸规划及其性质 第三节一维搜索方法 1.0.618法 2. Newton法 3.非精确一维搜索方法 第四节无约束最优化方法 1.无约束问题的最优性条件 2.最速下降法 3.共轭方向法 第五节约束最优化方法 1.约束最优化问题的最优性条件 2.简约剃度法
2．Gomory 割平面法计算步骤 第三节 分枝定界法 1．分枝定界法的基本思想 2．分枝定界法的计算步骤 第四章 非线性规划 1.教学基本要求 掌握非线性规划基本形式和求解模式；掌握凸函数和凸规划的概念及性质；掌握 0.618 法、Newton 法，了解 Goldstein 法和 Armijo 法；掌握无约束最优化问题的最优性质，熟练 运用最速下降法和共轭方向法求解无约束最优化问题；掌握约束最优化问题的最优性质，熟 练运用简约梯度法和惩罚函数法求解约束最优化问题。 2.教学重点和难点 教学重点：0.618 法、Newton 法，无约束最优化问题的最优性质，最速下降法和共轭方 向法。 教学难点：约束最优化问题的求法。 3.教学内容 第一节 基本概念 1．非线性规划问题 2．非线性规划方法概述 第二节 凸函数和凸规划 1．凸函数及其性质 2．凸规划及其性质 第三节 一维搜索方法 1．0.618 法 2．Newton 法 3．非精确一维搜索方法 第四节 无约束最优化方法 1．无约束问题的最优性条件 2．最速下降法 3．共轭方向法 第五节 约束最优化方法 1．约束最优化问题的最优性条件 2．简约剃度法
3.惩罚函数法 第五章动态规划 1.教学基本要求 理解动态规划的基本概念和基本原理。掌握动态规划模型的建立与求解方法。 2.教学重点和难点 教学重点:动态规划模型的建立与求解方法 教学难点:动态规划模型求解方法 3教学内容 第一节多阶段决策问题 1.多阶段决策问题及例 第二节最优化原理 1.用递推法解最短路线问题 2.最优化原理 第三节确定性的定期多阶段决策问题 1.旅行售货员问题 2.多阶段资源分配问题 3.用最优化原理解某些非线性规划问题 4.排序问题 第四节确定性的不定期多阶段决策问题 1.最优线路问题 2.有限资源分配问题 第六章图与网络分析 1.教学基本要求 掌握图、子图、连通基本概念,掌握树、支撑树、和最小树的基本性质,掌握最短有I 路方程基本原理、最大流问题的基本原理,熟练求解最小树问题、最短有向路问题、最大 问题等 2.教学重点和难点 教学重点:树、支撑树、和最小树的基本性质,最短有向路方程基本原理、最大流问题 的基本原理 教学难点:求解最小树问题、最短有向路问题、最大流问题 3教学内容 第一节图与子图
3．惩罚函数法 第五章 动态规划 1.教学基本要求 理解动态规划的基本概念和基本原理。 掌握动态规划模型的建立与求解方法。 2.教学重点和难点 教学重点：动态规划模型的建立与求解方法 教学难点：动态规划模型求解方法 3.教学内容 第一节 多阶段决策问题 1．多阶段决策问题及例 第二节 最优化原理 1．用递推法解最短路线问题 2．最优化原理 第三节 确定性的定期多阶段决策问题 1．旅行售货员问题 2．多阶段资源分配问题 3．用最优化原理解某些非线性规划问题 4．排序问题 第四节 确定性的不定期多阶段决策问题 1．最优线路问题 2．有限资源分配问题 第六章 图与网络分析 1.教学基本要求 掌握图、子图、连通基本概念，掌握树、支撑树、和最小树的基本性质，掌握最短有向 路方程基本原理、最大流问题的基本原理，熟练求解最小树问题、最短有向路问题、最大流 问题等。 2.教学重点和难点 教学重点：树、支撑树、和最小树的基本性质，最短有向路方程基本原理、最大流问题 的基本原理。 教学难点：求解最小树问题、最短有向路问题、最大流问题。 3.教学内容 第一节 图与子图
1.图与网络 2.关联矩阵和邻接矩阵 3.子图 第二节图的连通性 1.图的连通 2.图的割集 第三节树与支撑树 1.树及其基本性质 2.支撑树及基本性质 第四节最小树问题 1.最小树及其性质 2.求最小树的 Kruskal算法 3. Di jkstra算法 第五节最短有向路问题 1.最短有向方程 2.求最短有向路的 Di jkstra算法 第六节最大流问题 1.最大流最小割定理 2.最大流算法 第七节最小费用流问题 1.最小费用流算法 2.特殊的最小费用流一一运输问题 第八节最大对集问题 1.二分图对集 2.二分图的最大基数对集 3.二分网络的最大权对集一一分派问题 四、学时分配 章序 内容 课时 备注 绪论 2 线性规划 整数线性规划 非线性规划 8
1．图与网络 2．关联矩阵和邻接矩阵 3．子图 第二节 图的连通性 1．图的连通 2．图的割集 第三节 树与支撑树 1．树及其基本性质 2．支撑树及基本性质 第四节 最小树问题 1．最小树及其性质 2．求最小树的 Kruskal 算法 3． Dijkstra 算法 第五节 最短有向路问题 1．最短有向方程 2．求最短有向路的 Dijkstra 算法 第六节 最大流问题 1．最大流最小割定理 2．最大流算法 第七节 最小费用流问题 1．最小费用流算法 2．特殊的最小费用流——运输问题 第八节 最大对集问题 1．二分图对集 2．二分图的最大基数对集 3．二分网络的最大权对集——分派问题 四、学时分配 章序 内容 课时 备注 一 绪论 2 二 线性规划 8 三 整数线性规划 4 四 非线性规划 8
五 动态规划 6 图与网络分析 合计 五、主用教材及参考书 (一)主用教材: 《运筹学》主编:刁在筠出版社:高等教育出版社出版时间:2001年。 《运筹学》主编:徐玖平、胡知能等出版社:科学出版社出版时间:1998年。 (二)参考书 1.《运筹学教程》主编:胡运权出版社:清华大学出版社出版时间:2005年。 2.《运筹学》主编:钱颂迪李承治出版社:清华大学出版社出版时间:1990年 3.《运筹学应用案例》主编:陶谦坎出版社:西安交大出版社出版时间:1993年。 执笔:王永忠 审定:朱耀生梁桂珍
五 动态规划 6 六 图与网络分析 8 合计 36 五、主用教材及参考书 （一）主用教材： 《运筹学》主编：刁在筠 出版社：高等教育出版社 出版时间：2001 年。 《运筹学》主编：徐玖平、胡知能等 出版社：科学出版社 出版时间：1998 年。 （二）参考书： 1.《运筹学教程》主编：胡运权 出版社：清华大学出版社 出版时间：2005 年。 2.《运筹学》主编：钱颂迪 李承治 出版社：清华大学出版社 出版时间：1990 年。 3.《运筹学应用案例》 主编：陶谦坎 出版社：西安交大出版社 出版时间：1993 年。 执笔：王永忠 审定：朱耀生 梁桂珍