LibRCG  3.1.1
rlp.c File Reference

Implementation of linear programming functions. More...

Go to the source code of this file.

Macros

#define POS(R, C, NC)   ((R)*(NC)+(C))
 Given a row (R), a column (C), and the number of columns (NC) of a matrix, computes an equivalent 1D position. More...
 

Functions

static void fmprint (double *matrix, int nrows, int ncols, FILE *file)
 Prints a matrix associated to an optimization problem. More...
 
static double minimumc (double *matrix, int nrows, int ncols, int col, int *row)
 Finds the minimum value of a matrix's column. More...
 
static double minimumr (double *matrix, int ncols, int row, int *col)
 Finds the minimum value of a matrix's row. More...
 
int simplex (double *a, int n, int m, FILE *file)
 Applies the Simplex Algorithm to an optimization problem. More...
 
int simplexp (double *a, int n, int m, int pos, FILE *file)
 Applies the Simplex algorithm to a primal optimization problem. More...
 
int simplexd (double *a, int n, int m, int pos, FILE *file)
 Applies the Simplex algorithm to a dual optimization problem. More...
 

Detailed Description

Implementation of linear programming functions.

Author
Rui Carlos Gonçalves
Version
3.0
Date
07/2012

Definition in file rlp.c.

Macro Definition Documentation

#define POS (   R,
  C,
  NC 
)    ((R)*(NC)+(C))

Given a row (R), a column (C), and the number of columns (NC) of a matrix, computes an equivalent 1D position.

Definition at line 18 of file rlp.c.

Function Documentation

static void fmprint ( double *  matrix,
int  nrows,
int  ncols,
FILE *  file 
)
static

Prints a matrix associated to an optimization problem.

The file file, where the matrix will be printed, must be opened before calling this function.

Parameters
matrixthe matrix to print
nrowsthe number of rows
ncolsthe number of columns
filewhere the tables will be printed

Definition at line 31 of file rlp.c.

static double minimumc ( double *  matrix,
int  nrows,
int  ncols,
int  col,
int *  row 
)
static

Finds the minimum value of a matrix's column.

Parameters
matrixthe matrix
nrowsthe number of rows
ncolsthe number of columns
colthe column index
rowpointer where the row that contains the minimum value will be put
Returns
minimum value of the specified column

Definition at line 72 of file rlp.c.

static double minimumr ( double *  matrix,
int  ncols,
int  row,
int *  col 
)
static

Finds the minimum value of a matrix's row.

Parameters
matrixthe matrix row
ncolsthe number of columns
rowthe row index
colpointer where the row that contains the minimum value will be put
Returns
minimum value of the specified row

Definition at line 101 of file rlp.c.

int simplex ( double *  a,
int  n,
int  m,
FILE *  file 
)

Applies the Simplex Algorithm to an optimization problem.

Given a problem with n variables (x1, ..., xn) and m conditions (c1 = b1, ..., cm = bm), the function must receive a matrix a of size (m+1)*(n+m+2), containing:

  • at a[0][i-1] (for i in [1, n]) the coefficient of variable xi in the expression to minimize;
  • at a[0][i] (for i in [n, n+m+1]) the value 0;
  • at a[i][j-1] (for i in [1, m], and for j in [1, n]) the coefficient of variable xj in condition ci;
  • at a[i][j] (for i in [1, m], and for j in [n, n+m-1]) the identity matrix;
  • at a[i][n+m] (for i in [1, m]) the value of bi;
  • at a[i][n+m+1] (for i in [1, m]) the value of n+i.

Allows to specify the file where the table resulting from the application of the algorithm (using the parameter file).

Parameters
amatrix that represents the problem
nnumber of variable of the function
mnumber restrictions
filefile where the tables will be saved (or NULL)
Returns
0 if it is possible to solve the problem
1 otherwise

Definition at line 118 of file rlp.c.

int simplexd ( double *  a,
int  n,
int  m,
int  pos,
FILE *  file 
)

Applies the Simplex algorithm to a dual optimization problem.

The input matrix (a) must follow the format defined in function simplex.

Allows to specify the file where the table resulting from the application of the algorithm (using the parameter file).

Parameters
amatrix that represents the problem
nnumber of variables of the function
mnumber restrictions
posposition of the minimum value of the first row (it must be a negative value)
filefile where the tables will be saved (or NULL)
Returns
0 if it is possible to solve the problem
1 otherwise

Definition at line 197 of file rlp.c.

int simplexp ( double *  a,
int  n,
int  m,
int  pos,
FILE *  file 
)

Applies the Simplex algorithm to a primal optimization problem.

The input matrix (a) must follow the format defined in function simplex.

Allows to specify the file where the table resulting from the application of the algorithm (using the parameter file).

Parameters
amatrix that represents the problem
nnumber of variables of the function
mnumber restrictions
posposition of the minimum value of the restrictions' column (it must be a negative value)
filefile where the tables will be saved (or NULL)
Returns
0 if it is possible to solve the problem
1 otherwise

Definition at line 136 of file rlp.c.

LibRCG © 2004-2015   Rui Carlos Gonçalves