Apache常见的SimplexSolver ObjectiveFunction,用于最大化矩阵中值的总和

Question

我试图通过使用apache-commons的Simplex解算器解决以下线性问题:org.apache.commons.math3.optim.linear.SimplexSolver.

n行
m数是列数
L是每行总和的全局限制

这是我到目前为止:

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

double[][] A = calculateAValues();
// m = count of columns
// constraint 1: the sum of values in all column must be <= 1
for(int i = 0; i < m; i++) {
    double[] v = new double[n];
    for(int j=0; j < n; j++) {
        v[j] = 1;
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}
// n = count of rows
// constraint 2: sum of a_i,j in all row must be <= L (Limit)
for(int i = 0; i < n; i++) {
    double[] v = new double[m];
    for(int j=0; j < m; j++) {
        v[j] =  A[i][j];
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

double[] objectiveCoefficients = new double[n * m];
for(int i = 0; i < n * m; ++i) {
    objectiveCoefficients[i] = 1;
}

LinearObjectiveFunction objective = new LinearObjectiveFunction(objectiveCoefficients, 0);
LinearConstraintSet constraintSet = new LinearConstraintSet(constraints);

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet, GoalType.MAXIMIZE);
return solution.getValue();

我无法正确获得目标函数,也可能缺少其他一些东西.我的每一次尝试,到目前为止造成UnboundedSolutionException.

Answer 1

错误似乎出现在线性约束的系数数组中。

您有n*m变量，因此约束和目标函数的系数数组必须具有 length n*m。不幸的是，SimplexSolver如果约束数组比目标函数的数组短，则会默默地扩展约束数组。因此，您的代码没有指定导致无界解决方案的正确约束。

约束1：所有列中的值之和必须<= 1

for(int j=0; j<m; j++)
{
    double[] v = new double[n*m];
    for(int i=0; i<n; i++)
        v[i*n + j] = 1;
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}

约束2：所有行中的a_i,j之和必须<= L (Limit)

// n = count of rows
for(int i=0; i<n; i++)
{
    double[] v = new double[n*m];
    for(int j=0; j<m; j++)
        v[i*n + j] = A[i][j];
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

客观咖啡因：

double[] objectiveCoefficients = new double[n * m];
Arrays.fill(objectiveCoefficients, 1.0);
LinearObjectiveFunction objective = LinearObjectiveFunction(objectiveCoefficients, 0);

由于约束 2，约束x_ij <= 1已经满足。也许还显式指定使用0 <= x_ija 的约束会让事情变得更清楚NonNegativeConstraint：

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet,
     GoalType.MAXIMIZE, new NonNegativeConstraint(true));