Linear Programming Supplements Supplements are PDF files covering subjects not included in the textbook.
 In this article, a variant of the primal approach, known as the dual simplex method, is considered that works in just the opposite fashion as the primal simplex. 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. For a given problem, both the primal and dual simplex algorithms will terminate at the same solution but arrive there from different directions. In this section, we deal implicitly with the issue of uncertainty in the data elements by determining the bounds over which each such element can range without effecting a change in either the optimal solution or optimal basis. Such investigations fall under the heading of sensitivity analysis. When a solution is obtained for a linear program with the simplex method, the solution to a second model, called the dual problem, is readily available and provides useful information for sensitivity analysis. There are several benefits to be gained from studying the dual problem, not the least of which is that it often has a practical interpretation that enhances the understanding of the original model. Duality also has important implications for the theoretical basis of mathematical programming algorithms. In this section, the dual problem is defined, the properties that link it to the original (called the primal) are listed, and the procedure for identifying the dual solution from the tableau is presented. All forms of the simplex method reach the optimum by traversing a series of basic solutions. Since each basic solution represents an extreme point of the feasible region, the track followed by the algorithm moves around the boundary of the feasible region. In the worst case, it may be necessary to examine most if not all of the extreme points. Interior point methods (IMPs) approach the optimal solution from the strict interior of the feasible region. . IPMs are of interest from a theoretical point of view because they have polynomial complexity, and from a practical point of view because they have produced solutions to many industrial problems that were hitherto intractable.

Operations Research Models and Methods
by Paul A. Jensen & Jonathan F. Bard