运筹学教学大纲

浙江财经学院

运 筹 学

教 学 大

数学与统计学院 计算运筹教研室

纲

目 录

前 言 ……………………………………………………………………………………（2） 第一章 线性规划简介……………………………………………………………………（4） 第二章 非线性规划………………………………………………………………………（5） 第三章 整数规划…………………………………………………………………………（7） 第四章 对策论……………………………………………………………………………（7） 第五章 动态规划…………………………………………………………………………（8） 第六章 图与网络…………………………………………………………………………（9）

前 言

一、课程简介

运筹学是研究现实世界中各种运行系统的一门学科，是经济计划、系统工程、现代管理等领域的强有力的工具，是一门研究如何有效地组织和管理人机系统的科学。它包含了许多分支，但从各种可供选择的方案中找出一个最好的或满意的方案，以实现系统的某一或某些指标整体最优化是其共同的特点。

本课程主要内容有：线性规划简介、非线性规划、整数规划、对策论、动态规划、图与网络等。

二、课程的教学目标和总的教学要求

通过本课程的学习，使学生掌握运筹学的基本理论、思想和方法，学会研究客观世界的各种运行系统中所发生的复杂问题，为现实或未来系统建立运筹学模型，并运用运筹学的方法和技巧进行分析，从而求得系统最优运行或最优设计的方案，为求解的实际问题提供最合理的决策，培养学生综合运用所学知识进行分析，解决实际问题的能力。

三、适用对象

数学与统计学院、工商管理学院、全校经济、管理类专业学生。

四、课程性质

本课程是专门为数学与统计学院统计学专业、信息与计算科学专业，工商管理学院工程管理专业、物流专业学生而开设的专业必修课，全校经济、管理类专业学生而开设的公共选修课、任意选修课。

五、总课时及各章的分配

专业必修课、和任意选修课的学分为3，授课总课时数为51学时。公共选修课的学分为2，授课总课时数为34课时。各章的学时具体安排如下： 章 节 第一章 第二章 第三章 第四章 第五章

教 学 内 容

线性规划简介 非线性规划 整数规划 对策论 动态规划

3学分 授课学时

12 12 6 9 6

2学分 授课学时

10 0 6 9 6

第六章 合计

图与网络

6 51

3 34

注：第一章内容讲到对偶单纯形方法，第四章内容讲到二人有限非零和对策。

六、使用教材及主要参考书目

（一）选用教材

魏权龄、胡显佑、严颖编著：《运筹学通论》，中国人民出版社，2000年。 （二）主要参考书目

1．胡运权主编：《运筹学教程》，清华大学出版社，1998年。 2．杨超主编：《运筹学》》，科学出版社，2004年。 3．徐渝、胡奇英主编：《运筹学》，陕西人民出版社，2001年。 4．徐祈宗主编：《运筹学》，机械工业出版社，2003年

第一章 线性规划简介

教学目的和要求：

1. 掌握线性规划数学模型的基本特征和标准形式，以及线性规划问题数学模型的建立方法。

2．学会用图解法求解两个变量的线性规划问题。

3．理解线性规划问题的解的概念，了解线性规划的基本理论。 4. 了解单纯形表的构成，熟练掌握运用单纯形法求解线性规划问题。 5. 掌握用两阶段法构造线性规划问题的初始可行解。

6. 理解原问题与对偶问题的关系，了解线性规划的对偶理论。

7．熟悉对偶单纯形法的计算步骤，掌握运用对偶单纯形法求解线性规划问题。

教学重点：

数学模型的建立；单纯形方法；两阶段方法；对偶单纯形方法。

教学难点：

单纯形表的构成；两阶段法构造初始可行解。

§1.1 基本概念

1． 线性规划问题的一般形式

2． 两个变量线性规划问题的图解法

§1.2 线性规划问题解的性质

1．线性规划问题的标准形式 标准形式；转化方法。 2．基本解和基本可行解

基本解、基本可行解和基本最优解的概念；解的性质。

§1.3 单纯形表

1．例 2．单纯形表 单纯形表的构成。

§1.4 单纯形方法

1．单纯形方法

2．求初始可行解—两阶段方法

§1.5 对偶线性规划

1．对偶线性规划问题 2．对偶线性规划的性质

§1.6 对偶单纯形方法

对偶可行基的概念；对偶单纯形方法求解。

第二章 非线性规划

教学目的和要求：

1. 理解凸集、凸函数和凸规划的基本概念及性质。 2. 掌握用库恩-塔克定理求解凸规划问题。 3. 掌握单变量极值问题的解法。

4. 掌握解无约束极值问题的最速下降方法和广义牛顿法。 5. 掌握用罚函数方法解非线性规划问题。 6．掌握线性约束条件下线性逼近的方法。

教学重点：

凸规划问题的基本概念和性质；库恩-塔克定理；单变量极值问题的解法；无约束极值问题的解法；罚函数方法；线性逼近方法。

教学难点：

库恩-塔克定理；罚函数方法；线性逼近方法。

§2.1 例子

非线性规划模型及其标准型。

§2.2 预备知识

1．n 维向量空间E n 向量空间；向量运算。 2．梯度

梯度的定义；梯度的几何意义；多变量函数的Taylor 展开。

§2.3 凸集、凸函数与凸规划

1．凸集和凸锥 凸集和凸锥的定义。 2．凸函数

凸函数、凹函数的定义及性质；凸函数的判别。 3．凸规划

凸规划的定义；凸规划问题的性质。

§2.4 非线性规划的库恩-塔克定理

库恩-塔克条件；库恩-塔克定理求解非线性规划问题。

§2.5 单变量极值问题的解法

1． “成功-失败”方法 2． “0.618”方法 3． 二次插值方法

§2.6 无约束极值问题的解法

1． 最速下降法 2． 广义牛顿法

§2.7 罚函数方法

罚函数的基本思想；罚因子的选取；罚函数方法求解。

§2.8 线性约束条件下线性逼近的方法

线性逼近的基本思想；线性逼近方法的迭代步骤。

第三章 整数规划

教学目的和要求：

1. 掌握整数规划的数学模型。

2. 掌握分枝定界法的基本思想和具体计算。 3．理解割平面的定义和性质，掌握具体求解方法。 教学重点：

分枝定界法；割平面方法。

教学难点：

分枝定界法和割平面方法的基本思想。

§3.1 整数规划的例子

1．下料问题 2．工厂设址问题 3．背包问题

§3.2 分枝定界法

1．0-1规划的解法 2．整数线性规划的解法

§3.3 割平面方法

割平面的定义及性质；割平面方法求解整数线性规划问题。

第四章 对策论

教学目的和要求：

1. 理解对策论的有关概念，了解对策模型的基本要素。

2. 了解矩阵对策在纯策略意义下的解和在混合扩充意义下的解。 3. 掌握矩阵对策的线性规划解法。 4. 了解二人有限非零和对策的均衡点。

教学重点：

对策模型；矩阵对策；二人有限非零和对策。

教学难点：

矩阵对策的线性规划解法。

§4.1 对策论的基本概念

1． 非合作对策（策略型）

零和对策、非零和对策的定义；策略型非合作对策的特点。 2． 非合作对策（扩展型）

斯坦克尔伯格模型、戈诺模型；扩展型非合作对策的特点。 3． 合作对策

§4.2 矩阵对策及其解

1． 矩阵对策在纯策略意义下的解 2． 矩阵对策在混合扩充意义下的解

§4.3 矩阵对策的线性规划解法

矩阵对策的简化；矩阵对策的线性规划求解。

§4.4 二人有限非零和对策

1．非合作的情形 2．合作的情形

第五章 动态规划

教学目的和要求：

1. 理解动态规划的基本概念和基本原理。

2. 掌握动态规划模型的建立，理解动态规划的最优化原则。

3．掌握最短路问题、多阶段配置问题、背包问题、资源分配问题和随机型采购问题的具体求解方法。

教学重点：

动态规划模型；最优化原则；具体问题的求解。

教学难点：

最优化函数方程。

§5.1 最短路问题与“最优化原则”

最短路问题求解；最优化原则。

§5.2 多阶段配置问题

多阶段配置问题求解。

§5.3 “背包”问题

一维背包问题求解；二维背包问题求解。

§5.4 资源分配问题

资源分配问题求解。

§5.5 随机型采购问题

随机型采购问题求解。

第六章 图与网络

教学目的和要求：

1. 掌握图论中的基本概念，了解图的矩阵表示。

2．了解欧拉图的概念，掌握中国邮路问题的求解方法。 3．了解哈密尔顿图的概念，掌握货郎担问题的求解方法。 4．了解有向图的概念，掌握排序问题的求解方法。

5．掌握最短通路问题、最大流问题、最小树问题等常用的网络最优化方法。 教学重点：

欧拉图；哈密尔顿图；最短通路问题；最大流问题；最小树问题。

教学难点：

各问题的基本思想和具体求解。

§6.1 基本概念

1．图与子图 2．图的矩阵表示 关联矩阵；邻接矩阵。 3．链、通路与回路

链；简单链；初等链；连通图。

§6.2 中国邮路问题与货郎担问题

1．欧拉图与中国邮路问题

欧拉链、欧拉图的定义；欧拉图的判别；中国邮路问题的求解。 2．哈密尔顿图

哈密尔顿通路的定义；判别哈密尔顿图的充分条件。 3．货郎担问题

货郎担问题的近似解法。 4．排序问题

有向图的概念；最优排序问题。

§6.3 最短通路问题

1．Dijkstra 算法 2．yen 算法

§6.4 最大流问题

1．基本概念

可行流、流量的定义；截集、最小截集的定义。

2．最大流的标号算法

可扩充路的定义；最大流的标号算法。

§6.5 最小树问题

1．树的概念和性质

2．最小树问题

10

PDF 文件使用 "pdfFactory" 试用版本创建