In Chapter 7, we looked at examples of linear programming (LP) problems that contained two decision variables. With only two variables, it is possible to use a graphical approach. We plotted the feasible region and then searched for the optimal corner point and corresponding profit or cost. This approach provides a good way to understand the basic concepts of LP. Most real-life LP problems, however, have more than two variables and are thus too large for the simple graphical solution procedure. Problems faced in business and government can have dozens, hundreds, or even thousands of variables. We need a more powerful method than graphing, so in this module we turn to a procedure called the simplex method.

How does the simplex method work? The concept is simple, and it is similar to graphical LP in one important respect. In graphical LP, we examine each of the corner points; LP theory tells us that the optimal solution lies at one of them. In LP problems containing several variables, we may not be able to graph the feasible region, but the optimal solution will still lie at a corner point of the many-sided, many-dimensional figure (called an n-dimensional polyhedron) that represents the area of feasible solutions. The simplex method examines the corner points in a systematic fashion, using basic algebraic concepts. It does so in an iterative manner—that is, repeating the same set of procedures time after time until an optimal solution is reached. Each iteration brings a higher value for the objective function so that we are always moving closer to the optimal solution.

Why should we study the simplex method? It is important to understand the ideas used to produce solutions. The simplex approach yields not only the optimal solution to the decision variables and the maximum profit (or minimum cost) but valuable economic information as well. To be able to use computers successfully and to interpret LP computer printouts, we need to know what the simplex method is doing and why.

We begin by solving a maximization problem using the simplex method. We then tackle a minimization problem and look at a few technical issues that are faced when employing the simplex procedure. From there, we examine how to conduct sensitivity analysis using the simplex tables. The module concludes with a discussion of the dual, which is an alternative way of looking at any LP problem.