简介一套面向运筹学与Java学习者的线性规划算法实现代码包解决在Java环境下建立线性规划模型、执行标准化并利用两阶段法求最优解的问题适合运筹学课程实践、算法学习或小型决策支持工具开发参考。资源共11个文件以Java源码和编译后的class文件为主体辅以IDEA项目配置xml、iml与Git忽略文件整体仅13KB轻量且可直接导入开发环境运行调试。已有3477人学习下载。代码中LP类封装了standardize、addArtificialVariables、twoStageMethod与solve等核心方法涵盖目标函数、约束条件、非负变量转换及人工变量两阶段求解的完整逻辑Main类借助Scanner在控制台接受用户输入的目标函数系数与约束参数直观演示了从模型录入到最优解输出的全流程。此外还包含人工变量处理、边界情况测试等细节可帮助读者将运筹学理论落地为可运行的Java程序也为进一步扩展单纯形法或性能优化提供了清晰的基础。1. 线性规划算法实现的Java版一份能直接改的求解器底子这次拆的是线性规划的 Java 算法实现源码包覆盖了单纯形法主体、两阶段法扩展、几组标准算例和一份简短的实现说明。先说结论线性规划最容易翻车的不是算法本身而是输入数据的组织、约束符号的处理和浮点精度这三个位置。这个资源正好把模型定义、求解器、测试用例拆成了清晰的三个层次适合正在做运筹学课程设计、刚学 Java 想找算法练手或者工作中突然要写一个排产/分配工具的人。拿到手之后不建议先读算法核心建议先跑它自带的一个算例再跟着模型类读代码。2. 建模先行约束矩阵与目标函数在 Java 里的三种组织方式2.1 从数学符号到字段变量、约束、目标函数怎么落成类单纯形法不关心业务含义只认标准形。任何线性规划问题到最后都会被拆成目标函数系数、约束矩阵、右端项和约束符号四样东西。资源里最值得先抄的就是这个LinearProgram模型类它把所有求解器要用的信息一次性封装好。public class LinearProgram { // 目标函数系数下标从 0 开始长度为 n private final double[] c; // 约束矩阵 Am 行 n 列a[i][j] 表示第 i 条约束中第 j 个变量的系数 private final double[][] a; // 约束右端项 b长度为 m private final double[] b; // 约束符号-1 表示 0 表示 1 表示 private final int[] sense; // 求解状态0 未求解1 找到最优2 无界3 无可行解 private int solveStatus; // 最优解向量长度为 n private double[] solution; public LinearProgram(double[] c, double[][] a, double[] b, int[] sense) { this.c c; this.a a; this.b b; this.sense sense; this.solveStatus 0; } }这套字段设计和数学标准形是一一对应的。sense数组是整个模型里最容易写错的地方它用 -1/0/1 三个整数表达不等号方向比直接用字符串{省内存也比布尔值isLessEqual更灵活因为等号约束需要单独占一个状态。这里的n是原始变量个数也就是业务里真正要决策的量比如生产计划里的产品数量m是约束条数。后续单纯形法构建增广矩阵时n和m共同决定初始矩阵的列数。2.2 输入数据组织为什么推荐用数组而不是字符串表达式常见做法是直接在调用方把数组构造好但更利于批量测试的是从一个简单文本文件加载。资源里给了一套固定格式第一行是变量数n和约束数m第二行是目标函数系数后面每一行是一条约束的系数、右端项、符号。这样设计是为了让测试用例能独立成文本文件每次改需求不用重新编译。public static LinearProgram loadFromFile(String path) throws IOException { try (BufferedReader br new BufferedReader(new FileReader(path))) { String[] nm br.readLine().trim().split(\\s); int n Integer.parseInt(nm[0]); int m Integer.parseInt(nm[1]); double[] c new double[n]; double[][] a new double[m][n]; double[] b new double[m]; int[] sense new int[m]; String[] cLine br.readLine().trim().split(\\s); for (int j 0; j n; j) { c[j] Double.parseDouble(cLine[j]); } for (int i 0; i m; i) { String[] parts br.readLine().trim().split(\\s); for (int j 0; j n; j) { a[i][j] Double.parseDouble(parts[j]); } b[i] Double.parseDouble(parts[n]); sense[i] Integer.parseInt(parts[n 1]); } return new LinearProgram(c, a, b, sense); } }注意这里把右端项放在第n个位置、符号放在第n1个位置是因为一行约束的系数正好占前n个。解析完成后立刻构造模型对象而不是返回一个 Map 或 List这样后续所有方法都能直接复用模型里的字段。用空格分隔比 CSV 更省事缺点是不能在约束系数里带空格类的可读注释所以我一般会把说明性文字放在同名的.md文件里而不是混进数据文件。字符串表达式那种2*x1 x2 100的输入方式在教科书里很常见但表达式解析会引入大量字符串处理代码而且不好排查空格、括号带来的问题资源选择数组和文本文件是为了把注意力留在算法上。2.3 为什么变量个数和约束个数最好在建对象时校验一次拿到模型类之后我建议在构造函数里做一次维度校验。资源里的版本简化了一些实际使用时a.length应该等于b.lengtha[i].length应该等于c.length这些不一致会在后续构建单纯形表时直接造成数组越界。public LinearProgram(double[] c, double[][] a, double[] b, int[] sense) { if (a.length ! b.length || a.length ! sense.length) { throw new IllegalArgumentException(约束矩阵行数与 b、sense 长度不一致); } for (int i 0; i a.length; i) { if (a[i].length ! c.length) { throw new IllegalArgumentException(第 i 行约束列数与变量数不一致); } } this.c c; this.a a; this.b b; this.sense sense; this.solveStatus 0; }这个校验是很多新手会跳过的步骤但恰恰是它能把“运行到一半数组越界”变成“构造时直接报错”。从排错成本看构造时发现问题的代价远低于求解迭代过程中发现问题。后面所有章节的代码都建立在这个模型类之上先把维度校验写好后面改数据格式、加人工变量时才不会到处找空指针。3. 单纯形法落地从标准形到主元迭代的完整代码路径3.1 标准形与松弛变量为什么每一行都要加一个单位列单纯形法要求在初始表里每个约束都对应一个基变量。对于型约束加一个系数为 1 的松弛变量就能直接作为初始基对于型约束需要加剩余变量但系数是 -1不能直接当基变量这正是第四章两阶段法的由来。资源先把只含约束的纯标准形跑通因此构建单纯形表时会为每个约束补一列松弛变量。private double[][] buildTableau() { int rows m 1; int cols n m 1; double[][] t new double[rows][cols]; // 目标函数行把 c 取负填入前 n 列 for (int j 0; j n; j) { t[0][j] -c[j]; } // 约束行系数填入 a松弛变量填对角线位置最右列放 b for (int i 0; i m; i) { for (int j 0; j n; j) { t[i 1][j] a[i][j]; } t[i 1][n i] 1.0; t[i 1][cols - 1] b[i]; } return t; }目标行取-c是因为单纯形法判断最优时看的是目标函数行的非负性。如果目标是最大化则目标行全部非负时达到最优如果是最小化则可以把最小化问题等价转换成最大化-c然后走同一套逻辑。松弛变量列放在n i位置正好形成一个从第n列开始的单位矩阵这样初始基就是松弛变量本身基变量取值等于b。最后边加一列右端项行数和列数在构造t时就固定下来后面所有操作都在这个二维数组里完成。3.2 进基与出基主元选择的两步判定每次迭代要决定哪个变量进基、哪个变量出基。进基变量的选择看目标函数行找最小负系数的列因为把它从 0 增大能最快改进目标函数值。出基变量看最小比值规则只在进基列系数为正的行里比右端项 / 系数比值最小的行先达到 0所以那一行的基变量出基。private int choosePivotColumn(double[] objRow) { int pivotCol -1; double minVal -1e-9; for (int j 0; j objRow.length - 1; j) { if (objRow[j] minVal) { minVal objRow[j]; pivotCol j; } } return pivotCol; } private int choosePivotRow(double[][] t, int pivotCol) { int pivotRow -1; double minRatio Double.MAX_VALUE; for (int i 1; i t.length; i) { double aij t[i][pivotCol]; if (aij 1e-9) { double ratio t[i][t[0].length - 1] / aij; if (ratio minRatio) { minRatio ratio; pivotRow i; } } } return pivotRow; }进基判断使用-1e-9而不是严格的 0是为了跳过那些因为浮点误差变成-1e-12的数值这类微小负值通常不是真正的进基候选。出基判断只取系数大于1e-9的行如果某列系数全都不大于这个阈值说明增加该变量不会让任何基变量降到 0问题就是无界的。最小比值规则保证迭代后所有基变量仍然非负这是单纯形法的几何意义所在每次都沿着可行域的边移动到一个更优的顶点。3.3 主元变换一行归一化、其余行消去选中主元行和主元列之后先让主元变成 1再用它消去其他行的同类列。private void pivot(double[][] t, int pivotRow, int pivotCol) { int rows t.length; int cols t[0].length; double pivotVal t[pivotRow][pivotCol]; for (int j 0; j cols; j) { t[pivotRow][j] / pivotVal; } for (int i 0; i rows; i) { if (i pivotRow) continue; double factor t[i][pivotCol]; if (Math.abs(factor) 1e-12) continue; for (int j 0; j cols; j) { t[i][j] - factor * t[pivotRow][j]; } } }这段代码的本质就是高斯消元。主元行除以主元值后主元位置变成 1其他行减去factor倍的主元行让它们在主元列的位置变成 0。跳过factor绝对值小于1e-12的行是纯性能优化那些行在主元列上本来就是 0消不掉也不需要消。注意这里没有记录基变量列表单纯形表的行顺序在迭代中保持不变基变量信息可以从表结构里反推每一行单位列所在的位置就是该行基变量的列索引。这个简化省去了索引数组的维护代价是提取解时多一步遍历。3.4 迭代循环、终止条件与解提取单纯形法的外层循环就是把选主元、换基、消元反复执行直到目标函数行没有负系数。为了防止退化导致的循环问题迭代次数要设一个上限。public boolean solve() { double[][] t buildTableau(); int maxIter 100 * (m n); for (int iter 0; iter maxIter; iter) { int pivotCol choosePivotColumn(t[0]); if (pivotCol 0) { solveStatus 1; extractSolution(t); return true; } int pivotRow choosePivotRow(t, pivotCol); if (pivotRow 0) { solveStatus 2; return false; } pivot(t, pivotRow, pivotCol); } solveStatus 2; return false; } private void extractSolution(double[][] t) { solution new double[n]; for (int j 0; j n; j) { int oneRow -1; boolean isUnit true; for (int i 1; i t.length; i) { double v t[i][j]; if (Math.abs(v) 1e-9) { if (oneRow ! -1) { isUnit false; break; } oneRow i; } } if (isUnit oneRow ! -1) { solution[j] t[oneRow][t[0].length - 1]; } else { solution[j] 0.0; } } }maxIter设成100 * (m n)的经验值是从血泪里总结出来的理论上单纯形法迭代次数不会超过组合数但退化情况下可能来回兜圈子设一个合理上限比无限循环好接受。extractSolution的逻辑是检查每个变量列是否恰好只有一个非零元素且这个非零元素是 1如果是则说明该变量的值就是那一行的右端项否则变量不在基里取 0。这种判断方式比维护基变量索引更稳因为它在数值扰动下仍能给出近似正确的解。4. 两阶段法扩展没有可行初始基时如何不被卡死4.1 什么场景必须用两阶段法纯标准形单纯形法要求所有约束都是且右端项非负。现实中更多问题是混合约束有有甚至右端项本身是负数。加剩余变量后系数为 -1在松弛变量矩阵里形成不了单位列约束一开始就没有松弛变量可用。下面是约束类型与补齐列的对应关系。约束类型需要补的变量初始基是否可用是否要人工变量松弛变量系数 1是否剩余变量系数 -1否是无否是两阶段法的思路就是面对无法直接形成单位矩阵的约束人为插入人工变量凑出一个单位矩阵先求一个辅助目标函数让所有人工变量归零如果人工变量归不了零说明原问题无可行解。这正是资源里solve()入口会先检查sense数组的原因。4.2 Phase I把目标函数临时换成人工变量之和Phase I 的做法是在每个需要人工变量的等式约束里插入人工变量把目标函数临时改成人工变量总和的最小化。在实现上构建初始单纯形表后要把目标函数行中所有基变量列的系数消成 0否则单纯形法会得出“人工变量已经是 0 但目标行还有负值”的错误结论。private double[][] buildPhaseOneTableau() { // 统计需要人工变量的约束数 int artificial 0; for (int i 0; i m; i) { if (sense[i] 0) { artificial; } } int rows m 1; int cols n m artificial 1; double[][] t new double[rows][cols]; // 目标行人工变量列系数设为 1其余为 0 for (int j n m; j n m artificial; j) { t[0][j] 1.0; } // 把基变量列消成 0保证迭代从可行基出发 for (int i 1; i rows; i) { for (int j 0; j cols; j) { if (t[i][j] 1.0) { double factor t[0][j]; for (int k 0; k cols; k) { t[0][k] - factor * t[i][k]; } } } } return t; }这里把人工变量列放在最后面方便在 Phase II 直接丢弃它们。完成“消基”处理后对这张表再跑一次第一章的单纯形迭代。如果最终目标行最小值大于容差说明无法把所有人工变量归零原问题无可行解如果归零就把当前单纯形表作为 Phase II 的初始表。4.3 Phase II换回原目标函数继续迭代Phase I 结束时单纯形表已经处于一个可行基状态但目标函数是辅助的需要替换成原问题目标函数行同时把人工变量列删除。替换后还要再次把当前基变量列消成 0因为目标行只要含有正的基变量系数就无法直接用于最优判定。private double[][] buildPhaseTwoTableau(double[][] phaseOneTable) { int artificialStart n m; int newCols artificialStart 1; double[][] t new double[m 1][newCols]; // 复制约束部分丢弃人工变量列 for (int i 1; i m; i) { System.arraycopy(phaseOneTable[i], 0, t[i], 0, newCols); } // 恢复原目标前 n 列填 -c其余 0 for (int j 0; j n; j) { t[0][j] -c[j]; } // 基变量列消 0 for (int i 1; i m; i) { int baseCol findBaseColumn(t, i); double factor t[0][baseCol]; if (Math.abs(factor) 1e-12) { for (int j 0; j newCols; j) { t[0][j] - factor * t[i][j]; } } } return t; }findBaseColumn可以在当前的约束行里找值为 1 且其余行该列为 0 的列也可以沿用 Phase I 记录的基变量索引显然后者更省事。Phase II 拿到这张表后再走一遍单纯形迭代出来的就是原问题的最优解。抖动的地方在于删除人工变量列时表格宽度变了所有索引都要重新对齐建议把新旧列数打印出来核对一遍。4.4 求解状态标志最优、无界、无可行解的返回约定资源把求解结果统一为几个整数状态码方便调用方通过getStatus()判断结果而不是靠异常来传播信息。状态码含义出现条件0未求解还没调用solve()1最优目标行无负系数且 Phase I 人工变量归零2无界进基列所有系数都小于等于 03无可行解Phase I 结束后人工变量和大于容差无界判断要放在主元选择里不能等循环结束才看。因为无界时迭代永远选不出主元行如果choosePivotRow返回 -1 后还用这个结果去pivot必然空指针。状态码方案配合前面的loadFromFile可以在测试脚本里一次性批量判断几十个算例是否正常这是后面验证章节的基础设施。5. 避坑笔记精度、退化与数据预处理里的五个坑5.1 纯循环算法反复进基出基跑到天荒地老现象单纯形法迭代次数远超正常范围程序长时间不退出甚至迭代到上限后输出NaN或乱码。原因退化情况下某些基变量取值为 0换基后目标函数值不增加。单纯形法退化为循环反复围绕同一个可行域顶点打转。纯理论里这个坑叫“循环”在实现里表现为无限迭代。解决资源里采用了 Bland 最小下标规则即进基时选最小负系数列、出基时选最小下标行而不是任选一个。这个规则虽然会让每次迭代的目标值改进更慢但严格保证了不会循环。我更建议有效果更快的做法在迭代循环里记录最近几次的目标函数值如果连续 3 次完全相同就切换到 Bland 规则。这样既保留 Dantzig 规则的速度又不会卡死。5.2 浮点精度最优解对不上手算结果现象求解结果和手算结果差距在1e-4量级比如本应取整的答案变成36.00000007回代验证时被判成违反约束。原因单纯形法每个主元变换都包含除法double运算会累积误差。迭代次数越多误差越大。这是所有数值算法的共性不是具体某行代码的问题。解决统一设置容差tol 1e-9所有判定逻辑用Math.abs(x) tol替代严格等于 0。提取解时如果某个分量与整数差值小于1e-6就直接四舍五入。切忌在每一处都手工调容差那样后面维护时会非常痛苦。把这个常量放在求解器内部一个静态字段里调试时只改一处。5.3 右端项为负初始基直接不可行现象读入数据时某行b[i] -50构建单纯形表后基变量为 -50迭代出来的“最优解”明显违反业务常识。原因标准形要求所有右端项非负单纯形法的所有比值判定都建立在b 0的前提上。教科书例题默认满足这个条件但真实数据经常出现负的右端项比如库存余额、现金流这类可能为负的业务量。解决在构建单纯形表之前做行变换如果b[i] 0把该行所有系数和右端项同时乘以 -1并把约束符号翻转。变变保持。这步必须和人工变量插入逻辑配合顺序颠倒了后面 Phase I 会多算甚至算错。5.4 冗余约束与线性相关行主元选择撞上除零现象约束矩阵里存在线性相关的行比如某一行刚好是另一行的两倍。运行时某个主元列出现两行比值完全相等消元后数值变得极其不稳定。原因预处理不充分。线性相关的约束虽然不改变可行域但会让单纯形表里的数值关系脆弱主元消元时分母极小放大浮点误差。解决在加载数据后增加一个冗余检查函数用高斯消元把约束矩阵化成行阶梯形统计有效行数。如果有效行少于m打印警告并把冗余行筛除后再构建模型。资源里的文本格式加载器没有自动筛除是需要使用者补的一环。我的习惯是写一个preprocess()方法在solve()入口调用统一完成负右端项翻转、冗余行删除两步。5.5 max 和 min 的符号混用最优解总感觉反着来现象求解结果与业务预期对不上明明是最大化利润算出来却是某个极小值或者目标函数值符号反了。原因单纯形法内部统一按最大化处理但调用方传入的目标函数可能是最小化。如果构建单纯形表时没有把min c^T x等价转换成max -c^T x目标行符号就会错。解决在LinearProgram里增加一个maximize布尔字段构造模型时就固定求解方向。solve()内部构建目标行时统一用maximize ? -c[i] : c[i]填入解出来后在输出层再反转目标函数值。最好在模型类的注释里写明“目标函数始终按业务方向存储单纯形表内部按最大化处理”这样读代码的人不会被正负号绕晕。6. 把结果变可信标准例题回归、随机压力与单纯形表调试6.1 标准例题回归先跑一组能查到答案的算例设计一个简单的生产排产算例结果可以手算验证。public static void main(String[] args) { double[] c {3.0, 2.0}; double[][] a { {2.0, 1.0}, {1.0, 3.0} }; double[] b {100.0, 120.0}; int[] sense {-1, -1}; LinearProgram lp new LinearProgram(c, a, b, sense); lp.solve(); double[] x lp.getSolution(); System.out.println(x1 x[0] , x2 x[1]); System.out.println(obj (3 * x[0] 2 * x[1])); }这个例子对应最大化3x1 2x2约束2x1 x2 100、x1 3x2 120两个变量非负。手算顶点可以验证最优解是x136、x228目标值164。第一次跑通这个例子后我对求解器核心的正确性就有了基本信任。之后每改一次代码先跑这个例子确认没有被改坏。6.2 随机压力与回代验证把解代回约束里才算数单靠一个标准例题只能证明“例子能跑通”不能证明“一般情况不会翻车”。随机生成约束矩阵并构造一个必然可行的解是更高性价比的验证手段。public static LinearProgram randomFeasible(int n, int m, Random rnd) { double[][] a new double[m][n]; double[] b new double[m]; double[] x new double[n]; for (int j 0; j n; j) { x[j] rnd.nextInt(5) 1; } for (int i 0; i m; i) { double sum 0; for (int j 0; j n; j) { a[i][j] rnd.nextInt(10) 1; sum a[i][j]; } b[i] sum rnd.nextInt(10); } int[] sense new int[m]; Arrays.fill(sense, -1); return new LinearProgram(new double[n], a, b, sense); }随机生成时先偷偷造一个x再让右端项大于等于A * x这样能保证至少存在一个可行解不会把问题变成无可行解方便专心检查最优性。求解后必须回代验证把解代回每个约束判断是否在容差范围内满足符号方向。这一步能顺手抓出“解向量维度对不上”和“约束符号翻转漏了一行”这两类问题。我在本地写了一个循环随机生成 500 个算例逐个检查状态码和回代结果跑完再手动看几个边界值。6.3 打印单纯形表调试肉眼比断点更快定位错误出现在迭代中后期时断点调试效率很低因为要反复跳进跳出。更实用的办法是在pivot方法里加一行可开关的打印把每次迭代后的表输出到控制台。private void logTableau(double[][] t, int iter) { if (!debugMode) return; System.out.println(--- iteration iter ---); for (int i 0; i t.length; i) { for (int j 0; j t[0].length; j) { System.out.printf(%8.2f , t[i][j]); } System.out.println(); } System.out.println(); }看表时只需要盯两个位置目标函数行还有没有负值右端项列有没有出现负值。目标行持续有负值但迭代卡在某一对行列之间基本就是主元选择逻辑的问题右端项出现负数说明上一步主元行选错了最小比值规则被破坏。这个打印方法培养出的读表习惯比任何 IDE 断点都耐用。从那以后我每次改约束加载或主元选择逻辑都强制走一遍标准例题回归加随机压力两关这个习惯帮我挡掉了不少低级翻车。希望帮到你。本文还有配套的精品资源点击获取