SOLUTION: Solve the following linear programming problem. Maximize P = x + 4y − 2z subject to 3x + y − z ≤ 80 2x + y − z ≤ 40 −x + y + z ≤ 80 x≥ 0, y≥ 0,

Maximize:

subject to the constraints:


We add non-negative slack variables s1, s2, s3
to the left sides of the inequalities to turn 
the inequalities into equations, and put the 
objective equation at the bottom.
 


We form the initial matrix ("tableau"):



The most negative number on the bottom row is -4.
It is in column 2, so we call column 2 "the pivot 
column". We divide each (the only) positive number 
above the pivot element INTO the number at the far
right to see which gives the smallest positive 
answer.

  40         
1)40        

We get the smallest (only) value when we divide 1 
into the number at the far right, so 1 in the pivot 
column is the pivot element.

The pivot element is already 1.  So we make 0's 
elsewhere in the pivot column, using the pivot row. 
Making an element of a column become 1 and all the 
other elements in the column become 0 is called 
"pivoting" on the pivot element.



R3*(-1)+R1-->R1 gets 0 for 1st element of pivot column.



R3*(-1)+R2-->R2 gets 0 for 2nd element of pivot column.



R3*(-1)+R3-->R3 gets 0 for 3rd element of pivot column.



R3*(4)+R4-->R4 gets 0 for bottom element of pivot column.



Now we start all over.

The most negative number on the bottom row is -2.
It is in column 3, so we call column 3 "the pivot column".
We divide each (the only) positive number above the pivot 
element INTO the number at the far right to see which 
gives the smallest positive answer.

  20         
2)40        

We get the smallest (only) value when we divide 2 into the 
number at the far right, so 2 in the pivot column is the 
pivot element.

The pivot element is not 1, so we must make it 1.

R3*(1/2)-->R3, makes the pivot element become 1

 

R3+R2--R2 makes the -1 in the pivot column become 0

 

R3*2+R4--R4 makes the bottom element in the pivot column become 0



There are no negative numbers on the bottom row, so the
matrix work is complete.

Now we turn the matrix back into a system of equations:



Solve the bottom equation for P



None of the variables can be negative, so the obvious
way to make P the largest possible value, is to choose
x, s2, and s3 all to be 0. That way we keep the entire
200 for P and subtract nothing from it. We substitute 0 
for them all in the system of equations:





So the maximum value for P is 200, when x=0, y=60, and z=20.

Edwin