lin_prog
Solves a linear programming problem using the revised simplex algorithm.
NOTE: For double precision, the function lin_prog has generally been superseded by the function linear_programming. Function lin_prog remains in place to ensure compatibility of existing calls. |
Synopsis
#include <imsl.h>
float *imsl_f_lin_prog (int m, int n, float a[], float b[], float c[], …, 0)
The type double function is imsl_d_lin_prog.
Required Arguments
int m (Input)
Number of constraints.
int n (Input)
Number of variables.
float a[] (Input)
Array of size m × n containing a matrix with coefficients of the m constraints.
float b[] (Input)
Array with m components containing the right-hand side of the constraints; if there are limits on both sides of the constraints, then b contains the lower limit of the constraints.
float c[] (Input)
Array with n components containing the coefficients of the objective function.
Return Value
A pointer to the solution x of the linear programming problem. To release this space, use imsl_free. If no solution can be computed, then NULL is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float *imsl_f_lin_prog (int m, int n, float a[], float b[], float c[],
IMSL_A_COL_DIM, int a_col_dim,
IMSL_UPPER_LIMIT, float bu[],
IMSL_CONSTR_TYPE, int irtype[],
IMSL_LOWER_BOUND, float xlb[],
IMSL_UPPER_BOUND, float xub[],
IMSL_MAX_ITN, int max_itn,
IMSL_OBJ, float *obj,
IMSL_RETURN_USER, float x[],
IMSL_DUAL, float **y,
IMSL_DUAL_USER, float y[],
0)
Optional Arguments
IMSL_A_COL_DIM, int a_col_dim (Input)
The column dimension of a.
Default: a_col_dim = n
IMSL_UPPER_LIMIT, float bu[] (Input)
Array with m components containing the upper limit of the constraints that have both the lower and the upper bounds. If no such constraint exists, then bu is not needed.
IMSL_CONSTR_TYPE, int irtype[] (Input)
Array with m components indicating the types of general constraints in the matrix a. Let ri = ai1x1 + … + ainxn. Then, the value of irtype(i) signifies the following:
irtype(i) | Constraint |
0 | ri =bi |
1 | ri ≤bui |
2 | ri ≥bi |
3 | bi ≤ri ≤bui |
Default: irtype = 0
IMSL_LOWER_BOUND, float xlb[] (Input)
Array with n components containing the lower bound on the variables. If there is no lower bound on a variable, then 1030 should be set as the lower bound.
Default: xlb = 0
IMSL_UPPER_BOUND, float xub[] (Input)
Array with n components containing the upper bound on the variables. If there is no upper bound on a variable, then −1030 should be set as the upper bound.
Default: xub = ∞
IMSL_MAX_ITN, int max_itn (Input)
Maximum number of iterations.
Default: max_itn = 10000
IMSL_OBJ, float *obj (Output)
Optimal value of the objective function.
IMSL_RETURN_USER, float x[] (Output)
Array with n components containing the primal solution.
IMSL_DUAL, float **y (Output)
The address of a pointer y to an array with m components containing the dual solution. On return, the necessary space is allocated by imsl_f_lin_prog. Typically, float *y is declared, and &y is used as an argument.
IMSL_DUAL_USER, float y[] (Output)
A user-allocated array of size m. On return, y contains the dual solution.
IMSL_USE_UPDATED_LP_ALGORITHM (Input)
Calls the function imsl_d_linear_programming to solve the problem. If this optional argument is present, then the optional argument IMSL_MAX_ITN is ignored. This optional argument is only valid in double precision.
Description
The function imsl_f_lin_prog uses a revised simplex method to solve linear programming problems, i.e., problems of the form
where c is the objective coefficient vector, A is the coefficient matrix, and the vectors bl, bu, xl, and xu are the lower and upper bounds on the constraints and the variables, respectively.
For a complete description of the revised simplex method, see Murtagh (1981) or Murty (1983).
Examples
Example 1
The linear programming problem in the standard form
is solved.
#include <imsl.h>
int main()
{
int m = 4;
int n = 6;
float a[ ] = {1.0, 1.0, 1.0, 0.0, 0.0, 0.0,
1.0, 1.0, 0.0, -1.0, 0.0, 0.0,
1.0, 0.0, 0.0, 0.0, 1.0, 0.0,
0.0, 1.0, 0.0, 0.0, 0.0, 1.0};
float b[ ] = {1.5, 0.5, 1.0, 1.0};
float c[ ] = {-1.0, -3.0, 0.0, 0.0, 0.0, 0.0};
float *x;
/* Solve the LP problem */
x = imsl_f_lin_prog (m, n, a, b, c, 0);
/* Print x */
imsl_f_write_matrix ("x", 1, 6, x, 0);
}
Output
X
1 2 3 4 5 6
0.5 1.0 0.0 1.0 0.5 0.0
Example 2
The linear programming problem in the previous example can be formulated as follows:
This problem can be solved more efficiently.
#include <imsl.h>
#include <stdio.h>
int main()
{
int irtype[ ] = {3};
int m = 1;
int n = 2;
float xub[ ] = {1.0, 1.0};
float a[ ] = {1.0, 1.0};
float b[ ] = {0.5};
float bu[ ] = {1.5};
float c[ ] = {-1.0, -3.0};
float d[1];
float obj, *x;
/* Solve the LP problem */
x = imsl_f_lin_prog (m, n, a, b, c,
IMSL_UPPER_LIMIT, bu,
IMSL_CONSTR_TYPE, irtype,
IMSL_UPPER_BOUND, xub,
IMSL_DUAL_USER, d,
IMSL_OBJ, &obj,
0);
/* Print x */
imsl_f_write_matrix ("x", 1, 2, x,
0);
/* Print d */
imsl_f_write_matrix ("d", 1, 1, d,
0);
printf("\n obj = %g \n", obj);
}
Output
X
1 2
0.5 1.0
D
-1
obj = -3.5
Warning Errors
IMSL_PROB_UNBOUNDED | The problem is unbounded. |
IMSL_TOO_MANY_ITN | Maximum number of iterations exceeded. |
IMSL_PROB_INFEASIBLE | The problem is infeasible. |
Fatal Errors
IMSL_NUMERIC_DIFFICULTY | Numerical difficulty occurred (moved to a vertex that is poorly conditioned). If float is currently being used, using double precision may help. |
IMSL_BOUNDS_INCONSISTENT | The bounds are inconsistent. |