DLPRS
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:
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).
Default: M = SIZE (A,1).
NVAR — Number of variables. (Input)
Default: NVAR = SIZE (A,2).
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).
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.
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.
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
