简介：这份资源是面向算法学习者与C++开发者的一份线性规划求解实践材料，核心是用C++实现经典的单纯形算法，帮助读者理解从初始基本可行解迭代到目标函数最优解的完整过程。包内共3个文件，以2个cpp源文件和1个h头文件为主，分别承担单纯形表数据结构定义、算法核心逻辑与程序入口的职责，压缩包整体约2KB，体量轻巧便于直接阅读与二次修改。目前已有742人学习下载，说明其在算法教学与课程实践中有一定参考价值。内容涉及线性规划标准形式转换、基变量与非基变量替换、单纯形表迭代、边界点求解等关键概念，并体现STL容器存储矩阵向量、异常处理与退出条件检查等C++编程技巧。读者可借此梳理单纯形法的数学原理与代码落地路径，作为运筹学、数值分析或算法设计课程的练习素材，也可在此基础上扩展性能优化与测试用例。

1. 从一份 C++ 单纯形法程序说起：谁需要它，能解决什么

如果你正在学运筹学、做线性规划作业，或者需要在某个 C++ 工程里嵌入一个轻量级的 LP 求解器，大概率绕不开单纯形法。网上 Python 版本的实现一抓一大把，但 C++ 的、能直接编译运行、代码结构还看得过去的，其实没那么多。这份 C++ 实现的单纯形算法计算程序，解决的就是这个场景：给你一个不依赖第三方库、纯标准 C++ 写成的单纯形法求解器，输入线性规划模型，输出最优解和最优值。

它适合三类人：一是正在上运筹学课程、需要交作业或者做课程设计的同学，二是想把单纯形法嵌进自己 C++ 项目里当求解模块的开发者，三是想通过读代码来理解单纯形法迭代过程的自学者。不适合谁？不适合需要求解大规模稀疏 LP 的生产环境——那种场景你应该直接上 GLPK、CLP 或者 OR-Tools，手写单纯形法在数值稳定性和性能上都扛不住。

这份程序的核心价值在于“透明”：你能看到每一步迭代的基变量、检验数、入基出基选择，而不是面对一个黑匣子。对于教学和小规模问题求解来说，这比调库有用得多。

2. 单纯形法的 C++ 落地：从数学模型到代码结构

2.1 标准型转换与算法选型

单纯形法不是拿来就能直接用的，它要求线性规划问题必须先转成标准型。所谓标准型，就是目标函数求最大值、约束条件全部是等式、右端项非负、所有变量非负。你拿到的问题大概率长这样：

max z = 3x1 + 5x2 s.t. x1 <= 4 2x2 <= 12 3x1 + 2x2 <= 18 x1, x2 >= 0

这不是标准型，因为约束是不等式。转换方法是引入松弛变量，把每个不等式变成等式：

max z = 3x1 + 5x2 + 0s1 + 0s2 + 0s3 s.t. x1 + s1 = 4 2x2 + s2 = 12 3x1 + 2x2 + s3 = 18 x1, x2, s1, s2, s3 >= 0

这一步在代码里通常用一个函数来完成，输入原始系数矩阵、不等式方向、右端项，输出标准型的 A 矩阵、b 向量、c 向量。常见做法是用一个StandardForm结构体来承载转换结果，同时记录哪些变量是松弛变量，方便最后从解向量里提取原始变量的值。

为什么不用对偶单纯形法或者大 M 法？因为这份程序面向的是教学和小规模问题，两阶段法或者大 M 法会增加代码复杂度，而大多数教材例题的初始基可行解直接由松弛变量给出，不需要额外处理。如果你的问题有人工变量，这份程序可能不直接支持，需要你自己扩展。

2.2 核心数据结构与迭代主循环

代码的核心是一个单纯形表（tableau），通常用二维vector<vector<double>>表示。表的行数是约束个数加一行目标函数行，列数是变量个数加一列右端项。初始表的构造逻辑是：把标准型的 A 矩阵和 b 向量填进去，目标函数行的系数取 -c（因为单纯形法通过检验数判断最优性，检验数 = c_j - z_j，初始基变量的检验数为零）。

下面是一个简化的单纯形表结构和主循环框架：

#include <vector> #include <iostream> #include <cmath> #include <limits> const double EPS = 1e-9; struct SimplexResult { bool optimal; // 是否找到最优解 bool unbounded; // 是否无界 double optimalValue; // 最优目标函数值 std::vector<double> solution; // 最优解向量 }; SimplexResult simplex(std::vector<std::vector<double>> A, std::vector<double> b, std::vector<double> c) { int m = b.size(); // 约束个数 int n = c.size(); // 变量个数（含松弛变量） SimplexResult res; res.optimal = false; res.unbounded = false; // 构造单纯形表：m 行约束 + 1 行目标函数 // 每行有 n 个系数 + 1 个右端项 std::vector<std::vector<double>> tab(m + 1, std::vector<double>(n + 1, 0.0)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) tab[i][j] = A[i][j]; tab[i][n] = b[i]; } // 目标函数行：取 -c，右端项为 0 for (int j = 0; j < n; ++j) tab[m][j] = -c[j]; tab[m][n] = 0.0; // 记录基变量索引，初始基为松弛变量 std::vector<int> basis(m); for (int i = 0; i < m; ++i) basis[i] = n - m + i; while (true) { // 步骤 1：找入基变量——目标行中最小负系数对应的列 int pivotCol = -1; double minVal = -EPS; for (int j = 0; j < n; ++j) { if (tab[m][j] < minVal) { minVal = tab[m][j]; pivotCol = j; } } if (pivotCol == -1) { // 目标行没有负系数，已到最优 res.optimal = true; break; } // 步骤 2：找出基变量——最小比值检验 int pivotRow = -1; double minRatio = std::numeric_limits<double>::max(); for (int i = 0; i < m; ++i) { if (tab[i][pivotCol] > EPS) { double ratio = tab[i][n] / tab[i][pivotCol]; if (ratio < minRatio - EPS) { minRatio = ratio; pivotRow = i; } } } if (pivotRow == -1) { // 入基列所有系数非正，问题无界 res.unbounded = true; break; } // 步骤 3：高斯消元（旋转运算） double pivot = tab[pivotRow][pivotCol]; for (int j = 0; j <= n; ++j) tab[pivotRow][j] /= pivot; for (int i = 0; i <= m; ++i) { if (i != pivotRow && std::fabs(tab[i][pivotCol]) > EPS) { double factor = tab[i][pivotCol]; for (int j = 0; j <= n; ++j) { tab[i][j] -= factor * tab[pivotRow][j]; } } } basis[pivotRow] = pivotCol; } // 提取解向量 res.solution.assign(n, 0.0); for (int i = 0; i < m; ++i) { res.solution[basis[i]] = tab[i][n]; } res.optimalValue = tab[m][n]; return res; }

这段代码的逻辑说明：主循环分三步走。第一步在目标函数行里找最小的负系数，对应入基变量。如果所有系数都非负，说明已经达到最优。第二步做最小比值检验，确定出基变量所在的行。如果入基列的所有系数都小于等于零，说明问题无界。第三步做旋转运算，把入基列变成单位向量，同时更新目标函数行。循环直到最优或无界。

参数说明：A是标准型的系数矩阵，b是右端项，c是目标函数系数。EPS是浮点比较的容差，取1e-9是常见做法，太小会导致数值噪声被当成有效值，太大会漏掉真正的最优条件。basis数组记录每一行当前基变量的列索引，初始时假设松弛变量构成初始基。

2.3 输入解析与结果输出

程序需要一个输入层，把用户写的线性规划模型转成上面函数能吃的格式。常见做法是定义一个文本格式，比如第一行写变量个数和约束个数，接下来每行写约束系数和右端项，最后一行写目标函数系数。解析的时候用ifstream逐行读，stringstream拆分。

#include <fstream> #include <sstream> #include <string> bool parseInput(const std::string& filename, std::vector<std::vector<double>>& A, std::vector<double>& b, std::vector<double>& c) { std::ifstream fin(filename); if (!fin.is_open()) return false; int n, m; fin >> n >> m; // n 个变量，m 个约束 A.assign(m, std::vector<double>(n, 0.0)); b.assign(m, 0.0); c.assign(n, 0.0); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) fin >> A[i][j]; fin >> b[i]; } for (int j = 0; j < n; ++j) fin >> c[j]; return true; }

逻辑说明：这个解析函数假设输入文件已经是标准型格式，即约束全是等式、变量全非负。如果你拿到的是不等式约束，需要先手动或写额外的转换函数引入松弛变量。参数方面，n和m的顺序要和文件内容一致，否则读出来的矩阵会错位。输出部分，把SimplexResult里的optimalValue和solution打印出来即可，注意只打印原始变量的值，松弛变量的值对用户意义不大。

3. 编译、运行与结果验证：把代码跑起来

3.1 编译环境与命令

这份代码只依赖 C++ 标准库，不需要任何第三方库。编译命令很简单：

g++ -std=c++11 -O2 -o simplex simplex.cpp

-std=c++11是因为代码里用了std::vector的初始化列表和auto之类特性，-O2开优化，小规模问题其实不开也行。如果你在 Windows 上用 MSVC，把g++换成cl，参数换成/std:c++11 /O2。编译报错最常见的原因是头文件漏了，<limits>和<cmath>是必须的，<vector>和<iostream>更不用说。

3.2 用教材例题做验证

拿一个经典例题来验证程序正确性。问题如下：

max z = 3x1 + 5x2 s.t. x1 <= 4 2x2 <= 12 3x1 + 2x2 <= 18 x1, x2 >= 0

转成标准型后，变量有 5 个（x1, x2, s1, s2, s3），约束 3 个。输入文件内容：

5 3 1 0 1 0 0 4 0 2 0 1 0 12 3 2 0 0 1 18 3 5 0 0 0

运行程序，期望输出最优值 36，最优解 x1 = 2, x2 = 6。如果输出不对，先检查输入文件的格式是否和解析函数匹配，再检查标准型转换有没有漏掉松弛变量。

3.3 边界情况测试

除了正常例题，至少还要测三种边界情况。第一种是无界问题，比如max z = x1 + x2, s.t. x1 - x2 <= 1, x1, x2 >= 0，程序应该报告无界。第二种是退化问题，即最小比值检验出现多个相同的最小比值，这时候不同的出基选择可能导致循环，虽然实际中很少遇到，但代码里最好加一个迭代次数上限。第三种是无穷多最优解，程序会输出其中一个，这是正常的，因为单纯形法只保证找到一个最优顶点。

提示：测试无界问题时，如果程序陷入死循环，检查最小比值检验里有没有正确处理所有系数非正的情况。

4. 避坑与排查：单纯形法实现里最容易翻车的几个点

4.1 浮点比较用==导致死循环

现象：程序在某些输入下一直循环，不输出结果也不报错。原因：判断检验数是否小于零时用了tab[m][j] < 0，而浮点运算的累积误差可能让一个理论上的零变成-1e-15，于是程序认为还能继续迭代。解决：所有浮点比较都加容差，用tab[m][j] < -EPS代替< 0，EPS取1e-9左右。同理，判断系数是否为正时用> EPS。

4.2 最小比值检验忽略了零和负数

现象：程序选出了一个不该出基的变量，导致解向量出现负值。原因：最小比值检验只考虑了tab[i][pivotCol] > 0的行，但如果某行系数是零或负数，理论上不应该参与比值计算。如果代码里漏了这个判断，可能选到错误的主元行。解决：在比值检验循环里加if (tab[i][pivotCol] > EPS)条件，确保只有正系数才参与比较。

4.3 标准型转换漏掉变量非负约束

现象：程序输出的解里某个原始变量是负数，但你的问题明明要求非负。原因：标准型转换时只引入了松弛变量，但没有检查原始变量是否已经在标准型里。如果原始问题有变量无非负约束，需要做变量替换（比如x = x' - x''），这份程序不直接支持。解决：在输入解析阶段加一个检查，如果发现解向量里原始变量为负，说明模型转换有问题，需要手动处理。

4.4 迭代次数没有上限

现象：遇到退化问题或者数值病态问题时，程序可能循环很多次甚至不终止。原因：单纯形法在理论上可能因为退化而循环（虽然极少见），实际中浮点误差也可能导致在几个基之间来回跳。解决：在主循环里加一个计数器，比如最多迭代1000 + 10 * (m + n)次，超过就报错退出，提示用户检查模型或数值精度。

4.5 输出解时混淆了松弛变量和原始变量

现象：程序输出的“最优解”里包含了松弛变量的值，用户拿去用发现变量个数对不上。原因：solution向量包含了所有变量（原始变量加松弛变量），但用户只关心原始变量。解决：在输出阶段只打印前n_original个分量，或者在SimplexResult里额外记录原始变量的个数，输出时截断。

5. 进阶技巧：用对偶信息做灵敏度分析

单纯形表在达到最优时，目标函数行里其实藏着对偶变量的信息。具体来说，最终表中松弛变量对应的检验数（取负号）就是对偶变量的值。这个信息可以用来做灵敏度分析：比如某个约束的右端项增加一个单位，最优值会变化多少。

拿前面的例题来说，最终表里 s1、s2、s3 对应的检验数分别是 0、-1.5、-1（具体数值取决于迭代过程），取负号得到对偶变量 y1=0, y2=1.5, y3=1。这意味着第二个约束的右端项每增加 1，最优值增加 1.5。你可以手动改一下输入文件里的 b 向量，把 12 改成 13，重新运行，看最优值是不是从 36 变成 37.5。如果是，说明对偶信息提取正确。

这个技巧的实用价值在于：你不需要重新求解整个问题，就能快速评估参数变化的影响。对于做课程设计或者写报告的人来说，这是一个很加分的扩展点。代码上只需要在SimplexResult里加一个dual向量，在最优时从最终表的目标行里提取即可。

// 在最优时提取对偶变量 res.dual.assign(m, 0.0); for (int i = 0; i < m; ++i) { // 松弛变量在最终表中的检验数取负即为对偶变量 // 这里假设松弛变量是最后 m 个变量 res.dual[i] = -tab[m][n - m + i]; }

注意这个提取逻辑依赖于松弛变量的排列顺序，如果你的标准型转换把松弛变量放在其他位置，索引要相应调整。另外，对偶变量只在最优时才有意义，无界或无可行解的情况下提取出来是错的。

从那以后我每次写完单纯形法代码，都会先用一个已知答案的小例题跑一遍，再手动改右端项验证对偶变量，最后才敢拿去做作业或者嵌到项目里。这个习惯帮我省了很多返工的时间。希望帮到你。

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