简介这份资源是面向算法学习者与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通常用二维vectorvectordouble表示。表的行数是约束个数加一行目标函数行列数是变量个数加一列右端项。初始表的构造逻辑是把标准型的 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::vectordouble solution; // 最优解向量 }; SimplexResult simplex(std::vectorstd::vectordouble A, std::vectordouble b, std::vectordouble c) { int m b.size(); // 约束个数 int n c.size(); // 变量个数含松弛变量 SimplexResult res; res.optimal false; res.unbounded false; // 构造单纯形表m 行约束 1 行目标函数 // 每行有 n 个系数 1 个右端项 std::vectorstd::vectordouble tab(m 1, std::vectordouble(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::vectorint 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_limitsdouble::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::vectorstd::vectordouble A, std::vectordouble b, std::vectordouble c) { std::ifstream fin(filename); if (!fin.is_open()) return false; int n, m; fin n m; // n 个变量m 个约束 A.assign(m, std::vectordouble(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 -stdc11 -O2 -o simplex simplex.cpp-stdc11是因为代码里用了std::vector的初始化列表和auto之类特性-O2开优化小规模问题其实不开也行。如果你在 Windows 上用 MSVC把g换成cl参数换成/std:c11 /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代替 0EPS取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具体数值取决于迭代过程取负号得到对偶变量 y10, y21.5, y31。这意味着第二个约束的右端项每增加 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]; }注意这个提取逻辑依赖于松弛变量的排列顺序如果你的标准型转换把松弛变量放在其他位置索引要相应调整。另外对偶变量只在最优时才有意义无界或无可行解的情况下提取出来是错的。从那以后我每次写完单纯形法代码都会先用一个已知答案的小例题跑一遍再手动改右端项验证对偶变量最后才敢拿去做作业或者嵌到项目里。这个习惯帮我省了很多返工的时间。希望帮到你。本文还有配套的精品资源点击获取