浙江财经学院
运 筹 学
教 学 大
数学与统计学院 计算运筹教研室
纲
目 录
前 言 ……………………………………………………………………………………(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" 试用版本创建
浙江财经学院
运 筹 学
教 学 大
数学与统计学院 计算运筹教研室
纲
目 录
前 言 ……………………………………………………………………………………(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" 试用版本创建