Section 4.3 Question 2

What are slack variables?

The graphical strategy for solving linear programming problems relies on the idea that the maximum value of the objective function will occur at a corner point of a bounded feasible region. The Simplex Method is no different, but we need to work with equations for the border of the feasible region in matrix form. The trouble is that augmented matrices are designed to solve equations and we have inequalities. For the graphical strategy, we simply converted each inequality to an equation. For the Simplex Method, we’ll introduce slack variables to change the inequalities to equalities.

Let’s start from one of the linear programming problems from section 4.2:

4_3_2_01

This problem is a standard maximization problem with the decision variables x and y. The goal of utilizing slack variables is to change the two inequalities to equalities. We do this by adding some unknown amount to the left hand side of each inequality.

For instance, let’s look at the first inequality 2x + y ≤ 4. This inequality corresponds to an infinite number of ordered pairs in the xy-plane. However, we can also think of this inequality as an equation. To do this you need to realize that the left hand side is less than or equal to 4. If we were to add a non-negative amount to the left side, we could increase it enough to guarantee that the left side is equal to 4. We’ll call this positive amount s1 and refer to it as the slack variable for the first inequality. The value for s1 is such that

2x + y + s1 = 4

In effect, the variable s1 takes up the slack in the two sides of the inequality.

We can apply the same reasoning to the second inequality x + 2y ≤ 4. If we add a different nonnegative amount s2 to the left side, the inequality changes to the equality

x + 2y + s2 = 4

Written in this format, each inequality is now an equality with the variables (including the slack variables) on the left side and the constant on the right side.

The objective function z = 5x + 6y already includes an equal sign, but not in the same format as the equations derived from the constraints. Subtract 5x and 6y from both sides of the objective function to put all of the variables on the left side of the equal sign. This leaves us with the equation

-5x – 6y + z = 0

If we put these three equations together, we get a system of three equations in five variables. Write the constraint equations on top of the equation corresponding to the objective function to give

4_3_2_02

This system can be written as an augmented matrix with three rows and six columns:

4_3_2_03

The vertical line corresponds to the equal sign in the equations and the horizontal line helps to distinguish the constraints from the objective function. This matrix is called the initial simplex tableau and is the starting point for the Simplex Method. The term tableau is used when dealing with matrices in the context of the Simplex Method.
The bottom row obtained from the objective function is called the indicator row. The variables above each column are not always shown, but we do so here to clarify how the variables match up with the coefficients in the augmented matrix.

Example 1    Find the Initial Simplex Tableau

Find the initial simplex tableau for the craft brewery linear programming problem:

4_3_2_04

Solution This problem is a standard maximization problem. To convert it to a system of equations, we need to add three different slack variables to the three different inequalities.

Using the slack variables s1, s2, and s3, we get three equations,

4_3_2_05

To these equations, we need to add the objective function. If we move all of the variables in P = 100x1 + 80x2 to the left side of the equal sign, we are left with -100x1 – 80x2 + P = 0.

Combine all of the equations together with the objective function on the bottom and we get

4_3_2_06

A 4 x 7 augmented matrix for this system of equations is

4_3_2_07

This is the initial simplex tableau for the craft brewery linear programming problem.