LINPROG Function
Solves linear programming problem using the revised simplex algorithm.
Usage
result = LINPROG(a, b, c)
Input Parameters
a—A two-dimensional matrix containing the coefficients of the constraints. The coefficient for the i-th constraint is contained in A (i, *).
b—A one-dimensional matrix containing the right-hand side of the constraints. If there are limits on both sides of the constraints, b contains the lower limit of the constraints.
c—One-dimensional array containing coefficients of objective function.
Returned Value
result—The solution x of the linear programming problem.
Keywords
Bu—An array with N_ELEMENTS(b) elements containing the upper limit of the constraints that have both the lower and the upper bounds. If no such constraint exists, Bu is not needed.
Double—If present and nonzero, double precision is used.
Dual—The name of the variable into which the array with N_ELEMENTS(c) elements, containing the dual solution, is stored.
Irtype—An array with N_ELEMENTS(b) elements indicating the types of general constraints in the matrix A. Let:
ri = Ai0x0 + ... + Ain–1xn–1
The value of Irtype (i) is described in the following list.
0—ri = Bi1—ri ≤ Bu2—ri ≥ Bi3—Bi ≤ ri ≤ Bu(Default: Irtype(*) = 0)Itmax—The maximum number of iterations. (Default: Itmax = 10,000)
Obj—The name of the variable into which the optimal value of the objective function is stored.
Xlb—Array with N_ELEMENTS(c) elements containing the lower bound on the variables. If there is no lower bound on a variable, 1030 should be set as the lower bound. (Default: Xlb(*) = 0)
Xub—Array with N_ELEMENTS(c) elements containing the upper bound on the variables. If there is no upper bound on a variable, –1030 should be set as the upper bound. (Default: Xub(*) = infinity)
Discussion
LINPROG uses a revised simplex method to solve linear programming problems; i.e., problems of the form:
subject to:
where c is the objective coefficient array, A is the coefficient matrix, and the arrays bl, bu, xl, and xu are the lower and upper bounds on the constraints and the variables.
For a complete discussion of the revised simplex method, see Murtagh (1981) or Murty (1983).
Example
The linear programming problem in the standard form:
min f(x) = –x0 – 3x1
and subject to:
x0 + x1 + x2 = 1.5
x0 + x1 + – x3 = 0.5
x0 + x4 = 1.0
x1 + x5 = 1.0
xi ≥ 0, for i = 0, ..., 5
is solved.
; Define the coefficients of the constraints.
RM, a, 4, 6
row 0: 1 1 1 0 0 0
row 1: 1 1 0 -1 0 0
row 2: 1 0 0 0 1 0
row 3: 0 1 0 0 0 1
; Define the right-hand side of the constraints.
RM, b, 4, 1
row 0: 1.5
row 1: .5
row 2: 1
row 3: 1
; Define the coefficients of the objective function.
RM, c, 6, 1
row 0: -1
row 1: -3
row 2: 0
row 3: 0
row 4: 0
row 5: 0
PM, LINPROG(a, b, c), Title = 'Solution'
For Additional Information
Murtagh, 1981.
Murty, 1983.
