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

1. Standard Form requires all variables to be on the left hand side (LHS) and all constants on the RHS

 P  - 3Q - 2R = 0 2Q + R ≤ 100 Q + R ≤ 80 Q ≤ 40

1. Change all inequalities equations to equality equations. This requires the adding of a slack or excess variable.

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 + S1 = 100                  (S1 : the first constraint slack variable)

(ii)        Q + R ≤ 80

Q + R + S2 = 80                      (S2 : the first constraint slack variable)

(iii)       Q ≤ 40

Q + S3 = 40                             (S3 : the first constraint slack variable)

Thus we have

 P  - 3Q - 2R = 0 2Q + R + S1 = 100 Q + R + S2 = 80 Q + S3 = 40

Where all variables (P, Q, R, S1, S2, S3) ≥ 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, S1, S2, S3), thus the no. of columns is 6 + 5 = 11

 Margin P Q R S1 S2 S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 0

For 2Q + R + S1 = 100. The coefficients of Q in this case is 2 and R is 1 and of S1 is 1. The coefficients of P, S2 and S3 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 S1 S2 S3 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, S1, S2 and S3. 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; S1 = 100, S2 = 80 and S3 = 40. This solution to this equation is called the basic feasible solution (it is the simplest solution). Q and R are thus the non-basic variables and P, S1, S2 and S3 are basic variables.

 P  - 3Q - 2R = 0 2Q + R + S1 = 100 Q + R + S2 = 80 Q + S3 = 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, S1, S2 and S3). 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 S1 column, the 1 appears in row 1, and thus S1 enters into row 1 of the BV column. The same applies for S2 and S3

 Margin P Q R S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P 0 0 2 1 1 0 0 100 S1 1 0 1 1 0 1 0 80 S2 2 0 1 0 0 0 1 40 S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P 0 0 2 1 1 0 0 100 S1 1 0 1 1 0 1 0 80 S2 2 0 1 0 0 0 1 40 S3 3

Back to ME30B main page

[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=X-2Y-S, 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.