企业官网建设流程全解析

简介：面向运筹学学习与Java算法实践的线性规划求解器源码包，适合已具备Java基础、希望把两阶段法落到代码中的读者，也便于课程实验和算法练习对照。压缩包共11个文件、约13KB，以2个java源码与2个class字节码为核心，辅以5个xml工程配置、1个iml模块描述和1个gitignore版本忽略文件，目录紧凑，导入IDE后即可查看结构。已有3481人学习下载，说明该主题在运筹学与编程交叉学习中具有一定参考需求。代码围绕LP类展开，涵盖线性规划标准化、人工变量添加、两阶段法求解与统一solve入口，Main类负责控制台参数输入和结果输出；配合数组、ArrayList与二维矩阵存储系数和解，读者可据此梳理约束转换、松弛变量处理及测试边界情况的思路，获得流程完整、便于二次开发的求解起点。

1. 从一张算不平的排产表说起：这套 Java 版线性规划实现到底能干什么

某开发者拿表格软件跑一个 8 变量 12 约束的排产模型，点了求解，转几秒弹出“未找到可行解”，把约束顺序调一下再跑，结果又出来了。问题往往不在模型本身，而在于求解器内部做了什么，你完全看不见。线性规划在运筹学里是最基础也最常被调用的一类模型，真正的工程痛点很少是“不会建模”，而是手里没有一个能读、能改、能嵌进 Java 服务里的求解器。这份 Java 版线性规划算法实现就是冲这个场景去的：它把单纯形法、两阶段法、大 M 法、对偶价格这些课本步骤拆成可断点、可打印的类和表，输入一组系数矩阵，输出解向量加一堆中间量。适合两类人：想把运筹学作业真正跑通的在校开发者，以及需要在业务系统里塞一个轻量求解模块、又不想起外部进程的 Java 后端。

2. 项目骨架与技术选型：一个求解器该拆成哪几层

拿到这类算法项目，我第一件事不是看算法，而是看包结构。算法写得再漂亮，如果模型对象、标准型转换、求解循环、IO 全糊在一个Main.java里，二次开发就等于重写。这套代码的分层思路很典型：模型层只描述数学式子，转换层负责把任意形式化成标准型，求解层只认标准型，IO 层负责把文本变成模型。四层之间是单向依赖，求解层完全不知道文件格式的存在，这一点决定了后面能不能把它抽成一个 jar 丢进业务服务。

技术栈上没有惊喜，也不需要惊喜：JDK 8 起步（用了List.of的地方改成Arrays.asList即可），Maven 管依赖，JUnit 4/5 写单元测试，全程零第三方数学库。这个选择是有道理的——线性规划的稠密单纯形表规模通常在几百行以内，用double[][]直接算比引一个带 native 的优化库更可控，出了问题至少栈是纯 Java 的，好排查。

2.1 目录结构与各层职责

linprog-java/ ├── pom.xml ├── samples/ │ └── prod.lp └── src/ ├── main/java/com/example/lp/ │ ├── model/ │ │ ├── LPModel.java # 目标函数 + 约束集合 + 优化方向 │ │ ├── Constraint.java # 单条约束：系数、关系符、右端项 │ │ └── Variable.java # 变量名与下界（为后续扩展预留） │ ├── transform/ │ │ └── StandardForm.java # 松弛/剩余/人工变量，符号翻转 │ ├── solver/ │ │ ├── Solver.java # 接口：solve(LPModel) -> SolveResult │ │ ├── SimplexSolver.java # 两阶段单纯形主流程 │ │ ├── Tableau.java # 单纯形表：主元、换基、检验数 │ │ └── SolveResult.java # 状态、解、目标值、对偶价格 │ ├── io/ │ │ └── LpFileParser.java # 极简 LP 文本格式解析 │ └── Main.java # 命令行入口 └── test/java/com/example/lp/ └── SimplexSolverTest.java

solver包里Solver是个只有一行方法的接口，SimplexSolver是它目前唯一的实现。这个接口现在看着多余，等你哪天要加内点法或者接外部求解器做对拍，就知道它是唯一的插入点。transform单独成包也是同理：标准型转换是最容易出 bug 的地方，把它从求解循环里剥出来，可以单独写测试用固定矩阵验证。

2.2 LPModel：把数学式子翻译成 Java 对象

模型层要做的事情只有一件：完整、无歧义地保存max c^T x, s.t. Ax (≤/≥/=) b。不校验、不转换、不猜测用户意图，校验放到转换层，这样模型对象可以被反复喂给不同的求解器。

public final class LPModel { public enum Direction { MAX, MIN } public enum Relation { LE, GE, EQ } private final int varCount; private final double[] cost; // 目标函数系数，长度 = varCount private final Direction direction; private final List<Constraint> constraints = new ArrayList<>(); public LPModel(int varCount, double[] cost, Direction direction) { if (cost.length != varCount) { throw new IllegalArgumentException("cost 长度与变量数不一致"); } this.varCount = varCount; this.cost = cost.clone(); // 防御性拷贝，避免外部改数组 this.direction = direction; } public LPModel add(Constraint c) { if (c.coef().length != varCount) { throw new IllegalArgumentException("约束系数维度不匹配"); } constraints.add(c); return this; // 链式调用，建模型时写起来短 } public int varCount() { return varCount; } public double[] cost() { return cost.clone(); } public Direction direction() { return direction; } public List<Constraint> constraints() { return Collections.unmodifiableList(constraints); } }

Constraint更简单，三个字段：double[] coef、Relation relation、double rhs。这里刻意没有做x >= 0的下界字段，因为这份实现默认所有变量非负，下界为负的变量需要用户在建模时自己拆成两个非负变量之差。这是个明确的取舍，写在类的注释里比藏在代码里强。

构造一个具体模型：

// max 3x1 + 2x2 // s.t. x1 + x2 <= 4 // 2x1 + x2 <= 5 // x1, x2 >= 0 LPModel model = new LPModel(2, new double[]{3, 2}, LPModel.Direction.MAX) .add(new Constraint(new double[]{1, 1}, LPModel.Relation.LE, 4)) .add(new Constraint(new double[]{2, 1}, LPModel.Relation.LE, 5));

这个例子的最优解是x = (1, 3)，目标值 9，后面所有测试都拿它当基准。手工能算出来的小例子是排查算法 bug 最有效的手段，比任何日志都直接。

2.3 从命令行走通第一次求解

克隆下来先别急着读算法，跑通再说。项目是标准 Maven 结构，mvn -q compile过了就说明 JDK 版本没问题。命令行入口支持两种输入：内置样例名和.lp文件路径。

# 1. 编译并跑内置样例 mvn -q compile java -cp target/classes com.example.lp.Main sample1 # 2. 跑自定义模型文件 java -cp target/classes com.example.lp.Main samples/prod.lp # 3. 跑单元测试（包含退化、无界、不可行三类边界用例） mvn -q test

.lp文件格式刻意做得极简，一行一个语义块，方便手写也方便脚本生成：

max 3 2 2 1 1 <= 4 2 1 <= 5

第一行是方向，第二行是目标系数，第三行是约束条数，之后每行一条约束。解析器只做split和Double.parseDouble，不引入任何语法分析框架——这种规模的输入用正则都是浪费。输出长这样：

status : OPTIMAL objective: 9.000000 x1 = 1.000000 x2 = 3.000000 slack[0] = 0.000000 slack[1] = 0.000000 dual[0] = 1.000000 dual[1] = 1.000000

dual就是影子价格，也就是对偶变量的取值。很多人跑出解就停了，其实对偶价格在做资源分配类业务时比原解更有用：它告诉你第 i 种资源每多一个单位，目标值能涨多少，涨到什么时候这套基就换了。这份实现把dual一并输出，算是留了个好东西。

提示：如果你的 JDK 是 17 以上，mvn compile可能因为--release配置报警告，改pom.xml里的maven.compiler.release即可，不影响运行。

3. 核心算法拆解：单纯形法从换基到收敛的完整链路

真正吃透这份代码，得顺着一次求解的调用链走一遍：SimplexSolver.solve()→StandardForm.from()→Tableau构造 → 循环pivot()→ 回填结果。这一步是整个项目的心脏，也是绝大多数人自己写单纯形法会翻车的地方。课本上讲单纯形法通常直接给一张已经标准化的表，但工程实现里，八成的 bug 出在“从原始模型到标准型”这一段，而不是换基本身。

3.1 标准型转换：松弛变量、剩余变量和符号翻转

标准型的要求是：所有约束为等式、所有右端项非负、所有变量非负、目标统一为最大化。四条要求对应四种变换，任何一条漏做，后面的求解都会给出看似合理实则错误的答案。

public static StandardForm from(LPModel model) { int n = model.varCount(); int m = model.constraints().size(); // 1. 统计需要追加的列：每条 LE 加 1 个松弛变量，每条 GE 加 1 个剩余变量， // 每条 GE/EQ 再加 1 个人工变量 int extra = 0, artCount = 0; for (Constraint c : model.constraints()) { if (c.relation() == LPModel.Relation.LE) extra += 1; else if (c.relation() == LPModel.Relation.GE) { extra += 1; artCount += 1; } else artCount += 1; } int total = n + extra + artCount; double[][] a = new double[m][total]; double[] b = new double[m]; int[] basis = new int[m]; int[] artificial = new int[artCount]; int col = n, artIdx = 0; for (int i = 0; i < m; i++) { Constraint c = model.constraints().get(i); System.arraycopy(c.coef(), 0, a[i], 0, n); b[i] = c.rhs(); // 2. 右端项为负时整行乘 -1，关系符随之翻转，否则初始基不可行 if (b[i] < 0) { for (int j = 0; j < total; j++) a[i][j] = -a[i][j]; b[i] = -b[i]; // 关系符翻转：LE <-> GE } switch (effectiveRelation(c, /* flipped */)) { case LE: a[i][col] = 1.0; basis[i] = col; col++; // 松弛变量直接进基 break; case GE: a[i][col] = -1.0; col++; // 剩余变量不进基 a[i][col] = 1.0; artificial[artIdx++] = col; basis[i] = col; col++; break; case EQ: a[i][col] = 1.0; artificial[artIdx++] = col; basis[i] = col; col++; break; } } // 3. 目标系数：MIN 取反，统一按最大化算 double[] cost = model.cost(); double sign = model.direction() == LPModel.Direction.MAX ? 1.0 : -1.0; double[] c = new double[total]; for (int j = 0; j < n; j++) c[j] = sign * cost[j]; return new StandardForm(a, b, c, basis, artificial, n, total, sign); }

这段代码里有三个参数点值得盯住。basis[i]是第 i 行基变量的列下标，LE 约束的初始基直接取松弛变量，GE 和 EQ 只能靠人工变量撑出一个单位基，这是两阶段法的前提。sign用来统一优化方向，最小化问题在内部全部转成最大化算，出结果时再乘回去，不这么做就得在单纯形循环里写两套符号判断，早晚写错。total是新矩阵的总列数，包含原始变量、松弛剩余变量和人工变量三部分，后面所有下标换算都基于它。

effectiveRelation这个辅助方法负责在右端项翻转后调整关系符：原来是<=且右端为负，翻转后变成>=，反之亦然。这里最容易出的问题是只在原约束上判断了一次关系符，忘了翻转，导致该加人工变量的地方加了松弛变量，第一阶段直接报“可行”，实际解是假的。

3.2 单纯形表的数据布局：一张二维数组怎么装下所有信息

Tableau的职责是把标准型装进一张表，并对外暴露三个动作：找入基列、找出基行、主元消去。表的结构是(m + 1) × (total + 1)，多出来的一行是检验数行（也叫目标行），多出来的一列是右端项。

public final class Tableau { private static final double EPS = 1e-9; private final double[][] a; // (m+1) x (n+1)，最后一行是检验数，最后一列是 RHS private final int[] basis; // 每行的基变量列号 private final int m; // 约束行数 private final int n; // 列数（不含 RHS） public Tableau(double[][] matrix, double[] cost, int[] basis, int[] artificial) { this.m = matrix.length; this.n = matrix[0].length; this.a = new double[m + 1][n + 1]; for (int i = 0; i < m; i++) { System.arraycopy(matrix[i], 0, a[i], 0, n); a[i][n] = rhs[i]; } // 目标行：放 -c（最大化），再对基变量做消元，保证基变量检验数为 0 for (int j = 0; j < n; j++) a[m][j] = -cost[j]; for (int i = 0; i < m; i++) { int b = basis[i]; double f = a[m][b]; if (Math.abs(f) > EPS) { for (int j = 0; j <= n; j++) a[m][j] += f * a[i][j]; } } this.basis = basis.clone(); } }

目标行那一步消元是新手最容易漏的。初始基里有人工变量，而人工变量在目标函数里有系数（第一阶段是 1，第二阶段是 0），如果不把基行的贡献消掉，检验数就带着偏差，选出来的入基列从一开始就是错的。写成a[m][j] += f * a[i][j]而不是减，是因为矩阵里存的是-c，符号得跟着走。这个+/-我见过太多人凭感觉写，结果在最大化最小化之间来回翻车，建议统一约定：表里只存“最大化形式”的-c，任何符号变换都在构造阶段一次性做完。

EPS = 1e-9是全局容差，后面所有判断都用它。这个值不是随便定的：约束系数在 1 到 100 量级、变量几十个的时候，1e-9 足够吸收浮点误差，又不会把真正的小检验数误判成 0。系数动辄上万的大模型需要重新调，这事得写进文档。

3.3 换基：入基列、出基行与主元消去

这是整个算法里唯一需要循环执行的部分。入基按最小检验数（Dantzig 规则）选，出基按最小比值检验选，选完做一次主元消去，基变量随之替换。

// 返回 true 表示继续迭代，false 表示已经收敛或判定无界 public boolean iterate() { // 1. 选入基列：检验数 < -EPS 的最负一列（最大化） int col = -1; for (int j = 0; j < n; j++) { if (a[m][j] < -EPS && (col == -1 || a[m][j] < a[m][col])) col = j; } if (col == -1) return false; // 无负检验数，已达最优 // 2. 选出基行：最小比值检验，只考虑系数 > EPS 的行 int row = -1; double best = Double.MAX_VALUE; for (int i = 0; i < m; i++) { if (a[i][col] > EPS) { double ratio = a[i][n] / a[i][col]; if (ratio < best - EPS) { best = ratio; row = i; } } } if (row == -1) throw new UnboundedException(); // 该列全非正，目标无界 // 3. 主元消去：本行归一化，其余行（含目标行）消元 pivot(row, col); basis[row] = col; return true; } private void pivot(int row, int col) { double p = a[row][col]; for (int j = 0; j <= n; j++) a[row][j] /= p; for (int i = 0; i <= m; i++) { if (i == row) continue; double f = a[i][col]; if (Math.abs(f) < EPS) continue; for (int j = 0; j <= n; j++) a[i][j] -= f * a[row][j]; } }

三个参数点。a[m][j] < -EPS里的负号对应“最大化”，如果哪天要改成直接支持最小化，这一行和收敛判定要一起改，别只改一处。a[i][col] > EPS决定哪些行可以参与比值检验，系数为负或为 0 的行参与进来会导致出基后解变成负数，直接违反可行性。pivot里循环写i <= m，把目标行也一起消元，这是把目标行塞进同一张表的好处，不用单独写一套检验数更新逻辑。

pivot的复杂度是O(m × n)，一次完整求解的迭代次数在 m 的量级，所以整体是O(m²n)。几十上百行约束的模型毫秒级出结果，不需要做稀疏化优化。

3.4 收敛判定与结果回填

迭代返回 false 之后，表里的信息足够回填出完整结果：每行的 RHS 就是该行基变量的取值，其余变量为 0，目标行的 RHS 取负就是最优值。

public SolveResult extract(int originalVars, double sign) { double[] x = new double[originalVars]; for (int i = 0; i < m; i++) { int b = basis[i]; if (b < originalVars) x[b] = a[i][n]; // 只回填原始变量 } double objective = -a[m][n] * sign; // 表里存的是 -z，再按 MIN/MAX 还原符号 // 对偶价格：松弛变量列的检验数取负，即为对应约束的影子价格 double[] dual = new double[m]; for (int i = 0; i < m; i++) { int slackCol = originalVars + i; // 前提是松弛变量按顺序追加 dual[i] = a[m][slackCol]; } return new SolveResult(Status.OPTIMAL, x, objective, dual); }

回填时b < originalVars的判断很关键，松弛变量和人工变量也在basis里，不过滤的话数组越界。objective = -a[m][n] * sign里外层负号是因为表里存的是-z，sign负责把最小化的结果翻回来。dual的取法依赖“松弛变量按约束顺序依次追加”这个约定，改StandardForm的追加顺序就必须同步改这里，属于隐性耦合，写注释比写文档管用。

4. 两阶段法与大 M 法：初始基可行解到底从哪来

只有<=约束的模型，松弛变量天然构成单位基，一次单纯形就能收敛。可一旦出现>=或=，初始基里必须有人工变量，而人工变量的取值一旦为正，原问题的约束就被破坏了。两阶段法和大 M 法解决的是同一个问题：怎么把人工变量从基里干净地赶出去。

4.1 第一阶段：最小化人工变量之和

第一阶段的思路很直接：构造一个新目标，只最小化所有人工变量之和。如果最优值大于 0，说明原问题无论如何都无法满足所有约束，直接判定不可行；如果等于 0，说明存在一个不含人工变量的可行基，可以进入第二阶段。

private double runPhaseOne(Tableau t, int[] artificial, int m, int n) { // 构造第一阶段目标：最大化 -(sum artificial)，等价于最小化人工变量之和 double[] phase1Cost = new double[n]; for (int col : artificial) phase1Cost[col] = 1.0; Tableau phase1 = t.withCost(phase1Cost); // 内部会重算检验数并消元 while (phase1.iterate()) { // 迭代上限保护，防止退化导致的意外死循环 if (++iterations > MAX_ITER) throw new IllegalStateException("阶段一迭代超限"); } return -phase1.objectiveValue(); // 返回 sum(artificial) }

phase1Cost只在人工变量列上取 1，其余为 0，交给withCost去处理基变量消元。MAX_ITER放到m * 50这个量级比较稳妥，正常模型远远达不到，真触发了就说明退化循环没处理好，宁可抛异常也不要静默死循环。

返回值-phase1.objectiveValue()是人工变量之和。判断逻辑是：

double infeasibility = runPhaseOne(tableau, artificial, m, n); if (infeasibility > 1e-7) { return SolveResult.infeasible(); // 原问题无可行解 }

阈值用1e-7而不是1e-9，因为第一阶段经过多轮消元，人工变量之和的数值噪声比单次运算大一个量级，卡太死会把本可行的模型判成不可行。这是纯经验值，但比拍脑袋定 0 靠谱得多。

4.2 第二阶段：恢复原目标函数重算检验数

第一阶段结束后，基里可能还残留着取值为 0 的人工变量——这不算错，只要它们不出基、值保持为 0，就不影响原问题的可行域。第二阶段要做的是把目标换成原始目标，重新消元算检验数，然后继续迭代。

private void enterPhaseTwo(Tableau t, double[] originalCost, int[] artificial, int[] basis, int m, int n) { // 1. 人工变量在第二阶段目标中系数为 0 double[] cost2 = originalCost.clone(); for (int col : artificial) cost2[col] = 0.0; // 2. 若人工变量仍在基里且值为 0，把它换出基： // 在本行找一个非人工、非零系数的列做主元；找不到说明该行是冗余约束 for (int i = 0; i < m; i++) { if (isArtificial(basis[i], artificial)) { int swapCol = -1; for (int j = 0; j < n; j++) { if (!isArtificial(j, artificial) && Math.abs(t.get(i, j)) > EPS) { swapCol = j; break; } } if (swapCol >= 0) t.pivot(i, swapCol); // 找不到就保留，该行对原问题无约束力 } } t.resetObjective(cost2); // 重算检验数并消元 }

这一步的坑集中在冗余约束上。人工变量停在基里、整行系数全为 0，说明这条约束是其他约束的线性组合，可以从问题里删掉。代码里选择“保留但不动”，因为删行会改变约束下标，进而影响对偶价格的输出顺序。保守做法是记一个标志位，输出dual时把冗余行标成 0，不做数组搬迁。

resetObjective必须在换出人工变量之后调用。顺序反了，检验数是按旧基算的，第二阶段第一步就会选错入基列，表现为解对了但目标值差一点，这种错最难受，因为它不报错。

4.3 大 M 法的实现与两者的取舍

大 M 法把两个阶段合成一个：直接给人工变量一个巨大的负系数-M，让它们只要取正值，目标函数就暴跌，从而在优化过程中被自动压到 0。

// 大 M 法：M 取系数量级的 1e6 倍以上，确保人工变量不被选用 public static double chooseBigM(double[][] a, double[] c) { double maxCoef = 1.0; for (double[] row : a) for (double v : row) maxCoef = Math.max(maxCoef, Math.abs(v)); for (double v : c) maxCoef = Math.max(maxCoef, Math.abs(v)); return maxCoef * 1e6; }

两者怎么选，我给个明确建议：默认用两阶段法，大 M 法只做交叉验证。大 M 的 M 值取得小，人工变量可能压不下去；取得大，和真实系数差出六个数量级，double的精度直接报废，检验数全是噪声，表现为“明明有解却报无界”或者“解出来一堆 1e-7 量级的负数”。两阶段法没有这个数值悬崖，第一阶段的最优值就是可行性判据，逻辑上更干净，代价只是多一遍迭代。项目里保留大 M 实现的价值在于对拍——同一个模型两条路径都跑一遍，结果一致才敢相信。

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

算法本身的伪代码不超过 30 行，但把它写成能稳定跑生产数据的代码，坑比想象的多。下面五条是我在调试这类实现时反复遇到的，每条都给了现象、原因和改法，照着排查能省不少时间。

5.1 可行性与基的初始化：两个直接判错的坑

第一条：右端项为负没翻转，第一阶段报不可行。

现象很迷惑：模型手工验证明明有可行解，程序返回INFEASIBLE，而且是第一阶段一开始就返回，迭代次数是 0。原因在StandardForm.from里，b[i] < 0的行没有整体乘 -1。负的右端项意味着初始基变量的取值为负，直接违反非负约束，第一阶段的目标函数再优化也压不到 0。解决办法就是代码里那段翻转，同时把关系符跟着翻：<= -5等价于>= 5，松弛变量要换成剩余变量加人工变量。排查技巧是在StandardForm.from结束时打印一遍矩阵和basis，看每行的 RHS 是否全非负，一眼就能确认。

第二条：人工变量停在基里没处理，第二阶段解是错的。

现象是第一阶段没问题，第二阶段跑完，解向量里有几个变量是 0，但目标值比手工算的小，约束代回去还差一点点。原因是人工变量以取值 0 的形式留在基里，第二阶段重算检验数时，这一行参与了消元，把原问题的可行性条件悄悄改掉了。改法是进入第二阶段前把人工变量换出基，也就是上节enterPhaseTwo那段逻辑。如果整行在非人工列上全是 0，说明这是冗余约束，标记跳过即可。

5.2 精度与循环：1e-9 到底该怎么用

第三条：检验数在 1e-12 量级反复入基，迭代次数爆表。

现象是while(iterate())跑了上万次还在动，打印检验数发现每次都有一个-1e-13左右的值被选中入基，出基后目标值几乎不变。这是典型的浮点噪声当成了改进方向。单纯形法本身在有理数上是有限步收敛的，浮点下必须靠容差截断。改法是把所有检验数比较统一成a[m][j] < -EPS，并且给迭代次数加硬上限。另外，判断“目标值有没有改进”的时候也别用==，改成和上一次的目标值比较，差值小于EPS就主动停。

第四条：退化基导致循环（cycling）。

现象是迭代次数很多但目标值一直不动，几个基之间来回切换。原因是最小比值检验里出现并列，且并列值都是 0，出基变量取值不变，换了基等于白换。经典解法是 Bland 规则：入基选下标最小的负检验数列，出基在比值并列时选下标最小的行。Bland 规则收敛性有保证，代价是迭代次数变多。我的做法是默认用 Dantzig 规则，检测到连续m * 2次目标值无改进时自动切换到 Bland，两边的好处都占上。

提示：退化是建模问题不是算法问题。约束之间存在线性相关、右端项里有大量 0，都会加剧退化，模型层能去冗余就先去。

5.3 无界、冗余与方向：容易被忽略的三处

第五条：无界判定漏写，数组越界或者解出NaN。

现象是某些模型跑着跑着抛ArrayIndexOutOfBoundsException，或者解向量里出现Infinity。原因在入基列确定后，比值检验没找到任何a[i][col] > EPS的行，此时row还是 -1，直接拿去调pivot(-1, col)就炸了。这在数学上的含义是目标函数无界，应该返回UNBOUNDED而不是继续算。改法就是在row == -1时立刻抛出专用异常或者返回状态，别让它流到下一层。同理，pivot里如果主元绝对值小于EPS，说明选错了行，也要拦一道。

除这五条之外还有两个小地方：最大化最小化方向弄反（症状是解对了目标值符号不对）、原始变量下标和表列下标混用（症状是解向量错位），排查时打印一次完整的表和basis数组，基本都能对上号。

6. 二次开发：从“能算”到“敢用在业务里”的改造路线

这份实现能跑通标准模型，但要接进真实业务，还有几刀要补。第一刀是把Solver接口用起来，写一个SolverRouter，按模型规模分流：约束少于 200 行走稠密单纯形，超过就提示用户换外部求解器，别硬扛。第二刀是输入格式，.lp文本适合调试，业务系统的模型多半从数据库或者 JSON 来，加一个ModelBuilder从 Map 构造LPModel就够了，别在求解层碰 JSON。

第三刀是对偶价格和灵敏度分析。现在dual是顺手输出的，但真正有用的是“目标系数在什么区间内变动，当前最优基不变”这类结论。实现思路是在最优表上算：非基变量的检验数除以主元列系数，取最小正比值，就是该系数允许的变动上限。下面这段可以挂在SolveResult上当一个分析入口：

// 计算某个非基变量目标系数的允许增量上限（最大化问题，当前基保持最优） public double allowedIncrease(int varIndex, Tableau t, int m) { double best = Double.MAX_VALUE; for (int i = 0; i < m; i++) { double colCoef = t.get(i, varIndex); if (colCoef > 1e-9) { // 只看正系数行 best = Math.min(best, t.getObjectiveCoef(varIndex) / colCoef); } } return best == Double.MAX_VALUE ? Double.POSITIVE_INFINITY : best; }

验证方法我一般固定走三步。第一步，用两个变量的小模型手算最优解，断言目标值精确相等。第二步，构造退化、无界、不可行三类边界用例各一个，断言返回的Status正确，这一步比第一步重要得多，因为错误大多藏在状态判定里。第三步，随机生成 50 个可行小模型，用两阶段法和大 M 法各跑一遍，两个解的目标值差小于 1e-6 才算过。随机对拍能抓出绝大多数下标换算和符号错误，我靠这招逮到过两次松弛变量列错位的问题。

最后说个习惯。这类数值算法我改完之后，一定会把Tableau的每次pivot前状态打到 debug 日志里，跑一遍最小用例，肉眼过一遍检验数和比值，确认没有异常大的数、没有反复入基同一列。这套动作看着笨，但它把“偶发错解”这种最贵的 bug 挡在了提交之前。希望帮到你。

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