简介：这份资源是面向算法学习者与C++开发者的一份线性规划求解实践材料，核心是用C++实现经典的单纯形算法，帮助读者理解从初始基本可行解迭代到目标函数最优解的完整过程。包内共3个文件，包含2个cpp源文件与1个h头文件，压缩包约2KB，分别承担单纯形表数据结构定义、算法核心逻辑与主程序入口的职责，结构紧凑，便于直接阅读与二次修改。资源围绕线性规划标准形式、单纯形表构建、基变量与非基变量替换、迭代终止条件等关键环节展开，同时涉及STL容器存储矩阵向量、异常处理与性能优化等C++编程技巧，适合作为课程设计、算法练习或数值计算入门的参考。目前已有742人学习下载，读者可借此掌握单纯形法的实现思路，并在此基础上扩展错误处理与测试用例，巩固算法设计与编程能力。

1. 单纯形法：为什么一个 1947 年的算法至今还在被反复重写

很多人第一次接触线性规划，会觉得单纯形法不过是「把不等式变成等式，然后换基迭代」的机械流程。但真正动手用 C++ 实现一遍就会发现，教科书上三行伪代码能讲完的东西，落到代码里全是坑：退化循环、数值精度、Bland 规则失效、大 M 法里 M 到底取多大。这些问题的本质，是单纯形法在数学上优雅、在浮点世界里脆弱的矛盾。

这份 C++ 实现的单纯形算法计算程序，解决的正是这个矛盾——它把线性规划从「数学作业」变成「可运行、可验证、可调试」的工程对象。你输入目标函数系数、约束矩阵和右端项，它输出最优解、最优值和迭代过程。听起来简单，但要让它在退化、无界、无可行解这些边界情况下都不翻车，需要理解的不只是算法步骤，而是每一步背后的数值稳定性设计。

搞懂这套机制，你收获的不只是一个算法实现，而是「如何把数值方法写成可靠代码」的通用能力。下面从数学形式到代码结构，逐层拆开。

2. 从标准型到单纯形表：数据结构决定了算法能走多远

2.1 为什么必须先转标准型

线性规划的标准型要求：目标函数求最大值、约束全为等式、右端项非负、变量非负。原始问题里那些「≤」「≥」和自由变量，必须先统一。这不是形式主义，而是因为单纯形法的迭代逻辑建立在「基可行解」上——只有标准型才能保证初始基可行解容易构造。

转换规则很直接：≤约束加松弛变量，≥约束减剩余变量再加人工变量，自由变量拆成两个非负变量之差。但代码里怎么存这些变量，直接决定了后续换基操作的复杂度。

常见的实现思路是用一个二维数组存单纯形表，行对应约束、列对应变量，最后一列存右端项。这种「表格法」直观，但每次换基都要做行变换，时间复杂度是 O(m×n)。另一种是「修正单纯形法」，只维护基矩阵的逆，适合大规模稀疏问题。这份实现走的是表格法路线，因为它的目标是教学和验证，不是求解万级变量的问题。

// 单纯形表结构：行 m+1（最后一行是目标函数行），列 n+1（最后一列是 RHS） struct SimplexTableau { int m, n; // m 个约束，n 个决策变量（含松弛/剩余/人工） std::vector<std::vector<double>> table; std::vector<int> basis; // basis[i] 表示第 i 行基变量对应的列索引 // 构造时把约束矩阵、右端项、目标系数填入 SimplexTableau(int constraints, int variables) : m(constraints), n(variables), table(m + 1, std::vector<double>(n + 1, 0.0)), basis(m, -1) {} };

这里basis数组是关键。它记录了每一行当前哪个变量在基里，换基时只需要更新这个数组和做行变换，不需要每次扫描整个表去找单位列。参数m和n在构造时就固定，意味着变量数在转换阶段已经确定——松弛变量、剩余变量、人工变量都算进n里。

2.2 单纯形表的行变换到底在做什么

换基操作的本质是高斯消元。选中入基变量列（检验数为正且最大），再按最小比值规则选出基变量行，然后对整张表做行变换，让入基列变成单位向量。这一步在代码里通常写成三层循环：外层遍历所有行，中层遍历所有列，内层做减法。

// 以 pivotRow 为主元行，pivotCol 为主元列，执行行变换 void pivot(SimplexTableau& st, int pivotRow, int pivotCol) { double pivotVal = st.table[pivotRow][pivotCol]; // 主元行归一化：整行除以主元 for (int j = 0; j <= st.n; ++j) { st.table[pivotRow][j] /= pivotVal; } // 其他行消元：减去主元行的倍数，使 pivotCol 列为 0 for (int i = 0; i <= st.m; ++i) { if (i == pivotRow) continue; double factor = st.table[i][pivotCol]; if (std::fabs(factor) < 1e-12) continue; // 已经是 0，跳过 for (int j = 0; j <= st.n; ++j) { st.table[i][j] -= factor * st.table[pivotRow][j]; } } // 更新基变量记录 st.basis[pivotRow] = pivotCol; }

注意1e-12这个阈值。浮点运算下，理论上应该是 0 的元素可能变成1e-15这种极小值，如果不跳过，后续计算会累积误差。但阈值也不能太大，否则会误杀真正的小系数。这个值的选取是数值稳定性的第一个踩坑点，后面会展开。

行变换完成后，目标函数行的检验数会更新。如果所有检验数都 ≤ 0（最大化问题），当前基可行解就是最优解。否则继续选入基变量，进入下一轮迭代。

2.3 检验数与最优性判断的代码落点

检验数存在单纯形表最后一行。初始时，目标函数行的系数是-c_j（因为要写成z - Σc_j x_j = 0的形式），换基后自动更新。判断最优的代码通常长这样：

// 返回入基列索引，-1 表示已最优 int findEnteringColumn(const SimplexTableau& st) { int enterCol = -1; double maxReducedCost = 1e-9; // 只有检验数大于此阈值才考虑入基 for (int j = 0; j < st.n; ++j) { if (st.table[st.m][j] > maxReducedCost) { maxReducedCost = st.table[st.m][j]; enterCol = j; } } return enterCol; }

这里用1e-9而不是0作为阈值，是为了避免在最优解附近因为浮点误差反复换基，导致死循环。这是单纯形法实现里最经典的「玄学」之一：理论上检验数必须严格大于 0 才换基，但实际代码里必须给一个容差。

3. 入基与出基规则：最小比值检验为什么能保证可行性

3.1 最小比值规则的数学推导

选定入基变量后，需要决定它增大到多少。约束是Ax = b，x ≥ 0。入基变量从 0 开始增大，其他非基变量保持 0，基变量随之变化。当某个基变量降到 0 时，就不能再增大了，否则该基变量变负，违反非负约束。

对每一行i，基变量x_{B_i} = b_i - a_{ij} * θ，其中θ是入基变量的增量，a_{ij}是入基列在第i行的系数。要求x_{B_i} ≥ 0，得到θ ≤ b_i / a_{ij}（当a_{ij} > 0时）。取所有正比值的最小值，对应的行就是出基行。

// 返回出基行索引，-1 表示问题无界 int findLeavingRow(const SimplexTableau& st, int enterCol) { int leaveRow = -1; double minRatio = std::numeric_limits<double>::infinity(); for (int i = 0; i < st.m; ++i) { double aij = st.table[i][enterCol]; if (aij > 1e-12) { // 只考虑正系数 double ratio = st.table[i][st.n] / aij; if (ratio < minRatio - 1e-12) { // 容差比较，避免浮点相等误判 minRatio = ratio; leaveRow = i; } } } return leaveRow; }

如果所有a_{ij} ≤ 0，说明入基变量可以无限增大而不违反约束，问题无界。代码里返回-1，上层捕获后输出「无界解」。

3.2 退化与循环：Bland 规则为什么不是万能的

当最小比值出现并列时，说明有基变量同时降到 0，这就是退化。退化本身不致命，但可能导致循环——换基后目标函数值不变，反复回到同一个基。理论上 Bland 规则（选最小索引入基、最小索引出基）能保证不循环，但实际代码里用 Bland 规则会大幅拖慢收敛速度。

常见的工程折中是：默认用最大检验数规则，同时记录迭代次数，超过某个上限（比如10 * (m + n)）就切换到 Bland 规则。这份实现里可以加一个iterationCount计数器，在findEnteringColumn里根据计数决定用哪种策略。

int findEnteringColumnWithAntiCycle(const SimplexTableau& st, int iterCount) { bool useBland = (iterCount > 10 * (st.m + st.n)); int enterCol = -1; if (useBland) { // Bland 规则：选索引最小的正检验数列 for (int j = 0; j < st.n; ++j) { if (st.table[st.m][j] > 1e-9) { enterCol = j; break; } } } else { // 最大检验数规则 double maxRC = 1e-9; for (int j = 0; j < st.n; ++j) { if (st.table[st.m][j] > maxRC) { maxRC = st.table[st.m][j]; enterCol = j; } } } return enterCol; }

这个「先快后稳」的策略，是数值优化里常见的思路：正常路径追求速度，异常路径保证正确性。

3.3 大 M 法与两阶段法的取舍

人工变量的处理有两种主流方案。大 M 法在目标函数里给人工变量一个巨大的负系数（最大化问题），迫使它们最终为 0。两阶段法先最小化人工变量之和，再求解原问题。

大 M 法的代码改动小，但M的取值是血泪经验：太小则人工变量可能留在基里，太大则数值精度崩溃。通常取1e6到1e8之间，但具体值依赖问题规模。两阶段法多一轮求解，但数值上更稳健。

// 大 M 法：在目标函数行给人工变量赋 -M const double BIG_M = 1e7; for (int j = 0; j < st.n; ++j) { if (isArtificial[j]) { st.table[st.m][j] = -BIG_M; // 最大化问题，人工变量系数为负 } }

如果问题里系数本身就有1e5量级，BIG_M取1e7可能不够大；如果系数是1e-3量级，1e7又可能引入严重误差。这就是为什么很多工业级求解器默认用两阶段法——它不依赖这个「魔法数字」。

4. 数值稳定性：浮点误差怎么让单纯形法翻车

4.1 主元选择的容差阈值

前面代码里反复出现的1e-12、1e-9不是随便写的。主元太小会导致行变换时误差被放大。假设主元是1e-10，归一化时整行除以它，原本1e-8的误差变成100，直接摧毁后续计算。

常见的做法是设置一个「主元下限」，比如1e-9。如果选出的主元绝对值小于这个值，就认为该列不能入基，或者触发重新选主元。有些实现会做「部分主元选取」——在入基列里选绝对值最大的元素作为主元，而不是机械按最小比值选。

// 带主元下限检查的出基行选择 int findLeavingRowStable(const SimplexTableau& st, int enterCol) { int leaveRow = -1; double minRatio = std::numeric_limits<double>::infinity(); const double PIVOT_TOL = 1e-9; for (int i = 0; i < st.m; ++i) { double aij = st.table[i][enterCol]; if (aij > PIVOT_TOL) { double ratio = st.table[i][st.n] / aij; if (ratio < minRatio - 1e-12) { minRatio = ratio; leaveRow = i; } } } return leaveRow; }

如果所有系数都小于PIVOT_TOL，返回-1，上层判断为无界或数值退化。这时候可以考虑用两阶段法重新求解，或者输出警告让用户检查输入数据。

4.2 迭代过程中的误差累积与重置

单纯形法迭代几十轮后，单纯形表里的元素可能已经严重偏离理论值。一个实用的技巧是每隔一定迭代次数（比如 50 轮），用当前基变量重新计算一次单纯形表——从原始矩阵重新做高斯消元，而不是继续在旧表上累加误差。

// 每 50 次迭代重置一次单纯形表 if (iterCount % 50 == 0 && iterCount > 0) { rebuildTableau(st, originalA, originalB, originalC); }

rebuildTableau根据当前basis数组，从原始数据重新构造表。这会增加计算量，但能显著提升数值稳定性。工业求解器里类似的技术叫「基重构」，是标配。

4.3 无界与无可行解的判定逻辑

无界解在findLeavingRow返回-1时触发。无可行解则发生在两阶段法的第一阶段结束时，人工变量之和大于 0。大 M 法里，如果最优解中人工变量不为 0，也说明无可行解。

// 检查解中是否残留人工变量 bool hasInfeasibleArtificial(const SimplexTableau& st, const std::vector<bool>& isArtificial) { for (int i = 0; i < st.m; ++i) { int col = st.basis[i]; if (col >= 0 && isArtificial[col] && st.table[i][st.n] > 1e-8) { return true; // 人工变量仍在基里且值非零 } } return false; }

这个检查必须在输出最优解之前做。很多教学实现忘了这一步，导致对无可行解的问题输出一个「最优解」，实际上那个解根本不满足原始约束。

5. 避坑与排查：单纯形法实现里最容易翻车的五个地方

5.1 现象：程序陷入死循环，迭代次数无限增长

原因：退化问题导致循环，或者检验数阈值设置不当，在最优解附近反复换基。解决：加入迭代上限计数器，超过10 * (m + n)后切换到 Bland 规则；同时把入基检验数阈值从0调到1e-9。

5.2 现象：输出最优解但代回原约束不满足

原因：人工变量未被正确清除，或者大 M 法的M取值太小，人工变量留在了基里。解决：在输出前检查所有人工变量是否为 0；如果使用大 M 法，尝试把M增大一个数量级，或者改用两阶段法。

5.3 现象：小规模问题结果正确，大规模问题结果偏差大

原因：浮点误差累积，单纯形表经过多轮行变换后严重失真。解决：每 50 轮迭代从原始数据重构单纯形表；主元选择时加1e-9下限，避免小主元放大误差。

5.4 现象：无界问题被误判为有最优解

原因：findLeavingRow里只检查了aij > 0，但没考虑aij极小的情况，导致选出一个实际不应该出基的行。解决：把aij > 0改成aij > 1e-12，并在返回-1时明确输出「问题无界」。

5.5 现象：约束矩阵里有零行或线性相关行，程序崩溃

原因：零行导致最小比值规则除零，线性相关行导致基矩阵奇异。解决：预处理阶段检测零行和重复行，直接剔除或报错；换基时如果主元绝对值小于1e-12，跳过该行并记录警告。

6. 设计取舍：教学实现与工业求解器之间差了什么

这份 C++ 单纯形法实现，定位在教学与验证之间。它把标准型转换、单纯形表迭代、最优性判断、无界/无可行解检测都写全了，代码结构清晰，适合逐行调试。但它和工业级求解器之间，还隔着几层工程取舍。

第一层是稀疏性。教学实现用稠密二维数组，m和n上千时内存和计算量都吃不消。工业求解器用稀疏矩阵存储，只记录非零元素，换基时也只更新受影响的行。第二层是数值技巧。除了前面提到的基重构，还有「LU 分解更新基逆」「Harris 比值检验」等，都是为了在浮点世界里走得更远。第三层是预处理。工业求解器会在求解前做「约束传播」「系数缩放」「冗余约束剔除」，把问题规模压下来再迭代。

但教学实现的价值恰恰在于它没有这些「黑魔法」。你能看到每一次换基、每一次行变换、每一次检验数更新，能单步调试，能打印中间表。这种透明度是理解算法底层机制的前提。等你把这份实现跑通、改过、踩过坑之后，再去看工业求解器的源码，那些稀疏存储和数值技巧就不再是黑匣子，而是「为了解决我遇到过的问题而存在的设计」。

我自己的习惯是：每学一个新算法，先用最朴素的方式实现一遍，故意让它在大问题上翻车，然后再去看成熟实现怎么解决。翻车的过程比顺利跑通更有价值，因为你知道边界在哪里。这份单纯形法实现就是这样一个起点——它不完美，但足够透明，足够让你把「为什么这么设计」想清楚。

从那以后我每次写数值代码，都会先问自己三个问题：浮点误差会不会累积到影响结果？退化情况有没有兜底策略？边界条件有没有显式检查？这三个问题问完，代码的可靠性通常能上一个台阶。希望这份实现和上面的拆解，能帮你在单纯形法乃至更广的数值优化领域，少走一些弯路。

本文还有配套的精品资源，点击获取