本科运筹学：大M法与两阶段法融合教学设计

本科运筹学：大M法与两阶段法融合教学设计一、教材与学情分析（一）教材内容分析【基础】本次课程“大M法、两阶段法”选自高等院校管理科学与工程类、数学与应用数学、经济类等专业的核心专业基础课《运筹学》教材，具体位于线性规划章节中的“单纯形法”之后。在学习了单纯形法的基本原理和标准求解过程后，学生已经掌握了在存在明显初始可行基（如松弛变量构成的单位矩阵）情况下的线性规划求解。然而，实际问题中的线性规划模型往往更为复杂，约束条件可能是“≥”或“=”的形式，导致标准化后的系数矩阵中不存在现成的单位矩阵，无法直接启动单纯形法。因此，大M法和两阶段法应运而生，它们是解决这一关键“启动”问题的两类经典的人工变量法。这部分内容不仅是单纯形法的延伸和深化，更是连接理论与实际应用、解决复杂约束下线性规划问题的桥梁，在整个线性规划乃至运筹学课程体系中具有承上启下的重要地位。（二）学情分析本次授课对象为大学本科二年级学生。在知识基础上，学生已经系统学习了线性代数的基本知识（如矩阵运算、向量线性相关性），并掌握了线性规划问题的建模、图解法以及基于单位矩阵的单纯形表迭代求解。然而，学生对“无初始可行基”问题的认知可能存在思维定式，容易机械套用单纯形表，而对“为何要引入人工变量”、“大M法中M的本质是什么”、“两阶段法的第一阶段究竟在算什么”等核心问题缺乏深入理解。在认知能力上，大二学生具备了一定的逻辑思维和抽象思维能力，但对于引入带参数的（M）运算仍会感到不习惯，对两阶段法中目标函数切换的深层目的容易混淆。因此，本次课程的设计需要从具体问题出发，引发认知冲突，通过对比分析和逐步推导，帮助学生跨越从“有基”到“造基”的思维鸿沟。二、教学目标设计（一）知识与技能目标【基础】1.学生能够准确识别线性规划标准型中是否存在单位矩阵，并判断何时需要引入人工变量。2.学生能够深刻理解大M法的基本原理，熟练掌握大M法引入人工变量及在目标函数中设置惩罚因子M的方法，并能正确运用单纯形表进行迭代求解，准确判定解的四种情况（唯一最优解、无穷多最优解、无界解、无可行解）。3.学生能够深刻理解两阶段法的基本原理，熟练掌握第一阶段辅助问题的构造与求解，并根据第一阶段的最优目标函数值判断原问题解的属性，进而顺利过渡到第二阶段，求解原问题的最优解。（二）过程与方法目标【重要】1.通过对比“有初始可行基”和“无初始可行基”的线性规划问题，引导学生经历“发现问题—提出假设—验证假设—解决问题”的科学探究过程，培养其逻辑推理和问题分析能力。2.通过对大M法和两阶段法的对比学习，引导学生分析两种方法的异同点、优缺点，培养其运用辩证思维审视和选择算法的能力。3.通过手算迭代与实际软件（如LINGO,MATLAB）求解结果的对比，让学生体会算法思想与计算工具相结合的重要性，增强实践应用意识。（三）情感、态度与价值观目标1.通过引入人工变量这一“创造性”的数学技巧，激发学生对数学模型的探究兴趣，感受数学家在解决实际问题时的智慧和巧妙构思。2.在迭代计算过程中，培养学生严谨细致、一丝不苟的科学态度和逻辑严密的思维习惯。3.通过运筹学在生产计划、资源配置等领域的应用案例，使学生体会科学决策的价值，树立优化意识和全局观念。三、教学重点与难点（一）教学重点【高频考点】1.大M法：惩罚因子M的引入目的，大M法的单纯形表求解步骤及最优解的判定。2.两阶段法：辅助问题的构造，第一阶段与第二阶段的衔接，解的判定准则。（二）教学难点【难点】1.大M法中抽象参数M的理解与运算（特别是检验数的计算）。2.两阶段法中第一阶段目标函数（人工变量和）与第二阶段目标函数（原目标函数）切换的逻辑必然性。3.对“无可行解”情形的准确识别与判定。四、教学方法与手段本课程采用“启发式讲授+问题驱动+对比分析+案例教学”相结合的模式。以具体问题为引线，让学生在尝试解决中遭遇困境，从而激发学习新方法的强烈动机。在讲解过程中，教师通过层层设问，引导学生思考“为什么要这么做”以及“不这样做会怎样”。利用板书与多媒体课件（PPT）相结合的方式，课件动态演示迭代过程，板书则重点展示关键步骤的逻辑推导和核心思想。特别强化大M法与两阶段法的对比教学，通过同一个例题的两种解法，让学生在比较中深化理解，掌握两种方法的精髓。五、教学实施过程（核心环节，共计90分钟）（一）创设情境，引入新课：从困境中寻找突破（约10分钟）1.回顾旧知，铺设台阶：教师首先带领学生回顾单纯形法的核心思想——从可行域的一个顶点（初始基可行解）出发，沿着边迭代到另一个更优的顶点。在标准型中，如果系数矩阵A中包含一个单位矩阵，我们直接取该单位阵为初始基，基变量就是对应的松弛变量或变量本身，初始解唾手可得。2.抛出问题，引发冲突：教师展示如下线性规划问题（板书或PPT展示）：例：用单纯形法求解下列线性规划问题max

Z=3x1−x2−x3\{max}Z=3x_1x_2x_3max

Z=3x1​−x2​−x3​s.t.

{x1−2x2+x3≤11−4x1+x2+2x3≥3−2x1+x3=1x1,x2,x3≥0\s.t.s.t.}\begin{cases}x_12x_2+x_3\le11\\4x_1+x_2+2x_3\ge3\\2x_1+x_3=1\\x_1,x_2,x_3\ge0\end{cases}s.t.

⎩⎨⎧​x1​−2x2​+x3​≤11−4x1​+x2​+2x3​≥3−2x1​+x3​=1x1​,x2​,x3​≥0​3.师生互动，分析困境：教师引导学生将该问题化为标准型。标准型为：max

Z=3x1−x2−x3+0x4+0x5\{max}Z=3x_1x_2x_3+0x_4+0x_5max

Z=3x1​−x2​−x3​+0x4​+0x5​s.t.

{x1−2x2+x3+x4=11−4x1+x2+2x3−x5=3−2x1+x3=1xj≥0,j=1,2,...,5\{s.t.}\begin{cases}x_12x_2+x_3+x_4=11\\4x_1+x_2+2x_3x_5=3\\2x_1+x_3=1\\x_j\ge0,j=1,2,...,5\end{cases}s.t.

⎩⎨⎧​x1​−2x2​+x3​+x4​=11−4x1​+x2​+2x3​−x5​=3−2x1​+x3​=1xj​≥0,j=1,2,...,5​教师提问：“现在的系数矩阵中，有没有现成的单位矩阵？”学生观察发现，只有x4x_4x4​的系数列向量是单位向量，系数矩阵的秩为3，我们需要一个3阶单位阵作为初始基，但现在只有一个。无法直接得到初始基可行解，单纯形法似乎“卡住了”。教师进一步引导：“既然没有现成的，我们能否‘构造’一个出来？这是否符合数学中常见的‘辅助元素’或‘待定系数’的思想？”从而引出本节课的主题——人工变量法，具体包括大M法和两阶段法。本环节通过制造认知冲突，有效地激发了学生的求知欲和探索欲。（二）核心原理探究一：大M法——引入惩罚机制（约30分钟）1.人工变量的引入（“造基”）：教师阐述核心思想：为了得到初始基，我们可以在每个缺少单位向量的约束方程中，人为地添加一个非负变量，称之为“人工变量”。这些人工变量与原有的松弛变量或剩余变量不同，它们没有实际的经济意义，纯粹是为了“凑出”一个单位矩阵而虚拟的。对于上面的例子，需要在第二个和第三个约束条件中分别加入人工变量，记作x6x_6x6​和x7x_7x7​。此时，新的系数矩阵中，x4,x6,x7x_4,x_6,x_7x4​,x6​,x7​的系数列向量构成一个单位矩阵，可以作为初始可行基。2.惩罚因子的设定（M的奥秘）【核心概念】：教师提问：“我们加入了人工变量，但原问题并没有这些变量。如何保证在最终的最优解中，人工变量都等于0，从而让解回到原问题的可行域中呢？”这里引出大M法的精髓——设置“惩罚因子”。教师解释：在目标函数中，给人工变量赋予一个极大的负系数（对于最大化问题）或极大的正系数（对于最小化问题）。这个极大的数通常用MMM表示，它代表一个任意大的正数。对于本例的max问题，新目标函数变为：max

Z=3x1−x2−x3+0x4+0x5−Mx6−Mx7\{max}Z=3x_1x_2x_3+0x_4+0x_5Mx_6Mx_7max

Z=3x1​−x2​−x3​+0x4​+0x5​−Mx6​−Mx7​教师强调：MMM就像一个“天价罚款”。只要人工变量不为零（哪怕是一个极小的正数），都会导致目标函数值急剧下降（或上升），从而被优化过程所排斥。只要原问题有可行解（即存在一个人工变量全为零的解），单纯形法在迭代过程中就必然会驱使人工变量离基，从而达到“消除惩罚”的目的。3.大M法的求解演绎【关键算法】：教师带领学生在黑板上构建初始单纯形表，并着重讲解含参数MMM的检验数计算方法。初始表中，基变量是x4,x6,x7x_4,x_6,x_7x4​,x6​,x7​，需要将基变量在目标函数中的系数通过行变换消去，以得到非基变量的检验数。（1）构建初始单纯形表：列出所有变量系数和常数项。（2）计算检验数：这是学生最容易出错的地方。教师应详细展示计算过程，例如：σ1=3−[0×1+(−M)×(−4)+(−M)×(−2)]=3−(0+4M+2M)=3−6M\sigma_1=3[0\times1+(M)\times(4)+(M)\times(2)]=3(0+4M+2M)=36Mσ1​=3−[0×1+(−M)×(−4)+(−M)×(−2)]=3−(0+4M+2M)=3−6M。教师解释：由于MMM是很大的正数，3−6M36M3−6M显然是一个负数。但我们此时是最大化问题，检验数正负决定了进基变量。随着迭代进行，检验数中依然会包含MMM，比较检验数的大小时，我们总是认为MMM远远大于任何有限数，因此包含正MMM的检验数最大，包含负MMM的检验数最小。（3）迭代过程：严格按照单纯形法的进基（选最大正检验数）、出基（最小比值原则）、旋转运算（初等行变换）规则进行。在迭代过程中，教师要不断引导学生观察人工变量的变化：它们是逐渐从基变量中被“赶”出去的。一旦某个人工变量离基，对应的列在后续迭代中可以忽略（相当于删除了该列）。（4）结果判定【难点辨析】：情形A：最优解中，所有人工变量均为非基变量（即取值为0），则得到原问题的最优解。情形B：在最终的单纯形表中，基变量中仍含有人工变量，且其取值不为0，则表明原问题无可行解。4.大M法小结：教师总结大M法的本质是通过惩罚机制，在扩大的可行域（包含人工变量）中寻找解，最终将解“拉回”到原问题的可行域。方法直观，但MMM的引入增加了计算复杂性，且在实际计算中，MMM的取值过小或过大都可能带来数值问题10。（三）核心原理探究二：两阶段法——任务分解与执行（约30分钟）1.问题的提出与过渡：教师提出：“大M法中的MMM只是一个符号，手算可行，但在计算机中，MMM必须取一个具体的数值。如果这个值取得不够大，可能会得到错误的结果；取得太大又会影响计算精度。有没有一种方法可以避开抽象的MMM？”从而引出两阶段法。2.第一阶段：判断可行性，寻找初始可行基【关键算法】：（1）构造辅助问题：教师讲解，目标不是直接求原问题，而是构造一个与原问题紧密相关的新问题——辅助问题。该问题的目标函数是求所有人工变量的和最小化（即min

w=xa\{min}w=x_amin

w=xa​的和），而约束条件就是加入人工变量后的原约束方程（不包含原目标函数）。对于同一个例子，辅助问题为：min

w=x6+x7\{min}w=x_6+x_7min

w=x6​+x7​s.t.

{x1−2x2+x3+x4=11−4x1+x2+2x3−x5+x6=3−2x1+x3+x7=1xj≥0,j=1,...,7\{s.t.}\begin{cases}x_12x_2+x_3+x_4=11\\4x_1+x_2+2x_3x_5+x_6=3\\2x_1+x_3+x_7=1\\x_j\ge0,j=1,...,7\end{cases}s.t.

⎩⎨⎧​x1​−2x2​+x3​+x4​=11−4x1​+x2​+2x3​−x5​+x6​=3−2x1​+x3​+x7​=1xj​≥0,j=1,...,7​（2）求解辅助问题：该问题显然有初始可行基（对应x4,x6,x7x_4,x_6,x_7x4​,x6​,x7​），直接用单纯形法求解。如果在最优解中，目标函数min

w=0\{min}w=0min

w=0，则说明所有人工变量都已离基（或虽在基中但取值为0），此时辅助问题的最优解中，前nnn个分量就是原问题的一个初始基可行解。如果在最优解中，min

w>0\{min}w>0min

w>0，则说明至少还有人工变量在基中且取值大于0，这意味着原问题无可行解，计算停止。（3）关键操作：在第一阶段迭代结束时，必须去掉所有人工变量（及其对应的列），并恢复原问题的目标函数系数，为第二阶段做准备。3.第二阶段：求解原问题的最优解【关键算法】：（1）构建初始单纯形表：以第一阶段最优单纯形表为基础，去掉人工变量所在的列，将目标函数行替换为原问题的目标函数系数（本例为max

Z=3x1−x2−x3+0x4+0x5\{max}Z=3x_1x_2x_3+0x_4+0x_5max

Z=3x1​−x2​−x3​+0x4​+0x5​）。（2）恢复典型形式：当前基变量在目标函数中的系数可能非零，需要通过初等行变换将其消去，得到标准的检验数行。（3）继续迭代：利用单纯形法继续求解，直到得到原问题的最优解或判定无界解。4.两阶段法小结：教师总结，两阶段法将一个带惩罚参数的问题分解为两个明确的阶段：第一阶段判断可行性并找基，第二阶段求最优解。这种方法逻辑清晰，避免了抽象参数MMM，在计算机实现中更为稳健。（四）对比辨析与深度融合（约15分钟）【重要】教师组织学生以小组为单位，针对同一个例题，对比大M法和两阶段法的求解过程与思想，并进行深入讨论。讨论要点包括：1.【共同点】：两种方法都是为了处理无初始可行基的问题而引入人工变量的方法。它们的核心目标都是“造基”，并且核心约束都是“让人工变量最终归零”。2.【不同点】：（1）处理人工变量的机制不同：大M法通过目标函数中的惩罚因子M，将人工变量“软性”地消除；两阶段法则通过第一阶段的目标函数（人工变量和），将问题“硬性”地分解为可行性判断和优化两个子任务。（2）计算复杂度：大M法需要始终带着参数M进行符号运算，计算检验数时容易出错；两阶段法在第一阶段是具体的数值计算，虽然多了一个阶段，但计算过程更为稳定和简洁。（3）解的判定：大M法在最终表中若基变量含非零人工变量，则判定无可行解；两阶段法在第一阶段若minw>0，则直接判定无可行解。3.【适用场景】：在实际应用中，特别是计算机求解时，由于大M法中的M难以确定一个既“足够大”又不影响数值稳定性的具体数值，因此计算机软件（如LINGO,MATLAB的linprog函数）通常采用两阶段法或其变种来求解线性规划问题10。通过对比，学生不仅能掌握两种具体方法，更能领悟到“殊途同归”的算法设计哲学——面对同一个困难，可以从不同角度、用不同策略进行攻克，从而提升思维的深度和广度。（五）案例实战与拓展（约15分钟）1.综合案例演练：教师给出一个包含混合约束的实际生产计划问题（如资源分配、产品配比问题），要求学生先建立线性规划模型，然后独立选择一种方法（大M法或两阶段法）进行手算求解（可只迭代一到两步以掌握核心步骤），最后利用运筹学软件（如LINGO）进行验证。2.问题探究：如果第一阶段辅助问题的最优解中，目标函数w=0，但某个人工变量仍留在基变量中且取值为0（即退化情况），这时能否开始第二阶段？如何处理？引导学生思考退化解对两阶段法过渡的影响。3.扩展视野：简要介绍在处理大规模线性规划问题时，还有哪些更高级的“启动”技术，如“PhaseI的偶单纯形法处理”等，激发学有余力的学生进行探究。（六）课堂小结与作业布置（约10分钟）1.课堂小结【重要】：（1）知识层面：我们学习了处理无初始可行基线性规划问题的两种经典方法——大M法和两阶段法。它们的共同核心是引入人工变量，区别在于处理人工变量的方式不同。（2）方法层面：通过对比学习，我们体会了“转化”与“分解”的数学思想。面对复杂问题，我们可以通过引入辅助元素（如人工变量、惩罚因子）或分解问题步骤（如两阶段）来化繁为简。（3）解的判定：再次强调对无可行解、无界解、无穷多最优解的准确判定，特别是无可行解在人工变量法中的判定准则【高频考点】。2.作业布置：（1）基础题（必做）：教材课后习题中关