1. The method

  • In the tableau implementation of the primal simplex algorithm, the right-hand-side column is always nonnegative so the basic solution is feasible at every iteration. For purposes of this section, we will say that the basis for the tableau is primal feasible if all elements of the right-hand side are nonnegative. Alternatively, when some of the elements are negative, we say that the basis is primal infeasible. Up to this point we have always been concerned with primal feasible bases.
  • In this section, a variant of the primal approach, known as the dual simplex method, is considered that works in just the opposite fashion. Until the final iteration, each basis examined is primal infeasible (some negative values on the right-hand side) and dual feasible (all elements in row 0 are nonnegative). At the final (optimal) iteration the solution will be both primal and dual feasible. Throughout the process we maintain dual feasibility and drive toward primal feasibility. For a given problem, both the primal and dual simplex algorithms will terminate at the same solution but arrive there from different directions