Expert: Sherry Wallin - 1/17/2011

Question
DETERMINE WHETHER THE GIVEN SIMPLEX TABLEU IS IN FINAL FORM. IF SO, FIND THE SOLUTION TO THE ASSOCIATED REGULAR LINEAR PROGRAMMING PROMBLEM. IF NOT, FIND THE PIVOT ELEMENT TO BE USED IN THE NEXT ITERATION OF THE SIMPLEX METHOD. SHOW ALL WORK.
x y u v P CONSTANT
1 1 1 0 0 6
1 0 -1 1 0 2
3 0 5 0 1 30

Answer
Crama~

I am not sure what you mean by final form. Also, where is the objective function?
Typically in any matrix when you are trying to solve a linear programming problem you want to have 1's down the diagonal and zeros beneath each 1 if possible. In our problem if I just look at the matrix you would need to get rid of the 1 and 3 in the first column so what that means is you would pivot on the element in row1 column1. Subtract row 2 from row 1 getting a new matrix as such:
1 1 1  0 0 6
0 1 2 -1 0 4
3 0 5  0 1 30

Now you need to make the 3 in the first column turn into a 0 and you do this again by pivoting on the 1 in row1 column 1. Multiply row 1 by -3 and add that result to row 3 making the result the new row 3:

1  1 1  0 0 6
0  1 2 -1 0 4
0 -3 2  0 1 12

Notice you have a 1 in the 2nd row 2nd column, that is good because that is your next pivot element. You will need to make the 1 and -3 in col 2 turn to 0's.

subtract row 2 from row 1 and make that result the new row 1:

1  0 -1  1 0 2
0  1  2 -1 0 4
0 -3  2  0 1 12

To make the -3 in the 2nd row 2nd column multiply row 2 by 3 and add it to row 3 and make that result your new row 3:

1  0 -1  1 0 2
0  1  2 -1 0 4
0  0  8 -3 1 0

Next you need the element in row 3 column 3 to be a 1 so divide row 3 by 8:
1   0  -1   1    0    2
0   1   2  -1    0    4
0   0   1  -3/8  1/8  0

Row 3 column 3 is your last pivot element you will use to make the -1 and 2 in column 3 turn to 0's.
Add row 1 to row 3 and make the result your new row 1

1   0   0   5/8  1/8  2
0   1   2  -1    0    4
0   0   1  -3/8  1/8  0

and finally multiply row 3 by a -2 and add the result to make your new row 2:

x   y   u     v     p    c
1   0   0   5/8  1/8  2
0   1   0  -1/4 -1/4  4
0   0   1  -3/8  1/8  0

You now have 1's down the diagonal and 0's in each of the columns with the 1's on the diagonal so there is no pivoting left to be done. The variables you started with are x,y,v,u,p,c where I used c to represent the constant

x = -5/8 v - 1/8 p - 2
y = 1/4 v +1/4 p - 4
u = 3/8 v - 1/8 p

v and p are 'free' variables meaning you have an infinite number of solutions depending on what values you assign to p and v


Math Prof