### LA04 Sparse linear programming: steepest-edge simplex method

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

$$\text{minimize}{c}^{T}x=\sum _{j=1}^{n}{c}_{j}{x}_{j}$$
subject to the constraints

$$Ax=b,\text{thatis,}\sum _{j=1}^{n}{a}_{ij}{x}_{j}={b}_{i},i=1,2,...m$$

$${l}_{j}\le {x}_{j}\le {u}_{j},1\le j\le k,$$ | (1) |

$${x}_{j}\ge 0,l\le j\le n.$$

The variables ${x}_{j}$,
$k+1\le j\le l-1$, if
any, are free (have no bounds). Full advantage is taken of any zero coeﬃcients
${a}_{ij}$. The inequalities
$0\le k<l\le n+1$ must hold.
Special values ${l}_{i}=-\sigma $
and ${u}_{i}=\sigma $
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.