The Simplex Method

The Augmented Problem

The simplex method is a method of solving linear programming problems by moving from corner point to corner point of the feasible region in the direction of greatest profit. It does this by solving systems of equations. In the previous linear programming problem, we didn’t have a system of equations. We just had a bunch of inequalities. So we will need to modify the problem a bit to eliminate the inequalities.

Here is Ty’s TV Manufacturing problem again.

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

Consider the first inequality, x₁ ≤ 4. This means that x₁ differs from 4 by some positive number. Suppose that 4 - x₁ = x₃. Then we can rewrite the first inequality into the equation x₁ + x₃ = 4.

Following this logic, we can do the same to the second and third inequalities using additional variables x₄ and x₅ so that the whole problem becomes

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

Note: The additional variables added to eliminate the inequalities are called slack variables. This problem containing both decision variables and slack variables is known as the augmented problem.

A solution to this problem will be an ordered quintuple (x₁, x₂, x₃, x₄, x₅).

Systems of Equations

A system of equations is a collection of equations in some number of variables. The number of equations and the number of variables forms an important relationship.

1) If number of equations = number of variables then we say the system is determined. There is one and only one solution.

2) If number of equations > number of variables then we say the system is over-determined. In this case there is usually no solution.

3) If number of equations < number of variables then we say the system is under-determined. This means that there is not enough information about the variables to find a solution.

We are interested in under-determined systems because forming an augmented problem (like the one above) usually creates an under-determined system of equations.

In an under-determined system, we have the freedom to arbitrarily set some of the variables to whatever we would want. The number of variable we can arbitrarily set is called the degree of freedom (abbreviated DOF). In general, DOF = # variables - # equations.

For a simple example, the following is a system of equations with one equation and 2 variables:

3x₁ + 2x₂ = 18.

I can’t solve this equation with the information available. I either need to know more about x₁ or x₂. But, 2 variables – 1 equation = 1 DOF. So theoretically, I can arbitrarily choose a value for either x₁ or x₂ to get a solution. For example, if I set x₁ = 0, then I can show that x₂ = 9. Alternatively, if I choose x₂ = 0, then I have x₁ = 6.

Why did I choose to set either value to 0? Look at the augmented problem above. In that problem there are 3 equations and 5 variables, so there are 2 DOF. This means that I can arbitrarily pick 2 variables and set them to what ever I want. I want to set them to 0. The reason is that when you set the some of the slack variables equal to 0, your decision variables are at a corner point. For instance, if I set x₄ and x₅ equal to 0, then x₂ = 6 and x₁ = 2, one of the corner points in the original problem (in fact the optimal solution). Also in this case, x₃ = 2.

Notice that there are exactly 2 variables equal to 0 (x₄ and x₅) and 3 variables not equal to 0 (x₁, x₂ and x₃). This is not a coincidence. The 2 variables equal to 0 represent the 2 degrees of freedom in the problem. We will call these variables non-basic variables. The other 3 nonzero variables will call basic variables. The simplex method works by switching basic and non-basic variables to step from corner point to corner point to achieve an optimal solution.

The Simplex Method

The simplex method is an algorithm, or set of steps, to solve linear programming problems that have been put into augmented form. The steps are:

1) Initialization

2) If optimal then stop

3) Otherwise, move to next corner point

3.5) Do some adjusting

4) Go to 2

The problem:

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

Initialization

The initialization works by assuming that all the decision variables are 0 and therefore non-basic. This means that all of the slack variables are basic. My initial solution is (0, 0, 4, 12, 18).

Iteration 1: Optimality Test

Clearly this solution is not optimal. An increase in either x₁ or x₂ will lead to an increase in R.

Iteration 1: Moving to another Corner Point

Which variable shall I increase? I would like to increase the variable which will result in the greatest increase in R. This means that I should increase x₂ since for each unit I increase x₂, R goes up by 5.

I will call x₂ the entering variable. How much can I increase x₂ by? Consider only the equations containing x₂.

	2x2	+ x4		= 12
3x1	+ 2x2		+ x5	= 18

I will solve each of these equations for the basic variable (x₄ and x₅). x₁ is still non-basic meaning that it is equal to 0.

x4	= 12	- 2x2
x5	= 18	- 2x2

But remember that slack variables must be positive, so

0 ≤	x4	= 12	- 2x2
0 ≤	x5	= 18	- 2x2

But this means that

0 ≤	12	- 2x2
0 ≤	18	- 2x2

Solving the inequalities for x₂ we have

x₂ ≤ 12/2 = 6

x₂ ≤ 18/2 = 9

Well, if x₂ has to be less than 6 and less than 9, then it can’t be any greater than 6. This is called the minimum ratio test. In this case x₄ is the basic variable associated to the minimum we just found.

We will call this basic variable the leaving variable. Remember, we want to make R as large as possible. To do so, we want to increase x₂ (the entering variable) as much as we can. So we will set x₂ = 6. But remember that

x4

= 12

- 2x2

In other words, x₄ = 0. Notice that the entering variable enters the set of basic variables by becoming nonzero. The leaving variable leaves the set of basic variables by becoming 0 (or non-basic). Hence the terms entering and leaving variables. So now x₂ is basic and x₄ non-basic.

My new solution to the problem is (0, 6, 4, 0, 6) and R = 30.

Iteration 1: Adjusting the problem

In order to take the next step, I will need to make a readjustment to the way the problem looks. I have just made x₂ as large as it can possibly get, so I want to, in some sense, eliminate it from the problem. To do that I will need to alter all of the equations involving x₂. First, notice that the objective function contains x₂. I’m going to rewrite it to make it look a little different and include it with the existing system of equations. Specifically, if R = 3x₁ + 5x₂, then I’m just going to get everything on one side of the equation so that R - 3x₁ - 5x₂ = 0. Now my system looks like

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

Number these equations 0 – 3.

Next, I want to look at the equation containing both entering and leaving variables and divide it by the coefficient of the entering variable (Equation 2- it’s shaded). Confused? Here is the equation in question.

2x2

+ x4

= 12

The coefficient of x₂ is 2. (A coefficient is just the number in front of the variable.)

Dividing the entire equation by 2 gives

x2

+ ½ x4

= 6

So my whole problem is now

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

Now, I’m going to add and subtract multiples of equation 2 so that each equation containing x₂ will get a zero coefficient for x₂. Confused again? Here’s what I mean: in equation 0, x₂ has a coefficient of -5. I want to make that 0. So I’m going to add 5 times equation 2 to equation 0 to get

	R	- 3x1	- 5x2		= 0
+ 5 * (			x2	+ ½ x4	= 6	)
	R	- 3x1		+ 5/2 x4	= 30

Then I replace this into my system of equations

R	- 3x1			+ 5/2 x4		= 30
	x1		+ x3			= 4
		x2		+ ½ x4		= 6
	3x1	+ 2x2			+ x5	= 18

Now I do the same to equation 3. But this time to get a zero coefficient, I will need to subtract 2 times equation 2 from equation 3.

	3x1	+ 2x2		+ x5	= 18
- 2 * (		x2	+ ½ x4		= 6	)
	3x1		- x4	+ x5	= 6

Again replacing the results into my system of equations

R	- 3x1			+ 5/2 x4		= 30
	x1		+ x3			= 4
		x2		+ ½ x4		= 6
	3x1			- x4	+ x5	= 6

Now that I have “eliminated” x₂ from the problem, I have completed one iteration of the simplex method. So now I go back to my optimality test. Is my new solution optimal? We know it’s not because we know the answer optimal solution is R = 36. But if we didn’t know that, how could we tell? In the first iteration the objective function, was R = 3x₁ + 5x₂. But we rewrote the objective function to get equation 0, R - 3x₁ - 5x₂ = 0. Now, after our “elimination” process, we can rewrite the new equation 0 back into objective function form: R = 3x₁ – 5/2 x₄. I can increase either x₁ or x₄, but increasing x₄ will decrease R (notice the negative sign on x₄). However, an increase in x₁ will lead to an increase in R. Therefore my solution must not be optimal. So we begin a new iteration with x₁ as the new entering variable.

Iteration 2: Optimality Test:

Is my new solution optimal? We know it’s not because we know the answer optimal solution is R = 36. But if we didn’t know that, how could we tell? In the first iteration the objective function, was R = 3x₁ + 5x₂. But we rewrote the objective function to get equation 0, R - 3x₁ - 5x₂ = 0. Now, after our “elimination” process, we can rewrite the new equation 0 back into objective function form: R = 30 + 3x₁ – 5/2 x₄. I can increase either x₁ or x₄, but increasing x₄ will decrease R (notice the negative sign on x₄). However, an increase in x₁ will lead to an increase in R. Therefore my solution must not be optimal. So we begin a new iteration with x₁ as the new entering variable.

Iteration 2: Moving to another Corner Point

I learned from my optimality test that I need to increase x₁; that is, x₁ is my new entering variable. To choose a new exiting variable, I look at all the equations containing x₁, except equation 0, and perform the minimum ratio test. For the minimum ratio test, I just took the coefficients of the entering variable and divided the right hand side of the equation by them. In this iteration,

Equation 1: 4/1 = 4

Equation 2: N/A - Doesn’t contain x₁

Equation 3: 6/3 = 2

That means that equation 3 will contain the leaving variable, but which one. Equation 3 only has one basic variable: x₅. Thus, x₅ will become the new leaving variable.

Iteration 2: Adjusting the problem

Here is the problem with the equation containing both entering and leaving variables highlighted.

R	- 3x1			+ 5/2 x4		= 30
	x1		+ x3			= 4
		x2		+ ½ x4		= 6
	3x1			- x4	+ x5	= 6

Just as in the last iteration, I want to “eliminate” the entering variable from the system. Just like last time I will divide the highlighted equation by the coefficient of the entering variable to get

R	- 3x1			+ 5/2 x4		= 30
	x1		+ x3			= 4
		x2		+ ½ x4		= 6
	x1			- 1/3 x4	+ 1/3 x5	= 2

To get a 0 coefficient for x₁ in equation 0, I will need to add 3 times equation 3 to equation 0.

	R	- 3x1	+ 5/2 x4		= 30
+ 3 *(		x1	- 1/3 x4	+ 1/3 x5	= 2	)
	R		+ 3/2 x4	x5	= 36

To get a 0 coefficient for x₁ in equation 1, I just need to subtract equation 3 from equation 1.

	x1	+ x3			= 4
- (	x1		- 1/3 x4	+ 1/3 x5	= 2	)
		+ x3	+ 1/3 x4	- 1/3 x5	= 2

Putting my new equations back into the problem,

R				+ 3/2 x4	x5	= 36
			x3	+ 1/3 x4	- 1/3 x5	= 2
		x2		+ ½ x4		= 6
	x1			- 1/3 x4	+ 1/3 x5	= 2

This completes the second iteration.

Iteration 3: Optimality Test:

By looking at equation 0 and solving for R we see that an increase in either x₄ or x₅ will decrease R. Therefore we know that we are done. Our final solution is (2, 6, 3, 0, 0) and R = 36.