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

ax + by + cz + . . .

Ax + By + Cz + . . . N

Ax + By + Cz + . . . N.

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.

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.

To sketch the linear inequality

3x - 4y 12,

3(0) - 4(0) 12.

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.

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.

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

A. Graph the feasible region.
B. Compute the coordinates of the corner points.
C. Substitute the coordinates of the corner points into the objective function to see which gives the optimal value.
D. 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. The textbook shows a straightforward way for determining whether optimal solutions exist in the case of unbounded feasible regions.

If you want to see a utility that automates the whole process, try our Linear Programming Grapher. It does everything automatically!

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.

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

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, . . . ,

Ax + By + Cz + . . . N,

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

The following is a standard LP 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 LP problem:

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

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

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 Chapter 2) 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.

On-Line Tutorial on the Simplex Method

Pivot and Gauss-Jordan Tool

Excel Pivot and Gauss-Jordan Tool

Simplex Method Tool

Free Macintosh Simplex Method Tool.

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.

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

x = 0, y = 2, z = 4, s = 4, t = 2/3, u = 0, p = -5,

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. 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.

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.

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

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.