Apache wspólne SimplexSolver ObjectiveFunction dla zmaksymalizowania sumy wartości w macierzy

Question

Próbuję rozwiązać następujący problem liniowy za pomocą solvera Simplex od Apache-commons: org.apache.commons.math3.optim.linear.SimplexSolver.

n jest liczba wierszy
m jest liczba kolumn
L to globalny limit wartości sumy każdego rzędu

To, co mam tak daleko:

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

Mam problem z prawidłowym ustawieniem funkcji celu oraz również może być kilka innych rzeczy. Każda moja dotychczasowa próba zaowocowała UnboundedSolutionException.

Answer 1

Błąd wydaje się znajdować się w macierzach współczynników więzów liniowych.

Masz zmienne n*m dlatego tablice współczynników dla wiązań i funkcji celu muszą mieć długość n*m. Niestety, SimplexSolver po cichu rozwija tablicę więzów, jeśli są one krótsze niż tablica funkcji celu. Twój kod nie określał poprawnych ograniczeń prowadzących do rozwiązania nieograniczonego.

Ograniczenie 1: suma wartości w całej kolumnie może być < = 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)); 
} 

Wiązanie 2: suma a_i, J w każdym rzędzie może być < = 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)); 
} 

obiektywne coffecifients:

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

Ograniczenie x_ij <= 1 jest już spełniony z powodu ograniczeń 2. Może to sprawia, że ​​rzeczy bardziej jasne również wyraźnie określić ograniczenia dla 0 <= x_ij użyciu NonNegativeConstraint:

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