This Simple Pivot Tool was developed by Robert Vanderbei at Princeton University to solve linear programming (LP) problems. The given tableau is for an LP with a maximization objective:
\[\begin{array}{llcl}
\text{max} & \zeta & = & p^T x \\
\text{s.t.} & Ax & \leq & b \\
& x & \geq & 0
\end{array}\]
\[\begin{array}{llcl}
\text{max} & \zeta & = & p^T x\\
\text{s.t.} & w & = & b-Ax \\
& w & \geq & 0 \\
& x & \geq & 0
\end{array}
\]
Solve a Linear Programming Problem
Set up an instance
By default, problems are assumed to have four variables and three constraints. To solve a problem of a different size, edit the two text fields to specify the number of rows and the number of columns you want. You can click on Generate Random Problem to quickly get a random problem or you can enter data elements into each text field to define a specific problem.
Select options
- Seed: The seed value controls how random problems are generated. With the default value of zero, the random number generator is seeded according to the system clock. Specifying a nonzero seed value gives random problems that can be repeated by starting over with the same seed value.
- Labels: The labels menu allows you to select the labels for the variable names, making it easy to set up some standard variants of the simplex method. If the dual labels are chosen and the seed value is nonzero, then the matrix entries will be the negative transpose of the values one would get with primal labels.
- Variable Names: The variable names are editable. To change the name of one of the xj‘s, just click on it as it appears in the objective function. Similarly, to change the name of a slack variable, wi, just click on the variable as it appears on the left side of its defining equation.
Complete the pivots
- Select a column with a positive coefficient in the \(\zeta\) row as the pivot column.
- For each row in the pivot column, calculate the ratio: divide the value of the right-hand side (\(b\)) by the coefficient of the pivot column element. Do this computation only for terms in the row with positive coefficients.
- Select the row with the smallest ratio as the pivot row. To make the pivot, click on the corresponding variable button in the tool.
- Continue the steps until all of the coefficients of the non-basic variables are less than or equal to zero. Primal infeasible right-hand side coefficients are highlighted in fuscia (after the first pivot) as are dual infeasible cost coefficients. When all of the fuscia cells are gone, the dictionary is optimal.
- Unboundedness occurs when a pivot column exists but there is no corresponding pivot row. Infeasibility occurs when a basic variable is assigned a negative value.
Links
Click here for a fancier version of the pivot tool, which includes artificial primal and dual objectives that enable one to do two phase methods directly with the tool. Click here for the Java Applet version of the same tool.