本科三年级 管理科学专业 割平面法算例求解教学设计

本科三年级管理科学专业割平面法算例求解教学设计一、教学基本信息（一）课程名称：运筹学/管理运筹学/数学规划（二）授课课题：整数规划求解技法（二）：Gomory割平面法算例深度剖析与实现（三）授课对象：本科三年级管理科学、应用数学、工业工程、物流管理等专业学生（四）授课时长：2学时（90分钟）（五）教学目标设定【核心目标】本小节致力于引导学生超越单纯算法记忆的表层，深入理解割平面法的几何本质与代数逻辑，使学生不仅能够“手算”经典算例，更能洞察算法每一步操作背后的数学原理，并初步建立利用计算机求解大规模问题的工程化思维。1.知识与技能目标（对应低阶认知目标）：（1）准确复述Gomory割平面法的基本思想：通过逐步添加线性约束（割平面）切割掉不含整数解的可行域部分，逼近整数最优解。【基础】（2）熟练掌握从最优单纯形表中提取“源行”，并据此推导Gomory切割方程（分数切割）的标准步骤。【核心重点】（3）能够规范地将切割方程转化为新的约束条件，并运用对偶单纯形法进行重新迭代求解，直至获得整数最优解。【核心难点】2.过程与方法目标（对应高阶认知目标）：（1）通过对一个非整数解的“切割—求解—再切割”的迭代过程，体验从“近似”到“精确”的极限逼近思想，培养逻辑推理与算法流程控制能力。【重要】（2）能够从几何视角解释割平面的作用——在保持原问题所有整数可行解的前提下，逐步收缩可行域，体会“松弛”与“收紧”的对偶关系。（3）通过分析算法可能出现的收敛缓慢问题，初步了解算法效率与问题规模的关系，培养批判性思维。3.情感、态度与价值观目标（对应育人目标）：（1）在反复迭代求解的过程中，体会科学研究的严谨性与精益求精的工匠精神。（2）理解数学算法背后蕴含的“逐步改善、逼近最优”的管理决策智慧，将“取其精华，去其糟粕（分数部分）”的哲学思想与科学决策相联系，树立科学的发展观。【课程思政融入点】（3）认识到精确算法在计算机尚未普及年代的历史意义，以及对当今启发式算法设计的启发作用，培养技术演进的历史观。二、教学重难点剖析（一）教学重点：【高频考点】1.Gomory切割方程的构造过程。这是割平面法的“发动机”，是一切后续计算的基础。必须确保学生能准确无误地从最终单纯形表中提取数据并进行分解。2.将切割方程引入原最优单纯形表后的对偶单纯形法迭代。这是算法的“方向盘”，必须让学生理解为何引入新约束后原最优解不再可行，以及如何利用对偶性快速恢复最优。（二）教学难点：【难点】1.切割方程中“整数部分”与“分数部分”的分解与移项逻辑。特别是当变量系数为负数时，如何按照“不超过该数的最大整数”进行规范分解，是学生最容易出错的地方。2.新引入的松弛变量在单纯形表中的系数向量构成（通常为1），以及为何此时必须启动对偶单纯形法而非原始单纯形法。3.从代数运算回溯到几何意义，建立“切割”的空间想象能力。这是从“术”到“道”的跨越。（三）教学关键点：【非常重要】1.选好“源行”的标准：通常选择具有最大分数部分的基变量所在行，以加速收敛。2.保证切割的有效性：新引入的约束必须能够“切掉”当前非整数最优解，但同时必须“保留”所有整数可行解。这是验证切割方程构造正确与否的法则。三、教学方法与准备（一）教学方法：1.启发式讲授法：以问题驱动，层层递进。“为什么非整数解不行？”——“如何构造一把‘刀’？”——“这把‘刀’为什么长这样？”——“切完后怎么继续走？”2.案例教学法：以一个经典、紧凑的算例贯穿始终，将抽象的算法附着于具体的数字运算之上，便于学生模仿与内化。3.可视化演示法：对于简单的二维问题，利用几何图形展示“切割”的过程，帮助学生建立直观认识。对于高维问题，引导学生类比想象。4.对偶分析法：始终强调原问题与对偶问题的视角切换，加深对单纯形法和对偶单纯形法内在统一性的理解。（二）教学准备：1.多媒体课件：包含清晰的算法流程图、关键的代数推导步骤（分步动画演示）、以及二维割平面几何动画。2.板书设计：预留主板书区域用于记录核心算例的完整单纯形表迭代过程，副板书区域用于推导切割方程及记录关键结论。3.预习任务单：要求学生提前复习单纯形法（特别是最终单纯形表的识别）和对偶单纯形法的迭代规则。四、教学实施过程（核心环节，占80%篇幅）【导入环节】温故知新，引出问题（约8分钟）（一）回顾整数规划的挑战：教师首先提出问题：“同学们，上节课我们学习了整数规划，知道了它在人员排班、生产调度、物流网络设计中的广泛应用。我们也认识到，直接对线性规划松弛解进行‘四舍五入’往往得不到可行解，或者得到的是劣解。【基础】那么，有没有一种系统性的方法，可以从松弛解出发，最终收敛到整数最优解呢？”（二）复习分支定界法思想：引导学生快速回顾分支定界法的核心——分而治之，通过隐枚举不断剪枝。这是一种“纵向”分割的策略。（三）引出新思路——横向切割：教师话锋一转：“今天，我们学习另一种截然不同的思想，它不是把问题分成两个子问题，而是像雕刻一样，一刀一刀地‘切’掉可行域中不含整数解的部分，直到剩下的多面体的顶点恰好是整数点。这种方法就是——割平面法。【重要】”教师板书新标题：整数规划的几何雕刻——Gomory割平面法算例详解。【环节一】预热：松弛问题的求解与“病灶”分析（约12分钟）（一）抛出经典算例：教师在大屏幕上展示本节核心算例。为了便于几何解释，选用一个二维纯整数规划问题。【算例】maximizez=x1+x2subjectto:x1+x2≤1（约束1）3x1+2x2≤12（约束2）x1,x2≥0,且为整数（二）求解松弛问题：教师带领学生，将此问题转化为标准型（加入松弛变量x3,x4），并利用单纯形法求解其线性规划松弛问题。教师在黑板上或通过PPT动画，一步步展示迭代过程，最终得到最优单纯形表。初始单纯形表（略去迭代过程，直接展示最终表）：|基变量|b(RHS)|x1|x2|x3|x4||:|:|:|:|:|:||x1|2|1|0|2/5|1/5||x2|3|0|1|3/5|1/5||σj|5|0|0|1/5|3/5|（三）诊断“病灶”——识别非整数解：教师引导学生观察最终表。“同学们请看，在当前最优基下，我们的解是什么？”引导学生回答：x1=2，x2=3。目标函数值z=5。“这是整数解吗？显然是的。那我们的算例是不是太简单了？”教师提出问题。为了演示割平面的完整过程，需要调整算例或更换一个有分数解的算例。教师迅速调整原问题目标函数为maxz=x1+2x2，并快速演示（或直接给出）新的最终单纯形表，确保出现非整数解。修正后算例（确保出现分数解）：maxz=x1+2x2s.t.s.t.x1+x2≤13x1+2x2≤12x1,x2≥0,整数求解其松弛问题，得到最终单纯形表（重点展示）：|基变量|b(RHS)|x1|x2|x3|x4||:|:|:|:|:|:||x1|2|1|0|2/5|1/5||x2|3|0|1|3/5|1/5||σj|5|0|0|1/5|3/5|教师指出：“现在的解是x1=2（整数），x2=3（整数）？等等，我们发现3是整数。这样还是不行。看来需要设计一个经典的教材例题。”教师换用经典算例（P71上的算例，通常是一个分数解更明显的例子，如x1=3/2,x2=1等）。假设P71的算例为：maxz=3x1+2x2s.t.s.t.2x1+3x2≤142x1+x2≤9x1,x2≥0,整数求解其松弛问题，得到最终单纯形表：【非常重要】|基变量|b(RHS)|x1|x2|x3|x4||:|:|:|:|:|:||x2|5/2|0|1|5/4|1/2||x1|13/4|1|0|3/4|1/2||σj|59/4|0|0|1/4|1/2|教师分析：“看！这个最优解是x1=13/4=3.25，x2=5/2=2.5。它们都不是整数。【基础】虽然这个解让目标函数值z=59/4=14.75很‘优’，但它不满足整数要求，不是我们最终想要的。那么，我们如何从这个‘坏’的最优解，一步步走向整数最优解呢？这就需要我们为问题添加一把‘手术刀’。”【环节二】核心揭秘：Gomory切割方程的构造（约20分钟）（一）引入“源行”的概念：教师讲解：“从最终单纯形表中，我们可以任选一个非整数基变量所在的行作为‘源行’（SourceRow），用它来生成切割方程。通常为了加快收敛速度，我们选择分数部分最大的那一行。”在本例中，x1=13/4=3.25，分数部分为0.25；x2=5/2=2.5，分数部分为0.5。因此选择分数部分最大的x2行（b=5/2）作为源行。（二）分解源行系数：教师将x2行的方程写出，并将所有常数和系数分解成整数部分和非负真分数部分之和。【核心难点】源行方程：x2+(5/4)x3+(1/2)x4=5/2分解规则：对于任何一个数，我们将其分解为“整数部分”和“非负分数部分”。整数部分是不超过该数的最大整数，记作[a]。分数部分f=a[a]，满足0≤f<1。教师带领学生逐一分解：常数项b=5/2=2+1/2。所以[b]=2，分数部分fb=1/2。变量x3的系数a13=5/4=1+1/4。所以[a13]=1，分数部分f13=1/4。变量x4的系数a14=1/2。注意：负数分解要格外小心！【易错点】教师重点讲解：不超过1/2的最大整数是多少？是1，因为1≤1/2。所以1/2=(1)+1/2。这里[a14]=1，分数部分f14=1/2。于是，源行方程可以重写为：x2+(1+1/4)x3+(1+1/2)x4=2+1/2（三）移项整理，导出切割方程：教师将整数部分全部移到等式左边，分数部分全部移到右边。(x2+1·x3+(1)·x42)=1/2(1/4)x3(1/2)x4教师指出：等式左边，记为LHS。由于xj都是非负整数，且系数都是整数，括号内的运算结果一定是整数！所以LHS是一个整数。等式右边，记为RHS。由常数分数减去非负变量的非负分数倍构成。RHS一定是一个小于等于1/2的数。一个整数（LHS）等于一个小于等于1/2的数（RHS）。这能推出什么？这个整数必须小于等于0！因此，我们得到一个关键不等式：1/2(1/4)x3(1/2)x4≤0移项整理，得到Gomory切割方程：(1/4)x3+(1/2)x4≥1/2为了将其加入单纯形表，需要化为等式。引入松弛变量s1（s1≥0），并注意将不等式化为≤形式后再加松弛变量。两边同乘以4以简化分数：x3+2x4≥2标准化：x32x4+s1=2，其中s1是新引入的松弛变量。【重要】（四）几何意义解读（关键）：教师在二维坐标图上画出原问题的可行域。指出当前最优解(3.25,2.5)的位置。然后解释我们推导出的切割方程在原变量空间中的等价形式。将x3=142x13x2，x4=92x1x2代入切割方程x3+2x4≥2，可以化简得到原变量空间的切割形式：比如2x1+x2≤7之类的（需根据实际代换结果而定）。教师在图上画出这条直线，展示它是如何切掉包含当前最优解的那一小块区域，但保留了所有整数点。【非常重要】【环节三】实战演练：将切割引入单纯形表并迭代求解（约25分钟）（一）扩充单纯形表：教师将新得到的约束方程x32x4+s1=2添加到原最优单纯形表中，形成一个新表。表631（引入切割后的初始单纯形表）|基变量|b(RHS)|x1|x2|x3|x4|s1||:|:|:|:|:|:|:||x2|5/2|0|1|5/4|1/2|0||x1|13/4|1|0|3/4|1/2|0||s1|2|0|0|1|2|1||σj|59/4|0|0|1/4|1/2|0|（二）分析新表的性质：教师引导学生观察新表。“请同学们看，这个表是可行的吗？b列出现了负数（s1=2），说明当前基解不可行。检验数行全部≤0，说明什么？”引导学生回答：对偶问题是可行的。【关键技能】“当一个线性规划问题的原问题不可行，而对偶问题可行时，我们应该用什么方法求解？”学生齐答：对偶单纯形法！（三）对偶单纯形法迭代求解：教师带领学生运用对偶单纯形法进行迭代。【高频考点】步骤1：确定出基变量。选择b列中最负的数所在行，即s1行。步骤2：确定入基变量。用该行的系数（负数）去除对应的检验数，取比值最小的那一列。对于x3列：(1/4)/(1)=1/4对于x4列：(1/2)/(2)=1/4两个比值相等，任选一个，比如x3作为入基变量。步骤3：进行旋转运算（高斯消元）。以1为主元进行行变换。经过一次对偶单纯形迭代后，得到新表：（假设以s1行、x3列为主元进行运算）|基变量|b(RHS)|x1|x2|x3|x4|s1||:|:|:|:|:|:|:||x2||0|1|0||||x1||1|0|0||||x3|2|0|0|1|2|1||σj||0|0|0|||教师带领学生填满表格中的问号，得到新解。（四）检验新解是否为整数：观察新表的b列。如果所有基变量取值均为整数，则得到整数最优解，算法终止。否则，需要继续在新表中寻找源行，构造新的切割方程，重复上述过程，直到所有基变量取值均为整数。本例经过一次切割后，可能得到整数解，也可能未得到，需视具体计算结果而定。若未得到，教师需展示第二次切割的过程。【环节四】收尾：算法的收敛性与历史评价（约10分钟）（一）强调算法的有限步收敛性：教师总结：“Gomory割平面法是一个精确算法，理论上已经证明，对于纯整数规划，通过有限次这样的切割，我们一定能够收敛到整数最优解。虽然在实际计算中可能存在收敛慢的问题，但其思想具有奠基性意义。”（二）课程思政融入点：教师引申：“‘割平面’的过程，就像我们在分析和解决复杂问题时，要不断剔除那些‘非理性’、‘非核心’的因素，保留并逼近问题的本质。正如我们在改革开放的进程中，要善于‘取其精华，去其糟粕’，吸纳先进经验，同时也要守住我们自己的核心利益和底线。这种不断自我修正、逼近真理的精神，正是科学管理和决策的精髓所在。”【热点】【课程思政】（三）作业布置与拓展思考1.手算练习：完成教材P72页习题5.3，用割平面法求解给定的整数规划问题，要求写出完整的迭代过程。2.编程挑战（选做）：感兴趣的同学可以尝试用Python（配合pulp或ortools库）或MATLAB实现Gomory割平面法，并与分支定界法的求解效率进行简单对比。【拓展】3.思考题：查阅资料，了解为什么割平面法在实际商用求解器（如Gurobi,CPLEX）中往往作