LA04 — Sparse linear programming: steepest-edge simplex method

Version 1.2.0

User documentation

Fortran

Single
Double

LA04 Sparse linear programming: steepest-edge simplex method

This package uses the simplex method to solve the linear programming problem

minimize c^{T} x = \sum_{j = 1}^{n} c_{j} x_{j}

subject to the constraints

A x = b, that is, \sum_{j = 1}^{n} a_{i j} x_{j} = b_{i}, i = 1, 2, . . . m

l_{j} \leq x_{j} \leq u_{j}, 1 \leq j \leq k,

(1)

x_{j} \geq 0, l \leq j \leq n .

The variables $x_{j}$ , $k + 1 \leq j \leq l - 1$ , if any, are free (have no bounds). Full advantage is taken of any zero coeﬃcients $a_{i j}$ . The inequalities $0 \leq k < l \leq n + 1$ must hold. Special values $l_{i} = - σ$ and $u_{i} = σ$ may be used in (1) to remove one or both bounds.

To accommodate roundoﬀ, all variables are permitted to lie slightly outside their bounds.

Precision: At least 8-byte arithmetic is recommended.