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

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).

 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 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 + S1 = 100

The most that Q can be is 50. (We set R and S1 = 0).

According to the second constraint:

Q + R + S2 = 80

The most that Q can be is 80 (R = S2 = 0)

Lastly, for the third constraint

Q + S3 = 40

The most that Q can be is 40 (S3 = 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 non-basic or value placed at 0. Since, this pivot row (in pink), has S3 as its basic variable, we will make S3 = 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 40 3 3* R3 + R0 1 0 -2 0 0 3 120 P 0 -2*R3 + R1 0 0 1 1 0 -2 20 S1 1 -R3 + R1 0 0 1 0 1 -1 40 S2 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 20 1 -R3 + R1 0 0 1 0 1 -1 40 S2 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 20 1 -R3 + R2 0 0 1 0 1 -1 40 S2 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 S2 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 S3 (shaded yellow). S3 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 S3 ≤ 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 20 1 -R3 + R2 0 0 1 0 1 -1 40 S2 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 = S3 0 1*R2 0 0 1 1 0 -2 20 R N/A 1 -1*R1 + R2 0 0 0 -1 1 1 20 S2 20 2 0 1 0 0 0 1 40 Q 40 3

We once more perform ero to make S3 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 S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 20 1 -R3 + R2 0 0 1 0 1 -1 40 S2 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 = S3 0 1*R2 0 0 1 1 0 -2 20 R N/A 1 -1*R1 + R2 0 0 0 -1 1 1 20 S2 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 S3 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, S3 = 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 S1 and S2 are not in the BV column, this means their value is zero. If S1 = S2 = 0, then it must means constraint 1 and 2 are binding (i.e. there is no slack – all resources have been used). S3 = 20, means the constraint is non-binding and there are 20 units not used.

 Margin P Q R S1 S2 S3 RHS BV Ratio Row 1 -3 -2 0 0 0 0 P EV = Q 0 0 2 1 1 0 0 100 S1 50 1 0 1 1 0 1 0 80 S2 80 2 0 1 0 0 0 1 40 S3 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 S1 20 1 -R3 + R2 0 0 1 0 1 -1 40 S2 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 = S3 0 1*R2 0 0 1 1 0 -2 20 R N/A 1 -1*R1 + R2 0 0 0 -1 1 1 20 S2 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 S3 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:  Back to ME30B main page

 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.