Simplex Algorithm for Maximisation problem
(Step 1 to Step 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 
[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.