Почему неверно выводит таблицу двойственного симплекс метода?
Неправильно выводит таблицу двойственного симплекс метода, я думаю она неправильно считает дельту, ну то что я в начале неправильно дельту ввожу. В общем правильно решает прямую, но неправильно двойственную вот вывод:
**Enter the number of variables:
2
Enter the number of constraints:
3
Enter the coefficients of the objective function:
20 40
Enter the coefficients of the constraint matrix:
3 6 2 8 4 7
Enter the constraint constants:
200 350 150
Enter true to maximize or false to minimize:
true
Прямой симплекс метод:
A1 A2 A3 A4 A5 A0
x3 3,00 6,00 1,00 0,00 0,00 200,00
x4 2,00 8,00 0,00 1,00 0,00 350,00
x5 4,00 7,00 0,00 0,00 1,00 150,00
△j 20,00 40,00 0,00 0,00 0,00 0,00
Optimal value = -0.0
A1 A2 A3 A4 A5 A0
x3 -0,43 0,00 1,00 0,00 -0,86 71,43
x4 -2,57 0,00 0,00 1,00 -1,14 178,57
x2 0,57 1,00 0,00 0,00 0,14 21,43
△j -2,86 0,00 0,00 0,00 -5,71 -857,14
Optimal value = 857.1428571428571
x2 = 21.428571428571427
Primal Simplex Tables:
A1 A2 A3 A4 A5 A0
x3 -0,43 0,00 1,00 0,00 -0,86 71,43
x4 -2,57 0,00 0,00 1,00 -1,14 178,57
x2 0,57 1,00 0,00 0,00 0,14 21,43
△j -2,86 0,00 0,00 0,00 -5,71 -857,14
Optimal value = 857.1428571428571
x2 = 21.428571428571427
Двойственный симплекс метод:
A1 A2 A3 A4 A5 A6 A7 A0
x6 3,00 2,00 4,00 -1,00 0,00 1,00 0,00 20,00
x7 6,00 8,00 7,00 0,00 -1,00 0,00 1,00 40,00
△j 200,00 350,00 150,00 0,00 0,00 1000000,00 1000000,00 0,00
Optimal value = 0.0
A1 A2 A3 A4 A5 A6 A7 A0
x3 0,75 0,50 1,00 -0,25 0,00 0,25 0,00 5,00
x7 0,75 4,50 0,00 1,75 -1,00 -1,75 1,00 5,00
△j 87,50 275,00 0,00 37,50 0,00 999962,50 1000000,00 -750,00
Optimal value = -750.0
x3 = 5.0
Primal Simplex Tables:
A1 A2 A3 A4 A5 A6 A7 A0
x3 0,75 0,50 1,00 -0,25 0,00 0,25 0,00 5,00
x7 0,75 4,50 0,00 1,75 -1,00 -1,75 1,00 5,00
△j 87,50 275,00 0,00 37,50 0,00 999962,50 1000000,00 -750,00
Optimal value = -750.0
x3 = 5.0**
Вот код класса, реализующий двойственный симплекс метод:
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 + numOfVariables + 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); 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); 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[pivotRow][j] * dualTableau[i][pivotColumn]
/ dualTableau[pivotRow][pivotColumn];
// zero out column pivotColumn
for (int i = 0; i <= numOfVariables; i++)
if (i != pivotRow)
dualTableau[i][pivotColumn] = 0.0;
// scale row p
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]);
}
}
}
}**