This website uses Flash animations. Flash was deprecated in 2020 and I am using the Ruffle Flash Emulator to make the content available. While it mostly works, you may need to use the Forward button to play the animations.
One chapter of the Finite Mathematics course that often gives students problems is the chapter on Linear Programming. The purpose of this project is to explain the different techniques of solving a linear programming problem. The process starts out with the geometric approach of shading a system of linear inequalities, moves to a table of intersecting lines, and ends with the simplex process using matrices. This project will provide a cohesive and clear migration path through the different techniques.
An extra portion at the end explains how the movement between intersection points works.
What is it that you should know and be able to do once you've worked through this site? Check out the goals and objectives.
This site contains Flash animations and Cascading Style Sheets (CSS). Most modern browsers (MSIE 6+, Netscape 7+, Firefox, Safari, Opera) should work as long as you have the Flash Player loaded. The website is coded to XHTML 1.0 Strict standards, so some of the fanciness or tricks of other websites is not present. For example, the assessment tool doesn't open in a new window like Respondus intended. You may need to click on a Flash animation to activate it.
Your objective in a linear programming problem is to maximize or minimize an objective function subject to some constraints. The constraints take the form of linear inequalities, hence the name "linear" in the type of problem.
A typical linear programming problem looks like this.
| Maximize | P | = | 40x | + | 30y | ||
|---|---|---|---|---|---|---|---|
| Subject to: | x | + | 2y | ≤ | 16 | ||
| x | + | y | ≤ | 9 | |||
| 3x | + | 2y | ≤ | 24 | |||
| x | , | y | ≥ | 0 |
The function P is called the objective function, the first three inequalities are called problem constraints because they usually come from the story problem, and x ≥ 0 and y ≥ 0 are called non-negativity constraints.
This problem will be utilized throughout the entire explanation.
The geometric approach to a linear programming problem involves sketching a feasible region, which is the solution to the system of linear inequalities.
The first step is to sketch the feasible region.
A bounded feasible region may be enclosed in a circle. A bounded feasible region will have both a maximum value and a minimum value.
An unbounded feasible region can not be enclosed in a circle. If the coefficients on the objective function are all positive, then an unbounded feasible region will have a minimum but no maximum.
An empty feasible region will have no maximum or minimum values.
The fundamental theorem of linear programming says that if there is a solution, it occurs on the boundary of the feasible region, not on the inside.
There are two ways that we can determine the optimal solution.
What we have looked at so far works pretty well when there are only two decision variables, but it's pretty ugly when you go to three or four or even more variables. This section is designed to show how to create that table of corner points without having to actually sketch the feasible region.
Because we're going to have more than two decision variables, we're going to start using subscripted variables instead of x and y. That is, we'll use x1, x2, x3, etc., instead of x and y.
Learn more about the table approach to linear programming.
So far, the techniques we've been using will work for any linear programming problem, whether it is a maximization or minimization problem. There is a technique that can be used to completely eliminate the graphing technique and the table technique, but it only works with a standard maximization problem.
A standard maximization problem is a linear programming problem that seeks to maximize the objective function where all problem constraints are less than or equal to a non-negative constant. The objective function may have coefficients that are any real numbers.
The simplex method works only for standard maximization problems.
We've now eliminated the need to make a graph at all and we can find the optimal solution only by making a table of all the intersections. But there are a lot of points out there. The number of intersection points is found by taking a combination of the number of equations two (since there are two decision variables) at a time. nC2 = n(n-1)/2, where n is the number of variables. Each x is a decision variable and each constraint gives a slack variable. So a system with three x variables and three constraints has six variables, which would have 6C3 = 20 intersection points. A system with four variables and five constraints would have 9 variables for 9C4 = 126 intersection points. Most of the intersection points are not in the feasible region, so that's a lot of extra calculation for no reason.
There is a better way. It's called the Simplex method. It uses a matrix and some row operations to make sure that we skirt around the edge of the feasible region until we obtain the maximum value.
See an example with three decision variables.
The first two steps are actually preliminary to the Simplex method. The Simplex method begins with step 3.
The instructor has written a pivot program for the TI-82, 83, 84, 85, or 86 calculators that will speed things up immensely for you.
The pivot program will perform all of the row operations needed to make the pivot element a one and clear out the pivot column. It does not pick the pivot row or column for you.
You will need to have the initial tableau displayed on the screen before running the pivot program.
Watch the Flash video: Using the Pivot Program to Perform the Simplex Method [501 KB]
The instructor has written a simplex program for the TI-82, 83, 84, 85, or 86 calculators that is even better than the pivot program.
The Simplex program will perform the entire simplex method for you when you have a standard maximization problem. It picks the pivot row and column and then performs the pivot procedure to clear out the pivot column. It even tells you when the procedure is done and you have your final tableau.
You will need to have the initial tableau displayed on the screen before running the simplex program.
Watch the Flash video: Using the Simplex Program to Perform the Simplex Method [492 KB]
Hopefully you've learned how each corner point corresponds to a tableau. That can be extended to points outside the feasible region as well, although there would be little reason to do that in this case. Each tableau corresponds to an intersection point.
Each intersection point is identified by its non-basic equations. In two dimensions, each non-basic equation represents a line and each intersection point is the intersection of two lines. In three dimensions, each non-basic equation represents a plane and each intersection point is the intersection of three planes.
If you want to follow a particular path, then you need to look at the non-basic variables for the point where you're at and the non-basic variables for the point to which you're moving. If these points are connected by a line segment (edge), then there will only be one variable difference. The variable that is non-basic at the current point but not at the destination point is the entering variable and will identify the pivot column. The variable that wasn't non-basic to begin with but is at the destination point is the exting variable and will identify the pivot row.
For example, if you want to move from point A where the non-basic variables are s3 = 0 and s4 = 0 to the point B where s1 = 0 and s4 = 0, then s3 is entering and s1 is exiting. I know that sounds backwards, but remember that entering and exiting refer to the basic variables and we're working with the non-basic variables. Pivot on the s3 column and the s1 row.
Here is another, perhaps less confusing, way to look at this. The pivot column represents the line (plane) you are leaving and the pivot row represents the line (plane) you are moving to. If you want to move from point A where the non-basic variables are s3 = 0 and s4 = 0 to the point B where s1 = 0 and s4 = 0, then you are leaving the s3=0 line, so pick s3 for the pivot column and moving to the s1=0 line, so pick s1 for the pivot row.
Use the Flash tool: The Graph, the Tableau, and the Pivot [15 KB] to understand how this all ties together.
The following assessments questions in these five categories.
There are two methods of assessment. They each contain the same questions, the manner of presentation is different.