简介：这份资源面向运筹学初学者与Java开发者，提供线性规划算法的完整可运行实现，帮助理解从模型标准化到两阶段法求解的全过程。包内共11个文件，以java源码、class字节码与xml工程配置为主，另有iml与gitignore等IDE辅助文件，压缩包约13KB，结构精简，便于直接导入开发工具阅读调试。核心代码围绕LP类展开，涵盖standardize()标准化、addArtificialVariables()添加人工变量、twoStageMethod()两阶段求解与solve()主入口，Main类通过Scanner接收控制台输入并输出最优解，配合数组与二维矩阵存储系数和解信息。已有3479人学习下载，适合作为课堂实验、课程设计或自学运筹学算法的参考样例，读者可据此掌握约束转换、人工变量处理与结果验证的排错思路。
1. 用 Java 手写一个单纯形法求解器，到底能跑多快
第一次在项目里遇到线性规划，是因为一个排产模块：几十个工位、上百个订单，约束条件写满两页纸，业务方还要求“尽量让总成本最低”。当时第一反应是找现成的求解器，但部署环境不允许引入外部二进制依赖，只能自己用 Java 实现。这份资源就是围绕这个场景展开的——用纯 Java 实现线性规划求解，核心是单纯形法，覆盖标准型转换、单纯形表迭代、最优解与无界解判定。它适合两类人：一类是运筹学课上听过单纯形法但没真正写过代码的学生，另一类是想在业务系统里嵌一个轻量求解能力、又不想背外部依赖的 Java 开发者。下面按“能干什么、怎么跑、怎么改”的顺序拆开讲。
2. 项目定位与技术选型：为什么用纯 Java 实现单纯形法
2.1 这个项目解决的是什么问题
线性规划要解决的是在一组线性约束下，最大化或最小化一个线性目标函数。典型形式是：目标函数max z = c1*x1 + c2*x2 + ...，约束是若干a1*x1 + a2*x2 <= b以及x >= 0。现实里的排产、配料、运输、预算分配，只要变量之间是线性关系，都能往这个模型上套。
这份资源的核心不是调库，而是把求解过程本身写出来。它做的事情包括：把用户输入的任意形式（最大化/最小化、<=/>=/=）统一转成标准型，构造初始单纯形表，然后反复做“选入基变量、选离基变量、主元消去”这三步，直到检验数全部满足最优性条件，或者判定问题无界。对学习者来说，能亲眼看到每一步表格怎么变；对工程来说，这套逻辑不依赖任何本地库，扔进任何 JVM 环境都能跑。
技术选型上，纯 Java 是刻意的。线性规划的数值计算对浮点精度敏感，用 Java 的double配合一个可配置的误差阈值（常见做法是1e-9到1e-6），足够应付教学和中小规模业务问题。没有引入 Apache Commons Math 之类的库，是为了让整个求解链路透明——每一行代码都能对应到课本上的公式，二次开发时改约束类型、加灵敏度分析都方便。
2.2 目录结构与模块划分
一个合格的 Java 线性规划实现，目录通常长这样（以 Maven 工程为例）：
linear-programming-java/ ├── pom.xml └── src/ ├── main/java/ │ └── lp/ │ ├── model/ │ │ ├── LinearProgram.java // 问题定义：目标函数、约束集合 │ │ ├── Constraint.java // 单条约束：系数、关系符、右端项 │ │ └── SolveResult.java // 求解结果：状态、最优值、变量取值 │ ├── solver/ │ │ ├── SimplexSolver.java // 单纯形法主流程 │ │ └── Tableau.java // 单纯形表的构造与主元变换 │ └── util/ │ └── NumberUtil.java // 浮点比较、误差处理 └── test/java/ └── lp/ └── SimplexSolverTest.java // 典型算例的断言这个划分的关键在于把“问题描述”和“求解算法”分开。model包只负责数据，solver包只负责计算，util收拢浮点比较这种容易写错的地方。二次开发时，想加一个新约束类型，只动model；想换求解策略（比如对偶单纯形），只动solver。这种分层不是过度设计，而是因为线性规划的输入形式太杂，混在一起写很快就会变成一坨。
2.3 核心数据结构设计
先看问题定义。LinearProgram持有一个目标函数系数数组、一个目标方向（最大化/最小化）和一组约束：
public class LinearProgram { private final double[] objective; // 目标函数系数 c private final boolean maximize; // true 为最大化 private final List<Constraint> constraints; public LinearProgram(double[] objective, boolean maximize) { this.objective = objective.clone(); this.maximize = maximize; this.constraints = new ArrayList<>(); } public void addConstraint(Constraint c) { constraints.add(c); } // getter 省略 }Constraint里存系数数组、关系符枚举和右端项b。关系符用枚举而不是字符串，避免运行时拼写错误：
public class Constraint { public enum Relation { LE, GE, EQ } // <=, >=, = private final double[] coefficients; private final Relation relation; private final double rhs; // 构造与 getter 省略 }SolveResult用一个状态枚举表达结果：OPTIMAL、UNBOUNDED、INFEASIBLE。这个设计很重要——线性规划不是每次都有解，无界和不可行必须能被调用方区分，否则业务层拿到一个null根本不知道发生了什么。
3. 标准型转换与单纯形表：从任意形式到可迭代的表格
3.1 为什么必须先转标准型
单纯形法只认一种形式：最大化、约束全是等式、所有变量非负。用户输入里出现的<=、>=、最小化，都得先处理掉。这一步如果偷懒，后面主元变换会直接算错，而且错得很隐蔽。
转换规则不复杂，但每条都要落到代码里：
- 最小化问题：目标函数整体取负，转成最大化，最后结果再取负回来。
<=约束：左边加一个松弛变量，系数为 1。>=约束：左边减一个剩余变量，系数为 -1，同时为了构造初始基，通常还要加一个人工变量。- 等式约束：直接加人工变量构造初始基。
人工变量的处理是单纯形法里最容易翻车的地方。常见做法是两阶段法：第一阶段最小化人工变量之和，如果最优值不为零，说明原问题不可行；为零则把人工变量从基里赶出去，进入第二阶段求原目标。这份实现里，我建议把两阶段逻辑单独抽成一个方法，别和主迭代搅在一起。
3.2 单纯形表的构造
标准型确定后，把所有变量（原变量 + 松弛/剩余 + 人工）的系数排成矩阵，加上右端项列，就是初始单纯形表。Tableau类负责这件事：
public class Tableau { private final double[][] matrix; // 行 = 约束，列 = 变量 + 右端项 private final int[] basis; // 每行基变量的列下标 private final int varCount; // 决策变量 + 松弛变量总数 public Tableau(double[][] a, double[] b, int[] initialBasis) { int rows = a.length; int cols = a[0].length + 1; // 多一列放 b matrix = new double[rows][cols]; for (int i = 0; i < rows; i++) { System.arraycopy(a[i], 0, matrix[i], 0, a[i].length); matrix[i][cols - 1] = b[i]; } this.basis = initialBasis.clone(); this.varCount = a[0].length; } }这里basis数组记录每一行当前哪个变量在基里。初始基一般就是松弛变量和人工变量所在的列。注意varCount只算到决策变量和松弛变量，人工变量在第二阶段要排除出候选入基集合，否则会算出错误的最优解。
3.3 主元变换的实现
单纯形法的一次迭代就三件事：找入基列、找离基行、做行变换。入基列看检验数，离基行看比值检验（最小比值规则），主元确定后把主元行归一化，再用它消去其他行的该列。
// 选入基列：检验数最大且为正的列（最大化问题） int enterCol = -1; double best = EPS; for (int j = 0; j < varCount; j++) { if (isBasic(j)) continue; // 基变量不参与 double reduced = reducedCost(j); // c_j - z_j if (reduced > best) { best = reduced; enterCol = j; } } if (enterCol == -1) return SolveResult.optimal(...); // 无正检验数，已达最优 // 选离基行：最小比值 b_i / a_i,enterCol，且 a_i,enterCol > 0 int leaveRow = -1; double minRatio = Double.MAX_VALUE; for (int i = 0; i < matrix.length; i++) { double a = matrix[i][enterCol]; if (a > EPS) { double ratio = matrix[i][matrix[0].length - 1] / a; if (ratio < minRatio) { minRatio = ratio; leaveRow = i; } } } if (leaveRow == -1) return SolveResult.unbounded(); // 入基列全非正，无界EPS是浮点误差阈值，通常取1e-9。这里有两个细节值得说：第一，isBasic(j)必须跳过基变量，否则会把已经在基里的列又选进来，导致死循环；第二，比值检验只考虑a > EPS的行，如果整列都非正，说明目标函数可以无限增大，直接返回无界。这两处是单纯形法实现里最常见的两个 bug 来源，写测试时一定要覆盖。
主元消去本身是标准的高斯消元：
double pivot = matrix[leaveRow][enterCol]; for (int j = 0; j < matrix[0].length; j++) { matrix[leaveRow][j] /= pivot; // 主元行归一化 } for (int i = 0; i < matrix.length; i++) { if (i == leaveRow) continue; double factor = matrix[i][enterCol]; if (Math.abs(factor) < EPS) continue; for (int j = 0; j < matrix[0].length; j++) { matrix[i][j] -= factor * matrix[leaveRow][j]; } } basis[leaveRow] = enterCol; // 更新基变量行变换之后别忘了更新basis，否则下一轮isBasic判断全错。这个顺序（先归一化主元行，再消其他行，最后更新基）建议固定下来，调试时按这个顺序打日志，出问题一眼能定位。
4. 跑起来与验证：从编译到第一个算例
4.1 环境准备与编译
工程是标准 Maven 结构，JDK 8 及以上都能跑。没有外部依赖，pom.xml里只需要 JUnit 做测试。编译和打包：
mvn clean package如果只想快速验证，不打包，直接编译源码目录也行：
javac -d out src/main/java/lp/model/*.java src/main/java/lp/solver/*.java src/main/java/lp/util/*.java跑测试用mvn test。测试类里应该至少覆盖四种情况：有唯一最优解、有多重最优解、无界、不可行。这四类结果的状态枚举不同，断言时先断状态再断数值，出错时更容易判断是算法问题还是数值精度问题。
4.2 一个完整算例
拿一个课本上的经典问题：最大化z = 3x1 + 2x2，约束x1 + x2 <= 4、x1 + 3x2 <= 6、x1, x2 >= 0。用这套 API 写出来：
double[] c = {3, 2}; LinearProgram lp = new LinearProgram(c, true); lp.addConstraint(new Constraint(new double[]{1, 1}, Constraint.Relation.LE, 4)); lp.addConstraint(new Constraint(new double[]{1, 3}, Constraint.Relation.LE, 6)); SimplexSolver solver = new SimplexSolver(); SolveResult result = solver.solve(lp); System.out.println(result.getStatus()); // OPTIMAL System.out.println(result.getObjectiveValue()); // 期望 10 左右 System.out.println(Arrays.toString(result.getVariables())); // x1=3, x2=0.5 附近这个算例的最优解是x1 = 3, x2 = 0.5，目标值10。跑出来如果目标值对但变量取值有1e-8级别的偏差，是正常的浮点误差；如果偏差到小数点后两位，那多半是主元选择或基变量更新出了问题。建议第一次跑通时把每次迭代的单纯形表打印出来，和手算对照一遍，比盯着最终结果猜要快得多。
4.3 结果解读与状态判断
SolveResult的状态必须被调用方认真处理。OPTIMAL时读目标值和变量；UNBOUNDED说明约束没把可行域封住，通常是建模时漏了上界；INFEASIBLE说明约束互相矛盾，两阶段法第一阶段的最优值不为零。业务代码里如果只判断“有没有结果”，把无界当成有解，后面会拿着一个不存在的方案去排产，这种坑我在项目里见过一次，排查了半天才发现是模型写错了。
提示：浮点比较一律走
NumberUtil里的isZero、isPositive，不要直接写== 0或> 0。单纯形法迭代几十轮之后，误差会累积，直接比较迟早出玄学问题。
5. 避坑与排查：单纯形法实现里最容易翻车的几处
5.1 死循环：入基列反复被选中
现象是程序卡在while循环里不退出，日志显示同一个变量反复进出基。原因通常是isBasic判断漏了人工变量列，或者检验数计算时没有排除基变量，导致已经最优的列还被当成候选。解决办法是把“候选入基列”的筛选条件写死：列不是基变量、检验数大于EPS、且该列不是人工变量（第二阶段）。三个条件缺一不可，建议抽成一个canEnter(j)方法，所有地方统一调用。
5.2 结果偏差大：主元选错或行变换顺序错
现象是目标值和手算差很多，但状态还是OPTIMAL。原因多半是主元行归一化之前就拿了pivot去做消元，或者消元时把主元行自己也减了一遍。正确顺序是：先保存pivot，归一化主元行，再对其他行做row_i -= factor * row_pivot，循环里跳过主元行本身。调试时把每次迭代的矩阵打印出来，和手算的表格逐行对，一般两三轮就能看出哪一步开始偏。
5.3 无界误判：比值检验的阈值写反
现象是明明有最优解的问题返回了UNBOUNDED。原因是比值检验里判断a > EPS写成了a >= 0或者a > -EPS，把负系数甚至零系数也纳入了候选，导致leaveRow选错或者选不到。记住规则：只有入基列系数严格为正的行才能参与比值检验，因为只有正系数才会让变量增大时约束先被顶到。这个符号错误在抄公式时特别容易发生，写完一定要拿一个已知有界的算例验证。
5.4 不可行问题被当成有解
现象是约束明显矛盾（比如x <= 1和x >= 2），但返回了OPTIMAL。原因是两阶段法的第一阶段没有正确检查人工变量之和是否为零，或者第二阶段没有把人工变量从基里清除就继续迭代。解决方法是第一阶段结束后显式检查：如果人工变量对应的目标值大于EPS，直接返回INFEASIBLE，不要进入第二阶段。这一步是硬性门槛，不能省。
5.5 大规模问题性能骤降
现象是变量数上百之后，迭代次数暴涨，单次求解从毫秒级掉到秒级。原因是每次迭代都全量扫描所有列算检验数，复杂度是O(m*n)乘以迭代次数。常见优化是维护检验数向量，主元变换时只更新受影响的列；或者入基规则从“最大检验数”换成 Bland 规则（选下标最小的正检验数列），虽然单步慢一点，但能避免循环，整体更稳。教学场景不用急着优化，但业务里变量上千时，这一步迟早要做。
6. 二次开发：把求解器嵌进业务系统的几个改造点
拿到这份代码之后，真正要落地到业务里，通常不是改算法，而是改接口和数值策略。第一个改造点是输入适配：业务数据往往是对象列表，不是double[]，建议在model包外面加一层LpModelBuilder，把订单、工位这些领域对象映射成系数矩阵，映射逻辑单独测试，别和求解器混在一起。第二个改造点是数值容差：EPS不要写死，做成构造参数，不同量级的问题（成本以元计 vs 以万元计）需要的阈值不一样，我一般会在配置里留一个solver.epsilon，默认1e-9，出问题时先调它。
第三个改造点是结果缓存与超时。单纯形法在最坏情况下是指数级的，业务系统不能无限等。常见做法是给solve加一个迭代次数上限，超过就返回一个TIMEOUT状态，让上层降级到贪心解。这个状态要加进SolveResult的枚举里，别用异常抛，异常在批量求解时开销太大。
第四个改造点是灵敏度分析。业务方经常问“某个约束放宽一点，成本能降多少”，这对应的是影子价格，也就是最优单纯形表里松弛变量对应的检验数。实现上不用重写算法，在Tableau里把最终表的检验数暴露出来，加一个getShadowPrices()方法即可。这个功能对二次开发的价值很高，因为它是从“能算”到“能解释”的关键一步。
最后一个技巧是关于测试的：每改一次主元逻辑或容差策略，都拿那四类标准算例（唯一解、多重解、无界、不可行）跑一遍回归，再补一个随机生成的小规模问题，和暴力枚举的结果对拍。单纯形法的 bug 往往不是崩，而是悄悄算错，对拍是唯一靠谱的后悔药。从那以后我每次动求解器核心代码，都强制先跑一遍这组回归，再谈业务联调。希望帮到你。
本文还有配套的精品资源，点击获取
