More Simplex Method

In the previous lecture we described a method to solve a linear programming problem. Now we will clean it up a little bit by eliminating the need to write down all the variables. Recall the problem from the last section

Maximize:	R =	3x1	+ 5x2
Subject to:		x1		≤ 4
			2x2	≤ 12
		3x1	+ 2x2	≤ 18

We begin by augmenting the problem with slack variables to eliminate the inequalities just like in the last lecture.

Maximize:	R =	3x1	+ 5x2
Subject to:		x1		+ x3			= 4
			2x2		+ x4		= 12
		3x1	+ 2x2			+ x5	= 18

Now we will turn the entire problem into a system of equations by rewriting the objective function to get all the variables on the left hand side and 0 on the right hand side. Nothing else will change in this step. So that this is our system of equations:

R	- 3x1	- 5x2				= 0
	x1		+ x3			= 4
		2x2		+ x4		= 12
	3x1	+ 2x2			+ x5	= 18

Now, we’re going to write this problem in matrix, or table form. Let us first construct an empty table. Each row will represent an equation. The columns will be labeled with the appropriate variables. RHS stands for Right Hand Side.

R

x1

x2

x3

x4

x5

RHS

We will fill the table by entering the coefficient of the variable in the appropriate equation. If a variable does not have a coefficient, then the entry into that cell is 1. If there is no variable in that equation, then we fill it in with a 0.

R	x1	x2	x3	x4	x5	RHS
1	-3	-5	0	0	0	0
0	1	0	1	0	0	4
0	0	2	0	1	0	12
0	3	2	0	0	1	18

We will add another column (labeled BV) to table to keep track of basic variables. Remember, the simplex method works by switching which variables are basic (nonzero) and which are non-basic (zero). Also remember that at the beginning of the simplex method, the basic variables will always be the slack variables.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	-5	0	0	0	0
x3	0	1	0	1	0	0	4
x4	0	0	2	0	1	0	12
x5	0	3	2	0	0	1	18

Iteration 1

The process of the simplex method in this form works exactly like it did before.

The optimality test becomes extremely simple at this point. If there are any negative values in the top row (other than in the R column), then the solution is not optimal.

To move to another point in the simplex method, we must identify entering and leaving variables. The entering variable is the variable with the “most negative” entry in the first row. In this example, -5 is less than -3 making x₂ the entering variable. We highlight that column. We will call this the pivot column.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	-5	0	0	0	0
x3	0	1	0	1	0	0	4
x4	0	0	2	0	1	0	12
x5	0	3	2	0	0	1	18

To find the leaving variable, we must perform the minimum ratio test. This is much easier than before. We just divide the numbers in the RHS column by the associated numbers in the pivot column (except in the first row; we leave that alone for now) and find the minimum. If the numbers in the pivot column are 0 or negative, we ignore them. We highlight the row associated with that minimum value. This row represents the leaving variable (identified in the BV column), so x₄ is the leaving variable. We will call the highlighted row the pivot row. The number in red is called the pivot number.

BV	R	x1	x2	x3	x4	x5	RHS	Minimum Ratio Test
	1	-3	-5	0	0	0	0	NA
x3	0	1	0	1	0	0	4	NA
x4	0	0	2	0	1	0	12	12/2 = 6
x5	0	3	2	0	0	1	18	18/2 = 9

Now that we have our entering variable, x₂, and out leaving variable, x₄, we need to make some adjustments to the table. In the previous lecture we did this by “eliminating” the entering variable from the other equations. We do the same thing here, but now we just have to add or subtract multiples of rows rather than equations. But the first thing I will do is divide everything in the pivot row by the pivot number to get a 1 in that cell. At the same time, I will replace the leaving variable in the BV column with the entering variable, just to keep track.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	-5	0	0	0	0
x3	0	1	0	1	0	0	4
x2	0	0	1	0	1/2	0	6
x5	0	3	2	0	0	1	18

To eliminate the entering variable from the other equations is equivalent to getting a making everything else in the highlighted column 0, specifically we need to work on the first and fourth rows of the table. To get a 0 in the x₂ column of the first row, I will need to multiply the pivot row by 5 and then add it to the first row.

	1	-3	-5	0	0	0	0
+ 5 * (	0	0	1	0	1/2	0	6	)
	1	-3	0	0	5/2	0	30

Replace the first row with the result. Good. We have a 0 in the first row of the pivot column.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	0	0	5/2	0	30
x3	0	1	0	1	0	0	4
x2	0	0	1	0	1/2	0	6
x5	0	3	2	0	0	1	18

To get a 0 in the fourth row of the pivot column, we will need to subtract twice the pivot row from it.

	0	3	2	0	0	1	18
- 2 * (	0	0	1	0	1/2	0	6	)
	0	3	0	0	-1	1	6

Replace the fourth row with the result.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	0	0	5/2	0	30
x3	0	1	0	1	0	0	4
x2	0	0	1	0	1/2	0	6
x5	0	3	0	0	-1	1	6

This completes the 1^st iteration of the simplex method. Notice, however, that there is still a negative number in first row. That means that we’re not done. So we repeat the process.

Iteration 2

In the first row, -3 is the “most negative number. We highlight that column, so x₁ that becomes the entering variable. And from the minimum ratio test, we see that x₅ must be the leaving variable.

BV	R	x1	x2	x3	x4	x5	RHS	Minimum Ratio Test
	1	-3	0	0	5/2	0	30	NA
x3	0	1	0	1	0	0	4	4/1 = 4
x2	0	0	1	0	1/2	0	6	NA
x5	0	3	0	0	-1	1	6	6/3 = 2

Now we swap the entering and leaving variables in the BV column and divide the pivot row by the pivot number to get a 1 in that spot.

BV	R	x1	x2	x3	x4	x5	RHS
	1	-3	0	0	5/2	0	30
x3	0	1	0	1	0	0	4
x2	0	0	1	0	1/2	0	6
x1	0	1	0	0	-1/3	1/3	2

Now we eliminate x₁ from the other equations by getting 0’s in the first and second rows. We’ll add 3 times the pivot row to the first row.

BV	R	x1	x2	x3	x4	x5	RHS
	1	0	0	0	3/2	1	36
x3	0	1	0	1	0	0	4
x2	0	0	1	0	1/2	0	6
x1	0	1	0	0	-1/3	1/3	2

Now we subtract the pivot row from the second row.

BV	R	x1	x2	x3	x4	x5	RHS
	1	0	0	0	3/2	1	36
x3	0	0	0	1	1/3	-1/3	2
x2	0	0	1	0	1/2	0	6
x1	0	1	0	0	-1/3	1/3	2

Thus completing the second iteration of the simplex method. Now there are no more negative numbers in the first row. Therefore we are done. Because we did the eliminations, we can read the answer to the problem straight out of the table.

BV	R	x1	x2	x3	x4	x5	RHS
	1	0	0	0	3/2	1	36
x3	0	0	0	1	1/3	-1/3	2
x2	0	0	1	0	1/2	0	6
x1	0	1	0	0	-1/3	1/3	2

The cell highlighted in yellow is the maximum value of R that we can achieve. The maximum value will always appear in this cell. This number should look familiar since we’ve solved this problem twice before. The values of the decision variables, x₁ and x₂, can be found by finding them in the BV column. Their values are in the RHS column.

x₁ = 2

x₂ = 6

Similarly, we know that at the end of the problem x₃ = 2. This is like “extra” information. Because x₄ and x₅ aren’t in the BV column (i.e. they’re non-basic) at the end of the simplex method, we know that they are both equal to 0. Therefore, our final solution is (2, 6, 2, 0, 0), R = 36.