SOLUTION: Maximize P=3x+y+3z Subject to 2x+y+z≦2 x+2y+3z≦5 2x+2y+z≦6 x,y,z≧0 Use simplex method

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