割り当てのためにシンプレックス アルゴリズムを 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
どんな助けやアドバイスも大歓迎です。どうもありがとうございました！