Summary of simplex method (for maximization problems)

1. Express your problem in the standard form for a maximization problem:

Objective Function P = c₁x₁+c₂x₂+...+c_nx_n

Problem Constraints a₁x₁+a₂x₂+...+a_nx_n < b

Nonnegativity constraints b, x₁, x₂, ... x_n > 0

The problem is to maximize P (in economics, probably profit), subject to the various constraints.

2. Introduce "slack variables" to "take up the slack" in your inequalities. For example, if you have 2x₁ + x₂ < 20, replace this with 2x₁ + x₂ + s₁ = 20. s₁ is a slack variable which turns the inequality into an equality. These equalities form your initial system, along with the equation -c₁x₁-c₂x₂-...-c_nx_n+P = 0.

3. Write the simplex tableau (a matrix) for the initial system. An example will illustrate. Let's say your initial system looks like this:

2x₁ + x₂ + s₁ = 20
3x₂ + s₂ = 10
-5x₁ -3x₂ + P = 0.

Then your simplex tableau is simply the coefficients of this system. We label the tops of the columns, first with all the x's, then with all the s's, then with P. We label the rows, first with the s's, then with P. This will be important later. Here's the tableau for this system:

4. Find the pivot element (if there is one), the entering variable, and the exiting variable. To do this, find the most negative number in the bottom row (left of column P). The column containing this is called the pivot column. If you find two equally large (in magnitude) negative numbers, it doesn't matter which you choose. Then, divide each positive element in the pivot column above the thinner line into the corresponding number in the last column. The row with the smallest result is the pivot row. Again, it doesn't matter what you do if there is a tie. The pivot element is the number in both the pivot column and the pivot row (i.e. the intersection). In the tableau above, this would be the 2 in the upper left-hand corner. The entering variable is the variable at the top of the pivot column (x₁ in this case) and the exiting variable is the one at left of the pivot row (s₁ in this case).

5. Perform pivoting. This is done by multiplying the pivot row by the reciprocal of the pivot element (in other words, whatever you must multiply by to make the pivot element a 1). The next step is to add multiples of the pivot row to other rows in order to transform the other numbers in the pivot column to 0's. Also, replace the name of the exiting variable with that of the entering variable.

6. Repeat 4 and 5 until the indicators in the bottom row of the simplex tableau are greater than or equal to zero. When this happens, read the optimal solution from the right-hand column. For each number in the right-hand column, look to the left-hand side of the row to find the variable with that value. These should be x's, not s's, because the s's are exiting variables and the x's are entering variables.

Geometrically, to understand what the simplex method is doing you must understand what the constraints are. If you have n variables (x's, not slack variables), each constraint is an n-dimensional "hyperplane." For example, if you have two variables, a constraint represents a line (as in the linear programming section). With three variables, a constraint is a plane. With four variables, a constraint is a 4-dimensional hyperplane, which you can't really visualize.

The area bounded by the planes is the feasible region (just like in 2-D linear programming!) and, just like in linear programming, the optimal solution will be at a corner. Rather than checking every corner, the simplex method quickly jumps from one corner to another, always moving in the right direction (the choice of the pivot element assures this). A detailed explanation of why this works is beyond the scope of this article, but may appear on EconoStocks in the future.

In practice one does not usually work through the steps of the simplex method by hand; computer programs do this. This allows linear maximization problems to be solved very quickly. For one implementation, as well as many other maximization and minimization routines, refer to Numerical Recipes [in C, in Fortran, in Pascal, or in Basic] by Press, Teukolsky, Vettering, and Flannery (see our bibliography page).