Linear Programming Workbench is a free tool for students to manipulate tableaux representing Simplex style linear programming problems. The problems are specified in canonical form using the notation in An Introduction to Linear Programming and Game Theory, Third Edition by . The student can adjust the tableau by pivoting, adjusting variables and constraints.
This tool works in web browsers that have Javascript enabled. Further details about the implementation are discussed below.
Selecting a basis label will display a context menu. The student can change the label of the basis, remove the constraint, add a slack or artifical variable, add a Gomory integer cut, or create branch and bound sub-programs.
Selecting a variable name will also display a context menu which allows the student to remove the variable.
The top left cell in the tableau is the menu. Selecting the menu displays a short list of operations that are available to the student. Primal Mode is used for primal pivoting and Dual Mode is used for dual pivoting. Selecting either of these modes exits from the Edit Mode. To help the student select the correct pivot term these modes display the appropriate ratio. Notice that the student can return to Edit Mode by selecting it on the menu.
Selecting 'Add Constraint' will add another constraint to the tableau. Selecting 'Add Variable' will add another variable to the tableau.
These instructions are accessible on the page by selecting 'Instructions' on the menu. Selecting Example 5 from the menu will replace the existing page with the example from the text.
The student can record a copy of the tableau by selecting 'Copy' on the menu. 'Mark & Copy' is similar but the copy of the tableau is marked. The marked tableau can be recalled later. This is useful during branch and bound calculations.
The most recent tableau can be removed by selecting 'Undo' on the menu. If the student pivots on the wrong term, for example, the resulting incorrect tableau can be removed and the problem continues from the previous step.
Finally, the student can save the current tableau (but not the history) by selecting 'Save' on the menu. This will display the current tableau on a new page without the history. The new page has a unique URL which includes information about the tableau. The student can bookmark the URL to share with an instructor or other students.
Suppose the student has the problem (Section 3.3 from the text):
| Minimize | -4x1 | + | x2 | + | x3 | + | 7x4 | + | 3x5 | = | z | |
| subject to | ||||||||||||
| -6x1 | + | x3 | - | 2x4 | + | 2x5 | = | 6 | ||||
| -3x1 | + | x2 | - | x3 | + | 8x4 | + | x5 | = | 9 | ||
| ∀ xi ≥ 0 |
The student then converts the problem into canonical form using x2 and x3 as basic variables.
| -6x1 | + | x3 | - | 2x4 | + | 2x5 | = | 6 | ||||
| -3x1 | + | x2 | + | 6x4 | + | 3x5 | = | 15 | ||||
| 5x1 | + | 3x4 | - | 2x5 | = | -21 | + z | |||||
| ∀ xi ≥ 0 |
This is the default problem for this tool which has 2 constraints and 5 variables.
Pivoting is the method that the simplex method uses to proceed from a feasible solution to improved feasible solution. When the feasible solution cannot be improved then the problem is solved. There are two styles of pivoting that are used in the simplex method: Primal and Dual. Primal pivoting considers the ratio of the object function coefficients to the various terms. Whereas Dual pivoting considers the ration of the RHS values to the various terms. The student selects a term in the tableau and this tool will execute a pivot and display the resulting updated tableau.
For the sample problem, the student enters 'Primal Mode' and selects the term 2x5 in constraint 1. The selected term is circled and the new revised tableau is displayed. Notice that the calculated terms use fractional notation. Next, the student selects the term 6x1 in constraint 2. Again, the selected term is circled and the new revised tableau is displayed. Also notice that the appropriate ratio is displayed in decimal form to make comparisons easier. In this case, the solution is optimal since all the remaining objective function coefficients are positive. The minimum value is z = 14 at xt = (1, 0, 0, 0, 6).
The tool supports Gomory cuts for solving integer problems. In the default problem change the term x5 of constraint 1 from 2 to 5, and then solve it by pivoting on the term 5x5. The solution moves to xt = (0, 57⁄5, 0, 0, 6⁄5). This is the solution to the so-called relaxed integer problem. Notice that hovering over the RHS values displays the value in decimal format. In this case, the student ought to select constraint 2 for the first cut.
Re-enter Edit Mode, by selecting it on the menu. Then select 'Add Integer Cut' from the basis label context menu on the left side of constraint 2. This modifies the tableau by adding a new slack variable, adding it to the basis, and calculating the new Gomory constraint that excludes the basis variables. Enter Dual Mode to solve this problem and select the term -2⁄5x3 in constraint 3. Now, variables x1 - x5 have integer values xt = (0, 12, 1, 0, 1) and the objective function value is 19.
This instructional tool is written in web standard languages: HTML, CSS and Javascript. The student may need to enable javascript in their web browser for the tool to work properly. It uses the jquery javascript library to support compatibility with most browsers. The layout is designed to work with as many devices as possible: computers, pads and phones. Internally the calculations use double precision floating point arithmatic. Fractional values displayed in the tableau are approximations of these floating point values. Small tolerances are used to identify values that are close to zero.