Simplex Algorithm for Maximisation problem
(Step 1 to 6) (Step 7 to 10) (Step 1 to 10)
Max P = 
3Q + 
2R 

s.t. 




2Q + 
R 
≤ 100 

Q + 
R 
≤ 80 

Q 

≤ 40 

Q, R ≥ 0 

Step 1. Convert LP to standard form
P  
3Q  
2R 
= 0 

2Q + 
R 
≤ 100 

Q + 
R 
≤ 80 

Q 

≤ 40 
Example, for 2X + Y ≤ 150, if this was converted into an equality equation we will have 2X + Y + S = 150. S is called a slack variable because suppose that 2X + Y = 130, then S will have to pick up a slack of 20 to ensure that the equation equals to 150, i.e. 130 + 20 = 150. If instead we had 2X + Y ≥ 150, then to convert this to equality we have 2X + Y  E = 150. E is called the excess, because suppose that 2X + Y = 180, then E will have to account for the excess 30 to ensure the equation is equal to 150 i.e. 180 – 30 = 150.
Thus for our case, converting our inequality equations to equality equations, we have:
(i) 2Q + R ≤ 100
2Q + R + S_{1} = 100 (S_{1} : the first constraint slack variable)
(ii) Q + R ≤ 80
Q + R + S_{2} = 80 (S_{2} : the first constraint slack variable)
(iii) Q ≤ 40
Q + S_{3} = 40 (S_{3} : the first constraint slack variable)
Thus we have
P  
3Q  
2R 



= 0 


2Q + 
R + 
S_{1} 


= 100 


Q + 
R + 
_{ } 
S_{2} 

= 80 


Q + 



S_{3} 
= 40 

Where all variables (P, Q, R, S_{1}, S_{2}, S_{3}) ≥ 0.
Step 2. Prepare the tableau for conducting the simplex algorithm
The tableau has to have a column for each variable, a row column, a ratio column, RHS column, basic variable (BV) column, a working column/margin i.e. no. of variables + 5.
In this case we have 6 variables (P, Q, R, S_{1}, S_{2}, S_{3}), thus the no. of columns is 6 + 5 = 11
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

































Step 3. Insert the coefficients and RHS of each variable into tableau
The coefficients of each variable are placed in its labelled column corresponding to its row. The objective function row is sometimes called row 0.
Thus for P – 3Q – 2R = 0, to put this into the tableau, in the first row, we place 1 under the P column, because the coefficient of P is 1. For Q, its coefficient is 3, and that goes under the Q column, and similarly, 2 is placed under the R column. The RHS value of this equation is 0, and thus 0 is placed under RHS column. Since this row is called row 0, we enter 0 under the row column.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 


0 






















For 2Q + R + S_{1} = 100. The coefficients of Q in this case is 2 and R is 1 and of S_{1} is 1. The coefficients of P, S_{2} and S_{3} are all 0. These coefficients are placed in the next row in the appropriate columns. The RHS is 100, and thus placed under the RHS column. This row is called row 1 and corresponds to the first constraint. This is continued for the next two constraints.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 


0 

0 
2 
1 
1 
0 
0 
100 


1 

0 
1 
1 
0 
1 
0 
80 


2 

0 
1 
0 
0 
0 
1 
40 


3 
Step 4. Determine the basic feasible solution (bfs) and the basic variables
If we look at the problem again, we notice that have four equations and six variables. If you recall when you did simultaneous equations, you always had two variables and two equations. To solve equations and ensure that a value is obtained for them we must have equal number of equations and equal number of variables. Unfortunately, we do not have in this case. To get around that problem, we set the some variables equal to zero, to allow equal number of variables and equal number of equations. So, in this case where we have 6 variables and 4 equations, we will need to set two variables equal to zero, and thus have 4 variables and 4 equations.
We note if we look at our equations, we see that if we set Q and R equal to zero, we can obtain values for P, S_{1}, S_{2} and S_{3}. The variables that are set to zero are called non basic variables (NBV) and those that a value has been obtained for are called basic variables (BV).
If Q = 0 and R = 0, then P = 0; S_{1} = 100, S_{2} = 80 and S_{3} = 40. This solution to this equation is called the basic feasible solution (it is the simplest solution). Q and R are thus the nonbasic variables and P, S_{1}, S_{2} and S_{3} are basic variables.
P  
3Q  
2R 



= 0 


2Q + 
R + 
S_{1} 


= 100 


Q + 
R + 
_{ } 
S_{2} 

= 80 


Q + 



S_{3} 
= 40 

Step 5. Place the basic variables into the tableau.
If we look at the tableau, we would note there are columns with only a one and three zeroes (shaded in pink). You will notice that these four columns are actually our basic variables columns (P, S_{1}, S_{2} and S_{3}). We need to enter our basic variables into the basic variables columns. To decide which row our basic variable should enter, we look at a basic variables column, and locate the row in which the 1 is placed. For example, for P, the 1 is located in row 0. Therefore, the basic variable, P, will enter in row 0, in the BV column. Similarly, for the S_{1} column, the 1 appears in row 1, and thus S_{1} enters into row 1 of the BV column. The same applies for S_{2} and S_{3}
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 

0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 

1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 

2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 

3 
Step 6. Determine the entering variable.
If we look back at our objective function:
P = 3Q + 2R
We note that if we wish to increase P, the best variable to have a high value is Q, because its coefficient of 3 is higher than R’s coefficient of 2.
Thus we will like to make Q as large as possible. Q is called our entering variable (EV). If you remember we had rewritten the objective equation as
P – 3Q – 2R = 0
And we placed its coefficients into the tableau. We note that the entering variable, Q, has the highest negative value. Thus, whenever we need to find the entering variable from the tableau, we look at the row containing the objective function (row 0), and locate the variable with highest negative value (shaded in yellow).^{[1]}
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 

0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 

1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 

2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 

3 
Step 7. Perform the ratio test
We have to remember the amount to which we can increase Q, our entering variable, is determined by the constraints.
Thus if we look at the first constraint:
2Q + R + S_{1} = 100
The most that Q can be is 50. (We set R and S_{1} = 0).
According to the second constraint:
Q + R + S_{2} = 80
The most that Q can be is 80 (R = S_{2} = 0)
Lastly, for the third constraint
Q + S_{3} = 40
The most that Q can be is 40 (S_{3} = 0)
An easier way to find the maximum values of Q for each constraint is finding the following ratio
RHS of Constraint 
Coefficient of the Entering Variable 
Thus for the first constraint the ratio will be . Same answers as we got previously.
We note according to these constraints can be Q ≤ 50 or Q ≤ 80 or Q ≤ 40. Now, since the value of Q has to satisfy all these constraints, Q has to taken the lowest value of Q ≤ 40. The lowest value is sometimes referred to the winner of the ratio test. The third constraint or row 3, has the lowest ratio, and it is called the pivot row.
We note that if Q ≤ 80 (for the second constraint), we have no guarantee it will satisfy the first constraint (Q ≤ 50) or the third constraint (Q ≤ 40).
We now enter the ratios for Q into the tableau, with each ratio to its corresponding row or constraint. Note: There is no ratio test for the objective function!! Since it is the objective function we wish to increase subject to the constraints. You may write if you wish, the entering variable in the row 0 space of the ratio column (shaded green). We look for the winner of the ratio test (i.e. the lowest ratio in red). We locate the value of our entering variable, Q, in our pivot row (shaded pink). This value (in blue) is sometimes referred to as the pivot variable.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
Step 8. Perform elementary row operations (ero) to make EV basic
Now, to make Q as large as possible that means, its value will no longer be zero and a value will be obtained. Thus, Q will have to become a basic variable. If Q becomes basic, then one of the current basic variables must become nonbasic or value placed at 0. Since, this pivot row (in pink), has S_{3} as its basic variable, we will make S_{3} = 0 and make Q the basic variable in this row.
Now if you recall, a basic variable column contained a one and some zeroes. Thus we need to make the Q column (shaded in tan) look like that too. Since, we have decided that row 3 is the pivot row; we will make Q have a value of 1 in this row, and zeroes in the rest of the rows.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
To carry out this operation, we perform something called elementary row operations. To do this, we multiply our whole pivot row by a value and then add it to another row to make its value in the column of the entering variable equal to zero.
(Note: we multiply a value by the pivot row and then add it to another row NOT the other way around)
So, in the case of our entering variable Q, we need to make the values for row 0, row 1 and row 2 = 0 and for row 3 = 1. Now to make the value 3 in row 0 (shaded red), to be 0, we will need to multiply row 3 (every value in row 3) by 3 and then add it to row 0.
If you cannot determine the multiplication value intuitively, note that the value we multiply the pivot row is always equal to
Thus for row 1, the value we will have to multiply row 3 by will be equal to (1)/ (1) * (3) = 3. In column Q we will have (3) * (1) + (3) = 0 (see table for corresponding shade). Thus, for column S_{3} we will have (3) * (1) + (0) = 3. We will do the same for all columns. We will enter these new values has a new calculation in a different row and extend our table.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 


0 

































We will continue performing the same type of eros for the row 1 and row 2. In row 1 case, we will multiply row 3 by 2 and then add it to row 1 (shaded pink) and in row 2 case multiply row 3 by 1 and add it to row 2 (shaded blue).
For the pivot row, we multiply the row by its reciprocal. We are lucky in this case, in that the pivot value is 1, and thus its reciprocal is 1, hence we don’t do anything to this row, However, if the pivot value was another value say 2, then we would have had to multiply the row by ½ (i.e. its reciprocal) to change the pivot value to 1.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 


0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 


1 
R3 + R1 
0 
0 
1 
0 
1 
1 
40 


2 

0 
1 
0 
0 
0 
1 
40 


3 
We now look at our columns that have only a one and zeroes, to determine the row for which the variable is basic as was done in Step 5. We note this time around Q is basic.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 

0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 

1 
R3 + R1 
0 
0 
1 
0 
1 
1 
40 
S_{2} 

2 

0 
1 
0 
0 
0 
1 
40 
Q 

3 
Step 9. Look for new entering variables
We will go through the whole process from Step 6, again, until we find no more entering variables. We will look in row 0 to determine if there are any negative numbers, and determine the most negative. In this case 2 under column R is the most negative (shaded yellow). Thus, R is our new entering variable. We will then perform our ratio test as in Step 7. We note this time that in row 3 we have a division of 40/0, this means that R is not constrained in row 3 (i.e. it has no bearing or value to row 3 and according to row 3 can be as big as it wishes), so we write not applicable (N/A) for that ratio. We find the winner of the ratio test is in row 1 (shaded pink). The pivot variable is thus 1 (shaded blue).
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 
EV = R 
0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 
20 
1 
R3 + R1 
0 
0 
1 
0 
1 
1 
40 
S_{2} 
40 
2 

0 
1 
0 
0 
0 
1 
40 
Q 
N/A 
3 
We thus have to make R basic (i.e. have a column with a one and zeros), and allow its value of 1 to be in row 1. We will perform ero as in Step 8, to accomplish this. We note that since row 3 has no R, we don’t have to perform any ero on this row. We will then enter the basic variables as in Step 5.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 
EV = R 
0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 
20 
1 
R3 + R2 
0 
0 
1 
0 
1 
1 
40 
S_{2} 
40 
2 
1*R3 
0 
1 
0 
0 
0 
1 
40 
Q 
N/A 
3 
2*R1 + R0 
1 
0 
0 
2 
0 
1 
160 
P 

0 
1*R2 
0 
0 
1 
1 
0 
2 
20 
R 

1 
1*R1 + R2 
0 
0 
0 
1 
1 
1 
20 
S_{2} 

2 

0 
1 
0 
0 
0 
1 
40 
Q 

3 
We again look for any entering variables in row 0. This time we notice that the most negative number in row 0 is 1 located under column S_{3} (shaded yellow). S_{3} is therefore our new entering variable. We perform the ratio test again. We note that for row 1, the ratio test will be (20/2) = 10. This means that S_{3} ≤ 0, and since this is not allowed, we enter that ratio as N/A. The winner of the ratio test is 20 in row 2 (shaded pink), and the pivot variable is 1 in row 2 (shaded blue)
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 
EV = R 
0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 
20 
1 
R3 + R2 
0 
0 
1 
0 
1 
1 
40 
S_{2} 
40 
2 
1*R3 
0 
1 
0 
0 
0 
1 
40 
Q 
N/A 
3 
2*R1 + R0 
1 
0 
0 
2 
0 
1 
160 
P 
EV = S_{3} 
0 
1*R2 
0 
0 
1 
1 
0 
2 
20 
R 
N/A 
1 
1*R1 + R2 
0 
0 
0 
1 
1 
1 
20 
S_{2} 
20 
2 

0 
1 
0 
0 
0 
1 
40 
Q 
40 
3 
We once more perform ero to make S_{3} basic in row 2 as in Step 8. We then place the basic variables as in Step 5. At the end of this iteration, we look once more at row 0 to see if there are any coefficients that are negative. We note that in row 0 (shaded in blue), there are no negative coefficients. Therefore, we have reached the end of our simplex algorithm procedure and have maximised P to its highest possible value.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 
EV = R 
0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 
20 
1 
R3 + R2 
0 
0 
1 
0 
1 
1 
40 
S_{2} 
40 
2 
1*R3 
0 
1 
0 
0 
0 
1 
40 
Q 
N/A 
3 
2*R1 + R0 
1 
0 
0 
2 
0 
1 
160 
P 
EV = S_{3} 
0 
1*R2 
0 
0 
1 
1 
0 
2 
20 
R 
N/A 
1 
1*R1 + R2 
0 
0 
0 
1 
1 
1 
20 
S_{2} 
20 
2 

0 
1 
0 
0 
0 
1 
40 
Q 
40 
3 

1 
0 
0 
1 
1 
0 
180 
P 

0 

0 
0 
1 
1 
2 
0 
60 
R 

1 

0 
0 
0 
1 
1 
1 
20 
S_{3} 

2 

0 
1 
0 
1 
1 
0 
20 
Q 

3 
Step 10. Determine the solution
To determine the solution, we look at the RHS column of the last iteration (shaded in yellow) and its corresponding BV column (shaded in mauve). The value of each BV in is the corresponding value in the RHS column i.e. P = 180, R = 60, S_{3} = 20 and Q = 20.
Thus if we look back at our objective function P = 3Q + 2R, and we substitute in Q and R values we have P = 3(20) + 3(20) = 180. It is the same P value that we obtained.
Since S_{1} and S_{2} are not in the BV column, this means their value is zero. If S_{1} = S_{2} = 0, then it must means constraint 1 and 2 are binding (i.e. there is no slack – all resources have been used). S_{3} = 20, means the constraint is nonbinding and there are 20 units not used.
Margin 
P 
Q 
R 
S_{1} 
S_{2} 
S_{3} 
RHS 
BV 
Ratio 
Row 

1 
3 
2 
0 
0 
0 
0 
P 
EV = Q 
0 

0 
2 
1 
1 
0 
0 
100 
S_{1} 
50 
1 

0 
1 
1 
0 
1 
0 
80 
S_{2} 
80 
2 

0 
1 
0 
0 
0 
1 
40 
S_{3} 
40 
3 
3* R3 + R0 
1 
0 
2 
0 
0 
3 
120 
P 
EV = R 
0 
2*R3 + R1 
0 
0 
1 
1 
0 
2 
20 
S_{1} 
20 
1 
R3 + R2 
0 
0 
1 
0 
1 
1 
40 
S_{2} 
40 
2 
1*R3 
0 
1 
0 
0 
0 
1 
40 
Q 
N/A 
3 
2*R1 + R0 
1 
0 
0 
2 
0 
1 
160 
P 
EV = S_{3} 
0 
1*R2 
0 
0 
1 
1 
0 
2 
20 
R 
N/A 
1 
1*R1 + R2 
0 
0 
0 
1 
1 
1 
20 
S_{2} 
20 
2 

0 
1 
0 
0 
0 
1 
40 
Q 
40 
3 

1 
0 
0 
1 
1 
0 
180 
P 

0 

0 
0 
1 
1 
2 
0 
60 
R 

1 

0 
0 
0 
1 
1 
1 
20 
S_{3} 

2 

0 
1 
0 
1 
1 
0 
20 
Q 

3 
The solution to this algorithm comes directly from the last iteration in a matrix form.
Remember matrix equation
AX = B
If we extract the entire binding variables columns we can write (shaded in blue) and then rearrange the columns to form an identity matrix, we note we get the same answers:
[1] If we were doing a minimization problem then we would look for the variable that will decrease the objective function the most i.e. the most positive in the tableau e.g. If U=X2YS, we will try and make Y the largest value, when we rewrite the problem U  X + 2Y + S = 0, and place it into the tableau, Y has the highest positive coefficient. All steps follow exactly the same (even the ratio test) except in the objective function row, we look for the most positive number to be the entering variable. The minimization problem is finished when there are only negative numbers in row 0.