NAME

LinearProgramming.pl - Macros for the simplex tableau for linear programming problems.

SYNPOSIS

Macros related to the simplex method for Linear Programming.

lp_pivot_element(...); # find the pivot element from a tableau
lp_solve(...);         # pivot until done
lp_current_value(...); # given a tableau, find the value of a requested variable
lp_display(...);       # display a tableau
lp_display_mm(...);    # display a tableau while in math mode
lp_pivot(...);         # perform one pivot on a tableau

Matrix display makes use of macros from PGmatrixmacros.pl, so it must be included too.

DESCRIPTION

These are macros for dealing with simplex tableau for linear programming problems. The tableau is a reference to an array of arrays, which looks like, [[1,2,3], [4,5,6]]. The entries can be real numbers or Fractions.

Tableaus are expected to be legal for the simplex method, such as

[[0,  3, -4,  5, 1, 0, 0, 28],
 [0,  2,  0,  1, 0, 1, 0, 11],
 [0,  1,  2,  3, 0, 0, 1,  3],
 [1, -1,  2, -3, 0, 0, 0,  0]]

or something similar which arises after pivoting.

MACROS

lp_pivot

Take a tableau, the row and column number, and perform one pivot operation. The tableau can be any matrix in the form reference to array of arrays, such as [[1,2,3],[4,5,6]]. Row and column numbers start at 0. An optional 4th argument can be specified to indicate that the matrix has entries of type Fraction (and then all entries should be of type Fraction).

$m = [[1,2,3],[4,5,6]];
lp_pivot($m, 0,2);

This function is destructive - it changes the values of its matrix rather than making a copy, and also returns the matrix, so

$m = lp_pivot([[1,2,3],[4,5,6]], 0, 2);

will have the same result as the example above.

lp_pivot_element

Take a simplex tableau, and determine which element is the next pivot element based on the algorithm in Mizrahi and Sullivan's Finite Mathematics, section 4.2. The tableau must represent a point in the region of feasibility for a LP problem. Otherwise, it can be any matrix in the form reference to array of arrays, such as [[1,2,3],[4,5,6]]. An optional 2nd argument can be specified to indicate that the matrix has entries of type Fraction (and then all entries should be of type Fraction).

It returns a pair [row, col], with the count starting at 0. If there is no legal pivot column (final tableau), it returns [-1,-1]. If there is a column, but no pivot element (unbounded problem), it returns [-1, col].

lp_solve

Take a tableau, and perform simplex method pivoting until done. The tableau can be any matrix in the form reference to array of arrays, such as [[1,2,3],[4,5,6]], which represents a linear programming tableau at a feasible point. Options are specified in key/value pairs.

pivot_limit => 10

limit the number of pivots to at most 10 - default is 100

fraction_mode => 1

entries are of type Fraction - defaults to 0, i.e., false

This function is destructive - it changes the values of its matrix rather than making a copy. It returns a triple of the final tableau, an endcode indicating the type of result, and the number of pivots used. The endcodes are 1 for success, 0 for unbounded.

Example:

$m = [[0,  3, -4,  5, 1, 0, 0, 28],
      [0,  2,  0,  1, 0, 1, 0, 11],
      [0,  1,  2,  3, 0, 0, 1,  3],
      [1, -1,  2, -3, 0, 0, 0,  0]];

($m, $endcode, $pivcount) = lp_solve($m, pivot_limit=>200);

lp_current_value

Takes a simplex tableau and returns the value of a particular variable. Variables are associated to column numbers which are indexed starting with 0. So, usually this means that the objective function is 0, x_1 is 1, and so on. This can be used for slack variables too (assuming you know what columns they are in).

lp_display_mm

Display a simplex tableau while in math mode.

$m = [[0,  3, -4,  5, 1, 0, 0, 28],
      [0,  2,  0,  1, 0, 1, 0, 11],
      [0,  1,  2,  3, 0, 0, 1,  3],
      [1, -1,  2, -3, 0, 0, 0,  0]];

BEGIN_TEXT
\[ \{ lp_display_mm($m) \} \]
END_TEXT

Accepts the same optional arguments as lp_display (see below), and produces nicer looking results. However, it cannot have answer rules in the tableau (lp_display can have them for fill in the blank tableaus).

To use with a MathObject matrix use

\[ \{lp_display_mm([$matrix->value]) \} \]

FIXME?  I've added an adaptor that allows you to use $matrix directly -- MEG

$matrix->value outputs an array (usually an array of array references) so placing it inside square bracket produces and array reference (of array references) which is what lp_display_mm() is seeking.

$matrix, by itself, produces a string representing a matrix. (This will be in TeX if the context has enabled texStrings.

lp_display

Display a simplex tableau while not in math mode.

$m = [[0,  3, -4,  5, 1, 0, 0, 28],
      [0,  2,  0,  1, 0, 1, 0, 11],
      [0,  1,  2,  3, 0, 0, 1,  3],
      [1, -1,  2, -3, 0, 0, 0,  0]];

BEGIN_TEXT
\{ lp_display($m)\}
END_TEXT

Takes the same optional arguments as display_matrix. The default for column alignment as "augmentation line" before the last column. It also adds a horizontal line before the last row if it is not already specified.

math/LinearProgramming.pl