《教学设计 运筹学大m法介绍》由会员分享，可在线阅读，更多相关《教学设计 运筹学大m法介绍（12页珍藏版）》请在金锄头文库上搜索。
1、运筹学教学设计运筹学教学设计人工变量法人工变量法大大 M M 法法1 目目 录录一、课程分析.2二、教学目标.2三、教学内容.3四、教学分析.3五、教学方法.3六、教学过程.4七、教学过程详细步骤.4八、课后作业.10九、参考资料及学生阅读资料.102 一、课程分析一、课程分析:本节课是运筹学第一章 1.4 节人工变量法，主讲大 M 法的应用与计算。要求学生了解并掌握什么是大 M 法？在什么时候应用？应用的范围以及此方法的优缺点。它是解线性规划问题行之有效的方法之一，对解决线性规划问题提供了一种思路。二、教学目标：二、教学目标：1.专业能力：通过学习大 M 法，能够应用并解决简单的 LP 问题
2、。2.知识目的：掌握人工变量的使用方法；学会构造初始可行基。3.情感态度价值观目标：培养学生的独立思考的能力；培养学生学习运筹学的兴趣及爱好；培养学生严密的逻辑思维能力。3 三、教学内容：三、教学内容：本节课在前面所学单纯形表法的基础上，进一步了解当无法得到初始可行基的构造方法，进而引出人工变量法中的大 M 法的处理思想与处理步骤。四、教学分析：四、教学分析：1.教学重点：大 M 法的使用步骤。2.教学难点：应用大 M 法进行初始可行基的构造。五、教学方法：五、教学方法：本节课采取问题探究教学，根据前面所学知识提出问题，即在前面所学章节方法的不足方面入手，引出新的思路，采用新的方法去弥补前面所
3、学无法解决的问题。根据前章节例题，继续探究当所求 LP 问题无法得到初始可行基时如何解决问题，进而引出人为的增添变量来形成单位向量的方法求解。然后根据步骤，计算解出问题的最优解。方式：通过“提出问题”“做出假设”“制定计划”“进行试验”“得出结论”“反思得失”几个环节进行教学。使得整个教学过程在师生的共同参与下进行，加强对问题的理解，提升学生解决问题的能力。4 六、教学过程：六、教学过程：1. 例题分析，发现问题；2. 提出解决方案；3. 进行计算；4. 归纳总结方法步骤，解题思想；5. 针对性练习；6. 讨论优缺点寻找新的解决方案；7. 作业及阅读资料。七、教学过程详细步骤：七、教学过程详细
4、步骤：第一环节：导入新课（第一环节：导入新课（1010 分钟）分钟）前面所举各例中，约束条件全是“”型，在每个不等式左面加上松弛变量，不等式变成等式，加入的松弛变量正好组成初始可行基，利用单纯形法求解即可。若当约束条件是“” ， “”型时，我们可能无法仅仅加入松弛变量找到初始可行基，此时无法利用单纯性表进行解答。此时我们人为的加上一些变量，使变量的系数矩阵出现单位向量，这时就可利用单纯形法进行求解，然而我们又不希望这些新填入的变量影响我们的求解，因此在计算过程中使它们5 都等于 0，这样即可解决问题，又不影响 LP 问题的结果。举例探究：minmin z=z= x x1 1 +3x+3x2 2
5、2x2x1 1 +x+x2 2 =4=43x3x1 1 +4x+4x2 2 x x3 3 =6=6x x1 1 +3x+3x2 2 +x+x4 4 =3=3 x x1 1 x x2 2 ,x,x3 3,x,x4 4 0 0 人为增加两列相当于又加入两个变量 x5、x6调整后的 A 矩阵还原成约束条件为：由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是 0 0。引入松弛变量引入松弛变量 x3、x4,将数学模型将数学模型 标准化。观察约束条件系数矩阵标准化。观察约束条件系数矩阵 A 103101430012AA 矩阵中不存在单位矩阵，因此矩阵中不存在单位矩阵，因
6、此 需要人工地构建一个单位矩阵需要人工地构建一个单位矩阵 001031010143100012A6 第二环节：进入新课（第二环节：进入新课（30分钟）分钟）（一）（一） 、大、大 M 法（法（10分钟）分钟）设要求解 LP 问题：（L）min = = 1, . = 1= , = 1,2, 0, = 1,2,.?其中，一切0（i=1,2,m）.1.在约束方程左边加非负变量，成为人工变量，在目标函数中增加含人工变量的项(i=1,2,m),M 为充分大的正 + 数。2.做辅助问题（ ）min = = 1+ = 1 + , . = 1+ + = , = 1,2, 0, = 1,2, + .?引入人工变
7、量，用单纯形法对（ ）求解，（ ）的最优解即为（L）的最优解（证明略）7 本质：原问题与辅助问题是等价的（详见课本本质：原问题与辅助问题是等价的（详见课本42页定理页定理1.9 ） 。 人工变量是虚拟变量，加入原方程中是作为临时基变量，人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的单纯形变换（迭代）经过基的单纯形变换（迭代） ，将人工变量均能换成非基，将人工变量均能换成非基变量，则所得解是最优解；变量，则所得解是最优解； 判别准则：若在最终表中检验数小于零，而且基变量中还判别准则：若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，则原问题无可行解。有某个非零的人工变量，
8、则原问题无可行解。（二）（二） 、例题讲解（、例题讲解（15分钟）分钟）：1.用大 M 法求解下述问题：minmin z=z= x x 1 1 +3x+3x 2 2s.t. 2x1 +x2 =43x1 +4x2 6 x1 +3x2 3x1,x2 0加入松弛变量 ，问题化为标准型：min z= x 1 +3x28 s.t. 2x1 +x2 =43x1 +4x2 -S2 =6x1 +3x2 +S3 =3x1 x2 ,S2,S30加入人工变量：min z= x 1 +3x2 +MR1 +MR2s.t. 2x1 + x2 +R1 =43x1 +4x2 -S2 +R2 =6x1 +3x2 +S3 =3x
9、1 , x2, S2,S3 ,R1,R20从问题的形式上可看出R1 R2 S3组成一组初始可行基，做出单纯形表如下：9 原问题最优解和最优值为 1= 2, 2= 0,= 2.（三）（三） 、难点解释：、难点解释：退化：在下一次迭代中有一个或几个基变量为0，从而出现退化解。课本57页表1.22（II） 。(可能会导致循环，永远达不到最优解。)为阻止退化现象，在单纯形迭代中需遵循以下原则：第一：如果几个正的检验数相等，则选其中下标最小的作为入基变量；第二，若有几个比值同时达到最小，则选其中下标最小的基变量作为换出变量第三环节：课程总结（第三环节：课程总结（5分钟）分钟）（一）（一） 、大、大 M
10、M 法步骤：法步骤：1. 添加人工变量构造初始可行基。2. 利用单纯形法求最优值。10 （二）（二） 、要点：、要点：1.加入人工变量使 LP 问题转化成标准型 LP 问题，人工变量只起过渡作用，不影响决策变量的取值。计算过程中要使人工变量取 0；2.M 为充分大的正数，只有这样才能迫使人工变量取 0；3.学会构造初始可行基；4.单纯形表的计算过程。 （步骤图）八、课后作业：八、课后作业：用大 M 法求解课本77页第15题九、参考资料及学生阅读资料九、参考资料及学生阅读资料运筹学导论 (编著者：费雷德里克.s. 希利尔)；运筹学教程(编著者：胡运全)；11 数据、模型与决策(编著者费雷德里克.s. 希利尔)运筹学基础教程(编著者：黄桐城等)；数学模型 （编著者：姜启源等）
