выполнимый метод застрял в бесконечном цикле

Я запустил следующий симплекс-метод, который написан на C ++. Код выглядит следующим образом:

#include<bits/stdc++.h>
#include<cstdio>
using namespace std;

#define maxm 500
#define maxn 500
double inf = 1e100;
double eps = 1e-13;

int row,col;
double A[maxm][maxn];
double B[maxn];
///////////////////////////////////////////////////////////////////////////////////////////
// Simon Lo's
// Simplex algorithm on augmented matrix a of dimension (m+1)x(n+1)
// returns 1 if feasible, 0 if not feasible, -1 if unbounded
// returns solution in b[] in original var order, max(f) in ret
// form: maximize sum_j(a_mj*x_j)-a_mn s.t. sum_j(a_ij*x_j)<=a_in
// in standard form.
// To convert into standard form:
// 1. if exists equality constraint, then replace by both >= and <=
// 2. if variable x doesn't have nonnegativity constraint, then replace by
// difference of 2 variables like x1-x2, where x1>=0, x2>=0
// 3. for a>=b constraints, convert to -a<=-b
// note: watch out for -0.0 in the solution, algorithm may cycle
// eps = 1e-7 may give wrong answer, 1e-10 is bettervoid pivot(int m, int n, double a[maxm][maxn], int B[maxm], int N[maxn], int r, int c) {
int i, j;
swap(N[c], B[r]);
a[r][c]=1/a[r][c];
for (j=0; j<=n; j++)if (j!=c) a[r][j]*=a[r][c];
for (i=0; i<=m; i++)if (i!=r) {
for (j=0; j<=n; j++)if (j!=c)
a[i][j]-=a[i][c]*a[r][j];
a[i][c] = -a[i][c]*a[r][c];
}
}
int feasible(int m, int n, double a[maxm][maxn], int B[maxm], int N[maxn]) {
int r, c, i; double p, v;
while (1) {
for (p=inf, i=0; i<m; i++) if (a[i][n]<p) p=a[r=i][n];
if (p>-eps) return 1;
for (p=0, i=0; i<n; i++) if (a[r][i]<p) p=a[r][c=i];
if (p>-eps) return 0;
cout<<"Sultan"<<endl;
p = a[r][n]/a[r][c];
for (i=r+1; i<m; i++) if (a[i][c]>eps) {
v = a[i][n]/a[i][c];
if (v<p) r=i, p=v;
}
pivot(m, n, a, B, N, r, c);
}
}
int simplex(int m, int n, double a[maxm][maxn], double b[maxn], double& ret)
{
int B[maxm], N[maxn], r, c, i; double p, v;
for (i=0; i<n; i++) N[i]=i;
for (i=0; i<m; i++) B[i]=n+i;
if (!feasible(m, n, a, B, N)) return 0;
while (1) {
for (p=0, i=0; i<n; i++) if (a[m][i]>p)
p=a[m][c=i];
if (p<eps) {
for (i=0; i<n; i++) if (N[i]<n)
b[N[i]]=0;
for (i=0; i<m; i++) if (B[i]<n)
b[B[i]]=a[i][n];
ret = -a[m][n];
return 1;
}
for (p=inf, i=0; i<m; i++) if (a[i][c]>eps) {
v = a[i][n]/a[i][c];
if (v<p) p=v, r=i;
}
if (p==inf) return -1;
pivot(m, n, a, B, N, r, c);
}
}
//////////////////////////////////////////////////////////////////////////////////////////////

void read_file()
{
freopen("Dimen.txt","r",stdin);

scanf("%d",&row);
scanf("%d",&col);

row = 30 ;
col = 100;

cout << row << " "<<col<<endl;

freopen("A1.txt","r",stdin);
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
scanf("%lf",&A[i][j]);
cout<"Completed A";

freopen("B1.txt","r",stdin);
for(int i=0;i<row;i++){
scanf("%lf",&A[i][col]);
}
cout<"Completed B";

freopen("F1.txt","r",stdin);
for(int j=0;j<col;j++){
scanf("%lf",&A[row][j]);
//B[i]=-B[i];
}
cout<"Completed F";}

int main()
{
read_file();
double value,opt=0;
int flag = simplex(row,col, A,B, value);
freopen("opt.txt","r",stdin);
scanf("%lf",&opt);
if(flag != -1)
{
cout<<"The result is "<<(value+opt);
}
else
{
cout<<"The result is infeasible";
}

return 0;
}

Но этот код работает в бесконечном цикле. Возможный метод застрял в бесконечном цикле. Как я могу решить эту ошибку? Пожалуйста, помогите мне .

-1

Решение

Давайте начнем с исправления неясных битов кода:

#include<bits/stdc++.h>

Вы не должны использовать любые включения, которые начинаются с bits/ включите стандартный заголовок, который будет включать его.

#include<cstdio>
using namespace std;

С помощью std Это плохая практика, это может запутать компилятор в больших проектах и ​​выбрать функцию / шаблон / то, что вы не хотели.

#define maxm 500
#define maxn 500

Как минимум измените их на

#define maxm (500)
#define maxn (500)

Так что подстановка макросов не запутается. Лучше использовать C ++ 11 и использовать

constexpr int maxm = 500;
constexpr int maxn = 500;

double inf = 1e100;
double eps = 1e-13;

Существуют стандартные способы поиска правильных значений для inf а также eps

double inf = std::numeric_limits<double>::max();

Из вашего кода, я полагаю, вы действительно имели в виду max double.
За eps Интересно, если вам нужно

double eps = std::numeric_limits<double>::epsilon();

или же

double eps = std::numeric_limits<double>::round_error();
1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]