This solver allows one to enter a linear programming problem in English (or Spanish), then parses and solves it. To see it in action, open the demo file in a browser, and press the "Examples" button.
Using it in your own code
Using the solver involves four steps:
- Create an lpProblem object and specify the LP problem to solve.
- Set flags describing the kind of problem or the kind of output you want.
- Call solve().
- Retrieve the solution.
Creating an lpProblem
You create a new lpProblem object with
p = new lpProblem();
The constructor takes an optional argument, another lpProblem object to copy. If you don't copy an existing object, you'll next want to specify the LP problem to solve. This can be done in one of several ways:
Specify the LP problem as a string.
p.problemStr to a full LP problem, given as a string. The string must have the form
Maximize <linear objective> subject to <linear constraints separated by commas or line breaks>
Maximize can be replaced by
minimize and Spanish can be used as well. If you want to constrain one or more variables to have integer values, add the following at the end of the string:
integer <comma separated list of variables>
Specify linear expressions using juxtaposition for multiplication, so
2x + 3y, not
>= to specify inequalities. The objective function may be specified as a linear expression or as an equation specifying the name of the objective function, like
p = 2x + 3y. Constraints should have the form
<linear expression> <= <number> where the inequality could also be
=. Do not put commas in numbers.
Specify the LP problem by setting the objective and constraint properties.
p.objectiveto a string representing the objective function, in the form
[max|min]imize [var =] <linear expression>.
p.constraintsto an array of strings representing the constraints.
- If you are solving an integer or mixed problem, set
p.integerUnknownsto an array of unknown names that should be constrained to be integers.
p.modecan be set to
lp_Integralfor all tableaus to have integer entries and solutions to be given as fractions
lp_Fractionfor all tableaus to have fractional entries and solutions to be given as fractions
lp_Decimalfor tableaus and solutions to be given using decimal notation.
false, in which case the slack and surplus variables are not shown as part of solutions. If set to
true, these variables are reported in solutions.
p.sigDigitsis the number of significant digits to show in decimal mode in tableau entries and solutions. It defaults to 6.
lp_verboseLevelis a global variable controlling what is saved in the global string
lp_trace_stringwhile the problem is being solved. The default is to save nothing. If
lp_verboseLevel = lp_verbosity_tableaus, all intermediate tableaus are saved. If
lp_verboseLevel = lp_verbosity_solutionsthen all tableaus and the corresponding basic solutions are saved. The string saved is HTML, suitable to insert in a
<div>, for example, to display on a web page.
lp_reportErrorsTois a global string controlling how errors are reported. If empty (the default), errors are not reported. If set to
"alert", errors cause alerts to be posted. If set to the ID of an HTML element, errors are inserted in that HTML element on the page.
Once the problem is set up and flags properly set, call
p.solve(), which takes no arguments. If something is wrong with the way the problem was stated, it may throw an error, which will be a string describing the problem. This string will also be available as
Retrieving the solution
p.status, which will be either
lp_optimal if an optimal solution was found, or
lp_no_solution if there was no solution. In the latter case, the property
p.message contains a string indicating why no solution was found.
Assuming a solution was found,
p.tableaus will be an array of all the tableaus generated by the simplex method (see Tableaus below for more information about these tableaus and methods to display them nicely) and
p.solutions will be an array of solutions, each being an array of values for the variables. The property
p.unknowns is an array giving the names of the unknowns in the order in which the values appear in the solutions.
To get the solutions as nicely formatted strings, call one of the following:
p.solutionToString()returns a string showing the solution of the problem, using the settings of
p.lastSolutionToString()is used internally to return the basic solution from the last tableau, which will not necessarily be the solution to the problem if doing integer or mixed programming.
p.formatUnknowns ( includeArtificalVariables )returns an array with the names of the unknowns in the order used in the following functions. The optional argument tells whether to include the slack and surplus variables (default:
p.formatLastSolution ( includeArtificalVariables, mode )returns the solution of the problem as an array of strings giving the values of the variables in the order specified in
p.unknowns. The optional arguments tell whether to include the artificial variables (default:
false) and the mode of solution to show (default: value of
p.formatIntegerSolution ( includeArtificalVariables, mode )is the corresponding routine you should use if doing integer or mixed programming.
p.formatLastObjectiveValue ( mode )returns a string representing the optimal value of the objective function (for non-integer/mixed programming). The mode is optional, defaulting to
p.formatIntegerObjectiveValue ( mode )is the corresponding routine to use when doing integer or mixed programming.
p.formatSolutions ( includeArtificalVariables, mode )is similar to
formatLastSolution, but returns an array of basic solutions, one for each tableau generated by the simplex method.
p.formatObjectiveValues ( mode )is similar to
formatLastObjectiveValuebut returns an array of all the values of the objective function for all of the tableaus.
tableau class extends
Array; tableaus are always two-dimensional arrays. The 0th row contains the variable names corresponding to each column and the 0th column contains the currently active variables corresponding to each row. The actual tableau starts with index , so the matrix itself uses 1-based indexing.
There are three methods added to the
pivot ( row, col, sigDigs )pivots on the entry in
[row][col]and returns a new tableau.
sigDigsis used to mitigate subtractive error and should usually be set to something large, like 13.
toString ( mode, sigDigs )returns an ASCII formatted string representing the tableau. It contains no HTML tags and is suitable for showing in
<pre>tags (but such tags are not part of the string).
modeis one of
sigDigsis used for rounding the entries, so might be something like 6.
toHTML ( mode, sigDigs, params )returns a string of HTML code representing the tableau as a
sigDigsare as for
paramsis an optional argument: If it has a
cellPaddingproperty, that is used to set the padding in the
<table>(default: 10); if it has a
lineColorproperty, that is used to set the color of the lines separating the first and last rows and columns from the rest of the tableau (default: