How to Maximize the Value of a Function Using the Simplex Method:
revised 01/30/02

Here the idea is to use Gauss-Jordan elimination on a matrix.  First, we will take each "less than or equal to" inequality, and add whatever quantity it would take to make it an equality, or equation, rather than an inequality.  Since we don't know what that quantity is, we give it a variable name, "s-sub something-or-other."   (These variables are traditionally named "s" to stand for the "slack" they take up between the "less than" and the "equals.")  Next, observe that the function we want to maximize is named "P", and it is an equation, but it is not equal to any numeric constant as are the equations that we made when we introduced the slack variables (one for each inequality).  So, to put it in the same form as these equations, we set the "P" equation equal to 0, but we have to keep the coefficient on "P" positive.

All the above is preparation for doing:

Step-by-step Procedure

Result of Doing Step on Example
Step 1.  Set up the initial matrix (sometimes called "tableau," each row consisting of the coefficients of the variables, including the slack variables, and the right-most entry of the row being the constant on the other side of the equation.  We put the function equation (in our example the P equation, set equal to 0), as the bottom row of the matrix

Notice something.  If you look at the matrix that is formed using only the coefficients of the slack variables, you can see that it looks exactly like a matrix that has been put into completely reduced form using Gauss-Jordan elimination.
So, if we were to assign the value of 0 to each of  x1, x2, and x3, then the rows of our initial matrix would read as follows:
     Row 1:        3(0)   +    3(0)  +      3(0) + 1(s1) + 0(s2) + 0(s3) + 0(P) =   66
     Row 2:       6(0)  +  (-2)(0)  +      4(0) + 0(s1) + 1(s2) + 0(s3) + 0(P) =   48
     Row 3:      3(0)   +    6(0)    +      9(0) + 0(s1) + 0(s2) + 1(s3) + 0(P) = 108
     Row 4:  -10(0) + (-50)(0)  + (-10)(0) + 0(s1) + 0(s2) + 0(s3) + 1(P) =     0

This means that letting   x1= x2= x3 = 0, and letting s1=66, s2 = 48 and s3= 108 does give us a solution to the system of equations.  The only trouble with this solution is it results in P=0 (as we can read from Row 4), not very good for a maximum value for P.

So, our strategy is going to be to look at the bottom row and observe which variable has the most negative coefficient there, and to make the column for that variable have a 1 in it somewhere and 0's elsewhere.  Why?  Because replacing its negative coefficient in the bottom row with 0 means multiplying by a positive number and adding to the bottom row, and hence adding to the value of P.  (The value of P is represented by the last entry in the bottom row).  We can sum this all up with:

Step 2.  Look at the bottom row and determine which variable has the most negative coefficient there

In our example, the variable x2 has the most negative coefficient (-50) in the bottom row.  This tells us that, first of all, we want to give x2 a non-zero value.  So, we want its column to have a 1 somewhere and 0's elsewhere.  But where should we put the 1?  In Row 1 or Row 2 or Row 3?  We answer this question by considering the ratio of each row's constant to that row's x2 coefficient.  In our example, these ratios are 66/3, 48/-2, and 108/6.  The coefficient of x2 that we want to make a 1 is the one whose ratio is the smallest non-negative value.  In our example, the coefficient of x2 that we will choose to make a 1 is the 6, since 108/6=18 is smaller than the other positive ratio.  This discussion leads to:

Step 3.  Consider the ratio of the constant to the x2 coefficient in each of the rows except the bottom row.  Choose the x2 coefficient that yielded the smallest  non-negative ratio. Row 1:  66/3 = 22
Row 2:  48/-2 is a negative value
Row 3: 108/6 = 18

Conclusion:  Choose the x2 coefficient in Row 3, that is, the 6
Step 4.  Multiply the row of the coefficient chosen in Step 3 by the reciprocal of that coefficient.

 
Step 5.  Make a new matrix, using the Row obtained in step 4 as a new row

Step 6.  Multiply the Row that has a 1 as its x2 coefficient by the additive opposite of the x2 coefficient in another row, and add the result of doing that to that other row.  In our example, the x2 coefficient in Row 1 is 3, so we will multiply the row that as a 1 as its x2 coefficient (in our example, this is Row 3) times -3, and add the result of doing that to Row 1.

 
Step 7.  Make a new matrix, using the new row obtained in step 6.

 
Step 8.  Repeat Step 6 for each of the x2 coefficients in the x2 column that are not either a 1 or a zero, including the coefficient in the bottom row.
Step 9.  Make a new matrix, using the rows obtained in Step 8.

Because ALL the coefficients in the bottom row are now non-negative, this tells us that this is the best we can do for P.  That is, P has a maximum value of 900 when x1=0., x2 = 18, x3 = 0,  s1=60, s2 =84, and s3 = 0.  Where is this solution coming from?  The variables whose columns have entries other than "a  1 somewhere and 0's elsewhere are given the value of 0.  This allows the variables whose columns do have "a  1 somewhere and 0's elsewhere" to take on the value of the constant of the row with coefficient "1"  (i.e., not zero).. 

to Frequently Asked Questions                                                          to eMathLab Home Page