Version 1.2.0

Code Download

  • Single
  • Double

LA04 Sparse linear programming: steepest-edge simplex method

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

minimize cTx = j=1nc jxj

subject to the constraints

Ax = b, that is, j=1na ijxj = bi, i = 1,2,...m

lj xj uj, 1 j k, (1)

xj 0, l j n.

The variables xj, k + 1 j l 1, if any, are free (have no bounds). Full advantage is taken of any zero coefficients aij. The inequalities 0 k < l n + 1 must hold. Special values li = σ and ui = σ may be used in (1) to remove one or both bounds.

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

Precision: At least 8-byte arithmetic is recommended.