программа не решает двойственный симплекс-метод
мне просто нужно чтобы работал двойственный симплекс метод, я написала код прямая работает но на двойственной не может найти входящий в базис столбец я не понимаю что сделать файл мейн:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of variables:");
int numOfVariables = scanner.nextInt();
System.out.println("Enter the number of constraints:");
int numOfConstraints = scanner.nextInt();
double[] objectiveFunctionCoefficients = new double[numOfVariables];
double[][] constraintCoefficients = new double[numOfConstraints][numOfVariables];
double[] constraintConstants = new double[numOfConstraints];
double[][] constraintDualCoefficients = new double[numOfVariables][numOfConstraints];
System.out.println("Enter the coefficients of the objective function:");
for (int i = 0; i < numOfVariables; i++) {
objectiveFunctionCoefficients[i] = scanner.nextDouble();
}
System.out.println("Enter the coefficients of the constraint matrix:");
for (int i = 0; i < numOfConstraints; i++) {
for (int j = 0; j < numOfVariables; j++) {
constraintCoefficients[i][j] = scanner.nextDouble();
}
}
for (int i = 0; i < numOfVariables; i++) {
for (int j = 0; j < numOfConstraints; j++) {
constraintDualCoefficients[i][j] = constraintCoefficients[j][i];
}
}
System.out.println("Enter the constraint constants:");
for (int i = 0; i < numOfConstraints; i++) {
constraintConstants[i] = scanner.nextDouble();
}
System.out.println("Enter true to maximize or false to minimize:");
boolean maximizeOrMinimize = scanner.nextBoolean();
SimplexMethod simplexMethod = new SimplexMethod(numOfConstraints, numOfVariables, maximizeOrMinimize);
simplexMethod.initializeTableau(objectiveFunctionCoefficients, constraintCoefficients, constraintConstants);
simplexMethod.solve();
System.out.println("Primal Simplex Tables:");
simplexMethod.printSolution();
DualSimplexMethod dualSimplexMethod = new DualSimplexMethod(numOfConstraints, numOfVariables,
maximizeOrMinimize);
dualSimplexMethod.initializeDualTableau(objectiveFunctionCoefficients,
constraintDualCoefficients, constraintConstants);
dualSimplexMethod.dualSolve();
System.out.println("Primal Simplex Tables:");
dualSimplexMethod.printDualSolution();
}
}
файл симплексметод:
public class SimplexMethod {
private double[][] tableau;
private int numOfConstraints;
private int numOfVariables;
private boolean maximizeOrMinimize;
private int[] basis;
public SimplexMethod(int numOfConstraints, int numOfVariables, boolean maximizeOrMinimize) {
this.maximizeOrMinimize = maximizeOrMinimize;
this.numOfConstraints = numOfConstraints;
this.numOfVariables = numOfVariables;
this.tableau = new double[numOfConstraints + 1][numOfVariables + numOfConstraints + 1]; //хранение симплекс таблицы
basis = new int[numOfConstraints]; //хранение базисных переменных
for (int i = 0; i < numOfConstraints; i++)
basis[i] = numOfVariables + i;
solve(); //решение злп симплекс методом
}
//метод заполняет симплес-таблицу коэффициентами и ограничений
public void initializeTableau(double[] objectiveFunctionCoefficients, double[][] constraintCoefficients,
double[] constraintConstants) {
for (int i = 0; i < numOfConstraints; i++) {
for (int j = 0; j < numOfVariables; j++) {
tableau[i][j] = constraintCoefficients[i][j];
}
tableau[i][numOfVariables + i] = 1;
tableau[i][numOfVariables + numOfConstraints] = constraintConstants[i];
}
for (int j = 0; j < numOfVariables; j++) {
tableau[numOfConstraints][j] = objectiveFunctionCoefficients[j];
}
printSolution();
}
public void solve() {
while (true) {
int pivotColumn = 0;
if (maximizeOrMinimize) { //поиск входящего столбца на основе макс значения
pivotColumn = findPivotColumn();
} else {
pivotColumn = dantzigNegative();
}
if (pivotColumn == -1) //Если pivotColumn равен -1, это означает, что достигнуто оптимальное решение, и цикл прерывается
break; // optimal
// find leaving row pivotRow
int pivotRow = minRatioRule(pivotColumn); //для поиска исходящей строки на основе правила минимального отношения
if (pivotRow == -1)
throw new ArithmeticException("Linear program is unbounded");
// pivot
pivot(pivotRow, pivotColumn);
// update basis
basis[pivotRow] = pivotColumn;
printSolution();
}
}
//проходит по столбцам таблицы симплекс-метода и находит индекс столбца с наивысшим значением в строке,
private int findPivotColumn() {
int pivotColumn = 0;
for (int j = 1; j < numOfConstraints + numOfVariables; j++)
if (tableau[numOfConstraints][j] tableau[numOfConstraints][pivotColumn])
pivotColumn = j;
if (tableau[numOfConstraints][pivotColumn] <= 0)
return -1; // optimal
else
return pivotColumn;
}
// выполняет поиск пивотного столбца с отрицательным значением в последней строке таблицы и возвращает его индекс, или -1, если такого
столбца нет
private int dantzigNegative() {
int pivotColumn = 0;
for (int j = 1; j numOfConstraints + numOfVariables; j++)
if (tableau[numOfConstraints][j] < tableau[numOfConstraints][pivotColumn])
pivotColumn = j;
if (tableau[numOfConstraints][pivotColumn] >= 0)
return -1; // optimal
else
return pivotColumn;
}
//происходит выбор опорной строки для пересчета в методе симплекса
private int minRatioRule(int pivotColumn) {
int pivotRow = -1;
for (int i = 0; i < numOfConstraints; i++) {
if (tableau[i][pivotColumn] <= 0)
continue;
else if (pivotRow == -1)
pivotRow = i;
else if ((tableau[i][numOfConstraints
+ numOfVariables] / tableau[i][pivotColumn]) < (tableau[pivotRow][numOfConstraints
+ numOfVariables] / tableau[pivotRow][pivotColumn]))
pivotRow = i;
}
return pivotRow;
}
//выполняет пересчет таблицы в методе симплекса после выбора опорной строки и столбца
private void pivot(int pivotRow, int pivotColumn) {
// everything but row p and column pivotColumn
for (int i = 0; i <= numOfConstraints; i++)
for (int j = 0; j <= numOfConstraints
+ numOfVariables; j++)
if (i != pivotRow && j != pivotColumn)
tableau[i][j] -= tableau[pivotRow][j] * tableau[i][pivotColumn]
/ tableau[pivotRow][pivotColumn];
// zero out column pivotColumn
for (int i = 0; i <= numOfConstraints; i++)
if (i != pivotRow)
tableau[i][pivotColumn] = 0.0;
// scale row p
for (int j = 0; j <= numOfConstraints + numOfVariables; j++)
if (j != pivotColumn)
tableau[pivotRow][j] /= tableau[pivotRow][pivotColumn];
tableau[pivotRow][pivotColumn] = 1.0;
}
// return optimal objective value
public double value() {
return -tableau[numOfConstraints][numOfConstraints
+ numOfVariables];
}
// print tableau
public void printSolution() {
System.out.print(" ");
for (int j = 1; j < numOfVariables + numOfConstraints + 1; j++) {
System.out.printf("%-8s", "A" + j);
}
System.out.print("A0");
System.out.println();
for (int i = 0; i <= numOfConstraints; i++) {
if (i == numOfConstraints) {
System.out.printf("%-6s", "?j ");
} else {
System.out.printf("%-6s", "x" + (basis[i] + 1));
}
for (int j = 0; j <= numOfConstraints + numOfVariables; j++) {
System.out.printf("%7.2f ", tableau[i][j]);
}
System.out.println();
}
System.out.println("Optimal value = " + value());
for (int i = 0; i < numOfConstraints; i++) {
if (basis[i] < numOfVariables) {
System.out.println("x" + (basis[i] + 1) + " = " + tableau[i][numOfConstraints + numOfVariables]);
}
}
System.out.println();
}
}
файл двойственный симплекс метод:
public class DualSimplexMethod {
private double[][] dualTableau;
private boolean dualMaximizeOrMinimize;
private int[] dualBasis;
private int numOfConstraints;
private int numOfVariables;
public DualSimplexMethod(int numOfConstraints, int numOfVariables, boolean maximizeOrMinimize) {
this.dualMaximizeOrMinimize = !maximizeOrMinimize;
this.numOfConstraints = numOfConstraints;
this.numOfVariables = numOfVariables;
this.dualTableau = new double[numOfVariables + 1][numOfConstraints + numOfVariables + numOfVariables + 1];
dualBasis = new int[numOfVariables]; //хранение базисных переменных
for (int i = 0; i < numOfVariables; i++)
dualBasis[i] = numOfConstraints + i;
dualSolve(); //решение злп симплекс методом
}
public void initializeDualTableau(double[] objectiveFunctionCoefficients, double[][] constraintCoefficients,
double[] constraintConstants) {
for (int i = 0; i < numOfVariables; i++) {
for (int j = 0; j < numOfConstraints; j++) {
dualTableau[i][j] = constraintCoefficients[i][j];
dualTableau[numOfVariables][j] = constraintConstants[j];
}
dualTableau[i][numOfConstraints + i] = -1;
dualTableau[i][numOfConstraints + numOfVariables + i] = 1;
dualTableau[i][numOfVariables + numOfConstraints + numOfVariables] = objectiveFunctionCoefficients[i];
}
dualTableau[numOfVariables][numOfConstraints + numOfVariables] = 1000000;
dualTableau[numOfVariables][numOfConstraints + numOfVariables + 1] = 1000000;
printDualSolution();
}
public void dualSolve() {
while (true) {
int pivotColumn = 0;
if (dualMaximizeOrMinimize) { //поиск входящего столбца на основе макс значения
pivotColumn = findPivotColumn();
} else {
pivotColumn = dantzigNegative();
}
if (pivotColumn == -1) //Если pivotColumn равен -1, это означает, что достигнуто оптимальное решение, и цикл прерывается
break; // optimal
// find leaving row pivotRow
int pivotRow = minRatioRule(pivotColumn); //для поиска исходящей строки на основе правила минимального отношения
if (pivotRow == -1)
throw new ArithmeticException("Linear program is unbounded");
// pivot
pivot(pivotRow, pivotColumn);
// update basis
dualBasis[pivotRow] = pivotColumn;
printDualSolution();
}
}
//проходит по столбцам таблицы симплекс-метода и находит индекс столбца с наивысшим значением в строке,
private int findPivotColumn() {
int pivotColumn = 0;
for (int j = 1; j <= (numOfConstraints + numOfVariables + numOfVariables); j++) {
if (dualTableau[numOfVariables][j] dualTableau[numOfVariables][pivotColumn]) {
pivotColumn = j;
}
}
if (dualTableau[numOfVariables][pivotColumn] <= 0) {
return -1; // optimal
} else {
return pivotColumn;
}
}
// выполняет поиск пивотного столбца с отрицательным значением в последней строке таблицы и возвращает его индекс, или -1, если такого
столбца нет
private int dantzigNegative() {
int pivotColumn = 0;
for (int j = 1; j < (numOfConstraints + numOfVariables + numOfVariables); j++) {
if (dualTableau[numOfVariables][j] < dualTableau[numOfVariables][pivotColumn]) {
pivotColumn = j;
}
}
if (dualTableau[numOfVariables][pivotColumn] <= 0) {
return -1; // optimal
} else {
return pivotColumn;
}
}
//происходит выбор опорной строки для пересчета в методе симплекса
private int minRatioRule(int pivotColumn) {
int pivotRow = -1;
for (int i = 0; i < numOfVariables; i++) {
if (dualTableau[i][pivotColumn] <= 0)
continue;
else if (pivotRow == -1)
pivotRow = i;
else if ((dualTableau[i][numOfConstraints
+ numOfVariables + numOfVariables] / dualTableau[i][pivotColumn]) < (dualTableau[pivotRow][numOfConstraints
+ numOfVariables + numOfVariables] / dualTableau[pivotRow][pivotColumn]))
pivotRow = i;
}
return pivotRow;
}
//выполняет пересчет таблицы в методе симплекса после выбора опорной строки и столбца
private void pivot(int pivotRow, int pivotColumn) {
// everything but row p and column pivotColumn
for (int i = 0; i <= numOfVariables; i++)
for (int j = 0; j <= numOfConstraints
+ numOfVariables + numOfVariables; j++)
if (i != pivotRow && j != pivotColumn)
dualTableau[i][j] = dualTableau[i][j] - dualTableau[pivotRow][j] * dualTableau[i][pivotColumn] /
dualTableau[pivotRow][pivotColumn];
for (int i = 0; i <= numOfVariables; i++)
if (i != pivotRow)
dualTableau[i][pivotColumn] = 0.0;
for (int j = 0; j <= numOfConstraints + numOfVariables + numOfVariables; j++)
if (j != pivotColumn)
dualTableau[pivotRow][j] /= dualTableau[pivotRow][pivotColumn];
dualTableau[pivotRow][pivotColumn] = 1.0;
}
public double dualValue() {
return dualTableau[numOfVariables][numOfConstraints
+ numOfVariables+numOfVariables];
}
public void printDualSolution() {
System.out.print(" ");
for (int j = 1; j < numOfVariables + numOfConstraints + numOfVariables + 1; j++) {
System.out.printf("%-8s", "A" + j);
}
System.out.print("A0");
System.out.println();
for (int i = 0; i <= numOfVariables; i++) {
if (i == numOfVariables) {
System.out.printf("%-6s", "?j ");
} else {
System.out.printf("%-6s", "x" + (dualBasis[i] + 1));
}
for (int j = 0; j <= numOfConstraints + numOfVariables+numOfVariables; j++) {
System.out.printf("%7.2f ", dualTableau[i][j]);
}
System.out.println();
}
System.out.println("Optimal value = " + dualValue());
for (int i = 0; i < numOfVariables; i++) {
if (dualBasis[i] < numOfConstraints) {
System.out.println("x" + (dualBasis[i] + 1) + " = " + dualTableau[i][numOfConstraints + numOfVariables + numOfVariables]);
}
}
}
}