Math 120, Chapter 4

Linear Programming: The Simplex Method

Chapter 3 in the textbook introduced the basic ideas of linear programming through the graphical method. However, this method is limited to two decision variables. The simplex method overcomes this limitation but requires considerable effort by the student to understand. The purpose of these pages is to help in obtaining that understanding. To achieve this goal we follow an example from beginning to end.

The simplex method starts with the selection of one corner point (often the origin) from the feasible region. Then, in a systematic way, a neighboring corner point is found that improves the value of the objective function. We continue until an optimum solution is found or it is apparent that none exists. Here is our example. Write it down on a sheet of paper.

Maximize z = 4x1+3x2
Subject to:2x1+x2£40
x1+x2£30
x1 £15
wherex1andx2³0

This is a standard maximizing problem. All the decision variables must be nonnegative and the constraints "less than or equal to". The constants on the righthand side are not negative. Also note that this problem can be solved by the graphical method since there are but two decision variables. We will use the graphical method to give us insight into the simplex method. Below is the graph of the feasible region.

feasible?

Where do you find the corner points of the feasible region? More importantly, how do you find the corner points? A corner point is found where two lines (including the axes) intersect. But note that two of the lines above intersect at (15,15) which is outside the feasible region. We can "see" this. A computer does not have access to this visual information and must be provided with a numerical procedure (the simplex method) to determine which intersections are feasible.

Wherever two lines cross there corresponds a basic solution. If the intersection point is in the feasible region, then there corresponds a basic feasible solution. Solutions to what? A SYSTEM OF LINEAR EQUATIONS! Where is this system of equations? All I see are inequalities. Let's produce these equations. Each constraint of the problem can be turned into an equation by introducing a slack variable.

Consider the first constraint 2x1 + x2 £ 40. Since the variables are nonnegative, the quantity on the left side must be smaller than (or equal to) the quantity on the right side. There is some "slack". If the left side is 30, then the slack is 10. If the left side is 15, then the slack is 25. We let s1 be a variable that takes on these slack values. Thus, we now have the equation 2x1 + x2 + s1 = 40

If different slack variables ( s1, s2, s3 ) are introduced into the three constraints, then we get the following system of equations.

2x1+x2+ s1 = 40
x1+x2 + s2 = 30
x1 + s3= 15

Hmmmm.... There are more variables (five) than equations (only three). From what we learned in Chapter 2, there must be an infinite number of solutions or none at all. But if all the original decision variables are set to zero (we are at the origin) and the slack variables take on their largest possible values (40, 30, and 15), then we have at least one solution. Thus, there must be infinitely many solutions! How can a computer find them all? We're not interested in all of them. Why? Because most of the solutions correspond to being in the interior of the feasible region, or in the exterior of the feasible region, not on the boundary where the corner points are located. How can we ensure that a solution to this system corresponds to a corner point? By forcing two of the five variables to be zero and checking that the others are not negative!

Corner points are found by setting two of the five variables equal to zero and solving for the others provided all of the variables are nonnegative. If this is the case, then these solutions are called basic feasible solutions.

Here is a table of all the basic feasible solutions and their corresponding corner points. You should verify that each of the basic feasible solutions listed satisfy the system of equations. Also, note that the basic solution (but not feasible) given by (15,15,-5,0,0) corresponds to the point of intersection (15,15) mentioned earlier. It is not in the feasible region.

Do you see why?

2x1+x2+ s1 = 40
x1+x2 + s2 = 30
x1 + s3= 15
 Yields Þ
Basic feasible solutionCorner point
(0,0,40,30,15)(0,0)
(0,30,10,0,15)(0,30)
(15,0,10,15,0)(15,0)
(15,10,0,5,0)(15,10)
(10,20,0,0,5)(10,20)

In the next lessons you will learn how to produce the basic feasible solutions from the system of linear equations in a straightforward manner. But first some questions.

Exercises

  1. What makes a solution a basic solution?
  2. Plug in the point (15,15,-5,0,0) into the system of equations and verify that it is a basic solution.
  3. What makes a solution a basic feasible solution?
  4. Find ALL the basic feasible solutions to the following system of linear equations (all variables must be nonnegative, and exactly two of the variables must be zero). Hint: Trial and error.
    x1-x2+x3 = 3
    x2 +x4= 4
  5. Why exactly two variables equal to zero?

Return to Index Return to top of page Proceed to Next Lesson