12.38 math.simplex - Simplex solver

Module: math.simplex ¶

Implements the simplex algorithm to solve linear programming problems.

Function: simplex-solve A b goal c ¶

{math.simplex} A is an m x n array of numbers, b is a sequence of m numbers, c is a sequence of n numbers, and goal is either :maximize or :minimize. Returns an f64vector x of length n, such that it maximizes or minimizes the inner product c . x, while satisfying the constraint Ax <= b and x >= 0.

The array can be any type of arrays (see gauche.array - Arrays) and the two sequences can be any type of sequence, as far as they only contain real numbers. Internally it uses f64vector and f64array for calculation. The arguments aren’t mutated during computation.

You can have negative entries in b; the procedure uses two-phase simplex method in that case.

If you have a ’>=’ constraint, you can negate both sides to make it a ’<=’ constraint. If you have an equality in the constraint, you can either use it to reduce one variable, or add both ’>=’ and ’<=’ constraints.

If there can be multiple solutions, the procedure returns one of them. If there’s no solutions, it returns #f.

;; Maximize x1 + x2 under constraints of
;;     x1 + 0.5*x2 <= 2.0   and
;;   3*x1 +   2*x2 <= 12.0

(simplex-solve '#,(<array> (0 2 0 2) 1 0.5 3 2)
               '#f64(2.0 12.0)
               :maximize '#(1 1))

  ⇒ #f64(0.0 4.0)