Name
Algorithm::Simplex - An implementation of the Simplex Algorithm.
Synopsis
Given a linear program formulated as a Tucker tableau, a 2D matrix or ArrayRef[ArrayRef] in Perl, then 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.
Methods
new
Create a new tableau which has a _tableau attibute that is a ArrayRef[ArrayRef], i.e. two-dimensional array.
set_generic_variable_names_from_dimensions
Create 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.
get_bland_number_for
Given a column number (which represents a u variable) build the bland number from the generic variable name.
determine_bland_pivot_column_number
Find the pivot column using Bland ordering technique to prevent cycles.
determine_bland_pivot_row_number
Find the pivot row using Bland ordering technique to prevent cycles.
min_index
Detemine the index of the element with minimal value. Used when finding bland pivots.
exchange_pivot_variables
Exchange the variables when the a pivot is done. The method pivot does the algrebra while this method does the variable swapping.
set_number_of_rows_and_columns
Given a tableau (matrix), determine its size.
get_row_and_column_numbers
Get the dimensions of the tableau.
determine_bland_pivot_row_and_column_numbers
Higher level functions that uses other to return the (bland) pivot point.
Authors
Mateu X. Hunter hunter@missoula.org
Strong design influence by George McRae at the University of Montana.
License
You may distribute this code under the same terms as Perl itself.
Description
Base class for the Simplex model using Tucker tableaus. It defines some of the methods concretely, and others such as:
pivot
tableau_is_optimal
determine_positive_ratios
determine_simplex_pivot_columns
are implemented in one of the three model types:
Float
Rational
PDL
Limitations
The algorithm requires that the initial tableau be a feasible solution.