Advanced Pivot Tool

Back to Simplex Method Tools

This Advanced 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}\]

or equivalently

\[\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


Current Dictionary:

  

        

 

    


Set up an instance

By default, problems are assumed to have three constraints and four variables. 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.
  • Method: The method menu allows you to select an appropriate variant of the simplex method for your problem.
  • 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.

General Guidelines

  1. To make a pivot, click on the variable button that you want to pivot around. If you click on a button associated with a zero pivot element, the applet will complain.
  2. 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.
  3. Notice that the tableau includes an artificial objective row ($\zeta_0$) and an artificial right-hand side column ($x_0$), which can be used to guide pivot choices for either a primal or a dual phase one process. When generating a random problem, the coefficients in the artificial row are set to -1. Hence, this row represents a dual feasible objective function. Similarly, the artificial column is initialized to +1 and therefore represents a primal feasible objective. When pivoting, any infeasibilities that occur in these artificial row/columns are highlighted in yellow.

Links

  • Click here for further hints on how to use the applet.
  • Click here for a simpler version of the pivot tool that is designed for use when either the primal or the dual initial dictionary is feasible.
  • Click here for the Java Applet version of this tool.

Optimization Category (Linear Programing, Integer, MIP and etc.):