 |
Linear
Programming
Solves a minimization or maximization Linear Programming problem
(via a NAG procedure). (See a
refinery optimization problem.) |
|
|
| Max or
Min |
|
Objective: minimisation or maximisation. |
| nConstr, nVar |
|
Constraints (rows, as below) and structural
variables. |
| ItMax, MsgLvl |
|
Iteration limit and print level.† • |
| Cvec |
|
Coefficients in the objective function. • |
| Constraints |
|
Constraint constants and coefficients (in the form
below).
Symbols:
"<" means "≤"; i means
∞. |
| Solves a Linear Programming (LP)
problem (or linear program). The algorithm used is not Dantzig's
simplex method —pedagogically recommended—, but a
black-box NAG implementation based on an "inertia-controlling method"
[Gill et al., 1991]. An LP problem consists of a linear function,
the objective function, to be minimized or maximized,
subject to linear constraints. Here, these are of the form
Li ≤ ∑j=1,n
ai,j xi,j ≤ Ui,
for j = 1..m
where m (nConstr) is the number of constraints and n (nVar)
is the number of (non-negative) variables. (General variables may be
created as differences of non-negative ones.)
In the constraint box above, only the L's,
the a's and the U's must be supplied. Equality constraints
are made by setting the lower bound, L, and the upper bound,
U, equal. "Infinity" (∞) is 1020.
† "Iteration limit": 0, no limit (recommended).
"Print level": 0, no output; 1, final solution; 5, intermediate
solutions; 10, both. |
|
References or suggested reading:
• Dantzig, George
(1914–2005)
• Gill,
P. E. et al., 1991, "Inertia-controlling methods for general
quadratic programming", SIAM Rev., 33,
pp 1–36.
• Hillier, Frederick S., Gerald
J. Lieberman, 2005,
"Introduction to Operations Research", 8.th ed., McGraw-Hill,
New York, NY.
• Hillier, Frederick S., Gerald J.
Lieberman, 2004,
"Introduction to Operations Research", 8.th ed., McGraw-Hill,
New York, NY.
• NAG Fortran
Library Routine Document: E04MMF/A(.pdf). |
