Maximize P = 3x + y + 3z Subject to 2x + y + z ≦ 2 x + 2y + 3z ≦ 5 2x + 2y + z ≦ 6 x,y,z ≧ 0 We introduce non-negative slack variables s1, s2, and s3 which are just enough to make the left side of the inequalities equal to their right sides, and we also add 0P to the left side which does not change the value. 2x + y + z + s1 + 0P = 2 x + 2y + 3z + s2 + 0P = 5 2x + 2y + z + s3 + 0P = 6 We write the objective function P=3x+y+3z as -3x - y - 3z + 0s1 + 0s2 + 0s3 + P = 0 So we have this system of equations: 2x + y + z + s1 + 0P = 2 x + 2y + 3z + s2 + 0P = 5 2x + 2y + z + s3 + 0P = 6 -3x - y - 3z + 0s1 + 0s2 + 0s3 + P = 0 It is 4 equations in 7 variables, so it has many solutions, but we want the solution that maximizes the variable P. We put in all the coefficients of all the variables, including 0'a and 1's: 2x + 1y + 1z + 1s1 + 0s2 + 0s3 + 0P = 2 1x + 2y + 3z + 0s1 + 1s2 + 0s3 + 0P = 5 2x + 2y + 1z + 0s1 + 0s2 + 1s3 + 0P = 6 ----------------------------------------- -3x - y - 3z + 0s1 + 0s2 + 0s3 + 1P = 0 We want to get the bottom equation so that it will have no negative terms on it so that when we solve it for P, we will only have subtractions of positive numbers from it, and we can then make P largest by choosing the subtractions of non-negative variables to all be 0. Now we make it into a matrix with partitions (called the first "tableau"): x y z | s1 s2 s3 | P | k ------------------------------------------ 2.0 1.0 1.0 | 1.0 0.0 0.0 | 0.0 | 2.0 1.0 2.0 3.0 | 0.0 1.0 0.0 | 0.0 | 5.0 2.0 2.0 1.0 | 0.0 0.0 1.0 | 0.0 | 6.0 ------------------------------------------ -3.0 -1.0 -3.0 | 0.0 0.0 0.0 | 1.0 | 0.0 We want to end up with no negative numbers on the bottom row. We take the most negative number in the bottom row (these are called "indicators") and call the column which it's in "the pivot column" CHOOSE THE PIVOT COLUMN: We could choose either one of the -3's as the most negative indicator. We will choose the -3 in the column 1 as the most negative indicator. So column 1 is the pivot column. CHOOSE THE PIVOT ROW: To the side, divide each of the positive numbers in the pivot column INTO the number on the same row in the rightmost column (headed "k"): 1 5 3 2)2 1)5 2)6 We find that the least of these is 1, which was obtained when we divided the 2 in the pivot column row 1 into the 2 at the far right, so we call row 1 "the pivot row", and we call the element 2 "the pivot element". So we have a pivot column, a pivot row and a pivot element. Now we will do what is called "pivoting" on an element. 1. Divide the pivot row through by the pivot element. This causes the pivot element to become 1. 2. Multiply the new pivot row by whatever is necessary so that when it is added to the other rows there will be 0's everywhere else in the pivot column. 1.0 0.5 0.5 | 0.5 0.0 0.0 | 0.0 | 1.0 0.0 1.5 2.5 |-0.5 1.0 0.0 | 0.0 | 4.0 0.0 1.0 0.0 |-1.0 0.0 1.0 | 0.0 | 4.0 ------------------------------------------ 0.0 0.5 -1.5 | 1.5 0.0 0.0 | 1.0 | 3.0 That's the second tableau. It is not the final tableau because it has a negative indicator of -1.5 at the bottom of column 3. So the pivot column is column 3. CHOOSE THE PIVOT ROW: To the side, divide each of the positive numbers in the pivot column INTO the number on the same row in the rightmost column (headed "k"): 1.6 2 2.5)4 0.5)1 Since 1.6 is smaller than 2, the pivot row is row 2. The pivot element is the 1 on the second row. Now we pivot again. 1. Divide the pivot row through by the pivot element. (That's not necessary because the pivot element is already 1) 2. Multiply the pivot row by whatever is necessary so that when it is added to the other rows there will be 0's everywhere else in the pivot column. The final tableau is 1.0 0.2 0.0 | 0.6 -0.2 0.0 | 0.0 | 0.2 0.0 0.6 1.0 | -0.2 0.4 0.0 | 0.0 | 1.6 0.0 1.0 0.0 | -1.0 0.0 1.0 | 0.0 | 4.0 ------------------------------------------- 0.0 1.4 0.0 | 1.2 0.6 0.0 | 1.0 | 5.4 It is the final tableau because there are no negative numbers on the bottom row. Now we convert back to equations: 1.0x + 0.2y + 0.0z + 0.6s1 - 0.2s2 + 0.0s3 + 0.0P = 0.2 0.0x + 0.6y + 1.0z - 0.2s1 + 0.4s2 + 0.0s3 + 0.0P = 1.6 0.0x + 1.0y + 0.0z - 1.0s1 + 0.0s2 + 1.0s3 + 0.0P = 4.0 -------------------------------------------------------- 0.0x + 1.4y + 0.0z + 1.2s1 + 0.6s2 + 0.0s3 + 1.0P = 5.4 Simplifying: x + 0.2y + 0.6s1 - 0.2s2 + 0.0s3 = 0.2 0.6y + z - 0.2s1 + 0.4s2 + 0.0s3 + 0.0P = 1.6 y - s1 + s3 = 4.0 --------------------------------------------- 1.4y + 1.2s1 + 0.6s2 + P = 5.4 Solve the bottom equation for P P = 5.4 - 1.4y - 1.2s1 - 0.6s2 So obviously P takes on its maximum value when nothing is subtracted from the 5.4. This will be when y, s1, and s2 are all 0. Substituting 0 for these three variable in the above, and simplifying: x = 0.2 z = 1.6 s3 = 4.0 --------------------------------------------- P = 5.4 So P has the maximum value of 5.4 when x=0.2, y=0, z=1.6 Edwin