运筹学教案（胡运权版）

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业授课题目 ： 绪论教学目的与要求： 1.知识目标：掌握运筹学的概念和作用及其学习方法 2.能力目标：掌握运筹学的数学模型 3.素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：运筹学的数学模型教学难点： 运筹学的数学模型教学过程： 1.举例引入（ 5分钟）2.新课 （60分钟）（1）举例引入，绪论（30分钟）（2）运筹学与管理学（30分钟）3.课堂练习（20分钟）4.课堂小结（5分钟）5.布置作业绪论（2课时）【教学流程图】举例引入，绪论 运筹学运筹学与数学模型的

2、基本概念 管理学 课堂练习 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入：（5分钟）（1）齐王赛马的故事 （2）两个囚犯的故事 导入提问：什么叫运筹学？（二） 新课： 绪 论一、运筹学的基本

3、概念（用实例引入）例1-1 战国初期，齐国的国王要求田忌和他赛马，规定各人从自己的上马、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支付一千两银子给予获胜者。当时齐王的马比田忌的马强，结果每年田忌都要输掉三千两银子。但孙膑给田忌出主意，可使田忌反输为赢。试问：如果双方都不对自己的策略保密，当齐王先行动时，哪一方会赢？赢多少？反之呢？例1-2 有甲乙两个囚犯正被隔离审讯，若两人都坦白，则每人判入狱8年；若两个人都抵赖，则每人判入狱1年；若只有一人坦白，则他初释放，但另一罪犯被判刑10年。求双方的最优策略。 乙囚犯 抵赖 坦白 甲囚犯 抵赖 -1，-1 -10，0 坦白 0，-10 -8，

4、-8定义：运筹学（Operation Research）是运用系统化的方法，通过建成立数学模型及其测试，协助达成最佳决策的一门科学。它主要研究经济活动和军事活动中能用数学的分析和运算来有效地配置人力、物力、财力等筹划和管理方面的问题。二、学习运筹学的方法1、读懂教材上的文字；2、多练习做题，多动脑筋思考； 3、作业8次；4、考试；5、ERCEL操作与手动操作结合。二、学生练习 （20分钟）三、课堂小结（5分钟）授课题目 ： 第一章 线性规划及单纯形法第一节：线性规划问题及数学模型。教学目的与要求： 1.知识目标：掌握线性规划的基本概念和两种基本建模方法。2.能力目标：掌握线性规划建模的标准形式

5、及将普通模型化为标准模型的方法。要求学生完成P43习题1.2两个小题。3.素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、线性规划的基本概念和两种基本建模方法；2、线性规划建模的标准形式及将普通模型化为标准模型的方法。教学难点： 1、线性规划的两种基本建模方法； 2、将线性规划模型的普通形式化为标准形式。教学过程： 1.举例引入（ 5分钟）2.新课 （60分钟）（1）运筹学与线性规划的基本概念（20分钟）（2）结合例题讲解线性规划标准型的转化方法（20分钟）3.课堂练习（20分钟）4.课堂小结（5分钟）5.布置作业线性规划及单纯形法（2课时）【教学流程图】 运筹学运筹学与线性规划的

6、基本概念 线性规划（结合例题讲解） 线性规划的标准型 目标函数结合例题讲解线性规划标准型的转化方法 约束条件的右端常数 约束条件为不等式 课堂练习 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程： 第一

7、章 线性规划及单纯形法第一节 线性规划问题及其数学模型（用实例引入）例1-3 美佳公司计划制造、两种产品，现已知各制造一件时分别占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应制造两种家电各多少件时才能使获取的利润最大？ 生产1件产品生产1件产品每天可用能力（小时）设备A（台时）设备B（台时）调试 （小时） 0 6 1 5 2 1 15 24 5利润（元） 2 1 例1-4 有A、B、C三个工地，每天需要水泥各为17、18、15百袋。为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地。其单位运价如下表，求最佳调运方案。 工地水泥厂 ABC 甲 1 15 2 乙 2

8、4 2 工地水泥厂A B C供应量/百袋 甲 23 乙 27需求量/百袋 17 18 1550 线性规划的基本概念如果规划问题的数学模型中，决策变量的取值是连续的整数、小数、分数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则称这种规划问题为线性规划。将线性规划的普通型化为标准型对于minZ=CR,可转化为min(-Z)=-CR ；当约束条件中出现时，在左边加上一个“松弛变量”，使不等式变为等式；当约束条件中出现时，则在左边减去一个“松弛变量”。当某个决策变量或符号不限时，则增加两个决策变量和，令；当约束条件中有常数项时，则在方程两边同乘以（-1）。例1-5 将

9、下列非标准4型线性规划问题转化为标准型。 解：学生练习：P42习题1.2。二、学生练习 （20分钟）三、课堂小结（5分钟）授课题目 ： 第二节 图解法单纯形法原理教学目的与要求： 1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念；2.能力目标：掌握用图解法和单纯形法求解线性规划的原理；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、用图解法求解线性规划的计算步骤；2、用单纯形法求解线性规划的计算步骤。教学难点： 用单纯形法求解线性规划的计算原理； 教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟）（1）图解法（40分钟）（2）单纯形法原理（40分

10、钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一。线性规划的求解（2课时）【教学流程图】以学生自学引入 图解法线性规划求解方法介绍 单纯形法 ERCEL规划求解法 坐标系图解法的操作步骤 求出可行域 平移目标函数直线 化为标准型单纯形法的原理 迭代法 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提

11、高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入：（5分钟） 复习中学数学中的图解法。 导入提问：线性规划图解法中有哪些基本概念？（二） 新课： 第二节 图解法一、图解法的步骤（以学生自学引入）学生自学P16-17，教师检查看不懂文字的学生，并做好记录。提问：以P44的1.4题第1小题为例，图解法第一步是什么？以下逐步提出问题。 教师演示并总结如下：图解法适用于两个决策变量的线性规划非标准型。步骤如下；用决策变量建立直角坐标系；对于每一个约束条件，先取

12、等式画出直线，然后取一已知点（一般取原点）的坐标代入该直线方程的左边，由其值是否满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域。令Z等于任一常数，画出目标函数的直线，平移该直线，直至它与凸多边形可行域最右边的角点相切，切点坐标则为最优解。例1-5解 G（1，1.5）可行解满足约束条件的解，全部可行解的集合叫可行域。最优解使目标函数达到最大值的可行解。基变量利用矩阵的初等变换从约束条件的mn(nm)阶系数矩阵找出一个mm阶单位子矩阵，它们对应的变量叫基变量，其余的叫非基变量。矩阵的初等变换将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。4.课堂小结（

13、5分钟）5.布置作业：要求学生完成P43习题1.3两个小题。授课题目 ： 单纯法的计算步骤教学目的与要求： 1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念；2.能力目标：掌握用单纯形法求解线性规划的计算步骤；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：用单纯形法求解线性规划的计算步骤。教学难点： 1、用单纯形法求解线性规划的计算原理； 2、用单纯形法求解线性规划的计算步骤。教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟）单纯形法求解步骤3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）5.布置作业：要求学生完成P43习题1.4两个小题

14、。其中第1小题为作业一。第四节单纯法的计算步骤（2课时）【教学流程图】以学生自学引入 图解法线性规划求解方法介绍 单纯形法 ERCEL规划求解法 化为标准型单纯形法的操作步骤 求出初始表 迭代法 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理

15、想的教学效果。【教学内容】一 、教学过程：举例引入：（5分钟） 复习中学数学中的图解法。 导入提问：线性规划图解法中有哪些基本概念？新课：一、三个基本定理可行解满足约束条件的解，全部可行解的集合叫可行域。最优解使目标函数达到最大值的可行解。基变量利用矩阵的初等变换从约束条件的mn(nm)阶系数矩阵找出一个mm阶单位子矩阵，它们对应的变量叫基变量，其余的叫非基变量。矩阵的初等变换将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。单纯形表迭代法 教师先演示：化为标准型 做出初始单纯形表，求出检验数；确定检验数中最大正数所在的列为主元列，选择主元列所对应的非基变量为进基变量按最

16、小比值原则，用常数列各数除以主元列相对应的正商数，取其最小比值，该比值所在的行为主元行；主元列与主元行交叉的元素为主元，主元所对应的基变量为出基变量。对含常数列的增广矩阵用初等变换把主元变为1，主元所在的列的其余元素化为0。计算检验数，直到全部检验数小于等于0，迭代终止。基变量对应的常数列为最优解，代入目标函数得最优目标函数值。例1-6 解：先化为标准型： s.t. 其约束条件的系数增广矩阵为 0 5 1 0 0 15 6 2 0 1 0 24 1 1 0 0 1 5初始始基可行解为：，以此列出单纯形表如下。得：，代入目标函数得：Z=2R7/2+1R3/2+15/2R0+0R0=17/2。目标

17、函数2 1 0 0 0常数 决策变量基变量 初始表0000 5 1 0 0 6 2 0 1 0 1 1 0 0 1 15 24 5计算0 0 0 0 02 1 0 0 0第一次迭代0200 5 1 0 01 1/3 0 1/6 00 2/3 0 -1/6 1 15 4 12 2/3 0 1/3 00 1/3 0 -1/3 0 第二次迭代0210 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/22 1 0 1/4 1/2 0 0 0 -1/4 -1/24.课堂小结（5分钟）5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题

18、为作业一授课题目 ： 第五节 单纯形法的进一步讨论教学目的与要求： 1.知识目标：理解求解线性规划的人工变量法中大M法和两阶段法；2.能力目标：利用习题1.15巩固线性规划的建模；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、求解线性规划的人工变量法中两阶段法的计算步骤。2、人工变量法与普通单纯形法的区别。教学难点： 1、两阶段法的计算步骤； 2、习题1.15中的约束条件分析。教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟）（1）人工变量法（40分钟）（2）两阶段法（40分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结与单纯形法小结（5分钟）5布置作

19、业。单纯形法的进一步讨论（2课时）【教学流程图】用实例引入人工变量法 初始单纯形表中无单位矩阵人工变量法的例题讲解 引入人工变量 在目标函数中引入大M 两阶段法用ERCEL求解中的困难两阶段法的例题讲解 第一阶段的模型 第二阶段的模型 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳

20、动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入：（5分钟） 复习单纯形法。 导入提问：当初始单纯形表中不出现单位矩阵怎么办？（二） 新课： 单纯形法的进一步讨论（用实例引入人工变量法）例1-7 用单纯形法求解下列线性规划问题：解：将第二个约束条件化为等式（左边减去一个松弛变量）后，约束条件的系数矩阵不存在单位矩阵，这时可在约束条件第一、二等式的左边分别加上一个人工变量作为初始基变量，使之出现单位矩阵。为了使目标函数中的人工变量为0，令它们的系数为任意大的负值“-M”，然后采用一般单纯形表法求解。目标函数2 3 -5 -M 0 -M常数 决策变量基变量

21、 初始表-M-M1 1 1 1 0 02 -5 1 0 -1 1 7 10计算-3M 4M -2M -M M -M3M+2 3-4M 2M-5 0 -M 0 一次迭代-M20 7/2 1/2 1 1/2 -1/21 -5/2 1/2 0 -1/2 1/2 2 52 -M 0 0 320 1 1/7 2/7 1/7 -1/71 0 6/7 5/7 -1/7 1/74/745/72 3 15/7 16/7 1/7 -1/7 0 0 -50/7 -M-16/7 -1/7 -M+1/7所以最优解为：R=（45/7，4/7，0，0，0，0）例1-8 对LP模型： s.t. 用两阶段法求解。解：先分为标准

22、型： s.t. 对 s.t. 使用单纯形法求解，化为标准型后，列出单纯形表并迭代如下目标函数0 0 0 0 0 -1 -1常数 决策变量基变量 初始表-1-10 6 1 -1 0 1 05 2 1 0 -1 0 1 2 1 5 8 2 -1 -1 0 0 一次迭代 0-10 1 1/6 -1/6 0 1/6 05 0 2/3 1/3 -1 -1/3 11/3 1/3 5 0 2/3 1/3 -1 -4/3 0000 1 1/6 -1/6 0 1/6 01 0 2/15 1/15 -1/5 -1/15 1/51/31/15 0 0 0 0 0 -1 -1 在上表中的最终表中除去人工变量后，回归到

23、原来的标准型： s.t. 然后对该最终表继续使用单纯形法计算：目标函数-15 -24 -5 0 0 常数 决策变量基变量 初始表 -24-150 1 1/6 -1/6 0 1 0 2/15 1/15 -1/5 1/3 1/15 0 -9 6 -3 -3 一次迭代-24-5 -5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2 1/4 1/2 -15/2 0 0 -7/2 -3/2故1.15题分析：令i=1,2,3代表A，B，C三种商品，j=1,2,3代表前，中，后舱，代表装载于第j舱位的第i中商品的数量（件）。1、目标函数为运费总收入：2、约束条件：前中后舱载重限制：前中后舱

24、体积限制：三商品的数量限制：舱体平衡条件：前舱载重/中舱载重为：后舱载重/中舱载重为：前舱载重/后舱载重为：上三式中，20RR/3000=2/3，1500/3000=1/2，20RR/1500=4/3。3.课堂练习（穿插在例题讲解过程中）4.课堂小结与单纯形法小结（5分钟）图19：强调当非基变量的检验数为零时，线性规划存在多重解。5、布置作业二：1.15题授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题第二节对偶问题的基本性质教学目的与要求： 1.知识目标： 掌握一般形式对偶问题的对应规律、理解并应用对偶定理2.能力目标：掌握线性规划的对偶问题的基本性质；3.素质

25、目标：培养学生良好的职业道德、树立爱岗精神。教学重点：一般形式对偶问题的对应规律、对偶定理教学难点： 对偶定理教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟）（1）对偶问题的基本概念与解的性质； （2）一般形式的对偶问题 （3）对偶问题的基本性质3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）线性规划的对偶理论（2课时）【教学流程图】举例引入 对偶问题与原问题的结构特点线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表 线性规划的单纯形法求解实质 学生练习（结合例题讲解进行） 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，

26、过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入对偶问题的基本概念：（5分钟） 导入提问：线性规划的对偶问题与原问题的解是什么关系？（二） 新课： 第二章 线性规划的对偶理论与灵敏度分析 第一节 线性规划的对偶问题回顾例1-3：例1-3 美佳公司计划制造、两种产品，现已知

27、各制造一件时分别占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应制造两种家电各多少件时才能使获取的利润最大？ 生产1件产品生产1件产品每天可用能力（小时）设备A（台时）设备B（台时）调试 （小时） 0 6 1 5 2 1 15 24 5利润（元） 2 1 解：设为两种产品的产量，得线性规划问题： 现从另一角度提出问题：假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？设分别为单位时间内设备A，B和调试工序的出让价格，其线性规划模型如下表：原问题对偶问题目标函数最大利润为，其中：为两种产品的产量。某公司最小出让价为：，其中

28、：分别为单位时间内设备A，B和调试工序的出让价格。原问题对偶问题约束条件每生产1件商品在A，B设备和调试工序上的时间约束为：每生产1件商品的出让价不小于利润：可见：原问题（系数为mn矩阵）对偶问题（系数为nm矩阵）maRZminW目标函数中的系数成为对偶问题约束条件中的右端常数约束条件中的右端常数成为原问题中目标函数中的系数约束条件系数矩阵为对偶问题约束条件系数矩阵的转置。约束条件系数矩阵为原问题约束条件系数矩阵的转置。约束条件数有m个，第i个约束条件为“”，第i个约束条件为“”第i个约束条件为“=”变量数m个，第i个变量为“0”第i个变量为“0”第i个变量为自由变量变量数n个，第i个变量为“

29、0”第i个变量为“0”第i个变量为自由变量约束条件数有n个，第i个约束条件为“”，第i个约束条件为“”第i个约束条件为“=” 例1-6和例1-8分别用单纯形法和两阶段法可求得上述例题的原问题和其对偶问题的最终单纯形表如下：目标函数2 1 0 0 0常数 决策变量基变量原问题变量 原问题松弛变量 最终表0210 01 00 11 5/4 -15/2 0 1/4 -1/2 0 -1/4 3/215/2 7/2 3/20 00 -1/4 -1/2 变量对偶问题剩余变量 对偶问题变量 目标函数-15 -24 -5 0 0 常数 决策变量基变量 一次迭代-24-5 -5/4 1 0 -1/4 1/4 1

30、5/2 0 1 1/2 -3/2 1/4 1/2 -15/2 0 0 -7/2 -3/2从上两表看出两个问题变量之间的对应关系，同时看出只需求解其中一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。即原问题的最优解为：；其对偶问题的最优解为：。对偶问题的基本性质若线性规划原问题（LP）有最优解，其对偶问题（DP）也有最优解；LP的检验数的相反数对应于其DP的一组基本解，其中第j个决策变量的检验数的相反数对应于DP第i个剩余变量的解；LP第i个松弛变量的检验数的相反数对应于其DP的第i个对偶变量的解。反之DP的检验数对应于其LP的一组基本解。例1-9 解 加入松弛变量后，单纯形表迭代为：

31、 b 2 -1 2 1 0 2 1 0 4 0 1 4 6 -2 1 0 0 1 -1/2 1 1/2 0 1 0 1/2 3 -1/2 1 3 0 1 -5 -3 0 1 0 4 0 1 4 0 1 6 -1 2 6 0 0 -11 -2 -2 设对偶变量为和，剩余变量为，由上性质，有 为对偶问题的基本解。二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟）授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析第三节 影子价格教学目的与要求：1.知识目标：了解影子价格的实质2.能力目标：掌握求解线性规划的对偶单纯形法的计算步骤；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点

32、：对影子价格的理解。教学难点： 对影子价格的理解教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟） （1）影子价格的概念 （2）影子价格的实质 （3）影子价格的性质与计算3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）影子价格（2课时）【教学流程图】举例引入 线性规划影子价格基本概念 影子价格的实质 学生练习（结合例题讲解进行） 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多

33、次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入影子价格的基本概念：（5分钟） 导入提问：什么是影子价格？（二） 新课： 第二章 线性规划的对偶理论与灵敏度分析 第三节 影子价格对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。zR=wR= RRb= （2.26）对bi求偏导数，得到：（2.27

34、）即第i种资源影子价格RiR是zR对资源数量bi的变化率，是第i种资源增加一个单位时，最大产值的改变量。1资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源（设备B）的影子价格是0.25，当市场价格高于0.25时，可以卖出这种资源； 相反当市场价格低于影子价格时，就会买入这种资源。 随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。一般说对线性规划问题的求解是确定资

35、源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。授课题目 ： 第二章：线性规划的对偶理论与灵敏度分析第四节 对偶单纯形法教学目的与要求： 1.知识目标：理解线性规划单纯形法求解的实质；2.能力目标：掌握求解线性规划的对偶单纯形法的计算步骤；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：对偶单纯形法的计算步骤；对偶单纯形法与原问题单纯形法求解思路上的区别。教学难点： 1、对偶单纯形法的计算步骤； 2、用单纯形法求解线性规划的实质。教学过程： 1.举例引入（ 5分钟）2.举例讲解新课 （80分钟）（1）对偶问题的基本概念与解的性质

36、；（20分钟）（2）对偶单纯形法与原问题单纯形法解之间的关系；（20分钟）（3）对偶单纯形法与原问题单纯形法的求解原理（20分钟）（4）对偶单纯形法原理（20分钟）求解步骤（20分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）线性规划的对偶理论与对偶单纯形法（2课时）【教学流程图】举例引入 对偶问题与原问题的结构特点线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表 线性规划的单纯形法求解实质 初始表对偶单纯形法计算步骤 进基 出基 学生练习（结合例题讲解进行） 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发

37、提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入对偶问题的基本概念：（5分钟） 导入提问：线性规划的对偶问题与原问题的解是什么关系？（二） 新课： 第四节 对偶单纯形法一、对偶单纯形法的原理LP与DP在求解迭代过程中有三种情形：LP的b列LP的检验数含义均0 均 0则DP的检验数0且，这时LP与D

38、P均达到最优解。均0某个0则DP的某个变量0，说明原问题可行，对偶问题不可行。某个0全部0则DP的检验数0且，说明原问题不可行，对偶问题可行。对于第二种情形用单纯形法求解，第三种情形用对偶单纯形法求解。对偶单纯形法求解过程 1、用实例引入：例1-10 解 引入非负松弛变量，化为标准型； 将三个约束式两边分别乘以-1，得 目标函数-3 -9 0 0 0常数 决策变量基变量 初始表000-1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3计算0 0 0 0 0-3 -9 0 0 0 -3/-1 -9/-1第一次迭代-3001 1 -1 0 00 -3 -1 1

39、00 -6 -1 0 1 2 -1 -1 -3 -3 3 0 00 -6 -3 0 0 -6/-3 -3/-1 第二次迭代-3-901 0 -4/3 1/3 00 1 1/3 -1/3 00 0 1 -2 1 5/3 1/3 1 -3 -9 1 2 00 0 -1 -2 0最优解为：R=(5/3,1/3,0,0,1)总结对偶单纯形法求解过程： 由于用单纯形法求解极大化线性规划问题时，通过迭代直至所有检验数0，这时所得最优基也是对偶问题的可行基，因此单纯形法的求解过程是：在保持原始可行（即常数列保持0）的前提下，通过迭代实现对偶可行（全部0）。换一个角度考虑线性规划的求解过程：能否在保持对偶可行

40、（全部0）的前提下，通过迭代实现原始可行（即常数列保持0）？这就是对偶单纯形法的求解思路。第一步：建立初始单纯形表，计算检验数行，当全部0（非基变量的0）时，如果常数项0，即得最优解。如常数项至少有一元素0，且检验数仍然非正，则转下一步。第二步：将常数项0所在的约束条件两边同乘以-1，将常数列全变成非负，再使用原始单纯形法求解。如果上述处理过程中出现原始可行基不再是单位矩阵，可适当增加人工变量构造人造基，再用大M法求解。第三步：进行基变换先确定出基变量：选取常数列中绝对值最小的负元素对应的基变量出基，相应行为主元行。然后确定入基变量：由最小比值原则，选所在的列为主元列。这里为第j列的检验数，为

41、对应的主元行中非基变量的系数。主元行与主元列相交叉处的系数元素为主元素，其对应的非基变量为换入基变量。第四步：对主元素进行换基迭代后，用矩阵的初等变换将主元素变成1，并把主元列变成单位向量，得到新的单纯形表。二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟）授课题目 ： 第二章 线性规划的对偶理论与灵敏度分析第五节：灵敏度分析教学目的与要求： 1.知识目标：理解求解线性规划的单纯形法中灵敏度分析的基本原理；2.能力目标：分析的变化；分析的变化；增加一个变量的分析。3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、分析的变化；2、分析的变化；3、增加一个变量的分析。教学难

42、点： 1、灵敏度的基本概念；2、增加一个变量的分析。教学过程： 1.举例引入灵敏度（ 5分钟）2.举例讲解新课 （80分钟）（1）灵敏度的基本概念；（20分钟）（2）分析的变化；（20分钟）（3）分析的变化；（20分钟）（4）增加一个变量的分析。（20分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）灵敏度分析（2课时）【教学流程图】举例引入灵敏度 灵敏度线性规划灵敏度的基本概念 分析灵敏度的方法 线性规划模型参数 分析的变化分析线性规划模型中参数的变化 分析的变化 增加一个变量的分析 学生练习（结合例题讲解进行） 课堂小结 布置作业【教学方法】本课主要采用任务驱动和程序式思维相

43、结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入对偶问题的基本概念：（5分钟） 导入提问：线性规划的对偶问题与原问题的解是什么关系？（二） 新课： 第五节 灵敏度分析一、灵敏度分析的基本概念与原理由LP单纯形迭代法的基本原理： 将LP的标准型写成矩阵形式：

44、 maRZ=CR s.t. AR=b R0 其约束条件的系数矩阵为A，加上人工基I（I为单位矩阵）以后，迭代过程实际上为： （AI）（IA） 3 -1 0例1-11 求矩阵A= -2 1 1 的逆矩阵。 2 -1 4解 3 -1 0 1 0 0 -2 1 1 0 1 0 2 -1 4 0 0 1 1 0 1 1 1 0 = -2 1 1 0 1 0 0 0 5 0 1 1 1 0 1 1 1 0 = 0 1 3 2 3 0 0 0 1 0 1/5 1/5 1 0 0 1 4/5 -1/5= 0 1 0 2 12/5 -5/3 0 0 1 0 1/5 1/3再看美佳公司的LP约束条件系数的初始表

45、与最终表：目标函数2 1 0 0 0常数 决策变量基变量 初始表0000 5 1 0 0 6 2 0 1 0 1 1 0 0 1 15 24 5计算0 0 0 0 02 1 0 0 0第二次迭代0210 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/22 1 0 1/4 1/20 0 0 -1/4 -1/2因此有： 目标函数的系数 决策变量 初始表中约束条件的系数 B N b 最优表约束条件的系数 最优表的检验数 由上表看出，目标函数中的决策变量的系数（又叫参数）变动时，只影响最优表中的检验数，因此只要对最优表继续使用单纯形表法，直至

46、得到最优解为止。分析的变化例5-2 用教材上的例5。将代入原最优表中并继续迭代，得：目标函数1.5 2 0 0 0常数 决策变量基变量 第二次迭代01.520 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4 3/2 15/2 7/2 3/20 0 0 1/8 -9/4第三次迭代 0 15 20 0 4/5 1 -61 0 -1/5 0 10 1 1/5 0 0 6 2 30 0 -1/10 0 -3/2如果，代入原最优表，得目标函数2 0 0 0常数 决策变量基变量 第二次迭代01.5 0 0 1 5/4 -15/21 0 0 1/4 -1/20 1 0 -1/4

47、3/2 15/2 7/2 3/20 0 0 解 和 ，得：，故 。分析的变化设初始表中的常数列为b,那么最优表中的常数列为，现设初始表中的常数列为，那么最优表中的常数列为，也就是当初始表中的常数列有增量时，那么最优表中的常数列有增量。例5-3 设美佳公司这一例中的单纯形表中的初始表中的常数列中有增量： 0 8 ，设最优表中的常数列为，那么其增量为： 0 1 5/4 -15/2 0 10 = 0 1/4 -1/2 8 = 2 0 -1/4 3/2 0 -2用对偶单纯形法继续计算得：目标函数2 1 0 0 0常数 决策变量基变量 第二次迭代0 210 0 1 5/4 -15/21 0 0 1/4

48、-1/20 1 0 -1/4 3/2 35/2 11/2 - 1/20 0 0 -1/4 -1/2第三次迭代 0 2 00 5 1 0 01 1 0 0 10 -4 0 1 -6 15 5 20 -1 0 0 -2增加一个变量的分析（采用教材第三版P66的分析步骤和P67的例7。二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟） 授课题目 ： 第三章：运输问题第一节 运输问题及其数学模型教学目的与要求： 1.知识目标：掌握运输问题的基本概念；2.能力目标：掌握运输问题的模型特点，特别是基变量个数。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点： 初始调运方案的确定。教学

49、难点： 初始调运方案的确定。教学过程： 1.举例引入运输问题（ 5分钟）2.举例讲解新课 （70分钟）运输问题的基本概念；3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟） 5布置作业：（10分钟）运输问题：表上作业法与规划求解法（2课时）【教学流程图】举例引入运输问题 产地运输问题的基本概念 销地 运价与运量 学生练习（结合例题讲解进行） 课堂小结 布置作业：要求学生完成习题中例7的表上作业计算。【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容

50、的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一 、教学过程：举例引入运输问题的基本概念：（5分钟） 导入提问：线性规划在管理实践中有哪些应用？（二） 新课：第三章 运输问题第一节 运输问题及其数学模型引入P82的例1运输问题的数学模型及其特点 运输问题的数学模型具有下述特点：1、约束条件系数矩阵的元素为0或1；2、约束条件系数矩阵的每一列有两个元素，这对应于每一个元素在前m个约束条件中出现一次，在后n个约束条件中出现

51、一次；3、对于产销平衡运输问题，所有约束条件都有是等式约束，各产地产量之和等于各销地销量之和。 运输问题的解初始基可行解的确定应本着下列原则（1） 皆应满足模型中的所有约束；（2）基变量对应的约束方程组的系数列向量线性无关（3） 基变量的个数（非零变量的个数）m+n-1。（4） 为使迭代顺利进行，基变量的个数在迭代的过程中一直保持为（m+n-1）个。二、学生练习（穿插在例题讲解中）三、布置作业：对本章例题7进行具体推导 授课题目 ： 第三章：运输问题第二节 用表上作业法求解运输问题教学目的与要求： 1.知识目标：掌握运输问题的表上作业法；2.能力目标：掌握运输问题的建模和表上作业求解法；掌握解

52、的最优性检验法中的闭回路法和位势法的计算步骤。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、运输问题的建模和表上作业求解法；2、求检验数的两种方法；3、求解运输问题的ERCEL规划求解法。教学难点： 1、运输问题的建模和表上作业求解法及其解的最优性检验法中的闭回路法和位势法（求检验数的两种方法）；2、求解运输问题的ERCEL规划求解法。教学过程： 1.举例引入运输问题的求解（ 5分钟）2.举例讲解新课 （70分钟）（1）求解运输问题的表上作业法；（2）求解运输问题的规划求解法；3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟） 5布置作业：（10分钟）运输问题：表

53、上作业法与规划求解法（2课时）【教学流程图】举例引入运输问题的解 用最小元素法求初始方案求解运输问题的表上作业法 闭回路法 位势法 学生练习（结合例题讲解进行） 课堂小结 布置作业：要求学生完成习题中例7的表上作业计算。【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识

54、，达到理想的教学效果。【教学内容】一 、教学过程：举例引入运输问题的基本概念：（5分钟） 导入提问：线性规划在管理实践中有哪些应用？（二） 新课：第三章 运输问题 第二节 用表上作业法求解运输问题一般单纯形法 例 3-1 某部门有三个生产同类产品的工厂，产品由四个销地销售（数据见下表），求应如何调运才使总运费最小？ 销地产地产量 412411 16 21039 1085116 22销量814121448解：先写出LP数学模型如下：s.t. (目标函数和约束条件模型见教材P83)由模型可列出约束条件的系数矩阵如下： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

55、1 1 1 1 由上可见，单纯形表的系数矩阵中共有m+n=3+4=7行，有mRn=3R4=12列。基变量个数有m+n-1=3+4-1=6个，不能采用普通单纯形法求解，只能用表上作业法求解。表上作业法求初始可行解最小元素法先在表中找出一个运价最小的数（最小元素），给予尽可能满足，然后在余下的格子中，继续按此法安排调运。注意每次安排时，如果销地已满足需求，就划去该列；如果产地已分配完产量，就划去该行（划去是打“”之意）；如二者同时满足，只能在该最小元素所在的行或列上的其它空格上打“”，而不能同时划去该最小运价格所在的行与列。当最后只剩下一行（一列）还存在没有填数和打“”的格子时，规定应先在能同时满

56、足所在行与列的格子内填数（填数前所在行与列已同时满足时，该格子内应填写0），再按最小元素法填写其他格，直到满足填数的格子数等于m+n-1为止。调运方案的检验方法（怎样求空格检验数？）空格闭回路法空格闭回路指在一个封闭的直角回路的若干角点处，除了处为空格以外，其余角点都是实格。作法：从所在的空格开始，沿直线前进，碰到实格可拐弯也可不拐，但碰到空格应不改变方向，如此曲折前进，一直返回到起始空格。再将所在空格的单位运费加上正号，沿它的空格闭回路按顺时针方向再在第二个、第三个等有数格的单位运费前依次加上负号，正号，如此正负交错，最后得所在空格的检验数。位势法 方法：在初始调运方案表中增加一行和一列，在

57、列中填，在行中填（和称为位势），于是对于m+n-1个有数格成立下列关系： （1）由于和共有m+n个，因此上式组成的m+n-1个方程中多一个未知数，可任设一个未知量为一任意常数（一般设），求出全部和的值。再把这些和的值代入空格检验数的表达式： （2）3、换基对各空格检验数按的原则先选择进基，再做的空格闭回路，以角点为0号，按顺时针或反时针方向把其他角点依次标为1号，2号，如此排出各转角点的奇偶性，再求调整量（各奇数转角点的调运量），按“偶点处加调运量，奇点处减调运量”的方法，重新安排空格闭回路上转角点的调运量。4、再求新调运方案的检验数，再换基求更新的调运方案，如此迭代，直至空格检验数不出现负值

58、为止。 5、当某空格检验数时，同样可以选取它所在的空格进基，运用调整量调节器整后的方案仍为最优，不过目标函数值不会有所改善，称之为多解。例3-2 对例3-1用表上作业法求解。 解 先用最小元素法求初始调运方案如下表1，用空格闭回路法或位势法求得各空格检验数为：，由于存在负检验数，再进行迭代。得新调运方案如下表2。由于所有非基变量（空格）的检验数为正值，故这个调运方案为最优解。和检验数为：作业二：习题3.8表3-32，33。(答案见20RR级物流本科教案) 表1 初始调运方案 销地产地产量 412410116 16 2810329 1085141168 22销量814121448 表2 最优调运

59、方案 销地产地产量 412412116 16 2810392 1085141168 22销量814121448二、学生练习（穿插在例题讲解中）三、布置作业：用表上作业法进行计算求解。授课题目 ： 第三章 运输问题第三节：运输问题进一步讨论。教学目的与要求： 1.知识目标：掌握运输问题的基本概念；2.能力目标：掌握运输问题的建模和表上作业求解法；掌握解的最优性检验法中的闭回路法和位势法的计算步骤。 3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、运输问题的建模和表上作业求解法；2、求检验数的两种方法；3、求解运输问题的ERCEL规划求解法。教学难点： 1、运输问题的建模和表上作

60、业求解法及其解的最优性检验法中的闭回路法和位势法（求检验数的两种方法）；2、求解运输问题的ERCEL规划求解法。教学过程： 1.举例引入产销不平衡的运输问题（ 5分钟）2.举例讲解新课 （80分钟）（1）产销不平衡的运输模型相关的基本概念；（20分钟）（2）产大于销的运输问题；（20分钟）（3）销大于产的运输模型；（20分钟）（4）产销不平衡的运输模型在实际中的应用。（20分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）运输问题进一步讨论（2课时）【教学流程图】举例引入产销不平衡的运输问题 产大于销产销运输问题的基本概念 销大于产 基变量的个数 增加一个产地求解不平衡的运输问题