1. 项目概述从“硬凑”到“真解”的人工变量法实战搞运筹学或者生产调度、资源优化的朋友对线性规划肯定不陌生。单纯形法是咱们手里的核心武器但它的启动有个前提你得有一个现成的“可行基”也就是一个初始的可行解。这就像开车你得先打着火。可现实中很多问题特别是“≥”或“”约束条件一堆的时候想直接找到一个起点单位矩阵形式的基特别费劲。这时候“人工变量法”就派上用场了它本质上是一种“无中生有”的启动技巧通过引入一些额外的、成本极高的“人工变量”强行构造出一个初始可行基让单纯形法这个引擎先转起来然后再想办法把这些“临时工”清退掉找到原问题的真解。今天咱们不聊枯燥的理论直接上手拆解一个经典案例的第二次迭代全过程。为什么是第二次因为第一次迭代往往是初始化相对简单。第二次迭代开始才是检验算法理解、计算功底和逻辑判断的关键。我们会一步步走过中心元变换、检验数计算、最优解判定再到选择入基和出基变量。这个过程里任何一个计算失误或者逻辑误判都会导致后续全盘皆错。我结合自己多年教学和解决实际项目的心得把容易踩坑的地方和提速技巧都揉进去讲清楚。2. 案例回顾与第二次迭代的起始状态为了后续讨论有个落脚点我们先明确一下案例的初始模型。假设我们面对这样一个线性规划问题标准化后目标函数Max Z 3x₁ 5x₂ 约束条件x₁ x₃ 42x₂ x₄ 123x₁ 2x₂ x₅ 18x₁, x₂, x₃, x₄, x₅ ≥ 0这里x₃, x₄, x₅是松弛变量已经构成了一个单位矩阵的初始可行基所以不需要人工变量。但为了演示人工变量法的迭代我们假设一个更复杂的情况假如第三个约束原来是3x₁ 2x₂ ≥ 18我们引入了剩余变量x₅值为负不可行和人工变量R₁。经过第一次迭代大M法或两阶段法人工变量R₁已被替换出基我们得到了一个不含人工变量的可行基假设这个基是(x₃, x₄, x₂)对应的单纯形表如下这是第二次迭代的起点基变量系数x₁x₂x₃x₄x₅R₁解 (b)x₃01010-1/2...1x₄000011...6x₂53/21001/2...9检验数 σⱼ-9/20005/2...Z45注意上表中R₁列已被忽略因为人工变量出基后其列在后续计算中不再参与迭代可以删除以避免干扰。...代表该列数据已无关紧要。解的值和系数是假设的用于演示。这个表就是我们的“战场”。Z45是当前基可行解下的目标函数值。现在我们要开始第二次迭代目标是判断这个解是否最优如果不是就改进它。2.1 理解当前表格的“格局”在动手计算前先花半分钟看清表格的格局这能避免低级错误基变量列当前在基中的是x₃,x₄,x₂。它们的系数目标函数中的系数C_B分别是0, 0, 5。解列 (b)给出了当前基变量的取值x₃1,x₄6,x₂9。非基变量x₁和x₅取值为0。检验数行 (σⱼ)这是判断是否最优的生命线。其计算公式为σⱼ Cⱼ - C_B * B⁻¹ * Pⱼ在表格计算中体现为σⱼ Cⱼ - (基变量系数与对应列向量内积)。3. 最优解判定与入基变量选择单纯形法的核心逻辑是如果所有检验数 σⱼ ≤ 0最大化问题则当前解为最优解否则选择检验数最大的正数对应的变量进入基以最快提升目标函数。3.1 计算与判定根据上表非基变量x₁和x₅的检验数分别为σ₁ -9/2 -4.5σ₅ 5/2 2.5判定结果存在正检验数σ₅ 2.5 0因此当前解不是最优解。目标函数值还有提升的空间。选择入基变量在所有正检验数中σ₅是唯一的正数σ₁为负因此入基变量确定为x₅。选择最大正检验数变量入基被称为“最速上升规则”它通常能减少迭代次数。实操心得这里有个易错点。如果两个检验数都是正数比如σ₁3,σ₅2那么选x₁入基。但有些教材或软件会采用“Bland规则”选下标最小的变量来防止循环不过在非退化的普通案例中用最速上升规则更直观高效。咱们手算时认准“最大正数”就行。4. 出基变量选择与中心元确定确定了谁进来 (x₅)接下来就要决定谁出去。原则是可行性原则即保证新的基解仍然所有变量≥0。4.1 计算比值θ规则我们需要查看入基变量x₅所在的列常称“主元列”或“枢轴列”中对应于当前基变量行中正系数的那些行。计算每一行的比值θᵢ 解 bᵢ / 主元列系数 aᵢ₅。从表中提取数据对于基变量x₃行b₃ 1,a₃₅ -1/2。系数为负忽略。因为如果用一个负系数去除正数得到的比值是负的这不符合“替换后变量非负”的几何意义相当于沿可行域边界反向移动。对于基变量x₄行b₄ 6,a₄₅ 1。系数为正θ₄ 6 / 1 6。对于基变量x₂行b₂ 9,a₂₅ 1/2。系数为正θ₂ 9 / (1/2) 18。比值集合{θ₄6, θ₂18}。4.2 确定出基变量选择比值集合中最小的非负比值对应的基变量出基。这里最小比值是θ₄ 6它对应基变量x₄。因此出基变量是x₄。注意事项为什么选最小比值这保证了将入基变量x₅的值从0增加到这个最小比值时出基变量x₄的值刚好降到0而其他所有基变量仍保持非负。如果超过了这个最小比值x₄将变为负值解就不可行了。这是单纯形法能始终在可行域顶点间移动的关键。4.3 确定中心元入基列 (x₅) 与出基行 (x₄行) 交叉位置的元素称为中心元或枢轴元素。 在这个案例中中心元就是a₄₅ 1。5. 中心元变换表格更新的核心操作这是整个迭代中最需要细心和耐心的计算环节目的是通过行初等变换将中心元变为1并将其所在列的其他元素包括检验数行变为0从而让入基变量x₅替换出基变量x₄形成新的单位矩阵基。我们的目标是得到关于新基(x₃, x₅, x₂)的单纯形表。5.1 变换步骤详解设中心元位于第r行出基行第k列入基列其值为a_rk。变换规则如下更新出基行第r行即x₄行将整个出基行除以中心元a_rk使中心元变为1。新x₄行即将被替换为x₅行[0, 0, 0, 1, 1, ..., 6]÷ 1 [0, 0, 0, 1, 1, ..., 6]实际上因为中心元已经是1这一行数值不变。但基变量需要改变该行对应的基变量由x₄替换为x₅其系数C_B由原来的0变为x₅在目标函数中的系数。这里我们需要知道原问题中x₅的系数。假设x₅是剩余变量或松弛变量其系数为0。所以新行的系数C_B变为0。更新其他基变量行第i行i≠r和检验数行对于这些行用该行减去其主元列系数a_ik乘以新的出基行。公式新行 旧行 - (a_ik) * 新出基行让我们一步步计算已知新出基行即未来的x₅行L_r_new [0, 0, 0, 1, 1, ..., 6](基变量为x₅, C_B0)旧x₃行L₃_old [1, 0, 1, 0, -1/2, ..., 1],a₃₅ -1/2旧x₂行L₂_old [3/2, 1, 0, 0, 1/2, ..., 9],a₂₅ 1/2旧检验数行σ_old [-9/2, 0, 0, 0, 5/2, ..., Z45],a_σ₅ 5/2计算新x₃行L₃_new L₃_old - (-1/2) * L_r_new L₃_old (1/2) * L_r_new[1, 0, 1, 0, -1/2, ..., 1] (1/2)*[0, 0, 0, 1, 1, ..., 6][1, 0, 1, 0, -1/2, ..., 1] [0, 0, 0, 1/2, 1/2, ..., 3][1, 0, 1, 1/2, 0, ..., 4]计算新x₂行L₂_new L₂_old - (1/2) * L_r_new[3/2, 1, 0, 0, 1/2, ..., 9] - (1/2)*[0, 0, 0, 1, 1, ..., 6][3/2, 1, 0, 0, 1/2, ..., 9] - [0, 0, 0, 1/2, 1/2, ..., 3][3/2, 1, 0, -1/2, 0, ..., 6]计算新检验数行σ_new σ_old - (5/2) * L_r_new[-9/2, 0, 0, 0, 5/2, ..., 45] - (5/2)*[0, 0, 0, 1, 1, ..., 6][-9/2, 0, 0, 0, 5/2, ..., 45] - [0, 0, 0, 5/2, 5/2, ..., 15][-9/2, 0, 0, -5/2, 0, ..., 30]5.2 得到第二次迭代后的新表将上述结果整理并更新基变量和系数得到第二次迭代完成后的单纯形表基变量系数x₁x₂x₃x₄x₅解 (b)x₃01011/204x₅0000116x₂53/210-1/206检验数 σⱼ-9/200-5/20Z30核心技巧中心元变换时建议在草稿纸上严格按公式新行 旧行 - 系数 * 新出基行一步步计算并立即检查新表中入基列 (x₅列) 是否已变为单位向量[0, 1, 0]^T是的。基变量对应的列x₃,x₅,x₂是否构成一个单位矩阵检查x₃列[1,0,0]^T,x₅列[0,1,0]^T,x₂列[0,0,1]^T。是的说明行变换正确。解列b是否全部非负[4,6,6]^T≥0解是可行的。6. 第二次迭代结果分析与后续路径现在我们站在了一个新的顶点上。新基是(x₃4, x₅6, x₂6)非基变量是x₁和x₄目标函数值Z30。再次进行最优解判定检查检验数行。σ₁ -9/2 -4.5 0σ₄ -5/2 -2.5 0所有非基变量的检验数均为负数。结论对于这个最大化问题当前解即为最优解。因为任何一个非基变量x₁或x₄的值从0增加都会导致目标函数值下降检验数为负。最优解解读x₁* 0,x₂* 6,x₃* 4,x₄* 0,x₅* 6。最大化的目标函数值Z* 30。其中x₃和x₅是松弛/剩余变量它们的值代表了对应约束资源的“剩余”或“不足”。在这个解中第一个约束有4单位剩余 (x₃4)第三个约束有6单位剩余 (x₅6)而第二个约束资源被完全利用 (x₄0)。7. 人工变量法全流程中的关键陷阱与排查虽然我们演示的案例在第二次迭代后就达到了最优但在完整的人工变量法尤其是大M法中从引入人工变量到最终得到原问题最优解整个过程布满“坑点”。7.1 陷阱一大M法中M取值不当导致判断失误问题在目标函数中人工变量系数为-M最大化问题或M最小化问题。如果手算时M取值不够“大”在检验数计算中一个很小的正系数乘以M可能无法在数值上显著大于其他普通变量的系数导致错误地选择入基变量甚至误判最优解。排查与解决心算比较法在计算检验数σⱼ Cⱼ - Σ(C_B * a_ij)时将含M的项单独列出。例如如果检验数形如σ 5 - (2M 3)直接将其视为-2M 2。比较不同检验数时优先比较M的系数。系数更负对最大化问题的检验数更小。只有在M系数相同时才比较常数项。两阶段法优先对于手算或编程初学强烈推荐使用两阶段法代替大M法。第一阶段目标函数仅为“最小化人工变量之和”完全避免了M这个抽象大数计算更清晰不易出错。7.2 陷阱二迭代过程中出现退化与循环问题在确定出基变量时如果最小比值θ出现两个或更多相同的值则新解中会有基变量取值为0称为“退化”。在极端罕见情况下可能导致单纯形法在几个基可行解之间无限循环永远达不到最优。排查与解决识别退化当计算θ规则时出现两个相同的、最小的非负比值。Bland规则这是理论上避免循环的可靠方法。规则是1) 选择入基变量时在所有正检验数中选下标最小的变量2) 选择出基变量时在所有达到最小比值的行中选下标最小的基变量。在实际的非退化问题中很少需要但了解它能帮你理解算法完备性。扰动法思想可以想象给每个约束的右端常数b加上一个极其微小的、不同的正数ε理论上可以消除退化。手算时若遇到退化按Bland规则操作即可。7.3 陷阱三第一阶段结束时人工变量未全部出基问题在两阶段法中第一阶段目标是消除所有人工变量。若第一阶段最终最优值人工变量之和 0说明原问题无可行解。排查与解决明确结论如果第一阶段结束时即使目标值最小化了但仍有人工变量 0即还在基中且值为正或人工变量虽为0但仍在基中退化情况而目标函数值0则直接判定原问题无可行解。无需进入第二阶段。检查约束此时应回头仔细检查原问题的约束条件是否互相矛盾。例如是否同时要求x1 x2 ≤ 5和x1 x2 ≥ 10。7.4 陷阱四中心元变换时的计算错误这是最常出错的环节错误会像滚雪球一样影响后续所有迭代。系统性排查清单符号错误新行 旧行 - 系数 * 新出基行中的减号是否写成了加号特别是当系数为负数时容易混淆。系数用错用于相乘的系数a_ik必须是变换前旧表中该行在入基列的系数而不是其他列的系数。行覆盖顺序建议先计算出所有新行包括检验数行写在草稿上全部验算无误后再誊写到新表中。避免在原表上直接修改导致数据混乱。单位矩阵验证变换后立即检查新基变量对应的列是否构成单位矩阵。这是检验行变换是否正确的“金标准”。8. 从理论到实践算法思想与手工计算技巧最后我想分享一下超越这个具体案例的思考。人工变量法包括大M法和两阶段法的本质是一种可行性搜索优先于最优性搜索的策略。它承认“找到一个起点可能比直接找最优点更难”于是通过引入“惩罚项”或“辅助问题”来搭建一个通往可行域的桥梁。这种“分阶段解决”的思想在优化领域非常普遍。对于手工计算我有几个压箱底的技巧表格格式化画表时上下左右对齐每个格子只写一个数字。清晰的版面能极大降低看串行的概率。分步检查点每完成一次迭代强制自己进行三个检查1) 基列是单位阵吗2) b列全非负吗3) 基变量对应的检验数是0吗这三个都满足计算基本没问题。利用对称性在中心元变换时出基行以外的行其变换本质是“消去”入基列中该行的元素。你可以盯着目标心算“需要乘以多少倍的出基行才能把我这一行入基列的数变成0”这个乘数就是a_ik。这个案例的第二次迭代完整展示了单纯形法从一个可行基移动到另一个更优可行基的机械但精妙的步骤。掌握它你不仅掌握了线性规划的一种计算方法更理解了一种“迭代改进”的优化思想。无论是后续学习对偶理论、灵敏度分析还是接触更复杂的整数规划、非线性规划这种从局部信息检验数做出决策入基/出基通过局部操作行变换更新全局状态单纯形表的模式都会反复出现。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
