2022年第二章线性规划与单纯形法 .pdf

6 工程运筹学（教案）课程名称：工程运筹学适用专业：交通运输、农业工程、环境工程等适用年级：二年级学年学期：学年第一学期任课教师：赵秀荣编写时间：2005年 9 月（2010 年 3 月修改）名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 19 页 -7 教案部分第一章绪论本章教学目标：通过本章的学习，了解运筹学的简史、性质和特点，运筹学的工作步骤，运筹学的应用范围及运筹学的学习方法等。本章教学基本要求：（1）了解运筹学的简史、性质和特点（2）掌握运筹学的工作步骤（3）了解运筹学模型的分类（4）了解运筹学的应用范围及运筹学的学习方法等本章各节的教学内容与学时分配:1.1 运筹学简史1.2 运筹学性质和特点1.3 运筹学的工作步骤1.4 运筹学的模型与模型化1.5 运筹学的应用1.6 运筹学的学习方法授课学时：2 学时本章教学重点：（1）运筹学的工作步骤；（2）运筹学的学习方法本章教学内容的深化和拓宽：运筹学的模型与模型化本章教学方式：多媒体本章教学过程中应注意的问题：激发学生学习运筹学的兴趣本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章思考题：举例说明图解模型、相似模型、原样模型、数学模型第一章绪论：2 学时教学方式与手段：多媒体讲课提纲：(注：非多媒体情况下使用)教学内容：1.1 运筹学简史1914 年，军事运筹学家兰彻斯特（Lanchester）提出战斗方程1917 年丹麦工程师爱尔朗（Erlang）在哥本哈根电话公司研究电话通讯系统时提出排名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 19 页 -8 队论的一些著名公式20 世纪 30 年代已有运用运筹思想分析商业广告、顾客心理等。1947 年丹捷格（G.B.Dantzig）发表线性规划的成果，提出了单纯形法。1944 年冯诺依曼和摩根斯坦（O.Morgenstern）合著对策论与经济行为1948 年英国建立运筹学会，美国1952 年、法国1956 年、日本1957 年等。1959 年由英、美、法三国的运筹学会发起成立国际运筹学联合会（IFORS）,1980 年，我国成立运筹学会，我国1982 年加入（IFORS）。1976 年，欧洲运筹学会（EURO）成立。1985 年，亚太运筹学协会（APORS）成立。1.2 运筹学性质和特点一、运筹学的性质：运筹学是一门应用科学。二、运筹学的特点：学科发展时间短，给运筹学下定义较多1.3 运筹学的工作步骤（1）提出和形成问题（2）建立模型（3）求解（4）解的检验（5）解的控制（6）解的实施1.4 运筹学的模型与模型化一、模型分类（1）图解模型（2）相似模型（3）原样模型（4）数学模型二、构模的方法和思路（1）直接分析法（2）类比法（3）数据分析法（4）试验分析法（5）想定（构想）法1.5 运筹学的应用（1）市场营销（2）生产计划（3）库存管理（4）运输问题（5）财政和会计（6）人事管理（7）设备更新、维修和可靠性、项目选择和评价（8）工程的优化设计（9）计算机和信息系统（10）城市管理1.6 运筹学的学习方法（1）理解、掌握基本理论和方法的基础上，适当作些习题名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 19 页 -9（2）在建数学模型时，要结合实际应用。教案部分第二章线性规划与单纯形法本章教学目标：通过本章学习，掌握线性规划解题的一般方法图解法，单纯形法以及用计算机解决复杂线性规划问题的方法，并要求能用线性规划的理论解决生产实际中的问题。本章教学基本要求：（1）掌握线性规划模型的相关概念（2）熟悉线性规划模型的一般形式与标准形式（3）理解线性规划的图解法（4）掌握单纯形法（5）熟悉大M法、人工变量法（6）学会建立线性规划模型的技巧与方法（7）掌握线性规划模型的计算机求解方法本章各节的教学内容与学时分配:第二章线性规划（理论 8 学时，实验2 学时）2.1 线性规划问题；2.2 线性规划的图解法（2 学时）2.3 线性规划模型的标准形式；2.4 线性规划解的概念；2.5 线性规划的几何意义（2 学时）2.6 单 纯 形 法；2.7 单纯形法的进一步讨论（2 学时）2.8 线性规划问题应用（建模技巧）（2 学时）本章教学重点：教学重点：（1）线性规划应用及其数学模型、应用实例。（2）线性规划的标准形式及变换方法。（3）线性规划的图解法（4）线性规划的基本性质（5）单纯形法（6）单纯形法的进一步讨论人工变量法（7）应用题例（建模技巧）实验：线性规划问题的计算机应用本章教学内容的深化和拓宽：大 M法、两阶段法、退化与循环本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题本章教学过程中应注意的问题：需引入人工变量的线性规划模型及其求解方法本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 19 页 -10 本章作业与思考题：思考题：某农场有300 公顷土地及50000 元资金可用于发展生产。农场劳动力情况为秋冬季3500 人日，春夏季 4000 人日。各季劳动力本场用不了时可外出干活，春夏季外出干活收入为10 元/人日，秋冬季外出干活收入为8 元/人日。该农场种植三种作物：大豆、玉米、小麦并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛需投资2000 元，每只鸡需投资3 元。养奶牛时每头需拨出 1。5 公顷土地种饲草，并占用人工春夏季50 人日，秋冬季为100 人日，年净收入500 元/每头奶牛。养鸡不占用土地，但需人工为：每只鸡秋冬季需0。6 人日，春夏季为0。3 人日，年净收入 2 元/每只鸡。农场现有鸡舍最多允许养3000 只鸡，牛栏允许最多养60 头奶牛。三种作物每年需要的人工及收入情况见表4，现需确定该农场的经营方案，使年净收入为最大。试建立该问题的线性规划数学模型。(20 分)表 4：大豆玉米小麦秋冬季需人日数（人日/公顷）20 35 10 春夏季需人日数（人日/公顷）50 75 40 年净收入（元/公顷）300 550 480 作业题：分别用大 M法和两阶段法下面线性规划问题，并指出属哪一类解0,521515659351215x10max321321321321321xxxxxxxxxxxxxxz名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 19 页 -11 教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)第二章线性规划与单纯形法：8 学时2.1 线性规划问题2.1.1 线性规划问题的数学模型2.2 线性规划问题的图解法2.2.1 无穷多最优解（多重最优解）2.2.2 无可行解2.2.3 无有限最优解（无界解）2.3 线性规划问题的标准型2.3.1 普通标准型nnxcxcxcz2211max02122112222212111112111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa、2.3.2 矩阵型标准形式0maxXbAXCXz其中，TnxxxX21，。2.3.3 向量型标准形式）（njxbxaxczjinjjijnjjj,2,10max112.4 线性规划解的概念2.4.1 可行解、可行域、最优解；2.4.2 基、基本解、基本可行解、基变量、非基变量2.5 线性规划问题的几何意义2.5.1 基本概念名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 19 页 -12 凸集、凸组合、顶点2.5.2 基本定理2.6 单纯形法2.6.1 确定初始基可行解2.6.2 最优性检验2.6.3 单纯形表与（L,K）旋转变换(1)单纯形表(2)基的变换（L,K）旋转变换(3)大 M法2.7 单纯形法的进一步讨论2.7.1 两阶段法2.7.2 退化与循环2.8 线性规划应用举例生产计划问题套裁下料问题生产配套问题投资问题第三章线性规划的对偶理论及灵敏度分析本章教学目标：通过本章学习，掌握对偶问题与原问题关系及对偶单纯形法，了解影子价格和灵敏度在实际中的应用与分析。本章教学基本要求：本章各节的教学内容与学时分配:第三章线性规划的对偶理论及灵敏度分析（理论 6 学时）3.1 线性规划对偶问题；3.2 对偶单纯形法（2 学时）3.3 影子价格；3.4 灵敏度分析（2学时）3.4 灵敏度分析（2学时）本章教学重点：（1）对偶问题（2）线性规划的对偶理论（3）影子价格（4）对偶单纯形法（5）灵敏度分析名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 19 页 -13（6）应用案例本章教学内容的深化和拓宽：影子价格的经济含义，灵敏度分析本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题本章教学过程中应注意的问题：本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 19 页 -14 教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)第三章线性规划的对偶理论及灵敏度分析（6 学时）3.1 线性规划对偶问题3.1.1 引例3.1.2 对欧理论3.2 对偶单纯形法3.3 影子价格3.4 灵敏度分析3.4.1 目标函数中价值系数C的灵敏度分析（1）基变量价值系数的灵敏度分析（2）非基变量价值系数的灵敏度分析3.4.2 资源系数 b 的分析3.4.3 系数矩阵 A的分析（1）增加一个新变量的分析（2）增加一个新约束条件的分析（3）改变某非基变量的系数列向量分析（4）改变某基变量系数列向量的分析名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 19 页 -15 第四章运输问题本章教学目标：通过本章学习，掌握建立运输问题数学模型的方法以及表上作业法，掌握利用计算机解决运输问题应用问题的方法。本章教学基本要求：熟悉 运输问题的数学模型，掌握表上作业法求解运输问题熟悉产销不平衡的运输问题及其求解方法。本章各节的教学内容与学时分配:第四章运输问题（理论 5 学时，实验2 学时）4.1 运输问题的数学模型；4.2 表上作业法（2 学时）4.2 表上作业法；4.3 产销不平衡的运输问题及其求解方法（2 学时）4.4（运输问题应用题例（1 学时）本章教学重点：（1）运输问题的数学模型（2）表上作业法及其应用。（3）产销不平衡的运输问题及其求解方法。（4）应用案例。本章教学内容的深化和拓宽：伏格尔法本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题本章教学过程中应注意的问题：本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：教学方式与手段：多媒体课件与板书有机结合名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 19 页 -16 教学内容讲课提纲：(注：主要用于非多媒体情况下)4.1 运输问题的数学模型4.2 表上作业法4.2.1 确定初始调运方案（1）最小元素法（2）西北角法（3）伏格尔法4.2.2 最优性检验（1）闭回路法：（2）位势法4.2.3 闭回路调整法（确定最优方案）（1）取0|minijijlk对应的非基变量为换入变量。（2）以空格(L,K)为第一顶点，作一闭回路。（3）闭回路上偶序号顶点的运量均减去最小运量，奇数序号顶点的运量均加上，不在闭回路上的运量不变。4.3 产销不平衡问题及其求解方法4.3.1产大于销的问题4.3.2 销量大于产量问题第五章目标规划名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 19 页 -17 本章教学目标：通过本章学习，了解目标规划数学模型及目标规划单纯形法，掌握利用计算机解决目标规划应用问题的方法。本章教学基本要求：本章各节的教学内容与学时分配:第五章目标规划（理论 3 学时）51 目标规划的数学模型；52 目标规划的图解法。（2 学时）53 目标规划的单纯形解法（1 学时）本章教学重点：目标规划的数学模型本章教学内容的深化和拓宽：目标规划的图解法、单纯形法本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题本章教学过程中应注意的问题：图解法、正负偏差变量的引入本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 19 页 -18 教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)第五章目标规划5.1 目标规划数学模型5.1.1 偏差变量5.1.2 绝对约束 和目标约束5.1.3 优先因子5.1.4 目标规划的目标函数5.2 目标规划的图解法5.3 目标规划的单纯形法第六章整数规划本章教学目标：通过本章学习，了解整数规划问题及分枝定界法，掌握指派问题的解法，掌握整数规划问题的计算机解法。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 19 页 -19 本章教学基本要求：本章教学环节包括：课堂讲授、习题课、课外作业、实验。通过各个教学环节的教学，培养学生的自学能力、分析思考问题及解决问题的能力；重点培养数学建模及计算机应用求解与分析的能力。本章各节的教学内容与学时分配:61 整数规划问题；62 分枝定界法（2学时）63 0-1 整数规划；64 指派问题。（2 学时）实验：整数规划中指派问题的计算机求解。（2学时）本章教学重点：（1）分枝定界法（2）0-1 整数规划（3）指派问题（4）实验：指派问题的计算机求解本章教学内容的深化和拓宽：本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题采用启发式教学，鼓励学生课前自学、课后复习及做作业。培养学生的自学能力，以“少而精”为原则，精选教学内容，精讲多练。增加习题课，注重应用尤其是计算机解题应用，充分调动学生学习的主观能动性。本章教学过程中应注意的问题：本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)第六章 整数规划名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 19 页 -20 6.1 整数规划数学模型6.2 分枝定界法（Branch and Bound Method）6.3“01 型”整数规划的解法6.3.1“01 型”整数规划模型6.3.2 隐枚举法6.4 指派问题6.4.1 指派问题的数学模型6.4.2 指派问题的最优性质6.4.3 指派问题解法（匈牙利指派法）（1）变换效率矩阵，使各行各列都出现0 元素：（2）进行试指派，即找出不同行且不同列的0 元素：（3）：用最少直线覆盖效率矩阵中的0 元素：（4）调整效率矩阵，是出现新的0 元素：6.4.3 指派问题扩展第七章动态规划本章教学目标：通过本章学习，了解多阶段决策问题及动态规划的基本名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 19 页 -21 概念和基本方程，掌握和了解动态应用问题，资源分配问题，复合系统工作可靠性问题，设备更新问题。本章教学基本要求：本章教学环节包括：课堂讲授、课堂讨论，培养学生的自学能力、分析思考问题及解决问题的能力。本章各节的教学内容与学时分配:7.1 多阶段决策问题；7.2 动态规划的基本概念和最优性原理（2 学时）7.3 建立动态规划数学模型的步骤；7.4 动态规划应用举例；7.4.1 资源分配问题；7.4.2 符合系统工作可靠性问题（2 学时）7.4.3 设备更新问题；7.4.4 排序问题（2 学时）本章教学重点：（1）多阶段决策过程（2）动态规划的基本概念和基本方程（3）资源分配问题（4）复合系统工作可靠性问题（5）排序问题（6）设备更新问题本章教学内容的深化和拓宽：本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题采用启发式教学，鼓励学生课前自学、课后复习及做作业。培养学生的自学能力，以“少而精”为原则，精选教学内容，精讲多练。增加习题课，注重应用尤其是计算机解题应用，充分调动学生学习的主观能动性。本章教学过程中应注意的问题：本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 19 页 -22 教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)第七章动态规划7.1 多阶段决策问题7.2 动态规划的基本概念和最优性原理7.2.1 动态规划基本概念（1）阶段：（2）状态（3）决策（4）状态转移方程（5）策略（6）指标函数7.2.2 最优性原理和动态规划递推方程（1）最优性原理（2）递推方程)1,1,(,111nnkCxfuxTfxuxroptxfnnkkkkkkkkk7.3 建立动态规划数学模型的步骤7.4 动态规划应用举例7.4.1 资源分配问题（1）一维资源分配问题7.4.2 符合系统工作可靠性问题7.4.3 设备更新问题7.4.4 排序问题名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 19 页 -23 第八章动态规划本章教学目标：通过本章学习，了解各种排队系统的统计规律性，掌握对长分布、等待时间分布和忙期分布规律。本章教学基本要求：本章教学环节包括：课堂讲授、课堂讨论，作业。培养学生分析思考问题及解决问题的能力。本章各节的教学内容与学时分配:8.1 前言；8.2 基 本 概 念（2 学时）8.3 输入过程和服务时间分布；8.4 泊松输入负指数服务排队模型（2学时）8.5 系统容量有限制的情形（)/1/(NMM）；8.6 多服务台指数分布排队系统分析（2 学时）本章教学重点：（1）基本概念；（2）排队论中常用几种理论分布；（3）单服务台负指数分布排队系统分析；（4）多服务台负指数分布排队系统分析；（5）排队系统的优化及应用。本章教学内容的深化和拓宽：系统容量有限、顾客源有限的排队特征本章教学方式：多媒体与板书有机结合、与学生互动讨论分析实际问题采用启发式教学，鼓励学生课前自学、课后复习及做作业。本章教学过程中应注意的问题：型系统的比较个型系统和1/MMcCMM本章主要参考书目：1 甘应爱主编.2007 年.运筹学.北京：清华大学出版社2 吴祈宗主编.运筹学.机械工业出版社，2002本章作业与思考题：名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 19 页 -24 教学方式与手段：多媒体课件与板书有机结合教学内容讲课提纲：(注：主要用于非多媒体情况下)8.1 前言8.2 基 本 概 念8.2.1 系统特征和基本排队过程 (1)有请求服务的人或物顾客；(2)有为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时刻是随机的8.2.2 排队系统的基本组成部分 1输入过程2.服务规则到 3服务台情况。8.2.3 排队系统的描述符号与分类8.2.4 排队系统的主要数量指标 (1)队长和排队长（队列长）(2)等待时间和逗留时间8.2.5 一些数量指标的常用记号8.3 输入过程和服务时间分布8.3.1 输入过程 (1)定长输入。(2)泊松(poisson)输入(3)爱尔朗输入(4)一般独立输入(5)成批到达的输入8.3.2 到达时间间隔分布8.3.3 排队论研究的基本问题8-4 泊松输入负指数服务排队模型8.5 系统容量有限制的情形（)/1/(NMM）8.6 多服务台指数分布排队系统分析8.6.1 CMM/模型8.6.2 型系统的比较个型系统和1/MMcCMM名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 19 页 -