《管理科学专业本科〈运筹学〉课程对偶单纯形法教案》

《管理科学专业本科〈运筹学〉课程对偶单纯形法教案》一、教学基本信息【基础】本节课程题为“对偶单纯形法”，隶属于高等学校管理科学、工商管理、信息管理与信息系统及工程管理等专业的核心必修课《运筹学》5。授课对象为大学本科二年级学生。他们已完成高等数学、线性代数的学习，掌握了线性规划问题的建模、图解法及原始单纯形法的求解步骤，但对线性规划问题内在的对偶机理尚缺乏深刻认识。【重要】本节内容在课程体系中处于承上启下的枢纽位置。它既是对上一章节“线性规划的对偶理论”的具体应用和深化，又是后续进行“灵敏度分析”以及求解“整数规划”（如割平面法）的重要工具4。本教学设计旨在突破传统讲授中只重计算不重思想的窠臼，引导学生从对偶视角重新审视优化问题。二、教学目标设计依据OBE（成果导向教育）理念，结合学生的认知规律，设定以下三维教学目标：（一）知识与技能目标1.【基础】准确陈述对偶单纯形法与原始单纯形法在迭代原理上的根本区别，理解“保持对偶可行，逐步消除原始不可行”的核心思想2。2.【重要】熟练掌握对偶单纯形法的迭代步骤，能够独立完成从寻找初始正则基到得出最优解的完整计算过程8。3.能够准确识别对偶单纯形法的适用场景，特别是针对“≥”约束或等式约束且不含单位矩阵的极小化问题，能够灵活运用此方法简化计算7。（二）过程与方法目标1.通过对比分析，培养学生透过现象看本质的辩证思维能力，理解原问题与对偶问题如同一枚硬币的两面，在算法上可以实现对立统一。2.在求解线性规划问题时，引导学生根据不同的问题结构（变量少、约束多或约束为“≥”型），学会择优选择原始单纯形法或对偶单纯形法，培养算法优化的策略性思维。（三）情感态度与价值观目标1.【非常重要】通过介绍我国古代“田忌赛马”、“丁谓建宫”中的运筹思想，以及华罗庚、钱学森等老一辈科学家在建国初期排除万难回国推广运筹学的事迹，增强学生的民族自豪感与文化自信，理解运筹学在国民经济建设中的巨大作用1。2.在算法迭代的严谨推导中，培养学生一丝不苟、精益求精的工匠精神和科学精神。三、教学重点与难点（一）教学重点1.对偶单纯形法的基本原理及其与原始单纯形法的对偶关系。2.对偶单纯形法的迭代步骤（换出变量与换入变量的确定规则）4。3.对偶单纯形法的适用条件及计算实现。（二）教学难点1.【难点】【高频考点】理解“正则解”的概念，即为什么初始检验数必须全部非正（对于极大化问题）或全部非负（对于极小化问题）。2.当换出变量所在行所有系数均为非负数时，判断原问题无可行解的数学原理。3.将抽象的矩阵推导转化为具象的表上操作，理解每一次迭代实际上是在对偶问题的可行域中移动。四、教学实施过程（核心环节）本环节设计为3学时（约135分钟），采用“问题驱动—理论溯源—案例推演—算法对比—思政升华”的闭环教学模式。（一）创设情境，逆向导入（约10分钟）1.复习设问：教师在大屏幕上展示上一节课的经典生产计划问题（极大化利润），并提出问题：“假如工厂现在不打算生产，而是要将资源出租，应该如何确定最低租金（即对偶价格）？”由此引出对偶问题的最优解（影子价格）4。2.认知冲突：教师引导学生观察原问题最终单纯形表中的检验数行。提问：“大家注意到没有，原问题的最优单纯形表里，不仅给出了最优生产方案，还在检验数行直接给出了对偶问题的最优解。这是为什么？”3.引入课题：这种对应关系启发了一种新的算法思路——如果我们能先保证对偶问题的解是可行的（即检验数满足最优条件），然后通过迭代使原问题从不可行变为可行，不就能找到最优解了吗？这就是今天要学习的“对偶单纯形法”。（二）理论溯源，原理剖析（约25分钟）1.【重要】从单纯形表的矩阵形式看对偶关系教师通过板书，简要回顾单纯形法的矩阵描述6：当前约束条件为：X_B=B^{1}bB^{1}NX_NB^{1}X_s目标函数值：z=C_BB^{1}b+(C_NC_BB^{1}N)X_NC_BB^{1}X_s其中，检验数σ_j=C_jC_BB^{1}P_j，而单纯形乘子Y=C_BB^{1}就是对偶问题的解。由此得出结论：在单纯形表的检验数行，我们直接看到了对偶问题的解。如果所有检验数σ_j≤0（极大化问题），则意味着对偶问题的解是可行的（即满足对偶约束）。2.【难点】正则基的引入定义：如果原始问题的一个基，其所对应的检验数全部满足最优性条件（即对偶可行），但基变量的取值B^{1}b有负数分量（原始不可行），则称此基为正则基7。核心思想：对偶单纯形法就是从一个正则基出发，在保持检验数全部符合最优性条件（保持对偶可行）的前提下，逐步迭代，去掉基变量中的负分量，直到原始解也变成可行解（即B^{1}b≥0），此时即得最优解。（三）规则详解，算法构建（约20分钟）教师结合流程图，详细讲解对偶单纯形法的迭代步骤（以标准极大化问题为例，要求所有检验数σ_j≤0）4：1.第一步（初始表）：列出单纯形表，检查b列。若b列全部非负且σ_j≤0，则已达最优；若b列存在负数且σ_j≤0，则转入下一步。2.【高频考点】第二步（确定换出变量）：找出最负的基变量。通常取min{b_i|b_i<0}对应的基变量X_{B_r}换出。3.【高频考点】第三步（确定换入变量）：检查换出行r对应的所有系数a_{rj}。如果所有a_{rj}≥0，则问题无可行解，停止计算7。若存在a_{rj}<0，则计算比值θ=min_{j}{|σ_j/a_{rj}||a_{rj}<0}，选取θ最小者对应的非基变量X_k为换入变量。这里必须强调，比值规则与原始单纯形法恰好相反，目的是为了在迭代后保持所有检验数仍非正。4.第四步（迭代运算）：以a_{rk}为主元素进行旋转运算，得到新的单纯形表，返回第一步。（四）【非常重要】案例推演，实战演练（约40分钟）选取一个典型的、适合对偶单纯形法求解的例题进行板演，让学生直观感受算法的魅力。例题：用对偶单纯形法求解下述线性规划问题4：minz=2x_1+3x_2+4x_3s.t.x_1+2x_2+x_3≥32x_1x_2+3x_3≥4x_1,x_2,x_3≥0步骤一：转化模型。将问题转化为适于求解的形式（引入剩余变量，并乘以1构造基）。令z‘=z,将目标转为maxz’=2x_13x_24x_3。约束条件化为等式：x_12x_2x_3+x_4=32x_1+x_23x_3+x_5=4x_j≥0。步骤二：列初始单纯形表（表1）。（教师在此详细展示表的构造：基变量为x_4,x_5；b列为3,4；检验数σ_j为[2,3,4,0,0]，全部≤0，满足对偶可行性）。步骤三：第一次迭代。换出：min{3,4}=4，对应x_5换出（第2行）。换入：检查第二行a_{2j}：[2,1,3,0,1]。负数有2,3。计算比值：对于a_{21}=2:|σ1/a_{21}|=|(2)/(2)|=1对于a_{23}=3:|σ3/a_{23}|=|(4)/(3)|=4/3≈1.33取最小比值1，对应x_1，故x_1换入。主元素为2。步骤四：进行旋转运算，得到新表（表2，计算过程详细展开，讲解初等行变换技巧）。步骤五：检查新表（表2）b列。此时基变量变为x_4=1，x_1=2，b列仍有负数1，且检验数已变化但仍需保持非正（计算后应满足）。重复上述步骤，换出x_4，换入x_2或x_3，直至b列全部非负。最终得到最优单纯形表（表3），b列全为非负，检验数全为非正，得出最优解x_1=11/5，x_2=2/5，x_3=0，代入原目标得minz=28/5。（五）对比分析，归纳总结（约15分钟）1.【热点】原始对偶算法对比表：教师引导学生以小组讨论形式，填写以下对比表格，并从哲学角度进行升华7。对比维度 原始单纯形法 对偶单纯形法解题思路 保持原始可行（b≥0），逐步使检验数满足最优（σ≤0） 保持对偶可行（σ≤0），逐