我正在尝试在 java 中编写一个单纯形算法来进行分配。我的代码适用于某些输入，但算法经常陷入循环，从状态 A 重新计算到状态 B，然后返回到状态 A。进入无限循环。
起初我认为这是一个退化问题。但我实际上是在使用 Bland 的规则，进一步的头脑风暴和尝试调试让我意识到这是导致循环的约束不等式中的负系数。
所以我想我明白为什么会发生错误。但我不确定我应该如何改变我的算法来解决这个问题。
这是我的整个代码...
public class Main {
// initialize tableau
static double tableau[][] = new double[101][201];
static int variable[] = new int[100];
static int nCount, mCount, totalColumnCount;
public static void main(String[] args) {
try {
// read from file
Scanner s = new Scanner(new File("c:\\hw6\\input.txt"));
// for formatting double values to two decimal places
DecimalFormat oneDigit = new DecimalFormat("#,###0.00");
// ----------------------------------------initialize tableau---------------------------------------------------
// read number of n(variables) and m(constraints)
nCount = s.nextInt();
mCount = s.nextInt();
totalColumnCount = nCount + mCount + 1;
// fill variable[] with arbitrarily large values
for (int j = 0; j < mCount; j++) {
variable[j] = 200;
}
// get coefficients for objective function and store into tableau
for (int j = 0; j < nCount; j++) {
tableau[mCount][j] = -s.nextInt();
}
for (int j = nCount; j < nCount + mCount; j++) {
tableau[mCount][j] = 0;
}
tableau[mCount][nCount + mCount] = 1; // value of MAX (P)
tableau[mCount][nCount + mCount + 1] = 0; // RHS (which should be 0)
// get coefficients of constraint inequalities
for (int j = 0; j < mCount; j++) {
for (int k = 0; k < nCount; k++) {
tableau[j][k] = s.nextInt();
}
for (int k = nCount; k < nCount + mCount; k++) {
if (k - nCount == j)
tableau[j][k] = 1;
else
tableau[j][k] = 0;
}
// get the RHS
tableau[j][nCount + mCount + 1] = s.nextInt();
}
// store variables that each constraint refers to
for (int j = 0; j < mCount; j++) {
variable[j] = j + 1;
}
// ----------------------------------------initialize tableau---------------------------------------------------
// look for any negative values in the objective function
for (int j = 0; j <= totalColumnCount; j++) {
if (tableau[mCount][j] < 0) {
Coordinate pivot = findPivot();
pivotTo1(pivot);
pivotColumnTo0(pivot);
// for checking that this iteration of converting constraints has been calculated correctly
for (int k = 0; k <= mCount; k++) {
System.out.print("[ ");
for (int l = 0; l <= totalColumnCount; l++) {
System.out.print(oneDigit.format(tableau[k][l]) + " ");
}
System.out.println(" ]");
}
System.out.println();
// repeat looking for any negative values in the objective function
j = 0;
continue;
}
}
// get solutions
getSolution();
} catch (IOException e) {
System.out.println(e);
}
}
public static Coordinate findPivot() {
double currentMinColumn = Integer.MAX_VALUE;
double currentCalculation = Integer.MAX_VALUE;
int pivotColumn = 0;
int pivotRow = 0;
// find pivot column
for (int i = 0; i < totalColumnCount; i++) {
if (currentMinColumn > tableau[mCount][i]) {
currentMinColumn = tableau[mCount][i];
pivotColumn = i;
}
}
// find pivot
for (int i = 0; i < mCount; i++) {
if (currentCalculation > tableau[i][totalColumnCount] / tableau[i][pivotColumn]) {
currentCalculation = tableau[i][totalColumnCount] / tableau[i][pivotColumn];
pivotRow = i;
}
}
// return coordinate of pivot value
return new Coordinate(pivotRow, pivotColumn);
}
public static void pivotTo1(Coordinate pivot) {
double pivotValue = tableau[pivot.row()][pivot.column()];
// find factor to multiply to pivot's row to convert pivot to 1
double multFactor = 1.0 / pivotValue;
// convert the pivot's row
for (int i = 0; i <= totalColumnCount; i++) {
tableau[pivot.row()][i] *= multFactor;
}
// update variable for the constraint
variable[pivot.row()] = pivot.column();
}
public static void pivotColumnTo0(Coordinate pivot) {
double multFactor = 0;
// for all constraints
for (int i = 0; i < mCount + 1; i++) {
// skip constraint containing pivot
if (i == pivot.row())
continue;
// get multFactor of constraint
multFactor = -tableau[i][pivot.column()];
// update each constraint by making pivot column values become zero
for (int j = 0; j <= totalColumnCount; j++) {
tableau[i][j] = tableau[i][j] + (multFactor * tableau[pivot.row()][j]);
}
}
}
public static void getSolution() {
int solutionExists;
// for all variables
for (int i = 0; i < nCount; i++) {
solutionExists = 0;
// for all variables in the variable[] array
for (int j = 0; j < mCount; j++) {
// if the variable exists in the variable[] array print the value
if (i == variable[j]) {
System.out.println(tableau[j][totalColumnCount]);
solutionExists = 1;
break;
}
}
// if it does not exist print 0
if (solutionExists == 0) {
System.out.println(0);
}
}
}
}
（我本来希望只发布相关的代码片段，这样你们就不会那么费力地试图破译这个，我认为你们无论如何都需要整个代码来找到我的错误在哪里。我试图尽可能具体地发表评论。）
我将此视频用作理解单纯形法的参考：https ://www.youtube.com/watch?v=gRgsT9BB5-8
input.txt 如下所示：
这个有效
3 3 // number of variables (n), number of constraints (m)
6 5 4 // objective function: 6x1 + 5x2 + 4x3
2 1 1 180 // constraint 1: 2x1 + 1x2 + 1x3 <= 180
1 3 2 300
2 1 2 240
给出解决方案
48.0
84.0
0
这个不行
2 2
2 5
2 -1 4
-1 2 9
任何帮助或建议将不胜感激。非常感谢！