《运筹学》完整教案(本科)2011

《运筹学》教案适用专业：适用层次：本科教学时间：2011年上学期授课题目：绪论第一章线性规划及单纯形法第一节：线性规划问题及数学模型。教学目的与要求：1.知识目标：掌握运筹学的概念和作用及其学习方法；掌握线性规划的基本概念和两种基本建模方法。2.能力目标：掌握线性规划建模的标准形式及将普通模型化为标准模型的方法。要求学生完成P43习题1.2两个小题。3.素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、线性规划的基本概念和两种基本建模方法；2、线性规划建模的标准形式及将普通模型化为标准模型的方法。教学难点：1、线性规划的两种基本建模方法；2、将线性规划模型的普通形式化为标准形式。教学过程：1.举例引入（5分钟）2.新课（60分钟）（1）举例引入，绪论（20分钟）（2）运筹学与线性规划的基本概念（20分钟）（3）结合例题讲解线性规划标准型的转化方法3.课堂练习（20分钟）4.课堂小结（5分钟）5.布置作业《线性规划及单纯形法》（2课时）【教学流程图】举例引入，绪论运筹学运筹学与线性规划的基本概念线性规划（结合例题讲解）线性规划的标准型目标函数结合例题讲解线性规划标准型的转化方法约束条件的右端常数约束条件为不等式课堂练习课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一、教学过程：（一）举例引入：（5分钟）（1）齐王赛马的故事（2）两个囚犯的故事导入提问：什么叫运筹学？（二）新课：绪论一、运筹学的基本概念（用实例引入）例1-1战国初期，齐国的国王要求田忌和他赛马，规定各人从自己的上马、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支付一千两银子给予获胜者。当时齐王的马比田忌的马强，结果每年田忌都要输掉三千两银子。但孙膑给田忌出主意，可使田忌反输为赢。试问：如果双方都不对自己的策略保密，当齐王先行动时，哪一方会赢？赢多少？反之呢？例1-2有甲乙两个囚犯正被隔离审讯，若两人都坦白，则每人判入狱8年；若两个人都抵赖，则每人判入狱1年；若只有一人坦白，则他初释放，但另一罪犯被判刑10年。求双方的最优策略。乙囚犯抵赖坦白甲囚犯抵赖-1，-1-10，0坦白0，-10-8，-8定义：运筹学（OperationResearch）是运用系统化的方法，通过建成立数学模型及其测试，协助达成最佳决策的一门科学。它主要研究经济活动和军事活动中能用数学的分析和运算来有效地配置人力、物力、财力等筹划和管理方面的问题。二、学习运筹学的方法1、读懂教材上的文字；2、多练习做题，多动脑筋思考；3、作业8次；4、考试；5、EXCEL操作与手动操作结合。第一章线性规划及单纯形法第一节线性规划问题及其数学模型（用实例引入）例1-3美佳公司计划制造Ⅰ、Ⅱ两种产品，现已知各制造一件时分别占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应制造两种家电各多少件时才能使获取的利润最大？生产1件Ⅰ产品生产1件Ⅰ产品每天可用能力（小时）设备A（台时）设备B（台时）调试（小时）06152115245利润（元）21例1-4有A、B、C三个工地，每天需要水泥各为17、18、15百袋。为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地。其单位运价如下表，求最佳调运方案。工地水泥厂ABC甲11．52乙242工地水泥厂ABC供应量/百袋甲23乙27需求量/百袋17181550一、线性规划的基本概念如果规划问题的数学模型中，决策变量的取值是连续的整数、小数、分数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则称这种规划问题为线性规划。二、将线性规划的普通型化为标准型1、对于minZ=CX,可转化为min(-Z)=-CX；2、当约束条件中出现ininiibxaxaxa2211时，在左边加上一个“松弛变量”01ix，使不等式变为等式；当约束条件中出现ininiibxaxaxa2211时，则在左边减去一个“松弛变量”01ix。3、当某个决策变量0jx或符号不限时，则增加两个决策变量'jx和''jx，令'''jjjxxx；4、当约束条件中有常数项0ib时，则在方程两边同乘以（-1）。例1-5将下列非标准4型线性规划问题转化为标准型。解：学生练习：P42习题1.2。二、学生练习（20分钟）三、课堂小结（5分钟）授课题目：第二节图解法第三节单纯形法原理第四节单纯法的计算步骤教学目的与要求：1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念；2.能力目标：掌握用图解法和单纯形法求解线性规划的计算步骤；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、用图解法求解线性规划的计算步骤；2、用单纯形法求解线性规划的计算步骤。教学难点：1、用单纯形法求解线性规划的计算原理；2、用单纯形法求解线性规划的计算步骤。教学过程：1.举例引入（5分钟）2.举例讲解新课（80分钟）（1）图解法（20分钟）（2）单纯形法原理（20分钟）（3）单纯形法求解步骤（40分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一。《线性规划的求解》（2课时）【教学流程图】以学生自学引入图解法线性规划求解方法介绍单纯形法EXCEL规划求解法坐标系图解法的操作步骤求出可行域平移目标函数直线化为标准型单纯形法的操作步骤求出初始表迭代法课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一、教学过程：（一）举例引入：（5分钟）复习中学数学中的图解法。导入提问：线性规划图解法中有哪些基本概念？（二）新课：第二节图解法一、图解法的步骤（以学生自学引入）学生自学P16-17，教师检查看不懂文字的学生，并做好记录。提问：以P44的1.4题第1小题为例，图解法第一步是什么？以下逐步提出问题。教师演示并总结如下：图解法适用于两个决策变量的线性规划非标准型。步骤如下；1、用决策变量建立直角坐标系；2、对于每一个约束条件，先取等式画出直线，然后取一已知点（一般取原点）的坐标代入该直线方程的左边，由其值是否满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域。3、令Z等于任一常数，画出目标函数的直线，平移该直线，直至它与凸多边形可行域最右边的角点相切，切点坐标则为最优解。例1-5解可行解——满足约束条件的解，全部可行解的集合叫可行域。最优解——使目标函数达到最大值的可行解。基变量——利用矩阵的初等变换从约束条件的m×n(nm)阶系数矩阵找出一个m×m阶单位子矩阵，它们对应的变量叫基变量，其余的叫非基变量。矩阵的初等变换——将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。二、单纯形表迭代法教师先演示：1、化为标准型2、做出初始单纯形表，求出检验数；3、确定检验数中最大正数所在的列为主元列，选择主元列所对应的非基变量为进基变量4、按最小比值原则，用常数列各数除以主元列相对应的正商数，取其最小比值，该比值所在的行为主元行；主元列与主元行交叉的元素为主元，主元G（1，1.5）所对应的基变量为出基变量。5、对含常数列的增广矩阵用初等变换把主元变为1，主元所在的列的其余元素化为0。6、计算检验数，直到全部检验数小于等于0，迭代终止。基变量对应的常数列为最优解，代入目标函数得最优目标函数值。例1-6解：先化为标准型：s.t.0,,,,524261550002max543215214213254321xxxxxxxxxxxxxxxxxxZ其约束条件的系数增广矩阵为05100156201024110015初始始基可行解为：TX)5,24,15,0,0(，以此列出单纯形表如下。得：TX)0,0,0,2/15,2/3,2/7(，代入目标函数得：Z=2*7/2+1*3/2+15/2*0+0*0=17/2。目标函数21000常数决策变量基变量1x↓2x↓3x4x5x初始表←4x00005100[6]20101100115245计算0000021000第一次迭代←5x0200510011/301/600[2/3]0-1/61154122/301/3001/30-1/30第二次迭代0210015/4-15/21001/4-1/2010-1/43/215/27/23/22101/41/2000-1/4-1/24.课堂小结（5分钟）5.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一授课题目：第五节单纯形法的进一步讨论教学目的与要求：1.知识目标：理解求解线性规划的人工变量法中大M法和两阶段法；2.能力目标：利用习题1.15巩固线性规划的建模；3.素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、求解线性规划的人工变量法中两阶段法的计算步骤。2、人工变量法与普通单纯形法的区别。教学难点：1、两阶段法的计算步骤；2、习题1.15中的约束条件分析。教学过程：1.举例引入（5分钟）2.举例讲解新课（80分钟）（1）人工变量法（40分钟）（2）两阶段法（40分钟）3.课堂练习（穿插在例题讲解过程中）4.课堂小结与单纯形法小结（5分钟）5．布置作业。《单纯形法的进一步讨论》（2课时）【教学流程图】用实例引入人工变量法初始单纯形表中无单位矩阵人工变量法的例题讲解引入人工变量在目标函数中引入大M两阶段法用EXCEL求解中的困难两阶段法的例题讲解第一阶段的模型第二阶段的模型课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一、教学过程：（二）举例引入：（5分钟）复习单纯形法。导入提问：当初始单纯形表中不出现单位矩阵怎么办？（二）新课：第五节单纯形法的进一步讨论（用实例引入人工变量法）例1-7用单纯形法求解下列线性规划问题：解：将第二个约束条件化为等式（左边减去一个松弛变量）后，约束条件的系数矩阵不存在单位矩阵，这时可在约束条件第一、二等式的左边分别加上一个人工变量作为初始基变量，使之出现单位矩阵。为了使目标函数中的人工变量为0，令它们的系数为任意大的负值“-M”，然后采用一般单纯形表法求解。目标函数23-5-M0-M常数决策变量基变量1x↓2x↓3x4x5x6x初始表←6x-M-M111100[2]-510-11710计算-3M4M-2M-MM-M3M+23-4M2M-50-M0一次迭代←4x-M20[7/2]1/211/2-1/21-5/21/20-1/21/2252527M12M-M12M12M0827M62M012M123M32011/72/71/7-1/7106/75/7-1/71/74/745/72315/716/71/7-1/700-5