simplex

A naive pure-Ruby implementation of the Simplex algorithm for solving linear programming problems. Solves maximizations in standard form.

Why?

I wrote this because I needed to solve some small allocation problems for a web game I'm writing, and there didn't seem to be any Ruby 2.0 bindings for the "pro" solver libraries, and anyway they are hard to install on Heroku.

• Use it for: small LP problems, when you have trouble loading native or Java solvers, and when you can accept not that great performance.
• Don't use it for: large LP problems, when you have access to native solvers, when you need very fast solving time.

Usage

To solve the linear programming problem:

max x + y

 2x +  y <= 4
  x + 2y <= 3

  x, y >= 0

Like this:

result = Simplex.new(
  [1, 1],       # coefficients of objective function
  [             # matrix of inequality coefficients on the lhs ...
    [ 2,  1],
    [ 1,  2],
  ],
  [4, 3]        # .. and the rhs of the inequalities
).solution