Algorithm::Simplex - An implementation of the Simplex Algorithm.
Given a linear program formulated as a Tucker tableau, a 2D matrix or ArrayRef[ArrayRef] in Perl, seek an optimal solution.
my $initial_tableau =
[
[ 8, 3, 4, 40 ],
[ 40, 10, 10, 200 ],
[ 160, 60, 80, 0 ],
];
my $final_tableau_object = solve_LP('rational', $initial_tableau);
See the t/example_LPs.t for usage examples. In particular, study the solve_LP subroutine.
set the number of rows
set the number of columns given the tableau matrix
Set x variable names for the given tableau.
Given a column number (which represents a u variable) build the bland number from the generic variable name.
Find the pivot column using Bland ordering technique to prevent cycles.
Find the pivot row using Bland ordering technique to prevent cycles.
Detemine the index of the element with minimal value. Used when finding bland pivots.
Exchange the variables when the a pivot is done. The method pivot does the algrebra while this method does the variable swapping (and thus tracking).
Get the dimensions of the tableau.
Higher level function that uses others to return the (bland) pivot point.
Mateu X. Hunter hunter@missoula.org
Strong design influence by George McRae at the University of Montana.
#moose for solid assistance in the refactor: particularly _build_* approach and PDL + Moose namespace management, 'inner'.
You may distribute this code under the same terms as Perl itself.
Base class for the Simplex model using Tucker tableaus. It defines some of the methods concretely, and others such as:
are implemented in one of the three model types:
We have implicit variable names: x1, x2 ... , y1, y2, ... , u1, u2 ... , v1, v2 ...
Our variables are represented by:
x, y, u, and v
as found in Nering and Tuckers' book.
x and y are for the primal LP while u and v belong to the dual LP.
These variable names are set during BUILD of the tableau object.
The API is going to change.
The algorithm requires that the initial tableau be a feasible solution.
