使用Apache Commons Math实现线性规划遇UnboundedSolutionException求助

该问题是典型的运输优化问题（最大化利润的最小费用最大流变种），使用LibreOffice Solver可正常求解，但代码运行时抛出无界异常，以下是问题排查与解决方案：

依赖配置 #

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.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.Arrays;
import java.util.List;

public class Main {
    public static void simplex() {

        double[] supplierCapacities = {200, 100, 50}; // cells G8:G10
        double[] consummerCapacities = {150, 75, 50, Arrays.stream(supplierCapacities).sum()}; // cells B12:E12
        int numberOfSuppliers = supplierCapacities.length;
        int numberOfConsummers = consummerCapacities.length;

        double[] prices = {
                2, 2, 2, 1,
                2, 2, 2, 1,
                2, 2, 2, 1
        }; // cells B16:E18
        LinearObjectiveFunction objectiveFunction = new LinearObjectiveFunction(prices, 0); // cell C4 to maximize

        // constraints
        List<LinearConstraint> constraintsList = new ArrayList<>();

        // the amount of products from supplier N to any consumers must not exceed the supplier capacity
        // F8:F10 <= G8:G10
        for (int i = 0; i < numberOfSuppliers; ++i) {
            double[] coeffs = new double[numberOfConsummers];
            Arrays.fill(coeffs, 1.0);
            LinearConstraint lessOrEqualToSupplierCapacity = new LinearConstraint(coeffs, Relationship.LEQ, supplierCapacities[i]);
            constraintsList.add(lessOrEqualToSupplierCapacity);
        }
        // the amount of products received by consummer M from any supplier must not exceed the consommer capacity
        // B11:E11 <= B12:E12
        for (int i = 0; i < numberOfConsummers; ++i) {
            double[] coeffs = new double[numberOfSuppliers];
            Arrays.fill(coeffs, 1);
            LinearConstraint lessOrEqualtToConsommerCapacity = new LinearConstraint(coeffs, Relationship.LEQ, consummerCapacities[i]);
            constraintsList.add(lessOrEqualtToConsommerCapacity);
        }
        // gather up all constraints
        LinearConstraintSet linearConstraintSet = new LinearConstraintSet(constraintsList);

        // solve
        SimplexSolver solver = new SimplexSolver();
        PointValuePair solution = solver.optimize(objectiveFunction, linearConstraintSet, GoalType.MAXIMIZE, new NonNegativeConstraint(true));

        System.out.println(solution);
    }

    public static void main(String[] args) {
        simplex();
    }
}

抛出的异常 #

Exception in thread "main" org.apache.commons.math3.optim.linear.UnboundedSolutionException: solution non bornée
    at org.apache.commons.math3.optim.linear.SimplexSolver.doIteration(SimplexSolver.java:325)
    at org.apache.commons.math3.optim.linear.SimplexSolver.doOptimize(SimplexSolver.java:389)
    at org.apache.commons.math3.optim.linear.SimplexSolver.doOptimize(SimplexSolver.java:65)
    at org.apache.commons.math3.optim.BaseOptimizer.optimize(BaseOptimizer.java:153)
    at org.apache.commons.math3.optim.BaseMultivariateOptimizer.optimize(BaseMultivariateOptimizer.java:65)
    at org.apache.commons.math3.optim.nonlinear.scalar.MultivariateOptimizer.optimize(MultivariateOptimizer.java:63)
    at org.apache.commons.math3.optim.linear.LinearOptimizer.optimize(LinearOptimizer.java:94)
    at org.apache.commons.math3.optim.linear.SimplexSolver.optimize(SimplexSolver.java:154)
    at Main.simplex(Main.java:53)
    at Main.main(Main.java:59)

问题分析 #

代码核心错误是约束条件的变量维度不匹配：

• 目标函数的变量是12个（3个供应商×4个消费者的运输量），但构造供应商/消费者约束时，生成的系数数组长度仅为4或3，与变量总数不匹配，导致这些约束实际未生效。
• 有效约束缺失后，求解器判定问题无界，抛出UnboundedSolutionException。

正确的约束逻辑：

1. 供应商约束：对每个供应商i，其对应的4个运输量变量（i4到i4+3）的系数和为1，总和不超过该供应商的产能。
2. 消费者约束：对每个消费者j，其对应的3个运输量变量（04+j、14+j、2*4+j）的系数和为1，总和不超过该消费者的容量。

修正后的代码 #

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.Arrays;
import java.util.List;

public class Main {
    public static void simplex() {

        double[] supplierCapacities = {200, 100, 50}; // cells G8:G10
        double[] consumerCapacities = {150, 75, 50, Arrays.stream(supplierCapacities).sum()}; // cells B12:E12
        int numberOfSuppliers = supplierCapacities.length;
        int numberOfConsumers = consumerCapacities.length;
        int totalVariables = numberOfSuppliers * numberOfConsumers; // 3*4=12个运输量变量

        double[] prices = {
                2, 2, 2, 1,
                2, 2, 2, 1,
                2, 2, 2, 1
        }; // cells B16:E18
        LinearObjectiveFunction objectiveFunction = new LinearObjectiveFunction(prices, 0); // 最大化利润

        // constraints
        List<LinearConstraint> constraintsList = new ArrayList<>();

        // 供应商约束：每个供应商发往所有消费者的总量 ≤ 供应商产能
        for (int i = 0; i < numberOfSuppliers; ++i) {
            double[] coeffs = new double[totalVariables];
            // 填充当前供应商对应的4个变量系数为1
            for (int j = 0; j < numberOfConsumers; j++) {
                coeffs[i * numberOfConsumers + j] = 1.0;
            }
            constraintsList.add(new LinearConstraint(coeffs, Relationship.LEQ, supplierCapacities[i]));
        }

        // 消费者约束：每个消费者接收所有供应商的总量 ≤ 消费者容量
        for (int j = 0; j < numberOfConsumers; ++j) {
            double[] coeffs = new double[totalVariables];
            // 填充当前消费者对应的3个变量系数为1
            for (int i = 0; i < numberOfSuppliers; i++) {
                coeffs[i * numberOfConsumers + j] = 1.0;
            }
            constraintsList.add(new LinearConstraint(coeffs, Relationship.LEQ, consumerCapacities[j]));
        }

        LinearConstraintSet linearConstraintSet = new LinearConstraintSet(constraintsList);

        // 求解
        SimplexSolver solver = new SimplexSolver();
        PointValuePair solution = solver.optimize(objectiveFunction, linearConstraintSet, GoalType.MAXIMIZE, new NonNegativeConstraint(true));

        // 输出结果：变量值和目标函数值
        System.out.println("最优运输量：" + Arrays.toString(solution.getPoint()));
        System.out.println("最大利润：" + solution.getValue());
    }

    public static void main(String[] args) {
        simplex();
    }
}

说明 #

修正后的代码：

• 明确计算总变量数为numberOfSuppliers * numberOfConsumers
• 构造约束时，系数数组长度与总变量数匹配，正确定位每个运输量变量的位置
• 运行后可得到与LibreOffice Solver一致的有界解

内容的提问来源于stack exchange，提问作者remi