简介一套基于Java的线性规划算法实现资源面向运筹学入门者、算法学习者及需要完成相关课程设计的编程人员。资源包为RAR压缩格式共11个文件其中2个Java源码文件LP.java和Main.java构成主体分别实现LP类的标准化、人工变量添加与两阶段法求解以及控制台交互输入输出2个class文件为编译结果其余xml、iml、gitignore文件用于IntelliJ IDEA工程配置、模块识别与版本管理包体仅13KB便于直接导入运行。算法覆盖线性规划模型标准化、松弛变量与人工变量处理、两阶段法求最优解等关键环节用户可通过控制台输入目标函数系数及约束条件实时获得最优解。目前已有3478人学习或下载适合结合运筹学教材边看边调验证不同约束场景下的算法行为也可作为Java面向对象编程与数值计算结合的入门参考。1. 线性规划 Java 实现从教材表格到可运行的单纯形求解器线性规划是运筹学里最常被拿出来实战的模型生产排产、物流调运、投资组合本质上都能写成一组线性约束加一个线性目标。但很多人卡在“数学上会做、代码里跑不通”这一步——教材里的单纯形表画得清清楚楚落到 Java 代码里就全是数组越界和数值误差。这套 Java 版线性规划算法实现把从标准形转换、初始单纯形表构建到迭代求解、最优解提取的完整流程做成了一份可直接编译运行的工程代码不依赖任何第三方数学库JDK 8 环境就能跑。适合正在做课程设计或毕业设计的同学也适合需要在中小型业务系统里内嵌轻量求解器的开发者。新手能对照教材逐步理解每个数组的含义熟手可以直接改接口接入自己的数据。2. 标准形转换与算法选型单纯形法为什么适合轻量 Java 场景2.1 业务模型转标准形三类约束的统一处理任何 LP 问题目标函数可能是求最大或最小约束可能是小于等于、大于等于或等于。单纯形法只认标准形min cᵀx、Ax b、x ≥ 0。所以第一步不是写求解器而是写转换器这一步翻车的概率比迭代本身还高。常见做法是引入三类额外变量小于等于约束加一个松弛变量系数为 1大于等于约束减一个剩余变量系数为 -1同时为了凑出初始基再加一个人工变量等于约束直接加人工变量。人工变量只出现在两阶段法第一阶段或大 M 法的目标函数里它的存在是为了让初始基变量立刻可见。先看这套代码里的输入结构/** * 原始 LP 输入 * objective[] 目标函数系数 * constraints[] 约束矩阵每行一条约束 * rhs[] 右端常数 b * sense[] 约束方向-1 表示 1 表示 0 表示 * maximize 目标是否求最大 */ public class LpInput { public double[] objective; public double[][] constraints; public double[] rhs; public int[] sense; public boolean maximize; }然后是标准化与单纯形表的构建。表的结构是 m 行约束加一行检验数最后一列存右端常数人工变量列在进入一阶段前先按 0 系数放进目标行等一阶段开始再覆盖成临时目标/** * 构建初始单纯形表 [A | b] * 列顺序原始变量 - 松弛 - 剩余 - 人工 */ public static double[][] buildTableau(LpInput in) { int m in.constraints.length; int origN in.objective.length; int slack 0, surplus 0, artificial 0; for (int s : in.sense) { if (s -1) slack; // 加松弛 else if (s 1) { surplus; artificial; } // 减剩余、加人工 else artificial; // 加人工 } int n origN slack surplus artificial; double[][] tab new double[m 1][n 1]; int slackIdx origN, surplusIdx slackIdx slack, artIdx surplusIdx surplus; for (int i 0; i m; i) { System.arraycopy(in.constraints[i], 0, tab[i], 0, origN); if (in.sense[i] -1) tab[i][slackIdx] 1; else if (in.sense[i] 1) tab[i][surplusIdx] -1; if (in.sense[i] 0) tab[i][artIdx] 1; tab[i][n] in.rhs[i]; } // 目标行先填原始系数max 情形在外面取负 if (in.maximize) { for (int j 0; j origN; j) in.objective[j] -in.objective[j]; } System.arraycopy(in.objective, 0, tab[m], 0, origN); return tab; }两个参数值得特别注意。一是 surplusIdx 和 artIdx 的推进方向不同剩余变量列在松弛变量列之后人工变量列在最后顺序错了后面删列和提取解时全乱。二是这里把 in.objective 原地取负了是个副作用建议调用前先 clone 一份原始系数后面做二阶段恢复目标行时还要用到。注意标准形要求 b ≥ 0。如果某一行 rhs 为负先把整行乘以 -1 并把约束方向翻转否则初始基不可行第一阶段跑出来的结果没有意义。2.2 单纯形法 vs 内点法规模、精度与实现成本的一次算账选单纯形而不是内点法不是性能高低的问题而是工程成本的问题。内点法的核心是每次迭代解一个大型稀疏对称线性方程组需要 Cholesky 分解和共轭梯度法配合Java 里从零写一套稳定数值组件的工作量比单纯形大一个量级。单纯形法的本质是沿着可行域的顶点走每次迭代只做一次高斯消元代码量小、行为直观、方便调试而且对几百行约束以内的中小规模问题速度完全够用。维度单纯形法内点法核心运算枢轴消元一张表搞定稀疏 Cholesky依赖数值库适用规模几百行约束内稳定上千甚至上万约束更优数值精度迭代次数多但可控对病态矩阵敏感热启动支持改约束可继续迭代基本不支持实现成本几百行 Java 可跑需要大量数值组件如果你的业务数据规模到了上千约束且矩阵稀疏单纯形的每轮全表扫描会开始吃力这时候值得去评估成熟的优化库。但在课程设计和中小型业务系统里这套 Java 实现是性价比最高的选择。我一般接入前先看一眼约束矩阵的非零元比例非零元在 5% 以上说明稀疏性一般单纯形完全没问题如果非零元只有 1% 左右那才需要考虑换内点路线。3. 代码拆解单纯形表构建、迭代主循环与解提取3.1 求解器骨架与基变量索引单纯形表的行索引和列索引各有用处第 0 到 m-1 行是约束行第 m 行是检验数行第 0 到 n-1 列是变量第 n 列是右端常数。基变量索引数组 basis[i] 记录“第 i 行当前对应的基变量是哪一列”这个数组是提取解和实现 Bland 规则的关键。很多初次接触的同学会在 pivot 之后忘记更新它导致解全错。public class SimplexSolver { private double[][] tab; // 单纯形表tab[rows][cols] 是检验数行末位 private int[] basis; // basis[i] 第 i 行基变量的列号 private int rows, cols; private static final double EPS 1e-9; public SimplexSolver(double[][] tableau, int[] basis) { this.tab tableau; this.basis basis; this.rows tab.length - 1; this.cols tab[0].length - 1; } }初始化时松弛变量和人工变量对应的列天然构成单位矩阵的一部分所以 basis 可以按顺序填先填松弛变量的列号再填人工变量的列号。如果你用了某种“最右边补单位阵”的偷懒写法记得把 basis 与实际列位置对齐这一步错了后面全错。我给这段代码补一句提醒tab[rows][cols] 在最优解处的值含义是当前目标行右端常数符号规则和是否取负有关提取最优值时必须成对处理。3.2 主循环检验数、最小比值与枢轴运算主循环三个动作选入基变量、选出基变量、做枢轴消元。入基变量的标准是检验数小于 -EPS出基变量用最小比值原则只扫描入基列系数大于 EPS 的行避免除以零和接近零的数。public boolean solve() { while (true) { int enterCol chooseEntering(); if (enterCol -1) return true; // 所有检验数非负已达最优 int leaveRow chooseLeaving(enterCol); if (leaveRow -1) return false; // 入基列无非负系数无界解 pivot(leaveRow, enterCol); } } private int chooseEntering() { int col -1; for (int j 0; j cols; j) { if (tab[rows][j] -EPS) { // 检验数显著为负才考虑 if (col -1 || tab[rows][j] tab[rows][col]) col j; } } return col; } private int chooseLeaving(int enterCol) { int row -1; double minRatio Double.MAX_VALUE; for (int i 0; i rows; i) { if (tab[i][enterCol] EPS) { double ratio tab[i][cols] / tab[i][enterCol]; if (ratio minRatio) { minRatio ratio; row i; } } } return row; } private void pivot(int row, int col) { double pivotVal tab[row][col]; for (int j 0; j cols; j) tab[row][j] / pivotVal; for (int i 0; i rows; i) { if (i row) continue; double factor tab[i][col]; for (int j 0; j cols; j) { tab[i][j] - factor * tab[row][j]; } } basis[row] col; // 基变量更新别漏 }三处细节是调试时的重点第一个是 chooseEntering 里的 col -1 判断它处理了“第一列就是负数检验数”的情况。如果你把初始化写成 tab[rows][0]第一次与后续循环的行为就不一致结果会随机翻车。第二个是最小比值只扫入基列系数大于 EPS 的行。入基列系数为负或零的行比值没有几何意义硬除会得到错误出基目标甚至进入死循环。这个坑在约束里出现线性相关行时最容易触发。第三个是 pivot 里先归一化枢轴行再对其他行消元最后才更新 basis[row]。顺序不能反因为后面行消元时还要读当前行的系数basis 提前更新不会影响消元但会影响你对“当前基”的判断一旦中间打印调试就会看到错位信息。3.3 最优解提取与最优值符号迭代完成后基变量的值直接读右端常数列非基变量为 0。最优值的符号和标准化时是否对目标取负有直接关系求最大化时我们在前面把目标系数取了负所以回溯时要再取一次负。public double[] getSolution() { double[] x new double[cols]; for (int i 0; i rows; i) { if (basis[i] x.length) { x[basis[i]] tab[i][cols]; } } return x; } public double getOptimalValue() { return -tab[rows][cols]; // 因为求解的是 min cx }这里还有一个容易忽略的点basis[i] 可能指向人工变量列。如果某个基变量落在人工变量列上且取值为正说明原问题无可行解如果为 0说明约束有冗余。所以 getSolution 返回前最好把人工变量列对应的分量直接置 0避免业务侧把一个人工变量的残余值当成真实决策变量读走。我在接入业务数据时遇到过一次这种情况输出的“最优解”里混着一个永远不该出现的分量排查了半天才发现是人工变量列没清干净。4. 边界情况与数值稳定性退化、无界解与精度控制4.1 退化与 Bland 规则循环不死的保证退化是指存在某个基变量取值为 0此时最小比值会出现多个候选行并列。普通选取规则下连续几次枢轴运算后目标值可能不变极端情况下基变量组合绕一圈回到出发状态就是所谓的基循环。教材里说“理论上可能循环”工程上你就当它必然会发生尤其是约束里有冗余行的时候。Bland 规则的实现很便宜入基变量选满足检验数为负的最小下标出基变量在比值并列时选基变量列号最小的一行。把上一章的 chooseEntering 和 chooseLeaving 换成下面的版本即可private int chooseEnteringBland() { for (int j 0; j cols; j) { if (tab[rows][j] -EPS) return j; // 最小下标优先 } return -1; } private int chooseLeavingBland(int enterCol) { int row -1; double minRatio Double.MAX_VALUE; for (int i 0; i rows; i) { if (tab[i][enterCol] EPS) { double ratio tab[i][cols] / tab[i][enterCol]; if (ratio minRatio - EPS) { minRatio ratio; row i; } else if (Math.abs(ratio - minRatio) EPS) { if (row -1 || basis[i] basis[row]) { row i; // 并列时选基变量列号小的 } } } } return row; }注意这里的比值比较用了 minRatio - EPS 的容差并列判断用 Math.abs(ratio - minRatio) EPS。如果你直接写 ratio minRatio浮点运算下两个“理论上相等”的比值很可能不相等Bland 规则就名存实亡。另一方面Bland 规则会让迭代次数略微增加交换的是确定性——同一个输入无论跑多少次结果和中间路径完全一致这对自动化回归测试非常重要。4.2 无界解与无可行解的判定无界解的特征很直观某个入基变量的检验数为负但该列所有系数都不大于 EPS即没有任何约束能限制它增长。此时 chooseLeaving 返回 -1solve 返回 false。这个分支必须在主循环里单独处理否则就是死循环。无可行解需要两阶段法配合第一阶段把人工变量之和作为临时目标求最小值。如果一阶段最优值大于 EPS说明存在无法消除的人工变量原问题无可行解。注意是“大于 EPS”而不是“不为 0”因为浮点误差下理论为 0 的值可能算出 1e-12。public boolean phaseOne(double[][] tab, int m, int n, int artStart) { // 临时目标行人工变量系数 1其余 0 for (int j 0; j n; j) tab[m][j] 0; for (int j artStart; j n; j) tab[m][j] 1; // 基变量在目标行里的系数要消成 0否则检验数行不标准 for (int i 0; i m; i) { if (basis[i] artStart) { for (int j 0; j n; j) tab[m][j] - tab[i][j]; } } boolean ok solve(); // 复用主循环 return ok tab[m][n] EPS; // 人工变量之和接近 0 才可行 }一阶段结束后把人工变量列从表里删掉换回原目标函数同时清理基变量中的人工列再跑一次 solve 得到原问题的解。这个“二次求解”的流程是实现里最容易漏的一步很多翻车现场就是只跑了一次 solve 就把结果交出去了。完整驱动流程大致是这样public LpResult run(LpInput in) { double[][] tab buildTableau(in); int artStart computeArtStart(in); // 人工变量起始列 if (!phaseOne(tab, rows, tab[0].length - 1, artStart)) { return LpResult.infeasible(); } tab dropArtificialColumns(tab, artStart); // 删人工列 restoreObjective(tab, in); // 恢复原目标行 if (!solve()) return LpResult.unbounded(); return LpResult.of(getSolution(), getOptimalValue()); }dropArtificialColumns 之后原来的人工列全部消失基变量里凡是列号大于等于 artStart 的引用也要一并处理否则 getSolution 会数组越界。提示一阶段结束后恢复原目标行这一步必须用最初 clone 出来的系数而不是 buildTableau 里被取负后的数组。取负只该发生一次。4.3 EPSILON 取值与矩阵缩放的实践EPS 取 1e-9 是我在多数双精度场景下的默认值。检验数在 -1e-10 和 1e-10 之间震荡时1e-9 能稳定收敛但如果你把问题数据整体放大到 1e8 量级这个阈值就会误判。常见做法是先对约束矩阵做行归一化每一行除以该行最大绝对值让所有系数落在 -1 到 1 之间再做单纯形。这样顺带解决了病态矩阵的问题。我一般会额外输出每次迭代的检验数行和基变量列表到一个日志文件。数值问题最怕黑匣子把中间过程打出来后是精度问题还是逻辑问题一眼就能分清。这个习惯在调试退化案例时救过我很多次日志里看到基变量序列开始重复就立刻知道该上 Bland 规则了。5. 避坑指南Java 线性规划实现的五个典型翻车现场下面五条是我在拆解这套实现、拿它跑业务数据时实际踩过的坑按出现频率排序。每条按现象、原因、解决三段写可以直接对照自己的日志排查。5.1 现象结果总是差一点点说不出哪里错现象算出来的最优值比教材答案差 1e-6 上下解向量看起来合理但就是差一口气。原因最常见的两个源头。一是最大化问题在 buildTableau 里对目标系数取了负但 getOptimalValue 里忘了再取负二是检验数判断写成 tab[rows][j] 0浮点误差下某些边际变量的检验数在 -1e-12 附近震荡被错误地当成入基候选多迭代了一轮。解决先把目标符号的两处取负核对成对再把所有检验数判断统一改成 -EPS。最有效的排查手段是把初始单纯形表原样打印出来手算一轮检验数符号对不对一目了然。5.2 现象迭代上千轮不收敛目标值长期不动现象日志里目标值连续几百轮都一样轮数还在涨明显在绕圈。原因退化。约束矩阵里有成比例的冗余行或者某个基变量恒为 0导致最小比值出现并列普通选取规则反复把同一个变量换进换出。解决把入基出基函数换成 Bland 版本并在 solve 主循环里加迭代上限。我一般设 100 * (rows cols)超限直接抛异常把单纯形表 dump 出来看基变量序列是否重复。这个问题在小例子上可能永远不出现一旦数据规模上来就找你算账所以要提前兜底。5.3 现象系数跨几个数量级输出毫无常识现象目标系数在 1e6 量级约束系数在 1e-3 量级解出来本该是整数的变量出现诡异小数。原因矩阵病态。高斯消元过程中大数行把小数行的有效数字挤掉了EPS 阈值在这种尺度下也失去意义。解决进求解器之前先做行归一化每行除以该行的最大绝对值让系数落到 [-1, 1]同时记录缩放因子提取解时乘回去。几十行的小问题还可以用 BigDecimal 兜底但性能会掉一个数量级以上只适合当后悔药不适合当常规解法。5.4 现象约束顺序一换最优解跟着变现象同一组约束行顺序调整后目标函数值一样但最优解的分量明显不同。原因单纯形法收敛到哪个顶点取决于入基出基的选序。多个顶点同时最优时顺序不同就走不同的路径这不是算法错误但很容易让同事误判成代码有 bug。解决固定输入顺序或者直接启用 Bland 规则保证完全确定性。我习惯在回归测试里断言弱形式——比较目标值相等即可不要比较解向量逐元素相等否则测试会因为合法差异而变红。5.5 现象样例全过接真实数据就报无界或无可行解现象自己构造的三个例子都正常换成业务输入后一会儿报无界一会儿报无可行解数据看起来并没什么异常。原因十有八九是测试数据只覆盖了小于等于约束业务数据里混着大于等于和等于约束走了人工变量分支还有个隐蔽来源是 rhs 里有负数标准形要求 b ≥ 0负数行没有预处理直接进表。解决给三类约束各写一个用例再专门写一个 rhs 为负的用例。buildTableau 之前统一做一次行预处理rhs 0 时整行乘以 -1 并翻转约束方向。这一步在我接入每份新数据时都会强制检查已经成了肌肉记忆。注意如果五个坑都排查完仍然异常检查你用的 JDK 版本。旧版本里 StrictMath 和 Math 的默认实现差异会导致最后一位小数不同换 JDK 8 以上的默认 Math 实现即可。6. 进阶大 M 法的 M 值玄学与一套双重验证手法6.1 大 M 法的 M 值一个参数引发的数值玄学大 M 法把人工变量以权重 M 放进目标函数省去两阶段但 M 的大小直接决定数值稳定性。M 太大会压掉真实目标系数消元时出现大数吃小数M 太小又可能让人工变量留在最优基里解出来带着人工变量的残余值。常见做法是取目标函数最大绝对值的 100 倍左右同时保证 M 大于所有约束右端项之和。如果你发现每个问题都要手调 M说明两阶段法才是正解——它把 M 的选择完全消除了代价只是多跑一次单纯形。工程上我优先用两阶段只有验证教材例题时才顺手用大 M 法比对。6.2 双重验证教材例题加顶点枚举基准拿到这套代码后我建议先跑三组验证。第一组是教材例题覆盖退化和人工变量分支第二组是自己构造的 2 变量小问题用顶点枚举法暴力求解——把所有约束两两求交、检查交点是否落在可行域内、再比较目标值这份结果不依赖任何 LP 算法是天然的基准第三组是随机生成 50 个线性无关的小问题跑完和枚举结果比对只要有一组对不上就打印单纯形表定位。javac -encoding UTF-8 src/**/*.java java -cp src org.example.lp.Main如果你正好需要一份能直接编译运行的线性规划 Java 实现这份代码的入口类和测试用例都是现成的拿到手先跑一遍内置用例再替换成自己的业务数据。从那以后我每次接入新的 LP 数据都强制走一遍“行归一化 - 两阶段法 - Bland 规则 - 枚举比对”这四步前两步保证数值和行为正确后两步保证确定性和可回归。这套流程看着繁琐但能挡住绝大部分翻车希望帮到你。本文还有配套的精品资源点击获取