Linear Programming

Introduction

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.

Goals and Objectives

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.

Prerequisites for Viewing Site

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.

The Linear Programming Problem

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

The geometric approach to a linear programming problem involves sketching a feasible region, which is the solution to the system of linear inequalities.

Sketch the Feasible Region

The first step is to sketch the feasible region.

Existence of Solutions

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.

Fundamental Theorem of Linear Programming

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.

Determine the Optimal Solution

There are two ways that we can determine the optimal solution.

  1. Make a table of corner points
  2. Use the slope of the objective function

The Table Approach

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.

Standard Maximization Problems

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

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.

Learn the Simplex method.

See an example with three decision variables.

Summary of the Simplex Method

Flowchart of Simplex Method
  1. Convert the problem into the initial system by adding slack variables.
  2. Convert the initial system into the initial tableau.
  3. The pivot column is the column with the most negative value in the objective function. If there are no negatives, stop, you're done.
  4. Find the ratios between the non-negative entries in the right hand side and the positive entries in the pivot column. If there are no positive entries, stop, there is no solution.
  5. The pivot row is the row with the smallest non-negative ratio. Zero counts as a non-negative ratio.
  6. Pivot where the pivot row and pivot column meet.
  7. Go back to step 3 until there are no more negatives in the bottom row.

The first two steps are actually preliminary to the Simplex method. The Simplex method begins with step 3.

Using the Pivot Program on the Calculator to Perform the Simplex Method

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]

Using the Simplex Program on the Calculator to Perform the Simplex Method

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]

Can You Get There from Here?

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.

Assessment

The following assessments questions in these five categories.

  1. Basic: Questions dealing with basic and non-basic variables and their values.
  2. Labels: Decide the proper way to label the columns and rows.
  3. Simplex: Determine where to pivot and what will happen if you do.
  4. Slope: Use the slope to determine where the maximum will occur.
  5. Variables: Understand the relationship between the number of decision and slack variables and the size of the tableau.

There are two methods of assessment. They each contain the same questions, the manner of presentation is different.

  1. Practice Quiz - This multiple choice quiz gives you access to all the questions, but unfortunately, the questions aren't clearly identified by section, so you don't know which of the five areas above you're answering a question about and sometimes that can make it difficult (especially in the areas of simple vs multiple regression).
  2. Challenge - This multiple choice game is set up in a fashion similiar to the Jeopardy game. You may have either one or two players and the categories are identified so you know what the question is about.