简介这是一份线性规划算法实现的Java版学习资源面向需要掌握运筹学基础算法、希望在Java中落地求解器的开发者或学生。资源讲解线性规划模型构成、标准化处理、人工变量与两阶段法等内容并给出LP类与Main类的控制台交互实现可帮助读者理解从问题建模到代码求解的完整链路。压缩包共11个文件主体为2个Java源码及对应class文件另有5个XML配置、项目模块文件及版本管理文件整体仅13KB结构简洁适合直接阅读和二次修改。代码中涉及二维数组、ArrayList等常见数据结构适合分析算法流程或扩展为交互式求解器。已有3477人学习下载适合作为运筹学课程设计、算法学习或期末作业的参考。1. 线性规划在 Java 里落地自己手写还是直接接库“线性规划算法实现——Java版”这个标题翻译成实际需求通常是这样一句话我要在 Java 进程内把一个线性规划模型算成最优解。可能是课程设计里的资源分配可能是调度系统里要嵌入的生产排产也可能是面试八股里最容易被追问的那句“单纯形法你手写过吗”。它的下限是把教材里的单纯形法写成能跑的类上限是搞清楚 EPS、退化和对偶验证这些只有跑起来才会撞到的问题。下文按“先手写、再接库、再避坑”的顺序把一条能在本地跑通的路线讲清楚。适合三类人要交 Java 课程设计的学生、在系统里接 LP 求解的后端工程师、以及面试前想把手写版本练熟的人。2. 手写单纯形法标准形、选主元与一段能跑的 Java 代码2.1 先把问题收拾成标准形max 与 Ax ≤ b 的约定要手写单纯形法第一步不是写代码而是把任意线性规划问题统一成标准形。我一般约定目标函数求最大约束全是小于等于右端项 b 全部非负。用数学语言写就是max c^T xs.t. A x ≤ bx ≥ 0。为什么只用这种形态因为这种形态天然有一个初始基可行解每个小于等于约束各加一个松弛变量松弛变量就是初始基变量原始变量全部取 0基变量直接等于 b。只要 b ≥ 0第一个可行解不用算就白拿。很多教材把这一步叫“引入松弛变量”实操里它就是给每一行约束多开一列系数为 1。如果你的问题是 min直接把目标系数取相反数转成 max如果约束是 ≥两边乘 -1 后转成 ≤。但这里有个很容易踩的边界乘 -1 之后 b 可能变成负数而上面的标准形要求 b ≥ 0。一旦出现负 b单纯靠松弛变量凑不出初始可行解就需要人工变量和两阶段法。所以第二章这段代码只接受 b ≥ 0 的 Ax ≤ b 模型工程里遇到更复杂的形态优先走第三章的库。2.2 单纯形表选主元的循环逻辑两个判定一个旋转手写单纯形法的核心不是求逆矩阵而是维护一张 m1 行、nm1 列的单纯形表。行 0 是目标函数行行 1 到 m 是约束行列从 0 到 n-1 是原始变量n 到 nm-1 是松弛变量最后一列是右端项。外加一个 int[] basis记录每一行当前的基变量列号。每一轮迭代做三件事进基判定在目标函数行里找一个系数小于 -EPS 的列。这个列对应的非基变量每增加 1 单位目标函数有机会提升所以把它选为进基变量。选最小下标是为了避免后面遇到的退化循环这就是 Bland 规则的入门版。离基判定对进基列中系数大于 EPS 的每一行用右端项除以该系数得到比值选比值最小的那一行该行当前的基变量离基。这一步保证右端项始终非负也就维持了可行性。如果所有系数都不大于 0说明目标函数可以无限增大模型无界直接返回。旋转操作把主元行做主元归一化再用这一行消去其余所有行包括目标函数行。本质就是高斯消元把进基变量变成新基变量。循环直到目标函数行里找不到负系数为止。此时当前基可行解就是最优解右端项列对应原始变量的值就是最优解目标函数行最后一列的相反数是最优值。注意是相反数因为我把目标函数行初始化为 -c而不是 c这是为了消元符号统一。2.3 最小可运行代码与测试用例下面这个 Simplex 类只处理标准形代码可以直接复制到本地跑。它包含目标函数行初始化、进基判定、离基判定和 pivot 四部分没有额外依赖适合课程设计和面试手写题。import java.util.Arrays; /** * 手写单纯形法仅支持标准形 * max c^T x, s.t. A x b, x 0, b 0 */ public class Simplex { private static final double EPS 1e-9; private final double[][] table; private final int rows; private final int cols; private final int[] basis; public Simplex(double[][] A, double[] b, double[] c) { rows b.length; cols c.length rows; basis new int[rows]; table new double[rows 1][cols 1]; // 目标函数行初始化为 -c最终结果的相反数才是最优值 for (int j 0; j c.length; j) { table[0][j] -c[j]; } for (int i 0; i rows; i) { System.arraycopy(A[i], 0, table[i 1], 0, A[i].length); table[i 1][c.length i] 1.0; // 松弛变量 table[i 1][cols] b[i]; basis[i] c.length i; } } /** * 求解结果写入 solution 数组返回最优值。 * 模型无界时返回 Double.POSITIVE_INFINITY。 */ public double solve(double[] solution) { while (true) { int enter findEnteringColumn(); if (enter 0) break; int leave findLeavingRow(enter); if (leave 0) return Double.POSITIVE_INFINITY; pivot(leave, enter); } Arrays.fill(solution, 0.0); for (int i 0; i rows; i) { if (basis[i] solution.length) { solution[basis[i]] table[i 1][cols]; } } return -table[0][cols]; } // 进基选目标函数行最小下标的负系数列 private int findEnteringColumn() { for (int j 0; j cols; j) { if (table[0][j] -EPS) return j; } return -1; } // 离基最小比值原则比值并列时选基变量列号更小的行 private int findLeavingRow(int enterCol) { int leave -1; double minRatio Double.MAX_VALUE; for (int i 1; i rows; i) { double coefficient table[i][enterCol]; if (coefficient EPS) { double ratio table[i][cols] / coefficient; boolean smaller ratio minRatio - 1e-12; boolean tied Math.abs(ratio - minRatio) 1e-12 leave 0 basis[i - 1] basis[leave]; if (smaller || tied) { minRatio ratio; leave i - 1; } } } return leave; } // 旋转归一化主元行再消去其他所有行 private void pivot(int row, int col) { double pivotValue table[row 1][col]; for (int j 0; j cols; j) { table[row 1][j] / pivotValue; } for (int i 0; i rows; i) { if (i row 1) continue; double factor table[i][col]; for (int j 0; j cols; j) { table[i][j] - factor * table[row 1][j]; } } basis[row] col; } }对应的测试用例用经典的生产排产模型变量 x1、x2 是两种产品产量目标函数 3x1 2x2三条资源约束分别是 2x1 x2 ≤ 18、2x1 3x2 ≤ 42、3x1 x2 ≤ 24。手算最优解是 x13x212最优值 33。public class Main { public static void main(String[] args) { double[][] A { {2.0, 1.0}, {2.0, 3.0}, {3.0, 1.0} }; double[] b {18.0, 42.0, 24.0}; double[] c {3.0, 2.0}; Simplex simplex new Simplex(A, b, c); double[] x new double[2]; double value simplex.solve(x); System.out.printf(最优解: x1 %.6f, x2 %.6f%n, x[0], x[1]); System.out.printf(最优值: %.6f%n, value); } }这里的三个参数值得说明A 的每一行是一条约束的系数b 是对应右端项c 是目标函数系数。EPS 设置成 1e-9 是我常用的值如果模型系数本身很大比如上万可以适当放大到 1e-7否则小噪声会把选主元带偏。solve 方法返回的是最优值最优解写入传入的 x 数组无界时返回正无穷。这个版本不判断无解因为 b ≥ 0 且约束全是 ≤ 时x0 天然可行不存在无解一说。3. 用 Apache Commons Math 接库SimplexSolver 最小集成与模型构造3.1 为什么工程里我建议先接库而不是继续打磨手写版手写单纯形法有两个现实瓶颈。第一它只覆盖了标准形真实系统里经常出现 ≥ 约束、等式约束、负 b、混合整数变量这些都要额外实现两阶段法或分支定界代码量翻倍。第二单纯形法本质上对数值精度敏感教材例子系数都是整数工程里的系数可能来自浮点运算会出现退化、循环、接近零的主元需要花大量时间调 EPS。所以我的习惯是课程设计和面试用第二章的手写版本但凡是给真实业务做模块直接用 Apache Commons Math。它是 Java 生态里最出名的数学库自带 SimplexSolver底层是两阶段单纯形法支持 Relationship.LEQ、GEQ、EQ也支持等式约束和变量非负约束。它不用我维护表格和选主元只要把目标函数和约束描述清楚求解器自己处理初始可行解的问题。这不代表手写版本白费功夫。恰恰相反知道标准形、松弛变量、选主元、无界判定这些概念才能理解库返回的结果为什么长这样也知道某些场景该用什么关系约束。3.2 SimplexSolver 最小集成代码、Maven 依赖与运行结果Maven 项目里加入 commons-math3 依赖。如果你用 Gradle对应改一下依赖坐标即可。dependency groupIdorg.apache.commons/groupId artifactIdcommons-math3/artifactId version3.6.1/version /dependency下面这段代码和第二章的测试用例是同一个模型只是交给库去解import org.apache.commons.math3.optim.PointValuePair; import org.apache.commons.math3.optim.linear.*; import org.apache.commons.math3.optim.nonlinear.scalar.GoalType; import java.util.ArrayList; import java.util.Collection; public class ApacheSimplexExample { public static void main(String[] args) { // 目标函数: max 3*x1 2*x2 LinearObjectiveFunction f new LinearObjectiveFunction(new double[]{3.0, 2.0}, 0.0); CollectionLinearConstraint constraints new ArrayList(); constraints.add(new LinearConstraint( new double[]{2.0, 1.0}, Relationship.LEQ, 18.0)); constraints.add(new LinearConstraint( new double[]{2.0, 3.0}, Relationship.LEQ, 42.0)); constraints.add(new LinearConstraint( new double[]{3.0, 1.0}, Relationship.LEQ, 24.0)); SimplexSolver solver new SimplexSolver(); PointValuePair solution solver.optimize( f, constraints, GoalType.MAXIMIZE, new NonNegativeConstraint(true)); double[] point solution.getPoint(); System.out.printf(最优解: x1 %.6f, x2 %.6f%n, point[0], point[1]); System.out.printf(最优值: %.6f%n, solution.getValue()); } }逻辑说明LinearObjectiveFunction 的第一个参数是目标函数系数数组第二个参数是常数项偏移量一般填 0。LinearConstraint 的三个参数分别是约束系数向量、关系枚举和右端项。solver.optimize 接收四个 OptimizationData目标函数、约束集合、目标方向和变量非负约束。NonNegativeConstraint(true) 表示所有变量 ≥ 0这一步在工程里非常容易被漏掉。Commons Math 内部对变量有限制不加这个约束时某些模型可能返回无界或者异常结果后面避坑章节会展开。3.3 模型构造的两条硬规则目标方向与变量非负用 Commons Math 构造线性规划模型时我给自己定了两条硬规则。第一条目标方向直接用 GoalType.MAXIMIZE 或 GoalType.MINIMIZE不要在建模时手工翻转系数。很多人习惯把所有问题都转成 max把 min 的目标系数取反这其实没必要库原生支持最小化。手工翻转反而容易在验证结果时把自己绕晕。第二条变量非负约束必须显式声明。有些教学范例不写 NonNegativeConstraint因为库有这个默认行为但不同版本默认不一致写成显式参数最安全。另外约束关系不要滥用。LEQ 是小于等于GEQ 是大于等于EQ 是等式。等式约束在工程里很常见比如“总工时恰好等于 1000”Commons Math 支持 EQ但这会引入人工变量求解效率略低不是 bug。如果你的模型里有大量等式先检查是不是业务上本就是不等式别顺手写成等式给自己增加计算量。4. 参数与结果解读EPS、迭代上限、影子价格和大规模边界4.1 三个必调参数EPS、最大迭代次数和精度手写版本的 EPS 是我第一个调的参数。EPS 太小比如 1e-12会把浮点噪声当成有效系数进基和离基判断变得敏感EPS 太大比如 1e-5又可能把真正的主元漏掉导致提前收敛到非最优解。我一般以模型系数量级为参照系数都在百以内用 1e-9系数上到万用 1e-7。这个值不是玄学它本质上是“多小的数可以视为零”的阈值。Commons Math 的 SimplexSolver 也允许传入 MaxIterations控制最大迭代次数。虽然大多数问题几十次迭代就收敛但退化模型可能出现极长的迭代。我给课程设计里的代码通常显式传入一个 10000 的上限避免某个边界用例卡到怀疑人生。上限不是越大越好设置一个明确上限反而能在问题异常时快速暴露。第三个参数是精度。单纯形法内部全程用 double结果天然有浮点误差。如果业务对金额敏感不要直接用 double 做最终结算正确做法是用求解器算出最优解结构再拿 BigDecimal 重新核算一次目标值和约束余量除非你的模型和业务都允许千分位误差。4.2 最优表里还能读出什么影子价格与原问题验证只拿最优解是浪费。单纯形法的最优表里还藏着每个约束的影子价格也就是“这个资源再多一单位目标函数能增加多少”。在看代码之前先记住结论在目标函数行里松弛变量所在列的系数取相反数就是对应约束的影子价格。用第二章的例子三条约束分别对应三个松弛变量。最优解时前两条约束刚好卡满影子价格大于 0第三条约束松弛了一部分影子价格近似 0。你可以把第一条约束右端项从 18 改成 19重新求解会发现最优值增量正好等于那个影子价格。这个小实验是验证手写代码是否正确的最好方式也是面试时和面试官聊对偶价格的切入点。基于同样的原理我经常用约束余量来排查模型问题。如果某个本来就该稀缺的资源求解出来的松弛变量特别大说明约束系数或者右端项写错了。不要只看最优值把松弛变量打出来看看能省很多 debug 时间。4.3 什么时候别用单纯形法大规模稀疏场景的边界手写版本和 Commons Math 的 SimplexSolver 都是稠密实现底层用一个二维数组装整张表。变量数和约束数都在几百以内跑得很舒服一旦变量数上到几千、约束数上到几千内存和耗时就都不对劲了。原因是单纯形表里大量系数本来就是 0稠密存储把这些零全存成了 double空间浪费严重。遇到这种情况别再纠结手写直接换专业线性规划工具。Java 生态里常见的做法是接入 OR-Tools 的 linear_solver 模块底层是 GLOP 或 SCIP能处理稀疏矩阵也支持整数规划。Commons Math 在这个场景下只适合当教学和原型工具。明白这个边界至少能告诉面试官“我知道单纯形法不是银弹”。5. 避坑退化死循环、负右端项和整数场景的 5 个典型现场5.1 手写版本对某些输入卡死退化与 Bland 规则现象同一个模型手写单纯形法偶尔会陷入无限循环CPU 占用拉满但程序不退出。原因模型存在退化多个基可行解对应同一个顶点选主元规则不当会让基变量组合反复横跳。解决在进基和离基判定里都绑定最小下标规则。第二章代码里的 findEnteringColumn 从第 0 列开始找离基比值相同时选基变量列号更小的行这就是 Bland 规则的一种实现。只要坚持这个规则理论上可以避免退化循环。如果你手写版本还没加这个规则这是高优先级的后悔药。5.2 负右端项让模型失去初始可行解两阶段法的取舍现象把 约束两边乘 -1 后b 变成负数手写代码直接给出错误结果甚至返回无界。原因标准形要求 b ≥ 0负 b 意味着 x0 不再可行松弛变量不能直接当基变量。解决要么把负 b 的行再处理一遍通过变量替换变成正 b要么实现两阶段法先引入人工变量求一个初始可行解。我的建议是课程设计里没必要重复造轮子直接上 Commons Math 处理 GEQ 和 EQ省掉这一整块。5.3 Commons Math 返回 Infinity漏掉 NonNegativeConstraint现象一个看起来有界的问题用 SimplexSolver 求出来最优值是 Infinity或者抛出和“unbounded”相关的异常。原因没有加 NonNegativeConstraint(true)库允许变量取负值某些方向目标函数可以无限增大。解决加上 NonNegativeConstraint 后再跑。如果业务里确实存在自由变量要先把自由变量拆成两个非负变量的差比如 x u - vu, v ≥ 0再交给求解器。5.4 把 LP 小数解四舍五入当整数解整数场景的错误示范现象线性规划求出 x13.7顺手四舍五入成 4结果约束被破坏目标值也不对。原因线性规划的最优解可能落在非整数顶点四舍五入后的整数点甚至不在可行域里。解决如果变量必须取整数这是整数规划问题不是线性规划问题。正确做法是接整数规划求解器做分支定界或者用 OR-Tools 的 CP-SAT。线性规划在这类问题里只能用作松弛模型用来给分支定界提供上下界不能直接取整当最终答案。5.5 double[][] 把内存撑爆大规模患者的边界现象模型规模 5000 变量、5000 约束手写表格启动直接 OOM。原因稠密二维数组存了大约 1 亿个 double就算每个 8 字节也有近 800MB这还没算其他对象开销。解决换稀疏表示或者直接换支持稀疏矩阵的求解器。遇到这种规模别说是手写版本Commons Math 也会很吃力。工程上务实一点把 OR-Tools 之类的专业求解器作为选项你的 Java 代码只需要封装模型转换和结果解析。6. 进阶验证用对偶问题给手写求解器做正确性检查6.1 从原问题生成对偶模型手写求解器写完怎么证明它对我的习惯是构造对偶问题用同一个求解器去验证强对偶定理。对第二章的标准形模型对偶问题长这样min b^T ys.t. A^T y ≥ cy ≥ 0。也就是说原问题有 n 个变量、m 个约束对偶问题就有 m 个变量、n 个约束。用 Commons Math 验证时对偶目标函数系数是 b 数组第 j 个约束的系数向量是 A 第 j 列右端项是 c[j]。把对偶问题求出来最优值应该和原问题最优值相等。我常把这个验证写进课程设计的测试代码里面试时提到“我用对偶问题验证过手写求解器”比单纯说“我跑通了案例”有说服力得多。6.2 用同一组随机用例对比两个实现另一个可复现的验证方式是随机生成模型随机生成非负 A、非负 b、随机 c保证 b ≥ 0然后分别用手写 Simplex 和 Commons Math 求解对比最优值。我一般跑几百组规模在 10 变量、10 约束的小用例绝对误差允许放 1e-6 以内。只要出现一例误差超标先检查手写版本的 EPS 和退出条件再检查是不是目标函数行符号写反了。这个习惯帮我避免了很多“看起来能跑但答案不对”的翻车现场。最后说一个我自己的习惯手写版只作为学习和面试的储备正式代码一定把求解器封装成一个接口比如LinearSolver这样以后想换 OR-Tools 或者加整数规划能力业务代码不用动。希望这份从标准形到避坑的路线能帮你在 Java 里把线性规划真正跑起来。本文还有配套的精品资源点击获取 Java线性规划实现指南：从手写单纯形法到Commons Math接库
简介这是一份线性规划算法实现的Java版学习资源面向需要掌握运筹学基础算法、希望在Java中落地求解器的开发者或学生。资源讲解线性规划模型构成、标准化处理、人工变量与两阶段法等内容并给出LP类与Main类的控制台交互实现可帮助读者理解从问题建模到代码求解的完整链路。压缩包共11个文件主体为2个Java源码及对应class文件另有5个XML配置、项目模块文件及版本管理文件整体仅13KB结构简洁适合直接阅读和二次修改。代码中涉及二维数组、ArrayList等常见数据结构适合分析算法流程或扩展为交互式求解器。已有3477人学习下载适合作为运筹学课程设计、算法学习或期末作业的参考。1. 线性规划在 Java 里落地自己手写还是直接接库“线性规划算法实现——Java版”这个标题翻译成实际需求通常是这样一句话我要在 Java 进程内把一个线性规划模型算成最优解。可能是课程设计里的资源分配可能是调度系统里要嵌入的生产排产也可能是面试八股里最容易被追问的那句“单纯形法你手写过吗”。它的下限是把教材里的单纯形法写成能跑的类上限是搞清楚 EPS、退化和对偶验证这些只有跑起来才会撞到的问题。下文按“先手写、再接库、再避坑”的顺序把一条能在本地跑通的路线讲清楚。适合三类人要交 Java 课程设计的学生、在系统里接 LP 求解的后端工程师、以及面试前想把手写版本练熟的人。2. 手写单纯形法标准形、选主元与一段能跑的 Java 代码2.1 先把问题收拾成标准形max 与 Ax ≤ b 的约定要手写单纯形法第一步不是写代码而是把任意线性规划问题统一成标准形。我一般约定目标函数求最大约束全是小于等于右端项 b 全部非负。用数学语言写就是max c^T xs.t. A x ≤ bx ≥ 0。为什么只用这种形态因为这种形态天然有一个初始基可行解每个小于等于约束各加一个松弛变量松弛变量就是初始基变量原始变量全部取 0基变量直接等于 b。只要 b ≥ 0第一个可行解不用算就白拿。很多教材把这一步叫“引入松弛变量”实操里它就是给每一行约束多开一列系数为 1。如果你的问题是 min直接把目标系数取相反数转成 max如果约束是 ≥两边乘 -1 后转成 ≤。但这里有个很容易踩的边界乘 -1 之后 b 可能变成负数而上面的标准形要求 b ≥ 0。一旦出现负 b单纯靠松弛变量凑不出初始可行解就需要人工变量和两阶段法。所以第二章这段代码只接受 b ≥ 0 的 Ax ≤ b 模型工程里遇到更复杂的形态优先走第三章的库。2.2 单纯形表选主元的循环逻辑两个判定一个旋转手写单纯形法的核心不是求逆矩阵而是维护一张 m1 行、nm1 列的单纯形表。行 0 是目标函数行行 1 到 m 是约束行列从 0 到 n-1 是原始变量n 到 nm-1 是松弛变量最后一列是右端项。外加一个 int[] basis记录每一行当前的基变量列号。每一轮迭代做三件事进基判定在目标函数行里找一个系数小于 -EPS 的列。这个列对应的非基变量每增加 1 单位目标函数有机会提升所以把它选为进基变量。选最小下标是为了避免后面遇到的退化循环这就是 Bland 规则的入门版。离基判定对进基列中系数大于 EPS 的每一行用右端项除以该系数得到比值选比值最小的那一行该行当前的基变量离基。这一步保证右端项始终非负也就维持了可行性。如果所有系数都不大于 0说明目标函数可以无限增大模型无界直接返回。旋转操作把主元行做主元归一化再用这一行消去其余所有行包括目标函数行。本质就是高斯消元把进基变量变成新基变量。循环直到目标函数行里找不到负系数为止。此时当前基可行解就是最优解右端项列对应原始变量的值就是最优解目标函数行最后一列的相反数是最优值。注意是相反数因为我把目标函数行初始化为 -c而不是 c这是为了消元符号统一。2.3 最小可运行代码与测试用例下面这个 Simplex 类只处理标准形代码可以直接复制到本地跑。它包含目标函数行初始化、进基判定、离基判定和 pivot 四部分没有额外依赖适合课程设计和面试手写题。import java.util.Arrays; /** * 手写单纯形法仅支持标准形 * max c^T x, s.t. A x b, x 0, b 0 */ public class Simplex { private static final double EPS 1e-9; private final double[][] table; private final int rows; private final int cols; private final int[] basis; public Simplex(double[][] A, double[] b, double[] c) { rows b.length; cols c.length rows; basis new int[rows]; table new double[rows 1][cols 1]; // 目标函数行初始化为 -c最终结果的相反数才是最优值 for (int j 0; j c.length; j) { table[0][j] -c[j]; } for (int i 0; i rows; i) { System.arraycopy(A[i], 0, table[i 1], 0, A[i].length); table[i 1][c.length i] 1.0; // 松弛变量 table[i 1][cols] b[i]; basis[i] c.length i; } } /** * 求解结果写入 solution 数组返回最优值。 * 模型无界时返回 Double.POSITIVE_INFINITY。 */ public double solve(double[] solution) { while (true) { int enter findEnteringColumn(); if (enter 0) break; int leave findLeavingRow(enter); if (leave 0) return Double.POSITIVE_INFINITY; pivot(leave, enter); } Arrays.fill(solution, 0.0); for (int i 0; i rows; i) { if (basis[i] solution.length) { solution[basis[i]] table[i 1][cols]; } } return -table[0][cols]; } // 进基选目标函数行最小下标的负系数列 private int findEnteringColumn() { for (int j 0; j cols; j) { if (table[0][j] -EPS) return j; } return -1; } // 离基最小比值原则比值并列时选基变量列号更小的行 private int findLeavingRow(int enterCol) { int leave -1; double minRatio Double.MAX_VALUE; for (int i 1; i rows; i) { double coefficient table[i][enterCol]; if (coefficient EPS) { double ratio table[i][cols] / coefficient; boolean smaller ratio minRatio - 1e-12; boolean tied Math.abs(ratio - minRatio) 1e-12 leave 0 basis[i - 1] basis[leave]; if (smaller || tied) { minRatio ratio; leave i - 1; } } } return leave; } // 旋转归一化主元行再消去其他所有行 private void pivot(int row, int col) { double pivotValue table[row 1][col]; for (int j 0; j cols; j) { table[row 1][j] / pivotValue; } for (int i 0; i rows; i) { if (i row 1) continue; double factor table[i][col]; for (int j 0; j cols; j) { table[i][j] - factor * table[row 1][j]; } } basis[row] col; } }对应的测试用例用经典的生产排产模型变量 x1、x2 是两种产品产量目标函数 3x1 2x2三条资源约束分别是 2x1 x2 ≤ 18、2x1 3x2 ≤ 42、3x1 x2 ≤ 24。手算最优解是 x13x212最优值 33。public class Main { public static void main(String[] args) { double[][] A { {2.0, 1.0}, {2.0, 3.0}, {3.0, 1.0} }; double[] b {18.0, 42.0, 24.0}; double[] c {3.0, 2.0}; Simplex simplex new Simplex(A, b, c); double[] x new double[2]; double value simplex.solve(x); System.out.printf(最优解: x1 %.6f, x2 %.6f%n, x[0], x[1]); System.out.printf(最优值: %.6f%n, value); } }这里的三个参数值得说明A 的每一行是一条约束的系数b 是对应右端项c 是目标函数系数。EPS 设置成 1e-9 是我常用的值如果模型系数本身很大比如上万可以适当放大到 1e-7否则小噪声会把选主元带偏。solve 方法返回的是最优值最优解写入传入的 x 数组无界时返回正无穷。这个版本不判断无解因为 b ≥ 0 且约束全是 ≤ 时x0 天然可行不存在无解一说。3. 用 Apache Commons Math 接库SimplexSolver 最小集成与模型构造3.1 为什么工程里我建议先接库而不是继续打磨手写版手写单纯形法有两个现实瓶颈。第一它只覆盖了标准形真实系统里经常出现 ≥ 约束、等式约束、负 b、混合整数变量这些都要额外实现两阶段法或分支定界代码量翻倍。第二单纯形法本质上对数值精度敏感教材例子系数都是整数工程里的系数可能来自浮点运算会出现退化、循环、接近零的主元需要花大量时间调 EPS。所以我的习惯是课程设计和面试用第二章的手写版本但凡是给真实业务做模块直接用 Apache Commons Math。它是 Java 生态里最出名的数学库自带 SimplexSolver底层是两阶段单纯形法支持 Relationship.LEQ、GEQ、EQ也支持等式约束和变量非负约束。它不用我维护表格和选主元只要把目标函数和约束描述清楚求解器自己处理初始可行解的问题。这不代表手写版本白费功夫。恰恰相反知道标准形、松弛变量、选主元、无界判定这些概念才能理解库返回的结果为什么长这样也知道某些场景该用什么关系约束。3.2 SimplexSolver 最小集成代码、Maven 依赖与运行结果Maven 项目里加入 commons-math3 依赖。如果你用 Gradle对应改一下依赖坐标即可。dependency groupIdorg.apache.commons/groupId artifactIdcommons-math3/artifactId version3.6.1/version /dependency下面这段代码和第二章的测试用例是同一个模型只是交给库去解import org.apache.commons.math3.optim.PointValuePair; import org.apache.commons.math3.optim.linear.*; import org.apache.commons.math3.optim.nonlinear.scalar.GoalType; import java.util.ArrayList; import java.util.Collection; public class ApacheSimplexExample { public static void main(String[] args) { // 目标函数: max 3*x1 2*x2 LinearObjectiveFunction f new LinearObjectiveFunction(new double[]{3.0, 2.0}, 0.0); CollectionLinearConstraint constraints new ArrayList(); constraints.add(new LinearConstraint( new double[]{2.0, 1.0}, Relationship.LEQ, 18.0)); constraints.add(new LinearConstraint( new double[]{2.0, 3.0}, Relationship.LEQ, 42.0)); constraints.add(new LinearConstraint( new double[]{3.0, 1.0}, Relationship.LEQ, 24.0)); SimplexSolver solver new SimplexSolver(); PointValuePair solution solver.optimize( f, constraints, GoalType.MAXIMIZE, new NonNegativeConstraint(true)); double[] point solution.getPoint(); System.out.printf(最优解: x1 %.6f, x2 %.6f%n, point[0], point[1]); System.out.printf(最优值: %.6f%n, solution.getValue()); } }逻辑说明LinearObjectiveFunction 的第一个参数是目标函数系数数组第二个参数是常数项偏移量一般填 0。LinearConstraint 的三个参数分别是约束系数向量、关系枚举和右端项。solver.optimize 接收四个 OptimizationData目标函数、约束集合、目标方向和变量非负约束。NonNegativeConstraint(true) 表示所有变量 ≥ 0这一步在工程里非常容易被漏掉。Commons Math 内部对变量有限制不加这个约束时某些模型可能返回无界或者异常结果后面避坑章节会展开。3.3 模型构造的两条硬规则目标方向与变量非负用 Commons Math 构造线性规划模型时我给自己定了两条硬规则。第一条目标方向直接用 GoalType.MAXIMIZE 或 GoalType.MINIMIZE不要在建模时手工翻转系数。很多人习惯把所有问题都转成 max把 min 的目标系数取反这其实没必要库原生支持最小化。手工翻转反而容易在验证结果时把自己绕晕。第二条变量非负约束必须显式声明。有些教学范例不写 NonNegativeConstraint因为库有这个默认行为但不同版本默认不一致写成显式参数最安全。另外约束关系不要滥用。LEQ 是小于等于GEQ 是大于等于EQ 是等式。等式约束在工程里很常见比如“总工时恰好等于 1000”Commons Math 支持 EQ但这会引入人工变量求解效率略低不是 bug。如果你的模型里有大量等式先检查是不是业务上本就是不等式别顺手写成等式给自己增加计算量。4. 参数与结果解读EPS、迭代上限、影子价格和大规模边界4.1 三个必调参数EPS、最大迭代次数和精度手写版本的 EPS 是我第一个调的参数。EPS 太小比如 1e-12会把浮点噪声当成有效系数进基和离基判断变得敏感EPS 太大比如 1e-5又可能把真正的主元漏掉导致提前收敛到非最优解。我一般以模型系数量级为参照系数都在百以内用 1e-9系数上到万用 1e-7。这个值不是玄学它本质上是“多小的数可以视为零”的阈值。Commons Math 的 SimplexSolver 也允许传入 MaxIterations控制最大迭代次数。虽然大多数问题几十次迭代就收敛但退化模型可能出现极长的迭代。我给课程设计里的代码通常显式传入一个 10000 的上限避免某个边界用例卡到怀疑人生。上限不是越大越好设置一个明确上限反而能在问题异常时快速暴露。第三个参数是精度。单纯形法内部全程用 double结果天然有浮点误差。如果业务对金额敏感不要直接用 double 做最终结算正确做法是用求解器算出最优解结构再拿 BigDecimal 重新核算一次目标值和约束余量除非你的模型和业务都允许千分位误差。4.2 最优表里还能读出什么影子价格与原问题验证只拿最优解是浪费。单纯形法的最优表里还藏着每个约束的影子价格也就是“这个资源再多一单位目标函数能增加多少”。在看代码之前先记住结论在目标函数行里松弛变量所在列的系数取相反数就是对应约束的影子价格。用第二章的例子三条约束分别对应三个松弛变量。最优解时前两条约束刚好卡满影子价格大于 0第三条约束松弛了一部分影子价格近似 0。你可以把第一条约束右端项从 18 改成 19重新求解会发现最优值增量正好等于那个影子价格。这个小实验是验证手写代码是否正确的最好方式也是面试时和面试官聊对偶价格的切入点。基于同样的原理我经常用约束余量来排查模型问题。如果某个本来就该稀缺的资源求解出来的松弛变量特别大说明约束系数或者右端项写错了。不要只看最优值把松弛变量打出来看看能省很多 debug 时间。4.3 什么时候别用单纯形法大规模稀疏场景的边界手写版本和 Commons Math 的 SimplexSolver 都是稠密实现底层用一个二维数组装整张表。变量数和约束数都在几百以内跑得很舒服一旦变量数上到几千、约束数上到几千内存和耗时就都不对劲了。原因是单纯形表里大量系数本来就是 0稠密存储把这些零全存成了 double空间浪费严重。遇到这种情况别再纠结手写直接换专业线性规划工具。Java 生态里常见的做法是接入 OR-Tools 的 linear_solver 模块底层是 GLOP 或 SCIP能处理稀疏矩阵也支持整数规划。Commons Math 在这个场景下只适合当教学和原型工具。明白这个边界至少能告诉面试官“我知道单纯形法不是银弹”。5. 避坑退化死循环、负右端项和整数场景的 5 个典型现场5.1 手写版本对某些输入卡死退化与 Bland 规则现象同一个模型手写单纯形法偶尔会陷入无限循环CPU 占用拉满但程序不退出。原因模型存在退化多个基可行解对应同一个顶点选主元规则不当会让基变量组合反复横跳。解决在进基和离基判定里都绑定最小下标规则。第二章代码里的 findEnteringColumn 从第 0 列开始找离基比值相同时选基变量列号更小的行这就是 Bland 规则的一种实现。只要坚持这个规则理论上可以避免退化循环。如果你手写版本还没加这个规则这是高优先级的后悔药。5.2 负右端项让模型失去初始可行解两阶段法的取舍现象把 约束两边乘 -1 后b 变成负数手写代码直接给出错误结果甚至返回无界。原因标准形要求 b ≥ 0负 b 意味着 x0 不再可行松弛变量不能直接当基变量。解决要么把负 b 的行再处理一遍通过变量替换变成正 b要么实现两阶段法先引入人工变量求一个初始可行解。我的建议是课程设计里没必要重复造轮子直接上 Commons Math 处理 GEQ 和 EQ省掉这一整块。5.3 Commons Math 返回 Infinity漏掉 NonNegativeConstraint现象一个看起来有界的问题用 SimplexSolver 求出来最优值是 Infinity或者抛出和“unbounded”相关的异常。原因没有加 NonNegativeConstraint(true)库允许变量取负值某些方向目标函数可以无限增大。解决加上 NonNegativeConstraint 后再跑。如果业务里确实存在自由变量要先把自由变量拆成两个非负变量的差比如 x u - vu, v ≥ 0再交给求解器。5.4 把 LP 小数解四舍五入当整数解整数场景的错误示范现象线性规划求出 x13.7顺手四舍五入成 4结果约束被破坏目标值也不对。原因线性规划的最优解可能落在非整数顶点四舍五入后的整数点甚至不在可行域里。解决如果变量必须取整数这是整数规划问题不是线性规划问题。正确做法是接整数规划求解器做分支定界或者用 OR-Tools 的 CP-SAT。线性规划在这类问题里只能用作松弛模型用来给分支定界提供上下界不能直接取整当最终答案。5.5 double[][] 把内存撑爆大规模患者的边界现象模型规模 5000 变量、5000 约束手写表格启动直接 OOM。原因稠密二维数组存了大约 1 亿个 double就算每个 8 字节也有近 800MB这还没算其他对象开销。解决换稀疏表示或者直接换支持稀疏矩阵的求解器。遇到这种规模别说是手写版本Commons Math 也会很吃力。工程上务实一点把 OR-Tools 之类的专业求解器作为选项你的 Java 代码只需要封装模型转换和结果解析。6. 进阶验证用对偶问题给手写求解器做正确性检查6.1 从原问题生成对偶模型手写求解器写完怎么证明它对我的习惯是构造对偶问题用同一个求解器去验证强对偶定理。对第二章的标准形模型对偶问题长这样min b^T ys.t. A^T y ≥ cy ≥ 0。也就是说原问题有 n 个变量、m 个约束对偶问题就有 m 个变量、n 个约束。用 Commons Math 验证时对偶目标函数系数是 b 数组第 j 个约束的系数向量是 A 第 j 列右端项是 c[j]。把对偶问题求出来最优值应该和原问题最优值相等。我常把这个验证写进课程设计的测试代码里面试时提到“我用对偶问题验证过手写求解器”比单纯说“我跑通了案例”有说服力得多。6.2 用同一组随机用例对比两个实现另一个可复现的验证方式是随机生成模型随机生成非负 A、非负 b、随机 c保证 b ≥ 0然后分别用手写 Simplex 和 Commons Math 求解对比最优值。我一般跑几百组规模在 10 变量、10 约束的小用例绝对误差允许放 1e-6 以内。只要出现一例误差超标先检查手写版本的 EPS 和退出条件再检查是不是目标函数行符号写反了。这个习惯帮我避免了很多“看起来能跑但答案不对”的翻车现场。最后说一个我自己的习惯手写版只作为学习和面试的储备正式代码一定把求解器封装成一个接口比如LinearSolver这样以后想换 OR-Tools 或者加整数规划能力业务代码不用动。希望这份从标准形到避坑的路线能帮你在 Java 里把线性规划真正跑起来。本文还有配套的精品资源点击获取