← Previous Summary Next Summary → Review Exercises Textbook Lleveme a la Página Español
 Finite mathematics topic summary: linear programming

Tools: | Pivot and Gauss-Jordan Tool | Excel Pivot and Gauss-Jordan Tool | Simplex Method Tool

Subtopics: Linear Programming (LP) Problem | Sketching the Solution Set of a Linear Inequality | Feasible Region | Graphical Method | Standard Maximization Problem | Simplex Method for Standard Maximization Problem | Basic Solution | Non-Standard Constraints | Simplex Method for Minimization Problem | Solving a Matrix Game Using the Simplex Method

Linear Programming (LP) Problem

A linear programming problem is one in which we are to find the maximum or minimum value of a linear expression

ax + by + cz + . . .
(called the objective function), subject to a number of linear constraints of the form
Ax + By + Cz + . . .≤ N
or
Ax + By + Cz + . . .≥ N.
The largest or smallest value of the objective function is called the optimal value, and a collection of values of x, y, z, . . . that gives the optimal value constitutes an optimal solution. The variables x, y, z, . . . are called the decision variables.

Top of Page
Example

Here is an example of an LP problem:

Find the maximum value of

p = 3x - 2y + 4z
subject to
4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0

The objective function is p = 3x - 2y + 4z. The constraints are

4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0.

Q Wait a minute! Why can't I simply choose, say, z to be really large (z = 1,000,000 say) and thereby make p as large as I want?
A You can't because

Top of Page

Sketching the Solution Set of a Linear Inequality

To sketch the region represented by a linear inequality in two variables:

A. Sketch the straight line obtained by replacing the inequality with an equality.

B. Choose a test point not on the line ((0,0) is a good choice if the line does not pass through the origin, and if the line does pass through the origin a point on one of the axes would be a good choice).

C. If the test point satisfies the inequality, then the set of solutions is the entire region on the same side of the line as the test point. Otherwise it is the region on the other side of the line. In either case, shade out the side that does not contain the solutions, leaving the solution region showing.

Top of Page
Example

To sketch the linear inequality

3x - 4y ≤ 12,
first sketch the line 3x - 4y = 12.

Next, choose the origin (0, 0) as the test point (since it is not on the line). Substituting x = 0, y = 0 in the inequality gives
3(0) - 4(0) ≤ 12.
Since this is a true statement, (0, 0) is in the solution set, so the solution set consists of all points on the same side as (0, 0). This region is left unshaded, while the (grey) shaded region is blocked out.

Top of Page
Feasible Region

The feasible region determined by a collection of linear inequalities is the collection of points that satisfy all of the inequalities.

To sketch the feasible region determined by a collection of linear inequalities in two variables: Sketch the regions represented by each inequality on the same graph, remembering to shade the parts of the plane that you do not want. What is unshaded when you are done is the feasible region.

Top of Page
Example

The feasible region for the following collection of inequalities is the unshaded region shown below (including its boundary).

3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1
y ≥ 0.

Top of Page
Graphical Method

The graphical method for solving linear programming problems in two unknowns is as follows.

1. Graph the feasible region.
2. Compute the coordinates of the corner points.
3. Substitute the coordinates of the corner points into the objective function to see which gives the optimal value. This point gives the solution to the linear programming problem.
4. If the feasible region is not bounded, this method can be misleading: optimal solutions always exist when the feasible region is bounded, but may or may not exist when the feasible region is unbounded.
5. If the feasible region is unbounded, we are minimizing the objective function, and its coefficients are non-negative, then a solution exists, so this method yields the solution.

To determine if a solution exists in the general unbounded case:

1. Bound the feasible region by adding a vertical line to the right of the rightmost corner point, and a horizontal line above the highest corner point.
2. Calculate the coordinates of the new corner points you obtain.
3. Find the corner point that gives the optimal value of the objective function.
4. If this optimal value occurs at a point of the original (unbounded) region, then the LP problem has a solution at that point. If not, then the LP problem has no optimal solution.

If you want to see a utility that automates the whole process, try the They do everything automatically, including drawing the feasible region!

Top of Page
Example

Minimize C = 3x + 4y subject to the constraints

3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1,   y ≥ 0.

The feasible region for this set of constraints was shown above. Here it is again with the corner points shown.

Although the feasible region is unbonded, we are minimizing C = 3x + 4y, whose coefficients are non-negative, and so the method shown above left applies.

The following table shows the value of C at each corner point:

 Point C = 3x + 4y (1, 1.5) 3(1)+4(1.5) = 9 minimum (4, 0) 3(4)+4(0) = 12
Therefore, the solution is x = 1, y = 1.5, giving the minimum value C = 9.

Top of Page
Standard Maximization Problem

A standard maximization problem in n unknowns is a linear programming problem in which we are required to maximize (not minimize) the objective function, subject to constraints of the form

x ≥ 0, y ≥ 0, z ≥ 0, . . . ,
and further constraints of the form
Ax + By + Cz + . . . ≤ N,
where A, B, C, . . . and N are numbers with N nonnegative.

Note that the inequality here must be a "≤," and not "=" or "≥."

Top of Page
Examples

The following is a standard maximization problem:

Maximize P = 2x - 3y + z subject to

4x - 3y + z ≤ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.

The following is not a standard maximization problem:

Maximize P = 2x - 3y + z subject to

4x - 3y + z ≥ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.

Top of Page
Simplex Method for Standard Maximization Problem

To solve a standard maximization problem using the simplex method, we take the following steps:

Step 1. Convert to a system of equations by introducing slack variables to turn the constraints into equations, and rewriting the objective function in standard form.

Step 2. Write down the initial tableau.

Step 3. Select the pivot column: Choose the negative number with the largest magnitude in the bottom row (excluding the rightmost entry). Its column is the pivot column. (If there are two candidates, choose either one.) If all the numbers in the bottom row are zero or positive (excluding the rightmost entry), then you are done: the basic solution maximizes the objective function (see below for the basic solution).

Step 4. Select the pivot in the pivot column: The pivot must always be a positive number. For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in the Answer column in that row. Of these test ratios, choose the smallest one. The corresponding number b is the pivot.

Step 5. Use the pivot to clear the column in the normal manner (taking care to follow the exact prescription for formulating the row operations described in the tutorial on the Gauss Jordan method,) and then relabel the pivot row with the label from the pivot column. The variable originally labeling the pivot row is the departing or exiting variable and the variable labeling the column is the entering variable.

Step 6. Go to Step 3.

Top of Page

Top of Page
Basic Solution

To get the basic solution corresponding to any tableau in the simplex method, set to zero all variables that do not appear as row labels (these are the inactive variables).

The value of a variable that does appear as a row label (an active variable) is the number in the rightmost column in that row divided by the number in that row in the column labeled by the same variable.

Top of Page
Example

In the following tableau

 x y z s t u p Ans -1 0 0 1 0 0 0 4 1 0 3 0 0 8 0 12 4 0 0 0 3 0 0 2 -5 2 0 0 0 6 0 4 6 0 0 0 0 0 5 -25
the basic solution is
x = 0, y = 2, z = 4, s = 4, t = 2/3, u = 0, p = -5,
and the active variables are y, z, s, t, and p.

Top of Page
Nonstandard Constraints

To solve a linear programming problem with constraints of the form Ax + By + . . .≥ N with N positive, subtract a surplus variable from the left-hand side, rather than adding a slack variable. The basic solution corresponding to the initial tableau will not be feasible since some of the active variables will be negative, and so the rules for the initial pivoting are different from those above.

Star all rows that give a negative value for the associated active variable (except for the objective variable, which is allowed to be negative). If there are starred rows, you will need to begin with Phase I:

Phase I: Getting into the Feasible Region (Getting Rid of the Stars)
In the first starred row, find the largest positive number. Use test ratios as in the preceding section to find the pivot in that column (exclude the bottom row), then pivot on that entry. If the lowest ratio occurs both in a starred row and an unstarred row, pivot in a starred row rather than the unstarred one. Repeat until no starred rows remain, then go on to Phase II.

Phase II: Use the Simplex Method for Standard Maximization Problems
If there are any negative entries on the left side of the bottom row after Phase I, use the method described above for solving standard maximization problems.

For some on-line interactive examples, visit the tutorial for general linear programming problems.

Top of Page
Simplex Method for Minimization Problem

To solve a minimization problem using the simplex method, convert it into a maximization problem. If you need to minimize c, instead maximize p = -c.

Top of Page
Example

The minimization LP problem:

Minimize C = 3x + 4y - 8z subject to the constraints
3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0,   y ≥ 0,   z ≥ 0
can be replaced by the following maximization problem:
Maximize P = -3x - 4y + 8z subject to the constraints
3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0,   y ≥ 0,   z ≥ 0.

Top of Page
Solving a Matrix Game Using the Simplex Method

A game may be solved using the simplex method as follows.

Before you start, check for saddle points. If you find one, you have already solved the game; the optimal strategies are the pure strategies passing through a saddle point. Otherwise, continue with the following steps.

1. Reduce the payoff matrix by dominance.
2. Add a fixed number k to each of the entries so that they all become non-negative.
3. Set up and solve the associated linear programming problem using the simplex method.
4. Obtain the optimal strategies and the expected value as follows:

5. Column Strategy
1. Express the solution to the linear programming problem as a column vector.
2. Normalize by dividing each entry of the solution vector by the sum of the entries, or by the value of the objective variable p.
3. Insert zeros in positions corresponding to the columns deleted during reduction.

Row Strategy
1. Write down the row vector whose entries are the numbers appearing in the bottom row of the final tableau underneath the slack variables.
2. Normalize by dividing each entry of the solution vector by the sum of the entries.
3. Insert zeros in positions corresponding to the rows deleted during reduction.

Value of the Game
e = 1/p - k.

Top of Page
Last Updated: July 2007