18 #define POS(R,C,NC) ((R)*(NC)+(C))
31 static void fmprint(
double* matrix,
int nrows,
int ncols,FILE* file)
37 fprintf(file,
"--------------+");
45 fprintf(file,
" %12.4f |",matrix[
POS(i,j,ncols)]);
52 fprintf(file,
"--------------+");
72 static double minimumc(
double* matrix,
int nrows,
int ncols,
int col,
int* row)
78 if(matrix[
POS(i,col,ncols)]<res)
80 res=matrix[
POS(i,col,ncols)];
101 static double minimumr(
double* matrix,
int ncols,
int row,
int* col)
107 if(matrix[
POS(row,i,ncols)]<res)
109 res=matrix[
POS(row,i,ncols)];
123 aux=
minimumc(&a[nm2],m,nm2,n+m,&pos);
124 if(file)
fmprint(a,m+1,nm2,file);
125 if(aux<0) err=
simplexd(a,n,m,pos+1,file);
129 if(aux<0) err=
simplexp(a,n,m,pos,file);
136 int simplexp(
double* a,
int n,
int m,
int pos,FILE* file)
138 int nm,pivotc,pivotr,i,j,k,result=0;
139 double pivot,coef,aux,r;
150 if(a[
POS(i,pivotc,k)]>0)
152 r=a[
POS(i,nm,k)]/a[
POS(i,pivotc,k)];
160 if(pivotr==-1) result=1;
163 pivot=a[
POS(pivotr,pivotc,k)];
166 a[
POS(pivotr,i,k)]/=pivot;
172 coef=-a[
POS(i,pivotc,k)];
174 a[
POS(i,j,k)]+=coef*a[
POS(pivotr,j,k)];
178 coef=-a[
POS(0,pivotc,k)];
179 a[
POS(pivotr,nm+1,k)]=pivotc;
182 a[
POS(0,i,k)]+=coef*a[
POS(pivotr,i,k)];
183 if(a[
POS(0,i,k)]<aux)
189 if(file)
fmprint(a,m+1,k,file);
197 int simplexd(
double* a,
int n,
int m,
int pos,FILE* file)
199 int pivotc,pivotr,nm,i,j,k,result=0;
200 double aux,pivot,r,coef;
212 if(a[
POS(pivotr,i,k)]<0)
214 r=a[
POS(0,i,k)]/a[
POS(pivotr,i,k)];
222 if(pivotc==-1) result=1;
225 pivot=a[
POS(pivotr,pivotc,k)];
228 a[
POS(pivotr,i,k)]/=pivot;
230 aux=a[
POS(pivotr,nm,k)];
235 coef=a[
POS(i,pivotc,k)]>0?a[
POS(i,pivotc,k)]:-a[
POS(i,pivotc,k)];
238 a[
POS(i,j,k)]+=coef*a[
POS(pivotr,j,k)];
240 if(a[
POS(i,nm,k)]<aux)
247 a[
POS(pivotr,nm+1,k)]=pivotc;
248 if(file)
fmprint(a,m+1,k,file);
Implementation of linear programming functions.
int simplexp(double *a, int n, int m, int pos, FILE *file)
Applies the Simplex algorithm to a primal optimization problem.
#define POS(R, C, NC)
Given a row (R), a column (C), and the number of columns (NC) of a matrix, computes an equivalent 1D ...
static double minimumc(double *matrix, int nrows, int ncols, int col, int *row)
Finds the minimum value of a matrix's column.
static void fmprint(double *matrix, int nrows, int ncols, FILE *file)
Prints a matrix associated to an optimization problem.
static double minimumr(double *matrix, int ncols, int row, int *col)
Finds the minimum value of a matrix's row.
int simplex(double *a, int n, int m, FILE *file)
Applies the Simplex Algorithm to an optimization problem.
int simplexd(double *a, int n, int m, int pos, FILE *file)
Applies the Simplex algorithm to a dual optimization problem.