《运筹学》单纯形法与整数规划教学设计

《运筹学》单纯形法与整数规划教学设计一、课程基本信息（一）课程名称：运筹学（二）授课主题：单纯形法与整数规划（三）授课对象：大学本科三年级信息管理与信息系统、应用数学、管理科学、工业工程等专业（四）授课学时：2学时（90分钟）（五）教学类型：理论课与实践课结合（六）课程性质：专业核心课/必修课二、教材与学情分析（一）教材分析：【基础】本课程选用国家级规划教材《运筹学》（清华大学出版社，第4版）作为核心参考。本章节“整数规划”是线性规划的自然延伸和重要分支，而“单纯形法”作为求解线性规划问题的通用算法，是理解整数规划割平面法和分支定界法的基础。教材在内容编排上，从标准型的引入，到单纯形法的原理与步骤，再到整数规划概念的提出与求解思路，逻辑严谨，层层递进。然而，教材中理论推导较多，对算法背后的几何意义和经济管理背景的介绍相对简略，这为本教学设计提供了拓展和深化的空间，旨在将抽象的算法与生动的实际问题相结合。（二）学情分析：【重要】授课对象为大学三年级学生，他们已经完成了高等数学、线性代数等前序课程的学习，具备良好的矩阵运算能力和逻辑思维能力。在前序章节中，学生已经学习了线性规划问题的图解法、基本概念（可行解、基可行解、最优解）以及线性规划问题的标准型转化。这为本节课学习单纯形法奠定了坚实的理论基础。然而，学生可能存在的学习障碍包括：1.对单纯形法迭代原理的理解停留在机械计算层面，缺乏几何直观感受。2.对“退化”、“循环”等概念感到困惑，难以理解其实际影响。3.对整数规划与线性规划的本质区别认识不清，容易将二者割裂开来。4.缺乏将实际问题抽象为整数规划模型并进行求解的意识和能力。（三）教学理念与设计思路：【非常重要】本节课秉承“以学生为中心，以问题为导向，以能力培养为目标”的教学理念。教学设计的核心思路是：1.问题驱动：以一个经典的“生产计划与投资组合”综合案例贯穿始终，从建立线性规划模型，到单纯形法求解，再到引入整数约束，最后尝试求解整数规划，形成一个完整的闭环。2.几何直观与代数演绎相结合：借助二维图形的动态演示（模拟），帮助学生理解单纯形法“沿凸集边界顶点寻优”的几何本质，再严谨推导单纯形表的代数操作，实现从感性认识到理性认识的飞跃。3.算法思维与工具应用并重：不仅讲授单纯形法的详细计算步骤，更强调其作为迭代算法的思想精髓。同时，引入LINGO或MATLAB等优化软件进行演示，让学生体验从“手算”到“机算”的效率提升，并理解软件求解整数规划的基本原理。4.高阶思维培养：通过对整数规划“难解性”的探讨，激发学生的探索精神，引导学生思考如何根据问题特性选择合适的求解策略，培养其批判性思维和系统优化思维。三、教学目标根据布鲁姆教育目标分类法，本节课设定以下教学目标：（一）知识层面：1.熟练掌握线性规划问题单纯形法的求解步骤，包括：化标准型、初始单纯形表的构建、最优性检验、进基变量与离基变量的确定、主元旋转、迭代更新。2.深刻理解单纯形法迭代原理的几何意义（从可行域的一个顶点移动到相邻的改进顶点）。3.准确理解整数规划的基本概念、分类（纯整数规划、混合整数规划、01整数规划）及其与一般线性规划的本质区别。4.了解求解整数规划的两种基本方法：分支定界法和割平面法的核心思想。（二）能力层面：1.能够熟练运用单纯形法求解不超过4个变量、3个约束的小规模线性规划问题。2.能够将简单的实际决策问题（如含固定成本、互斥方案、逻辑约束的问题）正确地抽象为整数规划模型。3.能够使用优化软件（如LINGO）对整数规划模型进行求解，并能解读求解报告。4.初步具备运用优化思想和算法思维分析和解决复杂管理决策问题的能力。（三）素养层面：1.体会运筹学中“建模求解分析”的科学决策过程，培养严谨求实的科学态度和逻辑思维能力。2.认识到数学工具在管理实践中的巨大价值，增强学习的主动性和探索欲。3.理解现实决策中“离散性”和“整体性”的普遍存在，培养系统思考、全局优化的思维习惯。四、教学重点与难点（一）教学重点：【高频考点】1.单纯形法的迭代步骤与单纯形表的构建、更新计算。2.整数规划模型的建立，特别是如何引入01变量处理逻辑约束。（二）教学难点：【难点】1.单纯形法迭代原理的几何意义与代数运算之间的内在联系。2.对单纯形法中可能出现“退化”和“循环”现象的理解。3.整数规划与线性规划最优解之间的关系，理解为何不能简单地通过“四舍五入”获得整数解。五、教学方法与手段（一）教学方法：1.启发式讲授法：用于讲解核心概念和基本算法步骤。2.案例驱动教学法：以一个综合案例串联知识点，激发学生兴趣。3.几何图形动态演示法：利用GeoGebra或PPT动画模拟单纯形法的寻优路径，突破难点。4.问题探究式教学法：通过设置一系列问题链，引导学生思考算法背后的原理，如“为什么我们要找相邻的顶点？”、“如何判断一个解是否最优？”等。5.对比教学法：对比线性规划与整数规划的求解过程和最优解特性，加深学生理解。（二）教学手段：1.多媒体课件（PPT）：展示算法流程、案例文本、图形动画和软件操作界面。2.板书：用于关键公式推导、单纯形表示范计算、错误纠正等，与学生思维同步。3.优化软件（LINGO/MATLAB）：现场演示复杂模型的求解过程，验证手算结果。六、教学实施过程（90分钟）（一）导入与复习（5分钟）【基础】1.课程回顾：上节课我们学习了线性规划问题的图解法，它可以直观地帮助我们找到两个变量的线性规划问题的最优解。但是，当变量个数超过3个时，我们就无法在平面上作图了。那么，对于现实世界中动辄成百上千个变量的大规模问题，我们该如何求解呢？这就要引出我们今天的主角——单纯形法。2.创设情境：假设我们是一家小型制造企业的运筹分析师。企业计划生产两种产品：标准版手机和豪华版手机。生产一台标准版手机需要1小时加工、1小时装配，利润为300元；生产一台豪华版手机需要2小时加工、1小时装配，利润为500元。工厂每周可利用的加工工时不超过40小时，装配工时不超过30小时。此外，根据市场部门预测，豪华版手机每周市场需求不超过15台。我们该如何安排生产计划，才能使得周利润最大化？3.学生活动：引导学生快速将上述问题转化为线性规划模型。设生产标准版手机x1x_1x1​台，豪华版手机x2x_2x2​台。目标函数：max⁡z=300x1+500x2\maxz=300x_1+500x_2maxz=300x1​+500x2​约束条件：x1+2x2≤40x_1+2x_2\le40x1​+2x2​≤40（加工工时）x1+x2≤30x_1+x_2\le30x1​+x2​≤30（装配工时）x2≤15x_2\le15x2​≤15（市场需求）x1,x2≥0x_1,x_2\ge0x1​,x2​≥04.引出课题：这个模型正是我们上节课学习的线性规划模型。今天，我们就将用一种通用的数值方法——单纯形法，来求解它，并以此为基础，探究如果要求产量必须是整数时，问题会变得怎样复杂和有趣。（二）单纯形法的核心思想与准备（15分钟）【重要】1.从几何到代数：复习图解法中可行域的概念。在二维空间中，可行域是一个凸多边形。最优解一定在凸多边形的某个顶点（即可行域的极点）上取得。对于n维空间，这个结论依然成立：最优解一定在可行域的某个顶点（我们称之为“基可行解”）上取得。因此，寻找最优解的问题，就转化为在有限的基可行解中寻找使目标函数值最大的那个解。2.单纯形法的基本思想：单纯形法就是一种聪明地从一个基可行解出发，沿着可行域的边缘移动到另一个“相邻的”、能使目标函数值得到改善的基可行解，直到无法再改善为止的迭代算法。它并不是盲目地枚举所有顶点，而是有选择性地“爬山”。3.准备工作：化标准型【基础】为了进行代数运算，我们需要将上述模型转化为标准形式。标准形式要求：目标函数为最大化（或最小化），约束条件均为等式，且所有变量均为非负。引入松弛变量x3,x4,x5x_3,x_4,x_5x3​,x4​,x5​，将不等式约束化为等式：x1+2x2+x3=40x_1+2x_2+x_3=40x1​+2x2​+x3​=40x1+x2+x4=30x_1+x_2+x_4=30x1​+x2​+x4​=30x2+x5=15x_2+x_5=15x2​+x5​=15目标函数：max⁡z=300x1+500x2+0⋅x3+0⋅x4+0⋅x5\maxz=300x_1+500x_2+0\cdotx_3+0\cdotx_4+0\cdotx_5maxz=300x1​+500x2​+0⋅x3​+0⋅x4​+0⋅x5​此时，变量x1,x2x_1,x_2x1​,x2​称为决策变量，x3,x4,x5x_3,x_4,x_5x3​,x4​,x5​称为松弛变量，它们也有其经济含义：未被利用的资源（加工工时、装配工时、豪华版手机市场容量）。（三）单纯形法的表格形式与迭代求解（40分钟）【高频考点】【核心】1.构建初始单纯形表（5分钟）：从标准型中，我们可以立即找到一个初始基可行解。令非基变量x1=0,x2=0x_1=0,x_2=0x1​=0,x2​=0，则基变量x3=40,x4=30,x5=15x_3=40,x_4=30,x_5=15x3​=40,x4​=30,x5​=15。这个解对应着图解法中的原点(0,0)，即不生产任何产品，利润为0。我们将这个信息填入单纯形表。教师需详细讲解单纯形表的结构：第一行是目标函数系数的相反数（即检验数行，用于判断最优性），中间部分是约束方程系数矩阵，最右一列是资源常数项（即基变量的取值），最左一列标明当前基变量。2.最优性检验（5分钟）：讲解检验数\(\sigma_j=c_jC_BB^{1}P_j\)的经济含义：表示变量\(x_j\)每增加一个单位，目标函数能增加多少。在初始表中，检验数就是目标函数系数的相反数。对于最大化问题，如果所有非基变量的检验数都\(\le0\)，则当前解达到最优，因为任何变量的引入都无法再增加目标函数值。如果存在正的检验数，则说明对应的变量每增加一个单位，利润还能提高，当前解不是最优。在本例中，\(\sigma_1=300>0,\sigma_2=500>0\)，显然不是最优解。我们需要迭代。3.确定进基变量与离基变量（10分钟）：进基变量：选择正检验数中最大的那个对应的变量进入基变量。本例中，\(\max\{300,500\}=500\)，所以选择\(x_2\)进基。这符合“贪婪”的原则，优先考虑让单位利润最高的产品增产。离基变量：当确定\(x_2\)要增加时，我们需要从现有的三个基变量\(x_3,x_4,x_5\)中赶出一个。离基变量的确定依据是最小比值原则（\(\theta\)规则）。我们计算“右端项”与“进基变量所在列的正系数”的比值：对于\(x_3\)所在行：\(40/2=20\)对于\(x_4\)所在行：\(30/1=30\)对于\(x_5\)所在行：\(15/1=15\)选择最小比值\(\min\{20,30,15\}=15\)对应的\(x_5\)作为离基变量。这个比值的含义是在其他非基变量（此时只有\(x_1\)）为0的前提下，\(x_2\)最多能增加多少，而不会导致任一基变量变成负数。最小比值保证了新解的可行性。这里比值为15，意味着当\(x_2\)增加到15时，\(x_5\)首先变为0，被挤出基变量。4.主元旋转（20分钟）：这是单纯形法计算的核心步骤，教师需在板书上详细演示高斯消元过程，确保每个学生跟上。确定主元素：进基变量列与离基变量行交叉处的元素，即\(a_{32}=1\)。第一步：将主元所在行（即第3行）除以主元本身（1），使主元变为1。该行变为：\(0x_1+1x_2+0x_3+0x_4+1x_5=15\)。第二步：用新的主元行消去其他行（包括检验数行）中进基变量\(x_2\)的系数，使得\(x_2\)在其他行和检验数行的系数变为0。消去第1行：新第1行=旧第1行2×新第3行→\((10)x_1+(22)x_2+(10)x_3+(00)x_4+(02)x_5=4030\)→\(x_1+0x_2+x_3+0x_42x_5=10\)。消去第2行：新第2行=旧第2行1×新第3行→\((10)x_1+(11)x_2+(00)x_3+(10)x_4+(01)x_5=3015\)→\(x_1+0x_2+0x_3+x_4x_5=15\)。消去检验数行（第0行）：新检验数行=旧检验数行500×新第3行→\((3000)x_1+()x_2+(00)x_3+(00)x_4+(0500)x_5=07500\)→\(300x_1+0x_2+0x_3+0x_4500x_5=7500\)。移项到常规形式：\(z+0x_1+0x_2+0x_3+0x_4+500x_5=7500\)，所以新的检验数\(\sigma_1=300\)（注意符号处理），\(\sigma_5=500\)。但为了在表中表达清晰，通常记录检验数\(\sigma_j\)。迭代后的新基变量为\(x_3,x_4,x_2\)，对应的基解为\(x_2=15,x_3=10,x_4=15,x_1=0,x_5=0\)。目标值\(z=3000+50015=7500\)。观察新检验数，\(\sigma_1=300>0\)，说明仍未达到最优。5.进行第二次迭代（5分钟）：进基变量：\(x_1\)（因为\(\sigma_1=300>0\)）。计算最小比值：θ值基于新单纯形表。对于\(x_3\)行：\(10/1=10\)对于\(x_4\)行：\(15/1=15\)对于\(x_2\)行：\(15/0\)（系数为0，不参与比值，表示\(x_1\)的增加不会影响\(x_2\)的值，因此它不会限制\(x_1\)的增加）最小比值\(\min\{10,15\}=10\)，所以离基变量为\(x_3\)。主元为\(a_{11}=1\)。进行主元旋转，教师引导学生快速计算新表。最终得到新表，检验数全部≤0，得到最优解：\(x_1=10,x_2=15,x_3=0,x_4=5,x_5=0\)，最大利润\(z=30010+50015=10500\)元。此时，\(x_3=0\)表示加工工时被全部用完，\(x_4=5\)表示装配工时还剩余5小时，\(x_5=0\)表示豪华版手机的市场需求刚好被满足。6.几何意义回顾（2分钟）：结合PPT动画，回顾整个迭代过程：初始解(0,0)→第一次迭代后(0,15)→第二次迭代后(10,15)。这正是从可行域的一个顶点，沿着边界移动到另一个相邻顶点，最终达到最优顶点的过程。（四）引入整数规划（20分钟）【难点】【热点】1.问题深化（3分钟）：刚才我们得到了一个完美的生产计划：生产10台标准版和15台豪华版手机，获得最大利润10500元。但现在，销售部门突然提出，他们接到的是整机订单，产品必须以“台”为单位出货，不能有半台或小数台。而在我们的最优解中，x1=10,x2=15x_1=10,x_2=15x1​=10,x2​=15恰好是整数，非常幸运。但假如我们得到的最优解是x1=9.5,x2=15.2x_1=9.5,x_2=15.2x1​=9.5,x2​=15.2呢？我们能否简单地将其四舍五入为x1=10,x2=15x_1=10,x_2=15x1​=10,x2​=15？让学生思考，并指出可能的问题：四舍五入后的解可能不再是可行解（可能违背资源约束），或者即使可行，也离真正的最优整数解相去甚远。这就引出了整数规划问题。2.整数规划的定义与分类（5分钟）【基础】：定义：当线性规划问题中的全部或部分变量被限制为整数时，就构成了整数线性规划（IntegerLinearProgramming），简称整数规划（IP）。分类：（1）纯整数规划：所有变量都限制为整数。（2）混合整数规划：只有一部分变量限制为整数。（3）01整数规划：变量只能取0或1，常用于表示“是/否”、“选/不选”等决策。3.01变量的应用与建模【高频考点】（7分钟）：01变量是整数规划中一个非常强大且灵活的工具。回到我们的案例，假设企业想从两个新项目中选一个投资：项目A需要投入10万，预计年收益2万；项目B需要投入8万，预计年收益1.8万。总资金只有15万。这个投资决策与生产计划是联动的，因为资金来源于同一笔预算。我们该如何建模？引入01变量\(y_1,y_2\)，分别表示是否投资项目A、B（1表示投，0表示不投）。新增约束：（1）资金约束：\(10y_1+8y_2\le15\)（2）项目选择的逻辑关系：比如“最多选一个”，可表达为\(y_1+y_2\le1\)。（3）项目与产量的关联：如果投资A，标准版手机的产量必须增加某个比例？这需要通过引入大M法来处理更复杂的“ifthen”逻辑，例如“如果\(y_1=1\)，则\(x_1\ge5\)”。可转化为\(x_1\ge5y_1\)。通过这个例子，让学生感受到01变量在描述离散决策和逻辑关系中的强大建模能力。4.整数规划的求解思路与困难（5分钟）：提问：能否直接使用单纯形法求解整数规划？回答：不能。单纯形法求得的最优解可能在非整数顶点上。解释为什么不能简单“四舍五入”：以本案例为背景，假设某线性规划松弛问题的最优解是(9.5,15.2)，四舍五入得到(10,15)。但这个点可能不在可行域内，或者即使在内，也远非最优。整数规划的可行域是离散的点集，其最优解与松弛问题最优解之间没有简单的邻近关系。简要介绍两种经典算法思想：（1）分支定界法：【重要】隐式枚举法的思想。将原整数规划问题不断分解为两个子问题（分支），通过求解松弛问题的解来估算目标值的上界/下界（定界），并剪掉那些不可能产生更优解的分支。这是一种“聪明地穷举”。（2）割平面法：通过不断增加新的线性约束（割平面），逐步切掉松弛问题可行域中不包含整数可行解的部分，最终迫使最优解落在某个整数极点上。强调：整数规划问题的求解难度远大于线性规划，属于NPhard问题。随着问题规模的增大，求解时间可能呈指数级增长。这让学生对现实世界决策的复杂性有敬畏之心。（五）软件求解与结果分析（7分钟）1.LINGO软件演示：将我们的综合案例（包含投资选择的01变量）用LINGO代码写出，现场演示求解过程。代码示例：MODEL:MAX=300X1+500X2+2Y1+1.8Y2;X1+2X2<=40;X1+X2<=30;X2<=15;10Y1+8Y2<=15;Y1+Y2<=1;@GIN(X1);@GIN(X2);!指定X1,X2为整数变量;@BIN(Y1);@BIN(Y2);!指定Y1,Y2为01变量;END运行并观察求解报告，解读“Globaloptimalsolutionfound”的含义，查看目标函数值和各变量的取值。2.结果对比与分析：对比仅生产计划（无投资）的整数解与加入投资后的整数解，分析利润变化的原因，引导学生思考组合优化的价值。（六）课堂总结与作业布置（3分钟）1.知识回顾：（1）单纯形法：是一种从可行域一个顶点出发，沿边缘移动到相邻改进顶点，最终找到最优解的迭代算法。其核心步骤包括：化标准型、建立初始表、最优性检验、确定进基/离基变量、主元旋转。（2）整数规划：变量取整数的线性规划。其求解难度远高于线性规划，常用的方法有分支定界法和割平面法。01变量是处理逻辑选择问题的关键工具。2.思想升华：今天的课程，我们从几何直观走向代数计算，从连续决策走向离散决策。单纯形法体现了算法的精妙与效率，而整数规划则揭示了现实决策的复杂性与建模的灵活性。希望同学们不仅学会计算，更要理解算法背后的优化思想，并将其内化为系统思考和科学决策的思维习惯。3.作业布置：（1）【基础巩固】课后习题：用单纯形法求解教材P12