简介：这份资源是面向算法学习者与C++开发者的单纯形法完整实现程序，用于求解线性规划问题的最优解。单纯形法由丹齐格于1947年提出，通过迭代在基本可行解之间转换，逐步逼近目标函数最优值，是运筹学与数值计算中的经典算法。资源包共3个文件，包含2个cpp源文件与1个h头文件，压缩包约2KB，代码围绕单纯形表、基变量与非基变量替换、迭代终止条件等核心环节展开，结构紧凑，便于直接阅读与二次开发。目前已有742人学习下载，适合作为课程实验、算法练习或工程入门的参考实现。读者可从中理解线性规划标准形式的转换思路、单纯形表的构造方式以及C++中矩阵与向量的组织技巧，并借鉴异常处理与退出条件检查等工程细节，为后续性能优化和测试调试打下基础。
1. 用 C++ 手搓单纯形法：从建模到求解的完整计算程序
很多做运筹学作业或线性规划求解的开发者，第一次接触单纯形法都是在纸上推演表格，一旦变量数超过五个，手工迭代基本就崩了。这份 C++ 实现的单纯形算法计算程序，解决的正是这个痛点：把标准型线性规划问题丢进去，程序自动完成基变换、入基出基判断、迭代收敛，最后输出最优解和目标函数值。它适合两类人：一类是正在学运筹学、需要验证手工计算结果的学生；另一类是想把线性规划求解嵌进自己工程里的 C++ 开发者，拿过去改改输入输出就能用。整个项目不依赖第三方数学库，纯标准 C++ 实现，编译即跑，这也是它最实在的地方。
2. 项目结构与技术选型：为什么用纯 C++ 而不是调库
2.1 目录组织与文件职责
拿到这份源码，第一件事是看目录。这类单纯形法程序的结构通常很紧凑，常见做法是拆成三个部分：主入口、算法核心、以及输入输出辅助。我一般会按下面的方式组织，读者对照自己手上的源码可以快速定位：
simplex/ ├── main.cpp // 程序入口，负责读取问题、调用求解、打印结果 ├── simplex.h // 单纯形算法类声明，定义数据结构与接口 ├── simplex.cpp // 算法核心实现，迭代逻辑都在这里 └── README.md // 编译说明与输入格式约定main.cpp只做三件事：构造问题、调用SimplexSolver::solve()、输出结果。真正的计算全部压在simplex.cpp里。这种拆分的好处是，你想把求解器嵌到别的项目，只需要拿走simplex.h和simplex.cpp，main.cpp直接丢掉换自己的调用代码。
2.2 数据结构设计：表格法还是修正单纯形
单纯形法有两种主流实现路线：表格法（Tableau）和修正单纯形法（Revised Simplex）。这份程序用的是表格法，原因是它直观、易调试，适合教学和中小规模问题。核心数据结构是一张二维表，常见做法是用std::vector<std::vector<double>>存整张单纯形表，行代表约束，列代表变量加松弛变量，最后一列存右端项 b。
// simplex.h class SimplexSolver { public: // 构造时传入目标函数系数、约束系数矩阵、右端项 SimplexSolver(const std::vector<double>& c, const std::vector<std::vector<double>>& A, const std::vector<double>& b); bool solve(); // 执行迭代，返回是否找到最优解 double getOptimalValue() const; // 取最优目标函数值 std::vector<double> getSolution() const; // 取最优解向量 private: int m, n; // 约束数、原始变量数 std::vector<std::vector<double>> tableau; // 单纯形表 std::vector<int> basis; // 基变量索引 void buildTableau(); // 初始化表格，加入松弛变量 int findEnteringVariable(); // 入基变量（检验数为正且最大） int findLeavingVariable(int enterCol); // 出基变量（最小比值检验） void pivot(int row, int col); // 高斯消元做基变换 };这里几个参数要说明白：m是约束个数，n是决策变量个数。tableau的列数是n + m + 1，多出来的m列是松弛变量，最后 1 列是右端项。basis记录每一行当前哪个变量在基里，初始时全是松弛变量。findEnteringVariable返回检验数最大的列（最大化问题），findLeavingVariable用最小比值法则避免可行解跑出可行域。
2.3 为什么不用第三方库
有开发者会问，为什么不直接上某优化库？原因很实际：这份程序的目标是教学和轻量嵌入。第三方库动辄几十兆，编译链复杂，而单纯形法本身逻辑清晰，纯 C++ 实现不到三百行。对于变量数在几十以内的线性规划问题，表格法的性能完全够用。当然，如果你的问题规模上千，那确实该换修正单纯形法或专业求解器，这是后话。
3. 核心算法拆解：一次迭代到底发生了什么
3.1 初始化：把标准型变成单纯形表
单纯形法的第一步是把问题转成标准型。假设原始问题是最大化c^T x，约束是Ax ≤ b，x ≥ 0。程序通过加入松弛变量把不等式变成等式，构造初始基可行解。这一步在buildTableau()里完成。
void SimplexSolver::buildTableau() { // 表格列数 = 决策变量 n + 松弛变量 m + 右端项 1 tableau.assign(m, std::vector<double>(n + m + 1, 0.0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { tableau[i][j] = A[i][j]; // 填入约束系数 } tableau[i][n + i] = 1.0; // 第 i 行松弛变量系数为 1 tableau[i][n + m] = b[i]; // 右端项 } // 目标函数行（检验数行）放在最后一行，初始为 -c std::vector<double> objRow(n + m + 1, 0.0); for (int j = 0; j < n; ++j) { objRow[j] = -c[j]; // 最大化问题取负，便于统一判断 } tableau.push_back(objRow); // 初始基全是松弛变量 basis.resize(m); for (int i = 0; i < m; ++i) basis[i] = n + i; }逻辑说明：tableau比约束多一行，最后一行是检验数行。把-c放进去，是因为最大化问题里，检验数为负表示还有改进空间，迭代到全非负就最优。basis初始化为松弛变量索引，对应单位矩阵，保证初始解可行。参数上，A[i][j]是第 i 个约束里第 j 个变量的系数，b[i]必须非负，否则初始基不可行，需要两阶段法，这份程序默认输入满足b ≥ 0。
3.2 入基与出基：最小比值法则的代码落地
迭代的核心是选谁进基、谁出基。入基选检验数最负的那一列（对应最大化改进最快），出基用最小比值法则，保证右端项在消元后仍然非负。
int SimplexSolver::findEnteringVariable() { int enterCol = -1; double minVal = -1e-9; // 容差，避免浮点误差误判 int lastRow = m; // 检验数行索引 for (int j = 0; j < n + m; ++j) { if (tableau[lastRow][j] < minVal) { minVal = tableau[lastRow][j]; enterCol = j; } } return enterCol; // 返回 -1 表示已最优 } int SimplexSolver::findLeavingVariable(int enterCol) { int leaveRow = -1; double minRatio = 1e18; for (int i = 0; i < m; ++i) { double coef = tableau[i][enterCol]; if (coef > 1e-9) { // 只考虑正系数，否则比值无意义 double ratio = tableau[i][n + m] / coef; if (ratio < minRatio) { minRatio = ratio; leaveRow = i; } } } return leaveRow; // 返回 -1 表示问题无界 }参数说明：1e-9是浮点比较容差，单纯形法迭代多了容易积累误差，没有容差会出现死循环或误判。findEnteringVariable返回 -1 时，说明所有检验数非负，当前解就是最优解。findLeavingVariable返回 -1 时，说明入基列所有系数非正，问题无界，目标函数可以无限增大。这两个返回值在solve()里分别对应「最优」和「无界」两种终止状态。
3.3 基变换：pivot 消元的实现细节
选定入基列和出基行后，做高斯消元，把入基列变成单位向量。这一步是数值计算最容易翻车的地方，主元太小会导致误差爆炸。
void SimplexSolver::pivot(int row, int col) { double pivotVal = tableau[row][col]; // 归一化主元行 for (int j = 0; j <= n + m; ++j) { tableau[row][j] /= pivotVal; } // 其他行消元，包括检验数行 for (int i = 0; i <= m; ++i) { if (i == row) continue; double factor = tableau[i][col]; if (std::fabs(factor) < 1e-12) continue; for (int j = 0; j <= n + m; ++j) { tableau[i][j] -= factor * tableau[row][j]; } } basis[row] = col; // 更新基变量索引 }逻辑说明：先把主元行整体除以主元，让主元变成 1；然后对其他每一行，减去factor倍的主元行，把该列其他元素清零。注意循环上界是i <= m，因为检验数行也要消元。basis[row] = col更新基索引，保证后续能正确还原解向量。主元判断用1e-12是防止除以极小数，实际工程里如果主元绝对值小于阈值，通常要触发重新选主元或报数值不稳定。
3.4 主循环与终止条件
把上面几个函数串起来，solve()就是一个 while 循环：找入基、找出基、pivot，直到最优或无界。
bool SimplexSolver::solve() { buildTableau(); const int MAX_ITER = 10000; // 防止死循环的后悔药 int iter = 0; while (iter++ < MAX_ITER) { int enterCol = findEnteringVariable(); if (enterCol == -1) return true; // 最优 int leaveRow = findLeavingVariable(enterCol); if (leaveRow == -1) return false; // 无界 pivot(leaveRow, enterCol); } return false; // 迭代超限，视为失败 }MAX_ITER是血泪经验：浮点误差可能让检验数在 0 附近反复横跳，没有迭代上限，程序可能永远不退出。设成 10000 对中小规模问题足够，真超了说明输入有问题或需要换数值更稳的算法。
4. 编译运行与输入格式：从源码到可执行文件
4.1 编译命令与依赖
这份程序没有外部依赖，只要有 C++11 以上的编译器就能编。Linux 或 macOS 下：
g++ -std=c++11 -O2 -o simplex main.cpp simplex.cpp ./simplexWindows 下用 MinGW 或 Visual Studio 命令行同理，把源文件一起编译即可。-O2开优化，对单纯形法这种循环密集的代码有实际提升。如果编译报fabs未定义，检查有没有#include <cmath>，这是新手最常踩的坑。
4.2 输入格式约定
程序读取问题的方式通常有两种：硬编码在main.cpp里，或者从标准输入读。常见做法是前者，方便调试。一个典型输入长这样：
// main.cpp 中的问题定义 std::vector<double> c = {3, 5}; // 目标函数系数 std::vector<std::vector<double>> A = { {1, 0}, // 约束1: x1 <= 4 {0, 2}, // 约束2: 2*x2 <= 12 {3, 2} // 约束3: 3*x1 + 2*x2 <= 18 }; std::vector<double> b = {4, 12, 18}; // 右端项 SimplexSolver solver(c, A, b); if (solver.solve()) { std::cout << "最优值: " << solver.getOptimalValue() << std::endl; auto sol = solver.getSolution(); for (size_t i = 0; i < sol.size(); ++i) std::cout << "x" << i + 1 << " = " << sol[i] << std::endl; }参数说明：c是目标函数系数，长度等于决策变量数；A是约束系数矩阵，行数等于约束数，列数等于变量数；b是右端项，必须非负。这个例子是经典的线性规划入门题，最优解应该是x1 = 2, x2 = 6，目标值 36。跑出来对不上，先检查b有没有负数，再检查约束方向是不是都统一成了≤。
4.3 结果还原：从表格里取出解向量
迭代结束后，解藏在tableau的右端项列里，但只有基变量有值，非基变量全是 0。getSolution()要做的是按basis索引把值填回原变量位置。
std::vector<double> SimplexSolver::getSolution() const { std::vector<double> x(n, 0.0); // 决策变量初始为 0 for (int i = 0; i < m; ++i) { int var = basis[i]; if (var < n) { // 只关心原始决策变量 x[var] = tableau[i][n + m]; } } return x; }逻辑说明：遍历每一行，看基变量索引var，如果它落在原始变量范围[0, n)内，就把该行右端项赋给对应变量。松弛变量的值不需要输出。getOptimalValue()更简单，直接把检验数行最后一列取出来，注意符号——因为初始化时目标函数取了负，这里要取反。
5. 避坑与常见问题：迭代不收敛、结果对不上怎么办
5.1 现象：程序跑出无界，但问题明明有最优解
原因通常是约束方向没统一。单纯形法标准型要求所有约束是≤且b ≥ 0。如果原始问题里有≥或等式约束，直接塞进去会导致初始基不可行，程序误判无界。解决办法是先把问题转成标准型：≥约束两边乘 -1 变≤，但这样b可能变负，需要引入人工变量走两阶段法。这份程序默认不做两阶段，所以输入前必须自己保证b非负。
5.2 现象：迭代次数很多但检验数一直在 0 附近震荡
这是浮点误差导致的退化循环。原因在于主元太小，消元后误差被放大。解决方式有两个：一是加容差，把1e-9调大一点，比如1e-7；二是加 Bland 规则，入基时选下标最小的负检验数列，而不是选最负的，能理论上避免循环。我一般会在findEnteringVariable里加个开关，退化严重时切 Bland 规则。
5.3 现象：最优值和手工算的对不上，差一点点
先别怀疑算法，九成是浮点精度问题。检查输出时有没有做四舍五入，0.9999999和1.0在程序里是两个数。常见做法是在输出前统一处理，小于1e-6的当成 0，接近整数的保留整数。另外检查目标函数值有没有取反，初始化时-c进去，取结果时忘了取反，符号就反了。
5.4 现象：变量数一多，程序变慢甚至卡死
表格法的复杂度是 O(m*n) 每轮迭代，迭代轮数又和变量数相关，规模上去确实会慢。如果变量数超过几百，建议换修正单纯形法，只维护基矩阵的逆，内存和计算量都小一个量级。这份程序定位是教学和中小规模，硬扛大规模问题不是它的设计目标。
5.5 现象：编译通过但运行崩溃，提示 vector 越界
多半是A的行列数和c、b对不上。A的行数必须等于b的长度，列数必须等于c的长度。构造SimplexSolver时最好加个断言检查，assert(A.size() == b.size())和assert(A[0].size() == c.size())，把错误挡在构造阶段，比运行到一半崩溃好排查得多。
6. 二次开发改造：从教学程序到工程可用的求解器
这份程序拿来直接跑没问题，但要嵌进真实工程，还得做几处改造。第一处是输入输出解耦。现在问题硬编码在main.cpp，改成从文件或标准输入读，格式用简单的文本协议，比如第一行放m n，接着c，再接着A和b。这样你的上层业务代码可以用任意语言生成问题文件，C++ 程序只负责求解。
第二处是错误处理。现在的solve()只返回 bool，信息量太少。我一般会改成返回枚举：OPTIMAL、UNBOUNDED、INFEASIBLE、MAX_ITER_REACHED，再配一个getErrorMessage()。这样调用方能区分「问题本身无解」和「程序没算出来」，排查方向完全不同。
第三处是数值稳定性。把主元阈值、检验数容差做成可配置参数，退化时自动切 Bland 规则。下面是一个改造后的接口示意：
enum class SolveStatus { OPTIMAL, UNBOUNDED, INFEASIBLE, MAX_ITER }; struct SolverConfig { double pivotTol = 1e-9; // 主元最小阈值 double objTol = 1e-7; // 检验数容差 int maxIter = 10000; // 迭代上限 bool useBland = false; // 是否强制 Bland 规则 }; class SimplexSolver { public: SimplexSolver(const std::vector<double>& c, const std::vector<std::vector<double>>& A, const std::vector<double>& b, const SolverConfig& cfg = {}); SolveStatus solve(); // ... 其余接口不变 };改造完怎么验证？我的习惯是准备一组已知答案的测试用例，覆盖最优、无界、退化三种情况，每次改完跑一遍。特别是退化用例，构造一个检验数反复为 0 的问题，看程序能不能在有限步内退出。这一步别省，单纯形法的数值坑基本都藏在退化场景里。
从那以后我每次改求解器核心，都强制走一遍「已知答案用例 + 退化用例 + 大规模随机用例」三件套，少一件都不敢提交。希望这份拆解帮到你，拿到源码先跑通那个x1=2, x2=6的例子，再动手改输入输出，路子就顺了。
本文还有配套的精品资源，点击获取
