SOLUTION: ----------- --- Maximize f=7x1+5x2 subject to 8x1+6x2≤65 7x1+9x2≤70 x1≥0 x2≥0 [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ]

In these linear programming problems we assume that no variables are ever
negative, but they can be 0.  So all variables here are assumed to be
non-negative.  , .

Introduce non-negative slack variables s1 and s2 to turn the
inequalities into equations:



Rewrite  as 



Rewrite the system in matrix form using the five variables:


Next, we will perform the pivot operation. That is a method to make
one element in a column (the pivot column) 1, then use the 1 to
make all the other elements in the pivot column 0.

We will find the pivot indicator, the pivot column, the pivot row,
and the pivot element.

The pivot indicator is the most negative number on the bottom row.
In this case -7 is the most negative number on the bottom row, so
the pivot indicator is -7.

The pivot column is the column which the pivot indicator is in, so
the pivot column is the 1st column.

Next we determine the pivot element. To do that, we divide each positive
number in the pivot column above the pivot element into the number at the
far right, in the column indicated by an "=".
   8.125   10
8)65     7)70

8.125 < 10, so 8.125 is the smaller of them, and since it was the 8 that we used
to get the smaller quotient, that means 8 is pivot element.

The pivot row is the row that the pivot element is on, the 1st row.

Now we make the pivot element 1 by dividing the first row through by 8.



Now we make the 7 in the 1st column into a 0 by multiplying the 1st row by -7
and adding it to row 2:



Now we make the -7 in the 1st column into a 0 by multiplying the 1st row by 7
and adding it to row 3:



Now there are no negative numbers on the bottom row, so this is the final
matrix.  Now we convert the matrix back into a system of equations:



The bottom equation contains f that we wish to maximize:



Solve it for f



We wish to maximize f.  It will be the largest it can possibly be when
the two terms subtracted from 455/8 are as small as they can be.  They cannot
be negative, so the smallest they can be is 0.  So if we make both x2 and s1
equal to 0, we can keep the whole 455/8 for f and not subtract anything from
it.

So we choose x2 = 0 and s1 = 0. Substituting:





So the answer is that f has a maximum value of 455/8, when x1=65/8 and x2=0.

Edwin