教学设计 运筹学大M法介绍

运筹学教学设计运筹学教学设计 人工变量法人工变量法 大大 M M 法法 1 目目 录录 一 课程分析 2 二 教学目标 2 三 教学内容 3 四 教学分析 3 五 教学方法 3 六 教学过程 4 七 教学过程详细步骤 4 八 课后作业 10 九 参考资料及学生阅读资料 10 2 一 课程分析一 课程分析 本节课是 运筹学 第一章 1 4 节人工变量法 主讲大 M 法的 应用与计算 要求学生了解并掌握什么是大 M 法 在什么时候 应用 应用的范围以及此方法的优缺点 它是解线性规划问题 行之有效的方法之一 对解决线性规划问题提供了一种思路 二 教学目标 二 教学目标 1 专业能力 通过学习大 M 法 能够应用并解决简单的 LP 问题 2 知识目的 掌握人工变量的使用方法 学会构造初始可行基 3 情感态度价值观目标 培养学生的独立思考的能力 培养学生学习运筹学的兴趣及爱好 培养学生严密的逻辑思维能力 3 三 教学内容 三 教学内容 本节课在前面所学单纯形表法的基础上 进一步了解当无法得 到初始可行基的构造方法 进而引出人工变量法中的大 M 法的 处理思想与处理步骤 四 教学分析 四 教学分析 1 教学重点 大 M 法的使用步骤 2 教学难点 应用大 M 法进行初始可行基的构造 五 教学方法 五 教学方法 本节课采取问题探究教学 根据前面所学知识提出问题 即在 前面所学章节方法的不足方面入手 引出新的思路 采用新的 方法去弥补前面所学无法解决的问题 根据前章节例题 继续 探究当所求 LP 问题无法得到初始可行基时如何解决问题 进而 引出人为的增添变量来形成单位向量的方法求解 然后根据步 骤 计算解出问题的最优解 方式 通过 提出问题 做出假设 制定计划 进行试验 得出结论 反思得失 几个环节进行 教学 使得整个教学过程在师生的共同参与下进行 加强对问 题的理解 提升学生解决问题的能力 4 六 教学过程 六 教学过程 1 例题分析 发现问题 2 提出解决方案 3 进行计算 4 归纳总结方法步骤 解题思想 5 针对性练习 6 讨论优缺点寻找新的解决方案 7 作业及阅读资料 七 教学过程详细步骤 七 教学过程详细步骤 第一环节 导入新课 第一环节 导入新课 1010 分钟 分钟 前面所举各例中 约束条件全是 型 在每个不等式 左面加上松弛变量 不等式变成等式 加入的松弛变量正好组 成初始可行基 利用单纯形法求解即可 若当约束条件是 型时 我们可能无法仅仅加 入松弛变量找到初始可行基 此时无法利用单纯性表进行解答 此时我们人为的加上一些变量 使变量的系数矩阵出现单 位向量 这时就可利用单纯形法进行求解 然而我们又不希望 这些新填入的变量影响我们的求解 因此在计算过程中使它们 5 都等于 0 这样即可解决问题 又不影响 LP 问题的结果 举例探究 minmin z z x x1 1 3x 3x2 2 2x2x1 1 x x2 2 4 4 3x3x1 1 4x 4x2 2 x x3 3 6 6 x 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 1031 0143 0012 A A 矩阵中不存在单位矩阵 因此矩阵中不存在单位矩阵 因此 需要人工地构建一个单位矩阵需要人工地构建一个单位矩阵 001031 010143 100012 A 6 第二环节 进入新课 第二环节 进入新课 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 引入人工变量 用单纯形法对 求解 的最优解即为 L 的最优解 证明略 7 本质 原问题与辅助问题是等价的 详见课本本质 原问题与辅助问题是等价的 详见课本42页定理页定理1 9 人工变量是虚拟变量 加入原方程中是作为临时基变量 人工变量是虚拟变量 加入原方程中是作为临时基变量 经过基的单纯形变换 迭代 经过基的单纯形变换 迭代 将人工变量均能换成非基 将人工变量均能换成非基 变量 则所得解是最优解 变量 则所得解是最优解 判别准则 若在最终表中检验数小于零 而且基变量中还判别准则 若在最终表中检验数小于零 而且基变量中还 有某个非零的人工变量 则原问题无可行解 有某个非零的人工变量 则原问题无可行解 二 二 例题讲解 例题讲解 15分钟 分钟 1 用大 M 法求解下述问题 minmin z z x x 1 1 3x 3x 2 2 s t 2x1 x2 4 3x1 4x2 6 x1 3x2 3 x1 x2 0 加入松弛变量 问题化为标准型 min z x 1 3x2 8 s t 2x1 x2 4 3x1 4x2 S2 6 x1 3x2 S3 3 x1 x2 S2 S3 0 加入人工变量 min z x 1 3x2 MR1 MR2 s t 2x1 x2 R1 4 3x1 4x2 S2 R2 6 x1 3x2 S3 3 x1 x2 S2 S3 R1 R2 0 从问题的形式上可看出R1 R2 S3组成一组初始可行基 做出单纯 形表如下 9 原问题最优解和最优值为 1 2 2 0 2 三 三 难点解释 难点解释 退化 在下一次迭代中有一个或几个基变量为0 从而出现退化解 课本57页表1 22 II 可能会导致循环 永远达不到最优解 为阻止退化现象 在单纯形迭代中需遵循以下原则 第一 如果几个正的检验数相等 则选其中下标最小的作 为入基变量 第二 若有几个比值同时达到最小 则选其中下标最小的 基变量作为换出变量 第三环节 课程总结 第三环节 课程总结 5分钟 分钟 一 一 大 大 M M 法步骤 法步骤 1 添加人工变量构造初始可行基 2 利用单纯形法求最优值 10 二 二 要点 要点 1 加入人工变量使 LP 问题转化成标准型 LP 问题 人工变 量只起过渡作用 不影响决策变量的取值 计算过程中要 使人工变量取 0 2 M 为充分大的正数 只有这样才能迫使人工变量取 0 3 学会构造初始可行基 4 单纯形表的计算过程 步骤图 八 课后作业