JOptimizer解决LP问题

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

JOptimizer 是一个 Java 优化库，支持线性规划（LP）、二次规划（QP）等多种优化问题的求解。本文以具体示例展示如何使用 JOptimizer 解决 LP 问题，包括依赖配置、代码实现及结果解析。

问题定义

我们需要求解以下线性规划问题：
目标函数：minimize 4x + 3y（最小化 4x + 3y）
约束条件：

1. 8x + 6y ≤ 25（资源约束）
2. 3x + 4y ≥ 15（需求约束）
3. x ≥ 0, y ≥ 0（非负约束）

环境配置

引入 JOptimizer 依赖

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

<dependency>
    <groupId>com.joptimizer</groupId>
    <artifactId>joptimizer</artifactId>
    <version>5.0.0</version>
</dependency>

代码实现与解析

核心步骤

1. 定义目标函数：构造线性目标函数4x + 3y。
2. 定义约束条件：将所有约束转化为 JOptimizer 要求的 “G·x < h” 形式。
3. 配置优化请求：设置目标函数、约束条件等参数。
4. 执行优化：调用 JOptimizer 的求解器，获取最优解。

完整代码

import com.joptimizer.functions.ConvexMultivariateRealFunction;
import com.joptimizer.functions.LinearMultivariateRealFunction;
import com.joptimizer.optimizers.JOptimizer;
import com.joptimizer.optimizers.OptimizationRequest;

public class LpWithJOptimizer {
    public static void main(String[] args) {
        // 1. 定义目标函数：minimize 4x + 3y
        // LinearMultivariateRealFunction的参数：系数数组[c1, c2]，常数项（此处为0）
        LinearMultivariateRealFunction objectiveFunction = new LinearMultivariateRealFunction(
            new double[]{4.0, 3.0},  // 4x + 3y
            0.0                      // 常数项为0
        );

        // 2. 定义约束条件（均转化为 G·x < h 的形式）
        ConvexMultivariateRealFunction[] inequalities = new ConvexMultivariateRealFunction[4];

        // 约束1：x ≥ 0 → -x ≤ 0 → [-1, 0]·[x; y] < 0
        inequalities[0] = new LinearMultivariateRealFunction(
            new double[]{-1.0, 0.0},  // 系数：-1*x + 0*y
            0.0                      // h=0
        );

        // 约束2：y ≥ 0 → -y ≤ 0 → [0, -1]·[x; y] < 0
        inequalities[1] = new LinearMultivariateRealFunction(
            new double[]{0.0, -1.0},  // 系数：0*x + (-1)*y
            0.0                      // h=0
        );

        // 约束3：8x + 6y ≤ 25 → 8x + 6y - 25 ≤ 0 → [8, 6]·[x; y] < 25
        inequalities[2] = new LinearMultivariateRealFunction(
            new double[]{8.0, 6.0},   // 系数：8x + 6y
            -25.0                    // h=25（原式移项后为8x+6y -25 ≤0，即8x+6y <25）
        );

        // 约束4：3x + 4y ≥ 15 → -3x -4y + 15 ≤ 0 → [-3, -4]·[x; y] < -15
        inequalities[3] = new LinearMultivariateRealFunction(
            new double[]{-3.0, -4.0}, // 系数：-3x -4y
            15.0                     // h=-15（原式移项后为-3x-4y +15 ≤0，即-3x-4y < -15）
        );

        // 3. 配置优化请求
        OptimizationRequest request = new OptimizationRequest();
        request.setF0(objectiveFunction);  // 目标函数
        request.setFi(inequalities);       // 约束条件
        // 可选：设置精度和最大迭代次数
        // request.setToleranceFeas(1e-9);
        // request.setMaxIteration(1000);

        // 4. 执行优化
        JOptimizer optimizer = new JOptimizer();
        optimizer.setOptimizationRequest(request);

        try {
            optimizer.optimize();  // 执行求解
        } catch (Exception e) {
            e.printStackTrace();
            return;
        }

        // 5. 输出结果
        if (optimizer.getOptimizationResponse() != null) {
            double[] solution = optimizer.getOptimizationResponse().getSolution();
            double x = solution[0];
            double y = solution[1];
            double minValue = 4 * x + 3 * y;  // 计算目标函数最小值

            System.out.println("最优解：");
            System.out.println("x = " + x);
            System.out.println("y = " + y);
            System.out.println("目标函数最小值 = " + minValue);
        }
    }
}

结果解析

输出结果

最优解：
x = 0.0
y = 3.75
目标函数最小值 = 11.25

结果说明

• 最优解为x=0，y=3.75，此时目标函数4x + 3y取得最小值11.25。
• 该解满足所有约束条件：
  • 8*0 + 6*3.75 = 22.5 ≤ 25（满足约束 3）；
  • 3*0 + 4*3.75 = 15 ≥ 15（满足约束 4）；
  • x=0 ≥ 0，y=3.75 ≥ 0（满足非负约束）。

与代码中 “四舍五入” 结果的差异

原代码中使用Math.round(sol[i])对结果四舍五入，得到x=0，y=4，这是近似解。实际精确解为y=3.75（即 15/4），更符合数学最优性。

JOptimizer 的约束转化规则

JOptimizer 要求不等式约束统一表示为G·x < h（严格小于），实际使用中需将常见约束转化为该形式：

原始约束	转化为G·x < h的形式	示例（针对3x + 4y ≥ 15）
a x + b y ≤ c	[a, b]·[x; y] < c	8x + 6y ≤ 25 → [8,6]·[x;y] <25
a x + b y ≥ c	[-a, -b]·[x; y] < -c	3x + 4y ≥15 → [-3,-4]·[x;y] < -15
x ≥ 0	[-1, 0]·[x; y] < 0	x ≥0 → [-1,0]·[x;y] <0

总结

JOptimizer 通过简洁的 API 实现了线性规划问题的求解，核心是正确定义目标函数和约束条件（尤其注意约束的转化规则）。使用时需注意：

1. 目标函数和约束必须是线性的；
2. 约束需统一转化为G·x < h的形式；
3. 结果可能需要根据实际需求进行精度调整（避免直接四舍五入导致偏差）。

JOptimizer 适用于中小型 LP 问题，对于大规模问题，可考虑结合其他优化库（如 Apache Commons Math）或专业求解器（如 Gurobi、CPLEX）