- Recommended Practice Problems, 10th edition of Tan's Finite Mathematics
- Web Assign HW
- Due October 18, 2013
- Due October 22, 2013
Terminology
- Standard Maximization Problem
- Slack variables
- Basic variables
- Non-basic variables
- Feasible solutions
- Simplex Tableau
- Simplex Method
Summary
This lengthy section introduces the
Simplex Algorithm, which was developed by George Dantzig in 1939.
The method is too long to give a simple description here, so see the text and the slides for worked out examples.
Here I want to give some thoughts as to what the simplex algorithm does, and how it is related to, and how it is different from
the method of corners from Chapter 3.
Method of Corners: The method of corners tells us that in order to solve a linear programming problem, we need to draw the
region, then find the corners of the region. The we plug each corner point into the objective function. The maximum value is then the
largest value obtained by plugging in these corner points.
What's wrong with this? Why do we need another method?
- LPs with three variables will require finding corners or polyhedra in space, rather than corners of polygons in the plane.
LPs with more than three variables require finding corners of polytopes in higher dimensional space. Since we can't see
in these hihger dimensional spaces, we need to find a non-geometric approach to these problems.
- Even in two dimensions, finding the corners can be hard and time consuming. Suppose an LP has \(20\) constraints.
\(20\) constraints in two variables could give rise to a polygon with up to \(20\) corner points.
Each corner of the feasible region will arise as an intersection between two of the contraints. However, many of the
intersections are NOT corner points to the region. In fact, \(20\) constraints in two variables could give rise to as many as \(190\)
intersection points. So, if you used the method of corners, you would begin by finding \(190\) intersection points. Then you would
have to determine which of those points are corner points. At this point, you will throw out a large number of the intersection points.
This is very wasteful and time consuming.
- Even if you already know all of the corner points of the region, the method of corners can be slow and wasteful. If there are twenty
corners, you must evaluate the objective function at each of these twenty corners. Even if you plugged in nineteen of the twenty corners,
you still can't say much about the solution to the LP.
The
Simplex Algorithm presents a much smarter attack on the problem.
- You begin with a single corner. The simplex algorithm will be able to tell if this corner gives rise to an optimal solution.
- If the above corner does not give rise to an optimal solution, the simplex algorithm will tell us to move to a nearby corner.
The new corner will be "better". For example, in a maximization problem, the objective function will be larger at the new corner than
at the old corner.
- This process repeats until we eventually arrive at the best corner.
In other words, "are we currently the best? If not, find a better one, and repeat until we are the best."
The simplex algorithm is able to make its decisions based purely on algebra (no geometry required) which means this method works
regardless of the number of variables. The simplex algorithm does not require us to know all of the corners. It computes the corners as it
goes along, and it only looks at the corners that it needs to look at.
The above criticism of the method of corners are only valid when either the number of variables or the number of constraints
get large. Is it important to be able to solve LP with large numbers of variables and constraints? YES!
In standard real-life management decisions, there may be several variables attached to each employee, and likewise there may be several
constraints attached to each employee. If the company has \(100\) employees, management may be faced with an LP with \(400\) or so variables
and \(700\) or so constraints!