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.

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

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

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

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.

On-Line Tutorial on the Simplex Method

Pivot and Gauss-Jordan Tool

Excel Pivot and Gauss-Jordan Tool

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

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.

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:

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 = ¹/_p - k.