Macro Library simplex
Simplex method with mixed constraints solver
Mike Jenck, Originally developed May 16-26, 2014
licensed under GPL version 2 or later
File Version : 43
***** Internal Functions *****
***** DEPRECIATED Functions *****
function simplex(type, objective, constraints)
Creates and returns a new simplex matrix. elements are fractions
stored in the form of an array(numerator, denominator).
INPUTS:
type: a string that contains either "max" or "min"
objective: list or array of the coefficients
constraints: an array that contains the inequality information. Constraints are composed of
three parts:
first part is a list or array of the coefficients in the inequality
second part is the inequality '<=' or '>='
third part is the right hand number
Examples
objective function: f = x1+7x2+5x3
$objective = array(1,7,5)
or
$objective = "1,7,5"
constraint inequality: 3x1+x3 <= 35
$constraints[0] = array(array(3,1,0),"<=",35)
or
$constraints[0] = array("3,1,0","<=",35)
first part: array(3,0,1) or "3,0,1"
second part: "<="
third part: 35
use simplexdisplaytable() to create a string that can be used for display
simplexchecksolution(type,HasObjective,solutionlist,stuanswer, [ismixed=FALSE])
INPUTS:
type: a string that contains either "max" or "min"
HasObjective: either 0 or 1
default 0 Objective value is not included in the stuanswer array
1 Objective value is included and is the last column in the stuanswer array
solutionlist: an array of solutions (in the case of multiple solutions). In the form of
solutionlist[0] = array(solution values for matrix[0], IsOptimized)
solutionlist[1] = array(solution values for matrix[1], IsOptimized)
etc.
This is returned from simplexsolve
ismixed: an optional flag for the function that tells the routine to read max values instead of min ones for mixed constraints
default is FALSE
stuanswer: the answer the student submitted
RETURNS: 0 if no match is found, 1 if a match is found
function simplexcreateanswerboxentrytable(rows, cols, [startnumber, matrixname, linemode, header, tablestyle])
Create a string that is a valid HTML table syntax for displaying answerboxes.
INPUTS:
rows: number of rows to make
cols: number of columns to make
optional
startnumber: the starting number for the answerbox. Default is 0
matrixname: a string that holds the matrix name, like A or B. This does not contain
tick marks or brackets - if you want them you need to supply them.
default empty string
linemode: Show none, augmented, or simplex, value is either 0, 1 or 2
0 show no lines
1 show augmented line
default 2 show simplex lines
header: list or array of the variables "x1,x2,x3" that are used for the column titles.
default none
tablestyle: for any additional styles for the table that you may want. like "color:#40B3DF;"
default none
RETURNS: valid HTML table syntax for displaying answerboxes
function simplexcreateinequalities(type, objectivevariable, objective, constraints, [headers, displayASCIIticks, showfractions, includeinequalities] )
Creates an array of string that correspond to each line of the simple inequalities
INPUTS:
type: a string that contains either "max" or "min"
objectivevariable: the name of the objective function, like f of g.
objective: list or array of the coefficients
constraints: an array that contains the inequality information. Constraints are in the
form of array(array(3,1,0),"<=",35)
constraint first part is a list or array of the coefficients in the inequality
constraint second part is the inequality *<= or >=)
constraint third part is the number on the other side of the inequality
OPTIONAL
headers: list or array of the variables names to use
default "x1,x2,x3, ..." for max
default "y1,y2,y3, ..." for min
displayASCIIticks: put tick marks around each element of the table, either 0 or 1.
0 do not use math ticks
default 1 use math ticks
Use 0 if you are building an answerbox matrix.
showfractions: either 0 or 1
0 shows decimals
default 1 shows fractions
includeinequalities: either 0 or 1
0 does append the inequality and right hand sinde number ("<=",35)
default 1 include the full inequality
RETURNS: an array of strings
simplexcreatelatexinequalities()
function simplexcreateinequalities(type, objectivevariable, objective, constraints, [headers, displayASCIIticks, showfractions, includeinequalities] )
Creates an array of string that correspond to each line of the simple inequalities in latex form
INPUTS:
type: a string that contains either "max" or "min"
objectivevariable: the name of the objective function, like f of g.
objective: list or array of the coefficients
constraints: an array that contains the inequality information. Constraints are in the
form of array(array(3,1,0),"<=",35)
constraint first part is a list or array of the coefficients in the inequality
constraint second part is the inequality *<= or >=)
constraint third part is the number on the other side of the inequality
OPTIONAL
headers: list or array of the variables names to use
default "x1,x2,x3, ..." for max
default "y1,y2,y3, ..." for min
showfractions: either 0 or 1
0 shows decimals
default 1 shows fractions
includeinequalities: either 0 or 1
0 does append the inequality and right hand sinde number ("<=",35)
default 1 include the full inequality
RETURNS: an array of strings
function simplexconverttodecimals(simplexmatrix)
simplexmatrix: a valid simplex matrix.
this function takes the simplex matrix and converts all elements to decimals
(usefull when displaying the matrix)
function simplexconverttofraction(simplexmatrix)
simplexmatrix: a valid simplex matrix.
this function takes the simplex matrix and converts all elements to fractions
using "/" as the fraction bar (usefull when displaying the matrix)
function simplexdebug(simplexmatrix)
simplexmatrix: a valid simplex matrix.
a raw echo dump of the contents of the simplex matrix
Not intended to be used in question. This is to allow the question writer the ability to see what the
raw values are for each field. all values should have a "|" between them, in the form of
numerator | denominator.
function simplexdefaultheaders(simplexmatrix,type)
INPUTS
simplexmatrix: a valid simplex matrix.
type: a string that contains either "max" or "min"
creates the default header (x1,x2, ...,s1,s2,...) for max and
(x1,x2, ...,y1,y2,...) for min.
RETURNS: a string
simplexdisplaycolortable(simplexmatrix, [simplexmatrixname, displayASCIIticks, linemode, showentriesfractions=1, $pivot = array(-1,-1 ["blue","black"]), $header = array(), tabletextcolor = "black"])
Create a string that is a valid HTML table syntax for display.
INPUTS
simplexmatrix: a valid simplex matrix.
OPTIONAL
simplexmatrixname: a string that holds the matrix name, like A or B. You should leave balnk if you
are creating a simplex display
displayASCII: either 0 or 1
0 do not use math ticks
default 1 use math ticks
mode: either 0, 1 or 2
0 show no lines
1 show aumented line
2 show simplex lines
showfractions: either -1, 0 or 1
-1 show as string
0 convert simplex element to a decimal
default 1 convert simplex element to a fraction using "/" as the fraction bar
pivot: list or array that contains the row, column, border color, and text color. This puts a
border around the cell at (row,col). Both row and column are ZERO based.
default point none
default border color = blue
default text color = black
headers: list or array of the variables "x1,x2,x3" that are used for the column titles.
default none
tabletextcolor: text color for the table
default black
RETURNS: a string that is a valid HTML table syntax for display.
simplexdisplaylatex(simplexmatrix, [simplexmatrixname, showentriesfractions=1, $pivot = array(-1,-1)])
Create a string that is a valid latex syntax for display.
INPUTS
simplexmatrix: a valid simplex matrix.
OPTIONAL
simplexmatrixname: a string that holds the matrix name, like A or B. You should leave balnk if you
are creating a simplex for display
showfractions: either 0 or 1
0 convert simplex element to a decimal
default 1 convert simplex element to a \displaystyle\frac{}{}
pivot: list or array that contains the row, column. This puts a circle around the cell at (row,col).
Both row and column are ZERO based.
default point none
RETURNS: a valid latex string
simplexdisplaylatex2(simplex solution sets [, show$pivot=1, showentriesfractions=1])
Creates an array of strings that is valid latex syntax for display.
INPUTS
simplex solution sets: a valid solution sets array
OPTIONAL
showpivot :either 0 or 1
0 don't circle a pivot point
default 1 circle a pivot point
showfractions: either 0 or 1
0 convert simplex element to a decimal
default 1 convert simplex element to a \displaystyle\frac{}{}
RETURNS: a solution sets of valid latex
simplexdisplaytable2(simplex solution sets[, ASCII tick marks,mode,show fractions,header column names,CSS tabletextcolor=black, multiple solution pivot border color=red, multiple solution pivot text color=blue, pivot border color=blue, pivot text color=black)
Create a 1 or two dimensional array (depends on the input) that each element either contains a valid valid HTML table syntax or
a nbsp; for displaying in a browser.
INPUTS
simplex solution sets: a valid solution sets array
OPTIONAL
displayASCII: either 0 or 1
0 do not use math ticks
default 1 use math ticks
mode: either 0, 1 or 2
0 show no lines
1 show aumented line
2 show simplex lines
showfractions: either -1, 0 or 1
-1 show as string
0 convert simplex element to a decimal
default 1 convert simplex element to a fraction
headers: list or array of the variables "x1,x2,x3" that are used for the column titles.
default none
tablestyle: for any additional styles for the table that you may want. like "color:#40B3DF;"
default none
RETURNS: an array
simplexdisplaytable2string(simplexsetstable, cellpadding=5)
Creates a string used to display all pivot paths of the simplex matrix for displaying in a browser.
INPUTS
simplexsetstable: output from simplexdisplaytable2
cellpadding: cellpadding in the table for each cell
RETURNS: a string for displaying (usually in showanswer).
)
simplexfindpivotpoint(simplexmatrix)
INPUTS
simplexmatrix: a valid simplex matrix.
returns array(condition, pivotpoints )
where
condition: -1 means No Solution
0 found pivot point(s)
1 means no pivot points found
2 found possible multiple solution pivot point(s)
pivotpoints: an array where the entries are the row, column where the pivot point was
found. Both row and column are ZERO based.
$pivotpoints[0] = (0,1)
$pivotpoints[1] = (1,2)
simplexfindpivotpointmixed(simplexmatrix)
INPUTS
simplexmatrix: a valid simplex matrix.
returns array(condition, pivotpoints )
where
condition: -2 means Nnot a mixed constraint
-1 means No Solution
0 found pivot point(s)
1 means no pivot points found
2 found possible multiple solution pivot point(s)
pivotpoints: an array where the entries are the row, column where the pivot point was
found. Both row and column are ZERO based.
$pivotpoints[0] = (0,1)
$pivotpoints[1] = (1,2)
simplexgetentry(simplexmatrix,row,col)
gets an entry from the simplex matrix
INPUTS
simplexmatrix: a valid simplex matrix.
row: row number (zero based - first row is row 0)
col: column number (zero based - first row is row 0)
RETURNS: entry from a simplex matrix at given row and col
simplexpivot(simplexmatrix,pivotpoint)
this function pivots the simplex matrix on the given point
INPUTS
simplexmatrix: a valid simplex matrix.
pivotpoint: list or array that contains the point to be pivoted on.
Both row and column are ZERO based.
RETURNS: the pivoted simplex matrix
function simplexreadtoanswerarray(simplexmatrix, [startnumber, answer])
Create/extend an array of values read by rows for the simplex matrix starting at startnumber
INPUTS
simplexmatrix: a valid simplex matrix.
OPTIONAL
startnumber: starting number of the array. Default is 0
answer: pass $answer if extending an existing $answer array
RETURNS: an array
simplexreadsolution(simplexmatrix,type,showfractions)
This reads the simplex matrix to find the current solution to the optimization problem. It returns
an array that contains the solution.
INPUTS
simplexmatrix: a valid simplex matrix.
type: a string that contains either "max" or "min"
showfractions: either 0 or 1
0 shows decimals
default 1 shows fractions
RETURNS: an array(solution values for sm, IsOptimized)
For Max solutions the solution is an array in the form of:
x1, x2, etc, s1, s2, etc., f, IsOptimized
where f contains the maximum value
IsOptimized contains either a Yes or a No (objective has been reached)
For Min solutions the solution is an array in the form of:
x1, x2, etc, y1, y2, etc., g, IsOptimized
where g contains the minimium value
IsOptimized contains either a Yes or a No (objective has been reached)
simplexreadsolutionarray(simplexmatrix,type,showfractions)
This reads the simplex matrix to find the current solution to the optimization problem. It returns
an array that contains the solution.
INPUTS
simplexmatrix: a valid simplex matrix.
type: a string that contains either "max" or "min"
showfractions: either 0 or 1
0 shows decimals
default 1 shows fractions
RETURNS: an array(solution values for sm, IsOptimized)
For Max solutions the solution is an array in the form of:
x1, x2, etc, s1, s2, etc., f, IsOptimized
where f contains the maximum value
IsOptimized contains either a Yes or a No (objective has been reached)
For Min solutions the solution is an array in the form of:
x1, x2, etc, y1, y2, etc., g, IsOptimized
where g contains the minimium value
IsOptimized contains either a Yes or a No (objective has been reached)
simplexsetentry(simplexmatrix,row,col,numerator,denominator)
set entry for the simplex matrix at the given row and col with the given numerator and denominator.
INPUTS
simplexmatrix: a valid simplex matrix.
row: row number (zero based - first row is row 0)
col: column number (zero based - first row is row 0)
numerator: any integer
denominator any natural number
RETURNS: nothing
simplexsolutiontolatex(solution)
This function converts all fractions in the solution into latex fractions
\displaystyle\frac{numerator}{denominator}
INPUTS
solution - an array of "fractions" in the form of array(numerator, denominator)
RETURNS: an array of valid latex
simplexsolve2(simplexmatrix,type,[showfractions=1])
Mixed constraints
this method solves the minimization problem which has the following conditions
1) The objective function is to be minimized.
2) All variables are nonnegative.
3) The constraints are of the form: a1x1+ a2x2+ ... + anxn >= b where b is any constant
INPUTS:
simplexmatrix: a valid simplex matrix.
type: a string that contains either "max" or "min"
showfractions: either 0 or 1
0 shows decimals
default 1 shows fractions
RETURNS (simplexsets[][], $objectivereachedsolutionlist, runtime)
simplexsets[][] = a 2 dimensional array used to build an output for the various paths that could be used to solve the simple
parent column number: column of the parent simplex (zero based).
Pivot Point Condition:
pivot point: point that will be pivoted on
pivot points: array of all possible pivots
simplexmatrix: simplex matrix to pivot on
solution: the solution to the simplex matrix
| 0 | 1 | 2 |
0 | simplex (1 pivot) intial matrix | | |
1 | simplex (2 pivot) | | |
2 | simplex (1st pivot option from (1,0)) | | simplex (2nd pivot option from (1,0)) |
3 | simplex (2 pivot) | | simplex (1 pivot) |
4 | simplex (1st pivot option from (3,0)) | simplex (2nd pivot option from (3,0))| simplex (1 pivot) |
5 | simplex (0 pivot) | simplex (0 pivot) | simplex (0 pivot) |
simplexver()
This function returns the internal version number of the simplex file
INPUTS: None
RETURNS: the file verion number
*********************************************************************************************************************************
*********************************************************************************************************************************
internal utility functions needed for this module
*********************************************************************************************************************************
*********************************************************************************************************************************
createsimplexelement
simplextoarray
simplextodisplay
verifyconstraints
function createsimplexelement($value)
internal only
returns an array in the form of (numerator, denominator) that is calculated from $value
$value can be any valid real number, that will be converted into a fraction (proper or improper).
function simplextoarray(sm)
this function takes the simplex matrix and verifies that each entry is a
array in the form of (numerator, denominator)
then returns the verified simplex matrix.
the following are the verify functions to verify user input
the from is a string of the calling function, then the input to be
verified, then the program supplied default value
function verifyconstraints(type, constraints)
internal only
This function verifies that all of the constraints are vaild inequalities
type: max or min
constraints: the constraints to be verified
function hasmixedconstraints(constraints)
internal only
This function returns true if mixed constraints are found
false if all are the same type
simplexfindsolutioninlist(solutionlist,solution)
Trys to find the solution if it is already in the solution list.
INPUTS
solutionlist: an array of solutions (in the case of multiple solutions). In the form of
solutionlist[0] = array(solution values for matrix[0], IsOptimized)
solutionlist[1] = array(solution values for matrix[1], IsOptimized)
etc.
This is returned from simplexsolve
solution = array(solution values for matrix, IsOptimized)
RETURNS: 0 if no match is found, 1 if a match is found
simplexhasmixedconstrants($sm)
INPUTS:
$sm - a simpex matrix
RETURNS - true is it is a mixed contrant matrix
false - otherwise
***** DEPRECIATED *****
list of all DEPRECIATED functions are below
***** DEPRECIATED *****
simplexdisplaytable(simplexmatrix, [simplexmatrixname, displayASCIIticks, linemode, showentriesfractions=1, $pivot = array(-1,-1 ["blue","black"]), $header = array(), $tablestyle = ""])
***** DEPRECIATED *****
USE simplexdisplaycolortable instead
Create a string that is a valid HTML table syntax for display.
INPUTS
simplexmatrix: a valid simplex matrix.
OPTIONAL
simplexmatrixname: a string that holds the matrix name, like A or B. You should leave balnk if you
are creating a simplex display
displayASCII: either 0 or 1
0 do not use math ticks
default 1 use math ticks
mode: either 0, 1 or 2
0 show no lines
1 show aumented line
2 show simplex lines
showfractions: either -1, 0 or 1
-1 show as string
0 convert simplex element to a decimal
default 1 convert simplex element to a fraction using "/" as the fraction bar
pivot: list or array that contains the row, column, border color, and text color. This puts a
border around the cell at (row,col). Both row and column are ZERO based.
default point none
default border color = blue
default text color = black
headers: list or array of the variables "x1,x2,x3" that are used for the column titles.
default none
tablestyle: for any additional styles for the table that you may want. like "color:#40B3DF;"
default none
RETURNS: a string that is a valid HTML table syntax for display.
simplexnumberofsolutions(solutionlist)
***** DEPRECIATED *****
solutionlist: an array of solutions (in the case of multiple solutions). In the form of
solutionlist[0] = array(solution values for matrix[0], IsOptimized)
solutionlist[1] = array(solution values for matrix[1], IsOptimized)
etc.
This is returned from simplexsolve
returns: the number of solutions
simplexsolve(simplexmatrix,type)
***** DEPRECIATED *****
use simplexsolve2
this method solves the standard maximization problem which has the following conditions
1) The objective function is to be maximized.
2) All variables are nonnegative.
3) The constraints are of the form: a1x1+ a2x2+ ... + anxn <= b where b >0
INPUTS
simplexmatrix: a valid simplex matrix.
type: a string that contains either "max" or "min"
RETURNS array(solutionlist, smlist, pivotlist)
solutionlist: an array of solutions (in the case of multiple solutions). In the form of
solutionlist[0] = array(solution values for matrix[0], IsOptimized)
solutionlist[1] = array(solution values for matrix[1], IsOptimized)
etc.
smlist: an array of simplex matrix with
sma[0] = initial simplex matrix
sma[1] = the result of the first pivot
sma[2] = the result of the second pivot
sma[3] = the result of the third pivot
etc.
pivotlist: an array of pivot points
pivotlist[0][0] = the pivot used for the first pivot
pivotlist[0][1] = if exists, another possible pivot point for this step
pivotlist[1][0] = the pivot used for the second pivot
pivotlist[2][0] = the pivot used for the third pivot
etc.