LinearProgramming.pl |
topic started 9/14/2004; 2:05:18 PM last post 9/14/2004; 2:05:18 PM |

Michael Gage - LinearProgramming.pl 9/14/2004; 2:05:18 PM (reads: 1653, responses: 0) |

## NAMELinearProgramming.pl
## SYNPOSISMacros related to the simplex method for Linear Programming. lp_pivot_element() - find the pivot element from a tableau Matrix display makes use of macros from PGmatrixmacros.pl, so it
## DESCRIPTIONThese are macros for dealing with simplex tableau for linear Tableaus are expected to be legal for the simplex method, such as [[0, 3, -4, 5, 1, 0, 0, 28], or something similar which arises after pivoting.
## lp_pivotTake 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]]; 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_elementTake 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_solveTake 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) 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_valueTakes 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_mmDisplay 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]]; \[ \{ 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).
## lp_displayDisplay 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]]; \{ lp_display($m)\} 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. ## File path = /ww/webwork/pg/macros/LinearProgramming.pl |