# Linear Programming: Table Approach

Let's take our linear programming problem and work with it.

 Maximize Subject to: P = 40x + 30y x + 2y ≤ 16 x + y ≤ 9 3x + 2y ≤ 24 x , y ≥ 0

## Changing to Subscripted Variables

As mentioned earlier, we're going to switch from x and y to x1 and x2. The subscripted variables can be a little confusing at first, but they will make life much, much easier later on.

 Maximize Subject to: P = 40x1 + 30x2 x1 + 2x2 ≤ 16 x1 + x2 ≤ 9 3x1 + 2x2 ≤ 24 x1 , x2 ≥ 0

## Changing Inequalities into Equalities

We need to change the inequalities into equalities. This involves adding a variable to take up the slack between less than and equal to in the case of a ≤ constraint and subtracting a variable to remove the surplus in the case of a ≥ constraint.

• Add a slack variable, s, and change the ≤ to an = for each ≤ constraint.
• Subtract a surplus variable, s, and change the ≥ to an = for each ≥ constraint.
• Leave the = constraints alone since they are already equal.

The slack and surplus variables get subscripts as well. Use a subscript that corresponds to the constraint number. That is, use 1 for the first constraint, 2 for the second constraint, and so on.

We'll also require each of the slack and surplus variables to non-negative as well. In fact, every variable with the exception of the objective function will be required to be non-negative.

 Maximize Subject to: P = 40x1 + 30x2 x1 + 2x2 + s1 = 16 x1 + x2 + s2 = 9 3x1 + 2x2 + s3 = 24 x1 , x2 , s1 , s2 , s3 ≥ 0

## Unique Identification of Each Line

Each of the lines can be identified by setting exactly one variable to zero.

 x1 + 2x2 = 16 can be written as s1 = 0 x1 + x2 = 9 can be written as s2 = 0 3x1 + 2x2 = 24 can be written as s3 = 0 x1 = 0 can be written as x1 = 0 x2 = 0 can be written as x2 = 0

Here is the feasible region shown in two ways. The first way we saw earlier when lines were identified by x and y. Now we see them identified by a single variable equaling zero.

### Basic and Non-Basic Variables

Each line can be identified by one variable, the one variable that is set equal to zero. Since that variable is always zero on that line, it is called non-basic. Think of "basic" as meaning elementary, foundational, or important. Since that variable is zero, it's not important, or non-basic.

## Each Intersection Point Can Be Identified by its Non-Basic Variables

Since each line is identified by one variable, the non-basic variable, being zero, each intersection point can be identified by two variables being zero. The two variables that are zero at an intersection point correspond to the non-basic variables and the other variables are basic variables.

That means that is is possible to find the coordinates of all the points on the graph by creating a table listing all the different combinations of variables where exactly two of them at a time are zero. The two variables that are zero are the non-basic variables and the rest of the variables are basic.

Pt x1 x2 s1 s2 s3
A 0 0
B 0   0
C 0     0
D 0       0
E   0 0
F   0   0
G   0     0
H     0 0
I     0   0
J       0 0

The figure shows where each of those points is on the graph.

## Completing the Table

The key now is to figure out what the rest of the variables are. You need to find x1 and x2 to do that.

### Here are some examples

#### Point A: x1 = 0, x2 = 0

Take the values you know and plug them into the system of equations. Then solve for the remaining variables.

 0 + 0 + s1 = 16 0 + 0 + s2 = 9 0 + 0 + s3 = 24

So s1 = 16, s2 = 9, and s3 = 24

#### Point B: x1 = 0, s1 = 0

Since x1 and s1 are both in the first equation, plug zero in for them to find x2. When you do that, you get 2x2 = 16 so x2 = 8.

Now plug the x1 = 0 and x2 = 8 into the other equations to find s2 and s3.

 0 + 8 + s2 = 9 0 + 8 + s3 = 24

So x2 = 8, s2 = 1, and s3 = 16

#### Point G: x2 = 0, s3 = 0

Since x2 and s3 are both in the third equation, plug zero in for them to find x1. When you do that, you get 3x1 = 24 so x1 = 8.

Now plug the x1 = 8 and x2 = 0 into the other equations to find s1 and s2.

 8 + 0 + s1 = 16 8 + 0 + s2 = 9

So x1 = 8, s1 = 8, and s2 = 1

#### Point H: s1 = 0, s2 = 0

Since s1 and s2 are in the first and second equations, plug zero in for them to find x1 and x2 . When you do that, you get a system of linear equations.

 x1 + 2x2 = 16 x1 + x2 = 9

When you solve that system of linear equations (using substitution, elimination, Gaussian reduction, matrix inverses, or Cramer's Rule), you get x1 = 2 and x2 = 7. A refresher is avaliable about how to solve a system of linear equations.

Then, once you know x1 and x2, plug them into the third equation to find s3.

 2 + 7 + s3 = 24

So x1 = 2, x2 = 7, and s3 = 15

### The Values of All the Variables

Pt x1 x2 s1 s2 s3
A 0 0 16 9 24
B 0 8 0 1 16
C 0 9 -2 0 6
D 0 12 -8 -3 0
E 16 0 0 -7 -24
F 9 0 7 0 -3
G 8 0 8 1 0
H 2 7 0 0 15
I 4 6 0 -1 0
J 6 3 4 0 0

## Determining Which Points Are Feasible

From the graph that we had earlier, we can tell that points A, B, G, H, and J are feasible. Let's add another column to the table to identify whether or not the point is feasible.

Pt x1 x2 s1 s2 s3 Feasible?
A 0 0 16 9 24 yes
B 0 8 0 1 16 yes
C 0 9 -2 0 6 no
D 0 12 -8 -3 0 no
E 16 0 0 -7 -24 no
F 9 0 7 0 -3 no
G 8 0 8 1 0 yes
H 2 7 0 0 15 yes
I 4 6 0 -1 0 no
J 6 3 4 0 0 yes

Notice anything about the points that are not feasible?

What if I mention that one of the restrictions was that every variable be non-negative? Ahh, if there is any negative, then the point is not feasible. Wow, that's cool.

## Putting it All Together

Let's add one more column, this time for the objective function. But we only need to evaluate it for those points that are in the feasible region.

Pt x1 x2 s1 s2 s3 Feasible? P = 40x1 + 30x2
A 0 0 16 9 24 yes 0
B 0 8 0 1 16 yes 240
C 0 9 -2 0 6 no N/A
D 0 12 -8 -3 0 no N/A
E 16 0 0 -7 -24 no N/A
F 9 0 7 0 -3 no N/A
G 8 0 8 1 0 yes 320
H 2 7 0 0 15 yes 290
I 4 6 0 -1 0 no N/A
J 6 3 4 0 0 yes 330

The largest value of the objective function is P = 330 and occurs when x1 = 6 and x2 = 3.

We now have the ability to complete the entire linear programming problem without making a graph at all. Woohoo!