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