石河子大学教案 课程名称: 运筹学 课程代码 授课班级: 信管 任课教师: 常浩娟 信息学院信管系(部)信息组织教研室 石河子大学教务处制
石河子大学教案 课 程 名 称: 运筹学 课 程 代 码 授 课 班 级: 信管 任 课 教 师: 常浩娟 信息学院 信管系(部)信息组织教研室 石河子大学教务处制
课程名称:运筹学 专业:信息管理与信息系统 班级: 目录 第0章绪论 3 第1章线性规划及单纯形法 第2章线性规划的对偶理论 第3章运输问题 26 第4章整数规划与分配问题 第5章目标规划. . 第6章图与网络分析 47 第7章计划评审方法和关键路线法 63 1.任务的分解 2.绘制网络图 三、网络图分类 .64 第8章动态规划 69 总复习 .7 实验 线性规划问恩的Excel建模求解 7 实验二线性规划的建模与应用 实验三使用Excel进行灵敏度分析」 8 实验四运输问题的Excl建模求解 9 实验五目标规划问题分层Excel求解 .96 实验六图与网络分析折 101 实验七 网络计划的Excel求解 实验八动态规划的Excel求解。 107
课程名称:运筹学 专业:信息管理与信息系统 班级: 目 录 第 0 章 绪论.3 第 1 章 线性规划及单纯形法.5 第 2 章 线性规划的对偶理论.19 第 3 章 运输问题.26 第 4 章 整数规划与分配问题.36 第 5 章 目标规划.42 第 6 章 图与网络分析.47 第 7 章 计划评审方法和关键路线法.62 1.任务的分解.63 2.绘制网络图.63 三、网络图分类 .64 第 8 章 动态规划.69 总复习 .75 实验一 线性规划问题的 Excel 建模求解.77 实验二 线性规划的建模与应用.80 实验三 使用 Excel 进行灵敏度分析.87 实验四 运输问题的 Excel 建模求解.91 实验五 目标规划问题分层 Excel 求解.96 实验六 图与网络分析. 101 实验七 网络计划的 Excel 求解. 105 实验八 动态规划的 Excel 求解. 107
课程名称:运筹学 专业:信息管理与信息系统 班级: 教师姓名 常浩娟 职称 讲师 所在院系信息学院 课程名称 运筹学 总学时 授课班级 信管11-1,2 博学楼A419, 授课地点 博学楼C205. 授课时间 [1-4,8-15周1-2节,[-24周]5-6节,7周]5-6 节,[8-15周]5-6节 信工1机房 本课程是信总管理与信息系统专业的专业基础必修课,要求学生了解线性规 课程目标 划、运输问题、整数规划、0-1规划、分配问题、目标规划、图与网络分析、计 划评审方法、动态规划的基本理论,掌握相关概念和应用,重点掌握建模和求解 方法。 教材:《运筹学基础及应用》(第五版),胡运权主编,高等教有出版社,2008: 《实用运筹学一一运用Excl建模和求解》,叶向编著,中国人民大学出版 教材及主 社,2007 参考书:《运筹学》,运筹学教材编写组,清华大学出版社,2005: 要参考书 《实用运筹学一上机实验指导及习题解答》,叶向编著,中国人民大学 出版社,2007: 《运筹学试题精选与答题技巧》徐永仁哈尔滨工业大学出版社200 章节名称 学时 第0章绪论 2学时 第一章 线性规划及单纯形法 6学时实验2学时】 第二章 线性规划的对偶理论 6学时实验2学时 第三章 运输问题 4学时实验2学时】 第四章 整数规划与分配问题 6学时实验2学时 第五章 目标规划 4学时实验2学时 第六章 图与网络分析 6学时实验2学时
课程名称:运筹学 专业:信息管理与信息系统 班级: 1 教师姓名 常浩娟 职 称 讲师 所在院系 信息学院 课程名称 运筹学 总学时 48 授课班级 信管 11-1,2 授课地点 博学楼 A419, 博学楼 C205, 信工 1 机房 授课时间 [1-4, 8-15 周]1-2 节,[1-2,4 周]5-6 节 ,[7 周]5-6 节 ,[8-15 周]5-6 节 课程目标 本课程是信息管理与信息系统专业的专业基础必修课,要求学生了解线性规 划、运输问题、整数规划、0-1 规划、分配问题、目标规划、图与网络分析、计 划评审方法、动态规划的基本理论,掌握相关概念和应用,重点掌握建模和求解 方法。 教材及主 要参考书 教材:《运筹学基础及应用》(第五版),胡运权主编,高等教育出版社,2008; 《实用运筹学——运用 Excel 建模和求解》,叶向编著,中国人民大学出版 社, 2007 参考书:《运筹学》,运筹学教材编写组,清华大学出版社,2005; 《实用运筹学——上机实验指导及习题解答》,叶向编著,中国人民大学 出版社, 2007; 《运筹学试题精选与答题技巧》 徐永仁 哈尔滨工业大学出版社 2000 章 节 名 称 学 时 第 0 章 绪论 第一章 线性规划及单纯形法 第二章 线性规划的对偶理论 第三章 运输问题 第四章 整数规划与分配问题 第五章 目标规划 第六章 图与网络分析 2 学时 6 学时(实验 2 学时) 6 学时(实验 2 学时) 4 学时(实验 2 学时) 6 学时(实验 2 学时) 4 学时(实验 2 学时) 6 学时(实验 2 学时)
课程名称:运筹学 专业:信息管理与信息系统 班级: 第七章 计划评审方法和关键路线法 6学时实验2学时 第八章动态规划 6学时实验2学时 总复习 2学时
课程名称:运筹学 专业:信息管理与信息系统 班级: 2 第七章 计划评审方法和关键路线法 第八章 动态规划 总复习 6 学时(实验 2 学时) 6 学时(实验 2 学时) 2 学时
课程名称:运筹学 专业:信息管理与信息系统 班级: 第0章绪论 章节名称 第0章绪论 课堂教学 1. 了解运筹学发展简史、运筹学的性质及特点: 2.理解运筹学的研究内容、运筹学研究的方法及步骤: 目的 3.掌握运筹学在管理中的作用。 1. 运筹学发展简史 2.运筹学的性质及特点 教学内容及 3.运筹学研究的内容 学时分配 4.运筹学研究的步骤 5.运筹学在管理中的作 (共2学时) 重点、难点 重点:运筹学研究的内容和步骤: 以及对策 难点:掌握运筹学的概念和作用及其学习方法 教学方法和 教学方式:讲授+实验 手段 教学辅助手段:教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪、黑板 作业、思考题 预习第一章第一节内容 课后记 绪论部分可以缩减到一个课时,课下要求学生上网或到图书馆查阅相
课程名称:运筹学 专业:信息管理与信息系统 班级: 3 第 0 章 绪论 章节名称 第 0 章 绪论 课堂教学 目的 1.了解运筹学发展简史、运筹学的性质及特点; 2.理解运筹学的研究内容、运筹学研究的方法及步骤; 3.掌握运筹学在管理中的作用。 教学内容及 学时分配 1.运筹学发展简史 2.运筹学的性质及特点 3.运筹学研究的内容 4.运筹学研究的步骤 5.运筹学在管理中的作 (共 2 学时) 重点、难点 以及对策 重点:运筹学研究的内容和步骤; 难点:掌握运筹学的概念和作用及其学习方法 教学方法和 手段 教学方式:讲授+实验 教学辅助手段:教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪、黑板 作业、思考题 预习第一章第一节内容 课后记 绪论部分可以缩减到一个课时,课下要求学生上网或到图书馆查阅相
课程名称:运筹学 专业:信息管理与信息系统 班级: 关资料,自主学习和了解运筹学的具体发展历史 绪论 运筹学(operations research)是用数学方法研究各类系统最优化问题的学科。运筹 学通过建立系统的数学模型并求解,为决策者制定最优决策提供科学依据。 一、运筹学简史 ①萌芽阶段(1915年~30年代) ②经验阶段(30年代~50年代) ③理论阶段(50年代~70年代) ④推广阶段(70年代一一) 二、运筹学研究的基本特征 1.系统的整体观念 2.多学科的综合 3.模型方法的应用 二、运筹学的主要分支 1、数学规划:线性规划、非线性规划、整数规划、动态规划、目标规划等6.图论 与网络分析 2.随机服务理论:排队论 3.存贮理论 4.对策论 5.决策论 6系统仿真:随机模拟技术、系统动力学 四、运筹学的工作步骤 1,提出和形成问题 2.收集资料,确定参数 3.建立模型 4.模型求解和检验 5.解的控制 五、运筹学展望 1、运筹学与系统分析相结合 2、非数学理论和方法引入运筹学 3、分析者与决策者相结合(人机对话,决策支持系统)
课程名称:运筹学 专业:信息管理与信息系统 班级: 4 绪 论 运筹学(operations research)是用数学方法研究各类系统最优化问题的学科。运筹 学通过建立系统的数学模型并求解,为决策者制定最优决策提供科学依据。 一、运筹学简史 ① 萌芽阶段 (1915 年~30 年代) ② 经验阶段 (30 年代~50 年代) ③理论阶段 (50 年代~70 年代) ④推广阶段 (70 年代——) 二、运筹学研究的基本特征 1.系统的整体观念 2.多学科的综合 3.模型方法的应用 二、运筹学的主要分支 1、数学规划:线性规划、非线性规划、整数规划、动态规划、目标规划等 6. 图论 与网络分析 2. 随机服务理论:排队论 3. 存贮理论 4. 对策论 5. 决策论 6.系统仿真:随机模拟技术、系统动力学 四、运筹学的工作步骤 1. 提出和形成问题 2. 收集资料,确定参数 3. 建立模型 4. 模型求解和检验 5. 解的控制 五、运筹学展望 1、运筹学与系统分析相结合 2、非数学理论和方法引入运筹学 3、分析者与决策者相结合(人机对话,决策支持系统) 关资料,自主学习和了解运筹学的具体发展历史
课程名称:运筹学 专业:信息管理与信息系统 班级: 第1章线性规划及单纯形法 章节名称 第1章线性规划及单纯形法 1. 理解线性规划问题的特征,会建立线性规划问题的数学模型: 课堂教学 2.掌握图解法的步骤,用图解法解极大化和极小化问题: 3. 理解线性规划数学模型解的几种情况; 目的 4.理解单纯形法的解题思想和基本原理: 5.掌握单纯形解法和大M法。 1.线性规划问题及其数学模型 教学内容及 2.线性规划数学模型的图解法 学时分配 3.线性规划的单纯形法 (共6学时) 重点、难点 重点:线性规划问题的特征、数学模型,线性规划数学模型的图解法 以及对策 及解的几种情况,单纯形法的基本原理、单纯形解法和大M法。 难点:建模,线性规划数学模型解的性质,单纯形法的基本原理 教学方法和 教学方式:讲授+实验 手段 教学辅助手段:教具、板书、现代教学设施设备 数 冷 多媒体计算机、投影仪、黑板 作业、思考题 P47课后习题1.1、1.3、1.6、1.7、1.13、1.14 课后记 单纯形法的原理要讲清楚,不能简单介绍方法。模型要结合实际应用 5
课程名称:运筹学 专业:信息管理与信息系统 班级: 5 第 1 章 线性规划及单纯形法 章节名称 第 1 章 线性规划及单纯形法 课堂教学 目的 1.理解线性规划问题的特征,会建立线性规划问题的数学模型; 2.掌握图解法的步骤,用图解法解极大化和极小化问题; 3.理解线性规划数学模型解的几种情况; 4.理解单纯形法的解题思想和基本原理; 5.掌握单纯形解法和大 M 法。 教学内容及 学时分配 1.线性规划问题及其数学模型 2.线性规划数学模型的图解法 3.线性规划的单纯形法 (共 6 学时) 重点、难点 以及对策 重点:线性规划问题的特征、数学模型,线性规划数学模型的图解法 及解的几种情况,单纯形法的基本原理、单纯形解法和大 M 法。 难点:建模,线性规划数学模型解的性质,单纯形法的基本原理 教学方法和 手段 教学方式:讲授+实验 教学辅助手段:教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪、黑板 作业、思考题 P47 课后习题 1.1、1.3、1.6、1.7 、1.13、1.14 课后记 单纯形法的原理要讲清楚,不能简单介绍方法。模型要结合实际应用
课程名称:运筹学 专业:信息管理与信息系统 班级: 问题的分析 第一章线性规划及单纯形法 §1一般线性规划问题的数学模型 1、规划问题 生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用 获得最大的效益,这就是规划问题。 线性规划通常解决下列两类问题: (1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、 设备、原标材料、人工、时间等)去完成确定的任务或目标 (2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品 量最多、利润最大)》 2、线性规划数学模型三要素:决策变量(Decision variables),目标函数(Objective function),约束条件(Constraints) 3、建模条件 (①)优化条件:问题所要达到的目标能用线型函数描述,且能够用极值,用max或 min来表示: (2)限定条件:达到目标受到一定的限制,且这些限制能够用决策变量的线性等式 或线性不等式表示: (3)选择条件:有多种可选择的方案供决策者选择,以便找出最优方案。 4.建模步骤 ()确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目问什么就 设什么为决策变量: (2)找出所有限定条件:即决策变量受到的所有的约束: (仔)写出目标函数:即问题所要达到的目标,并明确是max还是min 5.线性规划数学模型的一般形式 例1.3某厂生产两种产品,下表给出了单位产品所需资源及单位产品利润。问如何 安排生产才能使利润最大?或如何考虑利润大,产品好销。 解: 1决策变量:设产品1、Ⅱ的产量分别为x1、2 2.目标函数:设总利润为2,则有:maxz=2x+边 、设备 产品 A B 利润(元) 0 2 2 0 有效台时1281612
课程名称:运筹学 专业:信息管理与信息系统 班级: 6 第一章 线性规划及单纯形法 §1 一般线性规划问题的数学模型 1、规划问题 生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用, 获得最大的效益,这就是规划问题。 线性规划通常解决下列两类问题: (1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源 (如资金、 设备、原标材料、人工、时间等)去完成确定的任务或目标 (2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品 量最多 、利润最大.) 2、线性规划数学模型三要素:决策变量(Decision variables),目标函数(Objective function),约束条件(Constraints) 3、建模条件 (1) 优化条件:问题所要达到的目标能用线型函数描述,且能够用极值,用 max 或 min 来表示; (2) 限定条件:达到目标受到一定的限制,且这些限制能够用决策变量的线性等式 或线性不等式表示; (3) 选择条件:有多种可选择的方案供决策者选择,以便找出最优方案。 4. 建模步骤 (1) 确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目问什么就 设什么为决策变量; (2) 找出所有限定条件:即决策变量受到的所有的约束; (3) 写出目标函数:即问题所要达到的目标,并明确是 max 还是 min。 5. 线性规划数学模型的一般形式 例 1.3 某厂生产两种产品,下表给出了单位产品所需资源及单位产品利润。问如何 安排生产才能使利润最大?或如何考虑利润大,产品好销。 解: 1.决策变量:设产品 I、II 的产量分别为 x1、x2 2.目标函数:设总利润为 z,则有: max z = 2 x1 + x2 产品 A B C D 利润(元) Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有效台时 12 8 16 12 问题的分析。 设备
课程名称:运筹学 专业:信息管理与信息系统 班级: 3.约束条件: max :=2x+3x 2x+2x2≤12 l+2x2≤8 4x≤16 4x≤12 x,3,20 (以线性规划数学模型的特点: 1)每个行动方案可用一组变量(1,.,x)的值表示,这些变量一般取非负值: 2)变量的变化要受某些限制,这些限制条件用一些线性等式或不等式表示: 3)有一个需要优化的目标,它也是变量的线性函数。 具备以上三个特点的数学模型称为线性规划(Linear Programming,简记为LP),一 般形式为: max(min)2=cx1+cx2++cnx。 [ax1+a2x2+.+anxn≤(=,2)b a2X1+a2x2+.+a2nxn≤(=,≥b2 am1+a2x2+.+4un≤(=,≥)bn x,x2,.xn20 采用求和符号Σ,可以简写为: max(min) :=2 i=l,2,.,m x,20 j=1,2.,n (2)、线性规划问题的数学模型向量形式: (min):=CX .a 其中: C=(c,c.c) x
课程名称:运筹学 专业:信息管理与信息系统 班级: 7 3.约束条件: 1 2 1 2 1 2 1 2 1 2 max 2 3 2 2 12 1 2 8 4 16 4 12 , , 0 z x x x x x x x x x x = + + + (1)、线性规划数学模型的特点: 1)每个行动方案可用一组变量(x1,.,xn)的值表示,这些变量一般取非负值; 2)变量的变化要受某些限制,这些限制条件用一些线性等式或不等式表示; 3)有一个需要优化的目标,它也是变量的线性函数。 具备以上三个特点的数学模型称为线性规划(Linear Programming,简记为 LP),一 般形式为: + + + = + + + = + + + = = + + + , , 0 ( , ) ( , ) ( , ) max(min) 1 2 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 1 1 2 2 n m m mn n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b z c x c x c x 采用求和符号Σ,可以简写为: = = = = = = x j n a x b i m z c x j i n j i j j n j j j 0 1,2, , ( , ) 1,2, , max(min) 1 1 (2)、线性规划问题的数学模型向量形式: = = 0 ( ) max (min) X p x B z CX j j 其中: ( ) C = c1 c2 c n = m b b B 1 , = mj j j a a P 1 , = n x x X 1
课程名称:运筹学 专业:信息管理与信息系统 班级: (3)、线性规划问题的数学模型矩阵形式: max (min)Z=CX 「AX≤(=·≥)B x≥0 其中: C=(c,c2.cn) 6.线性规划问题的标准形式 mxx Z=Ecx, i=12,m 520,j=1,2,n 特点: ()目标函数求最大值(有时求最小值) (2)约束条件都为等式方程,且右端常数项b:都大于或等于零 (3)决策变量x为非负。 7,将线性规划的普通型化为标准型 (1)对于minZ=CX,可转化为min(-Z=CX: (2)当约束条件中出现a+a22++anx,≤b,时,在左边加上一个“松驰变 量”x≥0,使不等式变为等式:当约束条件中出现aax+a2x2+.+awx。之b 时,则在左边减去一个“松弛变量”x之0: (3)当某个决策变量x,∠0或符号不限时,则增加两个决策变量x,和x,令 (4)当约束条件中有常数项b,∠0时,则在方程两边同乘以(-1)。 例1.6将下列非标准型线性规划问题转化为标准型。 minZ=3x,-2x,+4x. [2x+3x2+4x2300 5r5+5x+6ss400 ++x3≤200 ,≥0,x不限 解
课程名称:运筹学 专业:信息管理与信息系统 班级: 8 (3)、线性规划问题的数学模型矩阵形式: = = 0 ( ) max (min) X AX B Z CX 其中: ( ) C = c1 c2 c n = m b b B 1 , = m m n n a a a a A 1 1 1 1 , = n x x X 1 6. 线性规划问题的标准形式 i m x j n a x b s t Z c x j n j ij j i n j j j 1,2, , 0, 1,2, , . max 1 1 = = = = = = 特点: (1) 目标函数求最大值(有时求最小值) (2) 约束条件都为等式方程,且右端常数项 bi 都大于或等于零 (3) 决策变量 xj 为非负。 7.将线性规划的普通型化为标准型 (1)对于 minZ=CX,可转化为 min(-Z)=-CX ; (2)当约束条件中出现 i i in n bi a 1 x1 + a 2 x2 ++ a x 时,在左边加上一个“松弛变 量” xi+1 0 ,使不等式变为等式;当约束条件中出现 i i in n bi a 1 x1 + a 2 x2 ++ a x 时,则在左边减去一个“松弛变量” xi+1 0 ; (3)当某个决策变量 x j0 或符号不限时,则增加两个决策变量 ' j x 和 '' j x ,令 ' '' j j j x = x − x ; (4)当约束条件中有常数项 bi0 时,则在方程两边同乘以(-1)。 例 1.6 将下列非标准型线性规划问题转化为标准型。 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 min 3 2 4 2 3 4 300 5 6 400 . . 200 , 0, Z x x x x x x x x x s t x x x x x x = − + + + + + + + 不限 解: