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

\[\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 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*x*'s, just click on it as it appears in the objective function. Similarly, to change the name of a slack variable,_{j}*w*, just click on the variable as it appears on the left side of its defining equation._{i}

#### General Guidelines

- 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.
- 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.
- 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.