document.write( "Question 574988: Use the simplex method to maximize p= 5x+4y+3z subject to the constraints:
\n" ); document.write( "x>=0, y>=0, z>=0, x+y+z<=30, 2x+y+3z<=60, 3x +2y + 4z<= 84 \n" ); document.write( "
Algebra.Com's Answer #369370 by Edwin McCravy(20060)\"\" \"About 
You can put this solution on YOUR website!
Use the simplex method to maximize \r
\n" ); document.write( "\n" ); document.write( "P = 5x + 4y + 3z subject to the constraints:\r
\n" ); document.write( "\n" ); document.write( "x ≧ 0, y ≧ 0, z ≧ 0, x + y + z ≦ 30, 2x + y + 3z ≦ 60, 3x + 2y + 4z ≦ 84
\n" ); document.write( "
\n" ); document.write( "
\r\n" );
document.write( "You can ignore the three x ≧ 0, y ≧ 0, z ≧ 0, because the\r\n" );
document.write( "process itself keeps the variables non-negative.\r\n" );
document.write( "  \r\n" );
document.write( "Put the constraint inequalities, first the objective \r\n" );
document.write( "function equation ay the bottom{\r\n" );
document.write( "\r\n" );
document.write( " x +  y +  z ≦ 30 \r\n" );
document.write( "2x +  y + 3z ≦ 60 \r\n" );
document.write( "3x + 2y + 4z ≦ 84\r\n" );
document.write( " p = 5x + 4y + 3z\r\n" );
document.write( "\r\n" );
document.write( "Make the inequalities into equations by inserting\r\n" );
document.write( "slack variables s1, s2 and s3\r\n" );
document.write( "\r\n" );
document.write( " x +  y +  z + s1 = 30 \r\n" );
document.write( "2x +  y + 3z + s2 = 60 \r\n" );
document.write( "3x + 2y + 4z + s3 - 84\r\n" );
document.write( " p = 5x + 4y + 3z\r\n" );
document.write( "\r\n" );
document.write( "Spread the slack variables out so that all variables are\r\n" );
document.write( "lined up vertically, and and get zero on the right side \r\n" );
document.write( "of the bottom equation by subtracting the right side from \r\n" );
document.write( "both sides:\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "  x +  y +  z +   s1                   = 30 \r\n" );
document.write( " 2x +  y + 3z +         s2             = 60 \r\n" );
document.write( " 3x + 2y + 4z +               s3       = 84\r\n" );
document.write( "-5x - 4y - 3z                     +  P =  0\r\n" );
document.write( " \r\n" );
document.write( "Put in 1 coefficients and 0 times the missing\r\n" );
document.write( "variables,  \r\n" );
document.write( "\r\n" );
document.write( " 1x + 1y + 2z +  1s1 + 0s2 + 0s3  + 0P = 30 \r\n" );
document.write( " 2x + 1y + 3z +  0s1 + 1s2 + 0s3  + 0P = 60 \r\n" );
document.write( " 3x + 2y + 4z +  0s1 + 0s2 + 1s3  + 0P = 84\r\n" );
document.write( "-5x - 4y - 3z +  0s1 + 0s2 + 0s3  + 1P =  0\r\n" );
document.write( "\r\n" );
document.write( "Make this into a matrix (tableau):\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Now we pivot, which involves five steps\r\n" );
document.write( "1. finding the pivot element,\r\n" );
document.write( "2. finding the pivot column,\r\n" );
document.write( "3. finding the pivot row,\r\n" );
document.write( "4. dividing the pivot row through by the element in the pivot row\r\n" );
document.write( "5. using the resulting 1 in the pivot row to get 0's in all\r\n" );
document.write( "the other positions in the pivot column.\r\n" );
document.write( "\r\n" );
document.write( "1.  The pivot element is the most negative element on the bottom row, \r\n" );
document.write( "    which is the -5 at the bottom of the 1st column.\r\n" );
document.write( "2.  The pivot column is the column containing the pivot element, which\r\n" );
document.write( "    is the 1st column.\r\n" );
document.write( "3.  The pivot row is found by dividing each positive number in the pivot\r\n" );
document.write( "    column into the number in the far right in its row.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "30÷1=30, 60÷2=30, 84÷3=28\r\n" );
document.write( "\r\n" );
document.write( "The 28 is the smallest so so the 3rd row is the pivot row.\r\n" );
document.write( "We divide the pivot row through by the 3\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Multiply row 3 by -1 and add to row 1\r\n" );
document.write( "Multiply row 3 by -2 and add to row 2\r\n" );
document.write( "Multiply row 3 by 5 and add to row 4\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( " We repeat the process because there is still a negative number\r\n" );
document.write( "on the bottom row.\r\n" );
document.write( "\r\n" );
document.write( "1.  The pivot element is the most negative element on the bottom row, \r\n" );
document.write( "    (in the case the only one) which is the \"-2%2F3\" at the bottom of the 2nd\r\n" );
document.write( "    column.\r\n" );
document.write( "2.  The pivot column is the column containing the pivot element, which\r\n" );
document.write( "    is the 2nd column.\r\n" );
document.write( "3.  The pivot row is found by dividing each positive number in the pivot\r\n" );
document.write( "    column into the number in the far right in its row.\r\n" );
document.write( "\r\n" );
document.write( "     2÷\"1%2F3\" = 2·\"3%2F1\" = 2·3 = 6\r\n" );
document.write( "\r\n" );
document.write( "We skip dividing by the \"-1%2F3\", since it's negative:\r\n" );
document.write( "\r\n" );
document.write( "     28÷\"2%2F3\" = 28÷\"3%2F2\" = 42\r\n" );
document.write( "\r\n" );
document.write( "The 6 is the smaller so the 1st row is the pivot row.\r\n" );
document.write( "We divide the pivot row through by the \"1%2F3\", which\r\n" );
document.write( "is the same as multiplying it through by 3::\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Multiply row 1 by \"1%2F3\" and add to row 2\r\n" );
document.write( "Multiply row 1 by \"-2%2F3\" and add to row 3\r\n" );
document.write( "Multiply row 1 by \"2%2F3\" and add to row 4\r\n" );
document.write( " \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "There are no more negative numbers on the bottom row, so\r\n" );
document.write( "we are done pivoting.\r\n" );
document.write( "\r\n" );
document.write( "Now we convert it back into a system of equations:\r\n" );
document.write( "\r\n" );
document.write( " 0x + 1y + 2z +  3s1 + 0s2 - 1s3  + 0P =   6 \r\n" );
document.write( " 0x + 0y + 1z +  1s1 + 1s2 - 1s3  + 0P =   5 \r\n" );
document.write( " 1x + 0y + 0z -  2s1 + 0s2 + 1s3  + 0P =  24\r\n" );
document.write( " 0x + 0y + 5z +  2s1 + 0s2 + 1s3  + 1P = 144\r\n" );
document.write( "\r\n" );
document.write( " y + 2z +  3s1 - s3  =   6 \r\n" );
document.write( " z +  s1 + s2 - s3  =   5 \r\n" );
document.write( " 1x - 2s1 + s3 =  24\r\n" );
document.write( " 5z +  2s1 + s3  + P = 144\r\n" );
document.write( "\r\n" );
document.write( "Solve the bottom equation for P:\r\n" );
document.write( "\r\n" );
document.write( "P = 144 - 5z - 2s1 - s3  \r\n" );
document.write( "\r\n" );
document.write( "The most P can be is 144 and that is when z, s1 and s3 are all 0.\r\n" );
document.write( "\r\n" );
document.write( "Substituting those:\r\n" );
document.write( "\r\n" );
document.write( " y + 2(0) +  3(0) - (0)  =   6 \r\n" );
document.write( " (0) +  (0) + s2 - (0)  =   5 \r\n" );
document.write( " x - 2(0) + (0) =  24\r\n" );
document.write( " 5(0) +  2(0) + (0)  + P = 144\r\n" );
document.write( "\r\n" );
document.write( "or\r\n" );
document.write( "\r\n" );
document.write( "y = 6\r\n" );
document.write( "s2 = 5\r\n" );
document.write( "x = 24\r\n" );
document.write( "P = 144\r\n" );
document.write( "\r\n" );
document.write( "So P has maximum value 144 when x=24, y=6, and z=0  \r\n" );
document.write( "\r\n" );
document.write( "The slack variables turn out to be s1=0, s2=5, s3=0\r\n" );
document.write( "\r\n" );
document.write( "Edwin
\r
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );