Apache Common SimplexSolver ObjectiveFunction für die Maximierung der Summe der Werte in einer Matrix

Question

Ich versuche, das folgende lineare Problem zu lösen, indem ich den Simplex-Solver von Apache-Commons verwende: org.apache.commons.math3.optim.linear.SimplexSolver.

n ist die Anzahl der Zeilen
m die Anzahl der Spalten ist
L eine globale Grenzwert für den Summenwert jeder

Reihe ist

Das ist, was ich habe, so weit:

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(); 

Ich habe Probleme, die objektive Funktion richtig, und es könnten auch andere Dinge fehlen. Mein bisheriger Versuch führte zu UnboundedSolutionException.

Answer 1

Der Fehler scheint in den Koeffizientenarrays der linearen Integritätsbedingungen zu liegen.

Sie haben n*m Variablen, daher müssen die Koeffizientenfelder für die Abhängigkeiten und die Zielfunktionen die Länge n*m haben. Leider erweitert die SimplexSolver automatisch das Constraints-Array, wenn sie kürzer als das Array der Zielfunktion sind. Ihr Code hat also nicht die richtigen Einschränkungen angegeben, die zu einer unbegrenzten Lösung führen.

Constraint 1: die Summe der Werte in allen Spalte muss < = 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)); 
} 

Constraint 2 sein: Summe von a_i, j in allen Zeile muss < = L (Limit) sein

// 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)); 
} 

Ziel coffecifients:

Die Einschränkung x_ij <= 1 ist bereits wegen der Einschränkung erfüllt 2. Vielleicht eine Einschränkung angeben, kann auch die Dinge klar macht es explizit für 0 <= x_ij mit einem NonNegativeConstraint:

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