IDL Analyst Reference Guide: Optimization

IMSL_LINPROG

The IMSL_LINPROG function solves a linear programming problem using the revised simplex algorithm.

Syntax

Result = IMSL_LINPROG(a, b, c [, BU=array] [, /DOUBLE] [, DUAL=variable] [, IRTYPE=array] [, ITMAX=value] [, OBJ=variable] [, XLB=array] [, XUB=array])

Return Value

The solution x of the linear programming problem.

Arguments

a

Two-dimensional matrix containing the coefficients of the constraints. The coefficient for the i-th constraint is contained in A (i, *).

b

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 the coefficients of the objective function.

Keywords

BU

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

Name of the variable into which the array with N_ELEMENTS(c) elements, containing the dual solution, is stored.

IRTYPE

Array with N_ELEMENTS(b) elements indicating the types of general constraints in the matrix A. Let r_i = A_i0x₀ + ... + A_in–1 x_n–1. The value of IRTYPE (i) is described in Table 11-1.

Default: IRTYPE (*) = 0

ITMAX

Maximum number of iterations. Default: ITMAX = 10,000

OBJ

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, 10³⁰ 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, –10³⁰ should be set as the upper bound. Default: XUB (*) = infinity

Discussion

The IMSL_LINPROG function uses a revised simplex method to solve linear programming problems; i.e., problems of the form:

subject to:

where c is the objective coefficient vector, A is the coefficient matrix, and the vectors b_l, b_u, x_l, and x_u 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). This problem can be solved more efficiently.

Example

In this example, the linear programming problem in the standard form:

min f(x) = –x₀ – 3x₁

subject to:

is solved.

RM, a, 4, 6  
; Define the coefficients of the constraints.  
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  
RM, b, 4, 1  
; Define the right-hand side of the constraints.  
row 0: 1.5  
row 1:  .5  
row 2: 1  
row 3: 1  
RM, c, 6, 1  
; Define the coefficients of the objective function.  
row 0: -1  
row 1: -3  
row 2:  0  
row 3:  0  
row 4:  0  
row 5:  0  
PM, IMSL_LINPROG(a, b, c), Title = 'Solution'  
; Call IMSL_LINPROG and print the solution.  
Solution  
   0.500000  
   1.00000  
   0.00000  
   1.00000  
   0.500000  
   0.00000