Recap of the Simplex Method
- Convert your LP to standard form if necessary.
- If the right-hand sides of the constraints are all non-negative, add
slack variables, write the initial dictionary (by solving for the
slack variables) and skip to Phase 2, otherwise perform Phase 1.
- Phase 1.
- Form the auxiliary LP by adding a variable \(x_0\) that you
subtract from all the left-hand sides of constraints and by
replacing the objective function with \(w = - x_0\).
- Add slack variables and write down the initial dictionary, which
will be infeasible.
- Perform the special pivot to feasibility and then successive
standard pivots until you reach an optimal solution of the
auxiliary LP (this is guaranteed to happen!).
- If the optimal value is negative, then original LP is
infeasible. If the optimal value is zero, then the final
dictionary for the auxiliary LP furnishes a starting dictionary
for Phase 2: set \(x_0=0\) in the top part of the dictionary and
replace the \(w\)-row by the result of plugging in this top part
into the formula for the original objective function \(z\).
- Phase 2. Repeatedly perform standard pivots until either you
reach an optimal solution (when all coefficients or variables in
the \(z\)-row are \(\le 0\)) or you see the LP is unbounded (when
there is a choice of entering variable upon which no basic variable
imposes a limit).