. Same answers as we got previously. Simplex Algorithm for Maximisation problem
(Step 1 to Step 5) (Step 6 to 10) (Step 1 to 10)
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:
