ojAlgo解决LP问题

使用 ojAlgo 求解线性规划（LP）问题

ojAlgo 是一个专注于数值计算和优化的 Java 开源库，提供了简洁直观的 API 来求解线性规划（LP）、整数规划（IP）等问题。相比其他工具，ojAlgo 的代码可读性强，配置灵活，特别适合在 Java 项目中集成。本文以具体示例介绍如何使用 ojAlgo 求解 LP 问题。

问题定义

我们需要求解以下整数线性规划问题（变量为整数）：
目标函数：minimize 5x₁ + 6x₂ + 23x₃ + 5x₄ + 24x₅ + 6x₆ + 23x₇ + 5x₈（最小化加权和）
约束条件：

2x₁ + x₂ + x₃ + x₄ ≥ 100
2x₂ + x₃ + 3x₅ + 2x₆ + x₇ ≥ 150
x₁ + x₃ + 3x₄ + 2x₆ + 3x₇ + 5x₈ ≥ 100
变量约束：所有变量为非负整数（xᵢ ≥ 0且为整数）

环境配置

引入 ojAlgo 依赖

在 Maven 项目的pom.xml中添加依赖：

<dependency>
    <groupId>org.ojalgo</groupId>
    <artifactId>ojalgo</artifactId>
    <version>51.4.1</version>
</dependency>

代码实现与解析

核心步骤

创建模型：初始化ExpressionsBasedModel（ojAlgo 的优化模型容器）。
定义变量：添加目标函数中的变量，指定类型（整数）、下界（非负）和权重（目标函数系数）。
定义约束：通过Expression对象添加约束条件（不等式）。
求解优化：调用minimise()方法求解最小值，获取结果。

完整代码

import org.ojalgo.optimisation.ExpressionsBasedModel;
import org.ojalgo.optimisation.Optimisation;
import org.ojalgo.optimisation.Variable;

public class LpWithOjAlgo {
    public static void main(String[] args) {
        // 1. 创建优化模型
        ExpressionsBasedModel model = new ExpressionsBasedModel();

        // 2. 定义变量（x₁到x₈，均为非负整数）
        // 变量格式：名称、类型（整数）、下界（0）、权重（目标函数系数）
        model.addVariable(Variable.makeInteger("x1").lower(0).weight(5));   // x₁，权重5
        model.addVariable(Variable.makeInteger("x2").lower(0).weight(6));   // x₂，权重6
        model.addVariable(Variable.makeInteger("x3").lower(0).weight(23));  // x₃，权重23
        model.addVariable(Variable.makeInteger("x4").lower(0).weight(5));   // x₄，权重5
        model.addVariable(Variable.makeInteger("x5").lower(0).weight(24));  // x₅，权重24
        model.addVariable(Variable.makeInteger("x6").lower(0).weight(6));   // x₆，权重6
        model.addVariable(Variable.makeInteger("x7").lower(0).weight(23));  // x₇，权重23
        model.addVariable(Variable.makeInteger("x8").lower(0).weight(5));   // x₈，权重5

        // 3. 添加约束条件

        // 约束1：2x₁ + x₂ + x₃ + x₄ ≥ 100
        Expression constraint1 = model.addExpression("constraint1");
        constraint1.set(0, 2);  // x₁的系数为2（变量索引从0开始，对应x₁）
        constraint1.set(1, 1);  // x₂的系数为1
        constraint1.set(2, 1);  // x₃的系数为1
        constraint1.set(3, 1);  // x₄的系数为1
        constraint1.lower(100); // 约束下界为100（≥100）

        // 约束2：2x₂ + x₃ + 3x₅ + 2x₆ + x₇ ≥ 150
        Expression constraint2 = model.addExpression("constraint2");
        constraint2.set(1, 2);  // x₂的系数为2
        constraint2.set(2, 1);  // x₃的系数为1
        constraint2.set(4, 3);  // x₅的系数为3
        constraint2.set(5, 2);  // x₆的系数为2
        constraint2.set(6, 1);  // x₇的系数为1
        constraint2.lower(150); // 约束下界为150

        // 约束3：x₁ + x₃ + 3x₄ + 2x₆ + 3x₇ + 5x₈ ≥ 100
        Expression constraint3 = model.addExpression("constraint3");
        constraint3.set(0, 1);  // x₁的系数为1
        constraint3.set(2, 1);  // x₃的系数为1
        constraint3.set(3, 3);  // x₄的系数为3
        constraint3.set(5, 2);  // x₆的系数为2
        constraint3.set(6, 3);  // x₇的系数为3
        constraint3.set(7, 5);  // x₈的系数为5
        constraint3.lower(100); // 约束下界为100

        // 4. 求解最小值
        Optimisation.Result result = model.minimise();

        // 5. 输出结果
        System.out.println("优化结果状态：" + result.getState()); // 应显示OPTIMAL（最优）
        System.out.println("目标函数最小值：" + result.getValue());
        System.out.println("变量最优解：");
        for (Variable var : model.getVariables()) {
            System.out.println(var.getName() + " = " + var.getValue());
        }
    }
}

结果解析

输出结果

优化结果状态：OPTIMAL
目标函数最小值：600.0
变量最优解：
x1 = 30.0
x2 = 40.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 35.0
x7 = 0.0
x8 = 0.0

结果验证

目标函数值：5×30 + 6×40 + 23×0 + 5×0 + 24×0 + 6×35 + 23×0 + 5×0 = 150 + 240 + 210 = 600。
约束满足性：
1. 约束 1：2×30 + 40 + 0 + 0 = 100（满足≥100）。
2. 约束 2：2×40 + 0 + 3×0 + 2×35 + 0 = 80 + 70 = 150（满足≥150）。
3. 约束 3：30 + 0 + 3×0 + 2×35 + 3×0 + 5×0 = 30 + 70 = 100（满足≥100）。

ojAlgo 的优势

可读性强：通过Variable和Expression类直观定义变量和约束，代码逻辑清晰。
类型灵活：支持整数变量（makeInteger()）、二进制变量（makeBinary()）和连续变量（默认），无需手动转换约束格式。
集成便捷：纯 Java 实现，无外部依赖，适合嵌入 Java 应用程序。
结果丰富：Result对象包含优化状态（是否最优）、目标值和变量解，便于后续处理。

总结

ojAlgo 为 Java 开发者提供了简洁高效的线性规划求解方案，通过面向对象的 API 简化了变量和约束的定义过程。对于整数规划、混合整数规划等问题，ojAlgo 同样能提供稳定的求解能力。相比 JOptimizer，ojAlgo 的代码可读性更强，更适合复杂约束场景的开发。在实际项目中，可根据问题规模和类型选择合适的优化库，ojAlgo 是中小型整数规划问题的理想选择