DLPRS

 

   more...

Solves a linear programming problem via the revised simplex algorithm.

Required Arguments

A — M by NVAR matrix containing the coefficients of the M constraints. (Input)

BL — Vector of length M containing the lower limit of the general constraints; if there is no lower limit on the I-th constraint, then BL(I) is not referenced. (Input)

BU — Vector of length M containing the upper limit of the general constraints; if there is no upper limit on the I-th constraint, then BU(I) is not referenced; if there are no range constraints, BL and BU can share the same storage locations. (Input)

C — Vector of length NVAR containing the coefficients of the objective function. (Input)

IRTYPE — Vector of length M indicating the types of general constraints in the matrix A. (Input)
Let R(I) = A(I, 1) * XSOL(1) + … + A(I, NVAR) * XSOL(NVAR). Then, the value of IRTYPE(I) signifies the following:

IRTYPE(I)	I-th Constraint
0	BL(I).EQ.R(I).EQ.BU(I)
1	R(I).LE.BU(I)
2	R(I).GE.BL(I)
3	BL(I).LE.R(I).LE.BU(I)

OBJ — Value of the objective function. (Output)

XSOL — Vector of length NVAR containing the primal solution. (Output)

DSOL — Vector of length M containing the dual solution. (Output)

Optional Arguments

M — Number of constraints. (Input)
Default: M = SIZE (A,1).

NVAR — Number of variables. (Input)
Default: NVAR = SIZE (A,2).

LDA — Leading dimension of A exactly as specified in the dimension statement of the calling program. (Input)
LDA must be at least M.
Default: LDA = SIZE (A,1).

XLB — Vector of length NVAR containing the lower bound on the variables; if there is no lower bound on a variable, then 1.0E30 should be set as the lower bound. (Input)
Default: XLB = 0.0.

XUB — Vector of length NVAR containing the upper bound on the variables; if there is no upper bound on a variable, then -1.0E30 should be set as the upper bound. (Input)
Default: XUB = 3.4e38 for single precision and 1.79d + 308 for double precision.

FORTRAN 90 Interface

Generic: CALL DLPRS (A, BL, BU, C, IRTYPE, OBJ, XSOL, DSOL [, …])

Specific: The specific interface names are S_DLPRS and D_DLPRS.

FORTRAN 77 Interface

Single: CALL DLPRS (M, NVAR, A, LDA, BL, BU, C, IRTYPE, XLB, XUB, OBJ, XSOL, DSOL)

Double: The double precision name is DDLPRS.

Description

The routine DLPRS 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).

Comments

1. Workspace may be explicitly provided, if desired, by use of D2PRS/DD2PRS. The reference is:

CALL D2PRS (M, NVAR, A, LDA, BL, BU, C, IRTYPE, XLB, XUB, OBJ, XSOL, DSOL, AWK, LDAWK, WK, IWK)

The additional arguments are as follows:

AWK — Real work array of dimension 1 by 1. (AWK is not used in the new implementation of the revised simplex algorithm. It is retained merely for calling sequence consistency.)

LDAWK — Leading dimension of AWK exactly as specified in the dimension statement of the calling program. LDAWK should be 1. (LDAWK is not used in the new implementation of the revised simplex algorithm. It is retained merely for calling sequence consistency.)

WK — Real work vector of length M * (M + 28).

IWK — Integer work vector of length 29 * M + 3 * NVAR.

2. Informational errors

 

Type	Code	Description
3	1	The problem is unbounded.
4	2	Maximum number of iterations exceeded.
3	3	The problem is infeasible.
4	4	Moved to a vertex that is poorly conditioned; using double precision may help.
4	5	The bounds are inconsistent.

Example

A linear programming problem is solved.

 

USE DLPRS_INT

USE UMACH_INT

USE SSCAL_INT

 

IMPLICIT NONE

INTEGER LDA, M, NVAR

PARAMETER (M=2, NVAR=2, LDA=M)

! M = number of constraints

! NVAR = number of variables

!

INTEGER I, IRTYPE(M), NOUT

REAL A(LDA,NVAR), B(M), C(NVAR), DSOL(M), OBJ, XLB(NVAR), &

XSOL(NVAR), XUB(NVAR)

!

! Set values for the following problem

!

! Max 1.0*XSOL(1) + 3.0*XSOL(2)

!

! XSOL(1) + XSOL(2) .LE. 1.5

! XSOL(1) + XSOL(2) .GE. 0.5

!

! 0 .LE. XSOL(1) .LE. 1

! 0 .LE. XSOL(2) .LE. 1

!

DATA XLB/2*0.0/, XUB/2*1.0/

DATA A/4*1.0/, B/1.5, .5/, C/1.0, 3.0/

DATA IRTYPE/1, 2/

! To maximize, C must be multiplied by

! -1.

CALL SSCAL (NVAR, -1.0E0, C, 1)

! Solve the LP problem. Since there is

! no range constraint, only B is

! needed.

CALL DLPRS (A, B, B, C, IRTYPE, OBJ, XSOL, DSOL, &

XUB=XUB)

! OBJ must be multiplied by -1 to get

! the true maximum.

OBJ = -OBJ

! DSOL must be multiplied by -1 for

! maximization.

CALL SSCAL (M, -1.0E0, DSOL, 1)

! Print results

CALL UMACH (2, NOUT)

WRITE (NOUT,99999) OBJ, (XSOL(I),I=1,NVAR), (DSOL(I),I=1,M)

!

99999 FORMAT (//, ' Objective = ', F9.4, //, ' Primal ',&

'Solution =', 2F9.4, //, ' Dual solution =', 2F9.4)

!

END

Output

 

Objective = 3.5000

 

Primal Solution = 0.5000 1.0000

 

Dual solution = 1.0000 0.0000