In Chapter 7, we examined the use of graphical methods to solve LP problems that contained only two decision variables. This module moves us one giant step further by introducing the simplex method. The simplex method is an iterative procedure for reaching the optimal solution to LP problems of any dimension. It consists of a series of rules that, in effect, algebraically examine corner points in a systematic way. Each step moves us closer to the optimal solution by increasing profit or decreasing cost, while maintaining feasibility.

This module explains the procedure for converting less-than-or-equal-to, greater-than-or-equal-to, and equality constraints into the simplex format. These conversions employed the inclusion of slack, surplus, and artificial variables. An initial simplex tableau is developed that portrays the problem’s original data formulations. It also contains a row providing profit or cost information and a net evaluation row. The latter, identified as the $C_j-Z_j$ row, is examined in determining whether an optimal solution has yet been reached. It also points out which variable next enters the solution mix, or basis, if the current solution is nonoptimal.

The simplex method consists of five stpng: (1) identifying the pivot column, (2) identifying the pivot row and number, (3) replacing the pivot row, (4) computing new values for each remaining row, and (5) computing the $Z_j$ and $C_j-Z_j$ rows and examining for optimality. Each tableau of this iterative procedure is displayed and explained for a sample maximization and minimization problem.

A few special issues in LP that arise in using the simplex method are also discussed in this module. Examples of infeasibility, unbounded solutions, degeneracy, and multiple optimal solutions are presented.

Although large LP problems are seldom, if ever, solved by hand, the purpose of this module is to help you gain an understanding of how the simplex method works. Understanding the underlying principles helps you to interpret and analyze computerized LP solutions.

This module also provides a foundation for another issue: answering questions about the problem after an optimal solution has been found, which is called postoptimality analysis, or sensitivity analysis. Included in this discussion is the analysis of the value of additional resources, called shadow pricing. Finally, the relationship between a primal LP problem and its dual is explored. We illustrate how to derive the dual from a primal and how the solutions to the dual variables are actually the shadow prices.