Linear Programming

Linear Programming: The Simplex Method

Two Dimensional Problems

We can solve Linear Programming problems with just two variables by finding the corner points of the critical region and then evaluating the objective function at each of the corner points. The point that generates the largest value for the objective function is the solution and the value generated is the maximum possible value for the points of the critical region and the objective function. The trick is to first find the corner points. In two dimensions, that is in cases where we only need two variables, we can do this in a number of ways:

graphing on paper and inspecting the graph
graphing on the calculator and using the trace feature to find values of the corners
graphing on the calculator and asking the calculator to determine the intersection of pairs of lines
using the calculator to display tables of values for points on the lines and inspecting the tables to find common points (see note 1 below) [This also works best in a math class where the coordinates of corner points usually resolve to nice, even values. Real world problems do not have such conveniences.]
setting up the corresponding linear equations and solving them, in pairs, by hand (see note 1 below)
setting up the corresponding linear equations and solving them , in pairs, by using the rref function (see note 1 below)
setting up the corresponding linear equations and solving them, in pairs, by expressing the equations in matrix form and using the inverse matrix (see note 1 below).

Note 1: many of the techniques given above have to be used with some caution. Just because a pair of lines intersect at a point that does not make the point a corner point of the critical region. In the graph below lines L1 and L3 intersect but they do so outside of the critical region.

Three Dimensional Problems

We can solve Linear Programming problems with just three variables by finding the corner points of the critical region and then evaluating the objective function at each of the corner points. The point that generates the largest value for the objective function is the solution and the value generated is the maximum possible value for the points of the critical region and the objective function. The trick is to first find the corner points. In three dimensions, that is in cases where we only need three variables, we cannot easily construct a graph of the critical region. It is difficult to even visualize that critical region. In cases where the critical region is bounded and where all three variables need to be positive, the critical region will be a many-sided solid somewhere in the positive quadrant of three-space. It still has corner points, but since we cannot graph the solid we are limited in how we find the corner points. We can find them by:

using the calculator create lists of values for points on the planes and inspecting the lists to find common points - this would require some programming and, on the calculators, it would be a tedious process at best. Furthermore, it would be highly dependent upon answers having nice even values.
setting up the corresponding linear equations and solving them, in triples, by hand
setting up the corresponding linear equations and solving them , in triples, by using the rref function
setting up the corresponding linear equations and solving them, in triples, by expressing the equations in matrix form and using the inverse matrix.

All of these techniques need to be used with caution. Just because a triple of planes intersect at a point that does not make the point a corner point of the critical region.

Four and Higher Dimensions

We can solve Linear Programming problems with four or more variables by finding the corner points of the critical region and then evaluating the objective function at each of the corner points. The point that generates the largest value for the objective function is the solution and the value generated is the maximum possible value for the points of the critical region and the objective function. The trick is to first find the corner points. In four or higher dimensions, that is in cases where we have four or more variables, we cannot easily construct a graph of the critical region. It is seemingly impossible to even visualize that critical region. We could use the methods listed previously for three dimensional cases, but locating the corner points from amongst all of the points that could be generated will mean that for each point found we will have to recheck the point against all of the constraints to make sure it is still in the critical region.

The Simplex Method

The Simplex method solves Linear programming problems by manipulating a special matrix, called a tableau, using elementary row operations and following some explicit rules for the steps to be taken. The usual approach to presenting the Simplex Method is to do so first for some restricted situations and then second for general situations. The method will be described below. Examples will follow.

Restricted Cases (often called Standard Cases)

Requirements:

All variables need to have non-negative values.
We are looking to maximize the objective expression (function)
The constraints or inequalities that define our restrictions are all "less than or equal to" conditions where all of the variables are on the less than side and a nonnegative value is on the right side. Thus, each inequality is of the form a₁x₁ + a₂x₂ + a₃x₃ +...+ a_nx_n ≤ b where all of the a_i are numbers, b is a nonnegative number
The objective expression, or function, is expressed as
c₁x₁ + c₂x₂ + c₃x₃ +...+ c_nx_n = z
which is then rewitten as
c₁x₁ + c₂x₂ + c₃x₃ +...+ c_nx_n – z = 0
which is then rewitten as
^-c₁x₁ + ^-c₂x₂ + ^-c₃x₃ +...+ ^-c_nx_n + z = 0

Create the Tableau

The tableau will hold the work we are doing. Creating a tableau in the calculator will mean creating a matrix to hold numbers. We may well want to recreate that matrix on paper because we have row and column headings that we simply cannot put into the matrix on the calculator. The matrix in the calculator will have one more row than we have inequalities. The number of columns in the matrix will be the number of variables plus the number of inequalities plus 2.

The rows of the matrix correspond to the different inequalities and the objective expression (function). Thus, there is one more row than the number of inequalities.
The columns of the matrix correspond to the variables in the inequalities plus a new variable, called a slack variable, for each inequality plus a column for the variable z that represents the sum of the objective expression (function) plus a column for the constants at the right side of each of the standard inequalities. Thus, we have the number of columns as two more than the sum of the count of variables and the count of inequalites.
The rows are arranged as the inequalities on top and the objective function at the bottom.
The columns are arranged as the original variables on the left, followed by the slack variables in the same order as the inequalities, follwed by the column for the z variable, and ending, on the right, with the column for the constants.
The cells (the entries) of the matrix are the coefficients of the variables in the expanded equations.

Example

For the following inequalities ^-2x₁ + x₂ ≤ 16
x₁ + 3x₂ ≤ 34
x₁ + x₂ ≤ 18
4x₁ + x₂ ≤ 60
Maximize 4x₁ + 5x₂

First we create a separate slack variable for each inequality to make it an equality. This yields

^-2x₁ + x₂ + s₁ = 16
x₁ + 3x₂ + s₂ = 34
x₁ + x₂ + s₃ = 18
4x₁ + x₂ + s₄ = 60
And these can be expanded with an additional term of 0z, inserting the implied coefficient of 1, and filling in, with a coefficient of 0, all of the slack variables not related to an individual equality as ^–2x₁ + 1x₂ + 1s₁ + 0s₂ + 0s₃ + 0s₄ + 0z =16
1x₁ + 3x₂ + 0s₁ + 1s₂ + 0s₃ + 0s₄ + 0z = 34
1x₁ + 1x₂ + 0s₁ +0 s₂ + 1s₃ + 0s₄ + 0z =18
4x₁ + 1x₂ + 0s₁ + 0s₂ + 0s₃ + 1s₄ + 0z = 60
To this we add one additional row, the objective function rewritten as the equation (expanded with a nuimber of terms having a 0 coefficient as ^–4x₁ – 5x₂ + 0s₁ + 0s₂ + 0s₃ + 0s₄ + 1z =0
The coefficients of the five equations given above form the tableau matrix, augmented here with row and column headings.

	x₁	x₂	s₁	s₂	s₃	s₄	z
s₁	^–2	1	1	0	0	0	0	16
s₂	1	3	0	1	0	0	0	34
s₃	1	1	0	0	1	0	0	18
s₄	4	1	0	0	0	1	0	60
	^–4	^–5	0	0	0	0	1	0

That same matrix, rendered on a TI-83 appears as

Notice that there are no row or column headings on the TI-83 rendition. This is a small problem, but one that we could overcome immediately by writing down the matrix and adding the appropriate headings.

The Steps

Look at almost all of the final row of the matrix. In particular, ignore the final column in that row. Find the most negative number in that row (ignoring the final column), and note the column in which that most negative value exists. If more than one column has that most negative value then pick any of those columns. We need to choose one, but we do not care which of the tied values we choose. The chosen column becomes the work column.
Look at only the positive values above the final row in that work column. If there are no positive values then we are done and there is no solution. For each such positive value find the quotient of the number in the same row but in the final column divided by the positive number in the work column. Of all the ratios that we find, determine which one is the smallest. The positive element in the work column that yields the smallest such ratio is called the pivot position. As before, if there is a tie, choose any of the elements from the tie.
If the pivot element is not 1, then use the multiply row by a constant (*row) elementary row operation to change the pivot element to be 1. Once the pivot element is 1, use the multiply row by a constant and add the result to another row elementary row operation to convert all other non-zero values in the work column to be 0.
On the paper copy, take the label of the work column and use it to replace the label in the row of the pivot element. (This is a cute move and it will make things easier, but one can actually complete the process without doing this. An explanation will come later.)
If, with the exception of the final column, there are any negative values in the bottom row of the matrix, then return to step 1 and continue from there.
To get here we are done. We need to read out the solution. It will be the new row labels set equal to the value in the corresponding final column. Furthermore, the value of the objective function will be the number in the last row and last column.

Example Continued

We had the following matrix:

The -5 in column 2 of the final row is the most negative value. Thus, the second column is the work column. There are four positive values above the final row. We need to find the ratio of each item there divided into the corresponding number in the final column. Thus, we are looking at (16/1), (34/3), (18/1), and (60/1). Of these, the second one is the lowest value. Therefore the item, 3, in row 2 column 2 is the pivot element. We use the *row elementary row operation to change that pivot to 1 (i.e., multiply the second row by 1/3). Then we use the *row+ elementary row operation to make all the other values in the second column be 0. The result is the following matrix:

Ideally, we would have taken the label of the second column, namely x₂, and placed it as the new label for the second row.

At this point we see that there is still a negative value in the final row, excluding the final column. In particular, there is the value ^–7/3 in column 1. Thus, we make column 1 the work column. Now we need to examine all of the positive values above the ^–7/3. In this case there are only three such positive values, the ones in rows 2, 3, and 4. for each of these we form the ratio of the number in the same row but final column and the positive number in the work column. Thus, we need to look at (34/3) / (1/3) which is 34, (20/3) / (2/3) which is 10, and (146/3) / (11/3) which is 13.2727. The smallest of these values is the 10 from the computation in row 3. Therefore, the 2/3 in row three column one is the new pivot element. We use the *row elementary row operation to change the pivot to 1 (i.e., multiply row 3 by 3/2). Then we use the *row+ elementary row operation to change all other values in the work column, column 1, to be 0. The result is the following matrix:

Ideally, we would have taken the label of the first column, namely x₁, and placed it as the new label for the third row.

We see that there are no more negative values in the last row (of course, still ignoring the last column) so we are done. A more elaborate table display of the tableau would be:

	x₁	x₂	s₁	s₂	s₃	s₄	z
s₁	0	0	1	–3/2	7/2	0	0	28
x₂	0	1	0	1/2	–1/2	0	0	8
x₁	1	0	0	–1/2	3/2	0	0	10
s₄	0	0	0	3/2	–11/2	1	0	12
	0	0	0	1/2	7/2	0	1	80

The label of the first row is still s₁ and the tableau indicates that its value is 28, the number in the last column. The label of the second row is now x₂ and the tableau indicates that its value is 8, the number in the last column. The label of the third row is now x₁ and the tableau indicates that its value is 10, the number in the last column. The label of the fourth row is still s₄ and the tableau indicates that its value is 12, the number in the last column. The fifth row, which has held the objective function, has the value 80 in the final column. Thus, the value of the objective function is 80.

Since we are really interested in just the original variables, we see that the values of x₁ and x₂ are determined. (If either one of them had not made it over to be a label on the left side of the tableau, then we would have taken itsw value to be 0.) We can confirm the value at the solution point since we know that we want x₁=10, x₂=8 and that makes 4x₁ + 5*x₂, our original objective function become 4*10 + 5*8 or 80.

Expanding the Method

There were a number of restriction for the case presented above. In particular, we had to have the final column of constants be non-negative, we had to have all of the inequalities be "less than or equal" statements, and we could only find the maximum value for the objective function. There is an additional set of steps that we can perform that will remove the first restriction, and, as a consequence, allow us to remove the second restriction. After presenting that set of steps, we will look at the changes needed to minimize the objecdtive expression (function) in the critical region.

Preprocessing We will do a set of steps called "Preprocessing" to convert a tableau with one or more negative values in the final column into a tableau that has only non-negative values in the final column. If this preprocessing phase cannot reach that goal then there is no solution and we just stop the analysis. The steps in "Preprocessing" take place if there is at least one negative value in the final column (excluding the entry in the final row). The steps are:
Look at the final column of the matrix. In particular, ignoring the entry in the final row of the matrix, find the most negative value in the final column and note the row in which that most most negative value exists. If more than one row has the same most negative value then pick any one of those rows. The chosen row becomes the work row.
Look at all of the entries in the work row, except the entry in the last column. Find the most negative of those values. If there are no negative values in the work row then there is no solution. [This makes some sense since if we were to convert the row back to a "less than or equal to" inequality we would have all positive coefficients for each of our variables and since all the variables have to be non-negative it is hard to see how the sum of positive values (the products of the coefficients and the variables) could be less than or equal to the negative value that we would have on the right side of the less than or equal sign.] As usual, if there is a tie in the entries, pick one of them.
The chosen most negative value in the work row (but of course not the value in the final column) is in the pivot location. Use the *row elementary row operation to change the pivot value to be 1. Once that is done, use the *row+ elementary row operation to convert all other entries in the pivot column to be 0.
On the paper copy, take the label at the top of the pivot column and use it to replace the label on the left end of the work row.
If, with the exception of the entry in the last row, there are any negative values in the final column, then return to step 1 of the preprocessing actions above and continue from there.
To get here we are done with preprocessing and we can now move to the steps of the standard processing presented earlier.

That is the preprocessing phase. With that in place we can now process a system of inequalities that has a negative constant on the right side of the inequality. This is more significant than it might seem at first glance. Consider the inequality

7x₁ – 5x₂ ≥ 45 Until now we could not process a system of linear inequalities that included this example because it is a "greater than or equal to" inequality. We still cannot process it as it is stated. However, we could multiply both sides of this inequality by –1 to get the new inequality –7x₁ + 5x₂ ≤ –45 Now that we can process "less than or equal to" inequalities with a negative constant we can process a system that includes the modified inequality given above. Consider the following system 5x + 7y ≤ 71
–3x + y ≤ –1
3x + 2y ≥ 16
–x + 6y ≥ 8 This is the kind of system that we saw when we were graphing to find corner points and then solutions to maximization problems. In fact the graph of the system would be:

Now, with preprocessing, we first convert the system to 5x + 7y ≤ 71
–3x + y ≤ –1
–3x + –2y ≤ –16
x + –6y ≤ –8 and then proceed with our expanded Simplex Method.

Expanded Example

For 5x + 7y ≤ 71
–3x + y ≤ –1
–3x + –2y ≤ –16
x + –6y ≤ –8 maximize 4x -4y

We restate the objective as 4x -4y = z
Move the z to the other side 4x -4y - z = 0
and restate again, but with coefficient of z being 1, as -4x +4y + 1z = 0
Then, we create a slack variable for every inequality, thus creating s₁, s₂, s₃, and s₄. Rewrite each inequalities and the objective function using all of the variables, in this case x, y, s₁, s₂, s₃, s₄, and z. This gives rise to the following tableau:

	x	y	s₁	s₂	s₃	s₄	z
s₁	5	7	1	0	0	0	0	71
s₂	–3	1	0	1	0	0	0	–1
s₃	–3	–2	0	0	1	0	0	–16
s₄	1	–6	0	0	0	1	0	–8
	^–4	4	0	0	0	0	1	0

This, when put onto a TI-84 looks like

From this we see that there are negative values in the final column. Therefore, we need to do the preprocessing phase of the Simplex Method. We find the most negative value in the final column. That would be the –16 in row 3. That makes row 3 the work row. Now, with the exception of the final column, find the most negative value in the work row. That would be the –3 in column 1. That makes the row 3 column 1 entry the pivot location. The value there needs to be changed to be 1 via the *row elementary row operation. Therefore, multiply that row by –1/3. Thereafter, change the remaining elements in column 1 to be 0 via the *row+ elementary row operation. The resulting matrix will be:

On the paper copy we would copy the column heading of the pivot location, x, to overwrite the row label for the work row (it was s₃ and it becomes x).

Looking at the matrix above we see that there is still a negative value in the final column, so we start the preprocessing phase over. The most negative value (indeed the only negative value) in the final column is –40/3 in row 4. Make row 4 the work column. The most negative value (indeed the only negative value) in the work row (ignoring the final column) is –20/3 in column 2. Make row 4 column 2 the pivot location. Use the *row elementary row operation to change the pivot value to 1, i.e., multiply row 4 by –3/20. Then, convert the remaining entries in the pivot column, column 2, to 1 by use of the *row+ elementary row operation. The resulting matrix is

On the paper copy we would copy the column heading of the pivot location, y, to overwrite the row label for the work row (it was s₄ and it becomes y).

Looking at the matrix above we see that there are no negative values in the final column, so we are done with the preprocessing phase. We return to the regular (standard) Simplex Method procedures. The most negative value (indeed the only negative value) in the final row ignoring the final column is –1 in column 5. Make column 5 the work column. At this point, we need to find, for each positive value in the work column, the ratio of that positive value divided into the number in the final column nof the same row. Then we find the lowest such ratio. In our present case there is only one positive value, 37/20, in row 1 of the work column. Therefore, row 1 column 5 is the new pivot. Use *row to make that entry 1 and then use *row+ to make the rest of the entries in the work column be 0. The resulting matrix is

On the paper copy we would copy the column heading of the pivot location, s₃, to overwrite the row label for the work row (it was s₁ and it becomes s₃).

Looking at the matrix above we see that there are no negative values in the final row, so we are done with the Simplex Method. Our paper copy appears as

	x	y	s₁	s₂	s₃	s₄	z
s₃	0	0	27/37	0	1	11/37	0	20
s₂	0	0	17/37	1	0	26/37	0	26
x	1	0	6/37	0	0	17/37	0	10
y	0	1	1/37	0	0	–5/37	0	3
	0	0	20/37	0	0	48/37	1	28

From this tableau we read, in the labels on the left and the corresponding values in the right column, that when x has the value 10 and y has the value 3 then the the value of the objective expression (function) is 28, the value in the last row last column of the matrix.

The expanded method allowed us to process negative values on the right side of the inequalities. As a result, we were able to also process "greater than or equal to" inequalities because we could convert them to "less than or equal to" inequalities by multiplying both sides by –1. What remains is to be able to use the Simplex Method for solving problems with a request to minimize the objective function.

What if we have the same system of inequalities as above but we want to minimize the expression 4x – 4y. First, note that if we have values p, q, r, and s and we have the relations

–p > –q > –r > –s or –p < –q < –r < –s then we also have –s > –r > –q > –p From this we notice that while s is the largest value, –s is the smallest. In the same way p is the smallest and –p is the largest. If we want to find the minimum value of 4x – 4y it will be enough to find the maximum of –(4x – 4y). To minimize an objective expression, just maximize the opposite of the objective expression. The Simplex Method works to find such maximum values, all we have to do is to present the objective function as the opposite of its given statement and, at the end, remeber that the value we obtain will be the negative of the minimum value we seek.

Expanded Example

For 5x + 7y ≤ 71
–3x + y ≤ –1
–3x + –2y ≤ –16
x + –6y ≤ –8 minimize 4x - 4y

Because this is a minimize problem, our first step is to replace the objective function with its opposite, namely ^–4x + 4y We restate the objective as ^–4x + 4y = z
Move the z to the other side ^–4x + 4y &ndash z = 0
and restate again, but with coefficient of z being 1, as 4x + ^–4y + 1z = 0
Then, we create a slack variable for every inequality, thus creating s₁, s₂, s₃, and s₄. Rewrite each inequalities and the objective function using all of the variables, in this case x, y, s₁, s₂, s₃, s₄, and z. This gives rise to the following tableau:

	x	y	s₁	s₂	s₃	s₄	z
s₁	5	7	1	0	0	0	0	71
s₂	–3	1	0	1	0	0	0	–1
s₃	–3	–2	0	0	1	0	0	–16
s₄	1	–6	0	0	0	1	0	–8
	4	^–4	0	0	0	0	1	0

This, when put onto a TI-84 looks like

On the paper copy we would copy the column heading of the pivot location, x, to overwrite the row label for the work row (it was s₃ and it becomes x).

Looking at the matrix above we see that there is still a negative value in the final column, so we start the preprocessing phase over. The most negative value (indeed the only negative value) in the final column is –40/3 in row 4. Make row 4 the work column. The most negative value (indeed the only negative value) in the work row (ignoring the final column) is –20/3 in column 2. Make row 4 column 2 the pivot location. Use the *row elementary row operation to change the pivot value to 1, i.e., multiply row 4 by –-3/20. Then, convert the remaining entries in the pivot column, column 2, to 1 by use of the *row+ elementary row operation. The resulting matrix is

On the paper copy we would copy the column heading of the pivot location, y, to overwrite the row label for the work row (it was s₄ and it becomes y).

Looking at the matrix above we see that there are no negative values in the final column, so we are done with the preprocessing phase. We return to the regular (standard) Simplex Method procedures. The most negative value (indeed the only negative value) in the final row ignoring the final column is –1 in column 6. Make column 6 the work column. At this point, we need to find, for each positive value in the work column, the ratio of that positive value divided into the number in the final column nof the same row. Then we find the lowest such ratio. In our present case there are three positive values, 11/20, 9/20, and 1/10 in rows 1 through 3 of the work column. The ratios become 37/(11/20), 9/(9/20), and 4/(1/10). These evaluate to 67.2727..., 20, and 40. The lowest ratio is 20 in row 2. Make row 2 the work row. That makes row 2 column 6 the pivot cell. Use the *row elementary row operation to change the pivot cell to be 1, i.e., multiply row 2 by 20/9. Then, use the *row+ operation to change the rest of the pivot column, column 6, to be 0. The resulting matrix appears as

On the paper copy we would copy the column heading of the pivot location, s₄, to overwrite the row label for the work row (it was s₂ and it becomes s₄).

There is still a negative value in the last row, excluding the last column. Therefore, we repeat the standard process. The most negative value (indeed the only negative value) in the final row ignoring the final column is –8/9 in column 5. Make column 5 the work column. At this point, we need to find, for each positive value in the work column, the ratio of that positive value divided into the number in the final column nof the same row. Then we find the lowest such ratio. In our present case there is just one positive values, 26/9 in row 1 of the work column. Therefore, we do not even have to find the ratio, there is only one choice for a work row. Make row 1 the work row. That makes row 1 column 5 the pivot cell. Use the *row elementary row operation to change the pivot cell to be 1, i.e., multiply row 1 by 9/26. Then, use the *row+ operation to change the rest of the pivot column, column 5, to be 0. The resulting matrix appears as

On the paper copy we would copy the column heading of the pivot location, s₃, to overwrite the row label for the work row (it was s₁ and it becomes s₃).

Looking at the matrix above we see that there are no negative values in the final row, so we are done with the Simplex Method. Our paper copy appears as

	x	y	s₁	s₂	s₃	s₄	z
s₃	0	0	9/26	–11/26	1	0	0	9
s₄	0	0	17/37	37/26	0	1	0	37
x	1	0	1/26	–7/26	0	0	0	3
y	0	1	3/26	5/26	0	0	0	8
	0	0	4/13	24/13	0	0	1	20

From this tableau we read, in the labels on the left and the corresponding values in the right column, that when x has the value 3 and y has the value 8 then the the value of the opposite objective expression (function) is 20, the value in the last row last column of the matrix. Therefore, the value of our desired objective function is –20. When x=3 and y=8 the value of 4x – 4y is –20.