document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1001917>Question 1001917</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Maximize P=3x+y+3z<BR>\n" );
document.write( "Subject to 2x+y+z&#8806;2<BR>\n" );
document.write( "          x+2y+3z&#8806;5<BR>\n" );
document.write( "          2x+2y+z&#8806;6<BR>\n" );
document.write( "          x,y,z&#8807;0<BR>\n" );
document.write( "Use simplex method </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #619171 by </B><A HREF=/tutors/aboutme.mpl?userid=Edwin+McCravy><B>Edwin McCravy(20056)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=Edwin+McCravy><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=Edwin+McCravy><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=619171\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <PRE STYLE=\"white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;\">\r\n" );
document.write( "Maximize P = 3x + y + 3z\r\n" );
document.write( "Subject to \r\n" );
document.write( "2x +  y +  z &#8806; 2\r\n" );
document.write( " x + 2y + 3z &#8806; 5\r\n" );
document.write( "2x + 2y +  z &#8806; 6\r\n" );
document.write( "\r\n" );
document.write( "x,y,z &#8807; 0\r\n" );
document.write( "\r\n" );
document.write( "We introduce non-negative slack variables s1, s2, and s3\r\n" );
document.write( "which are just enough to make the left side of the \r\n" );
document.write( "inequalities equal to their right sides, and we also \r\n" );
document.write( "add 0P to the left side which does not change the value.\r\n" );
document.write( "\r\n" );
document.write( "2x +  y +  z +  s1             + 0P = 2\r\n" );
document.write( " x + 2y + 3z        + s2       + 0P = 5\r\n" );
document.write( "2x + 2y +  z              + s3 + 0P = 6\r\n" );
document.write( "\r\n" );
document.write( "We write the objective function P=3x+y+3z\r\n" );
document.write( "as\r\n" );
document.write( "\r\n" );
document.write( "-3x - y - 3z + 0s1 + 0s2 + 0s3 + P = 0 \r\n" );
document.write( "\r\n" );
document.write( "So we have this system of equations:\r\n" );
document.write( "\r\n" );
document.write( " 2x +  y +  z +  s1             + 0P = 2\r\n" );
document.write( "  x + 2y + 3z        + s2       + 0P = 5\r\n" );
document.write( " 2x + 2y +  z              + s3 + 0P = 6\r\n" );
document.write( "-3x -  y - 3z + 0s1 + 0s2 + 0s3 +  P = 0\r\n" );
document.write( "\r\n" );
document.write( "It is 4 equations in 7 variables, so it has many\r\n" );
document.write( "solutions, but we want the solution that maximizes\r\n" );
document.write( "the variable P.  We put in all the coefficients of \r\n" );
document.write( "all the variables, including 0'a and 1's:\r\n" );
document.write( "\r\n" );
document.write( " 2x + 1y + 1z + 1s1 + 0s2 + 0s3 + 0P = 2\r\n" );
document.write( " 1x + 2y + 3z + 0s1 + 1s2 + 0s3 + 0P = 5\r\n" );
document.write( " 2x + 2y + 1z + 0s1 + 0s2 + 1s3 + 0P = 6\r\n" );
document.write( "-----------------------------------------\r\n" );
document.write( "-3x -  y - 3z + 0s1 + 0s2 + 0s3 + 1P = 0\r\n" );
document.write( "\r\n" );
document.write( "We want to get the bottom equation so that it\r\n" );
document.write( "will have no negative terms on it so that when\r\n" );
document.write( "we solve it for P, we will only have subtractions\r\n" );
document.write( "of positive numbers from it, and we can then make\r\n" );
document.write( "P largest by choosing the subtractions of \r\n" );
document.write( "non-negative variables to all be 0.\r\n" );
document.write( "\r\n" );
document.write( "Now we make it into a matrix with partitions\r\n" );
document.write( "(called the first \"tableau\"):\r\n" );
document.write( "\r\n" );
document.write( "  x    y    z  | s1   s2   s3  |  P  |  k\r\n" );
document.write( "------------------------------------------ \r\n" );
document.write( " 2.0  1.0  1.0 | 1.0  0.0  0.0 | 0.0 | 2.0\r\n" );
document.write( " 1.0  2.0  3.0 | 0.0  1.0  0.0 | 0.0 | 5.0\r\n" );
document.write( " 2.0  2.0  1.0 | 0.0  0.0  1.0 | 0.0 | 6.0\r\n" );
document.write( "------------------------------------------\r\n" );
document.write( "-3.0 -1.0 -3.0 | 0.0  0.0  0.0 | 1.0 | 0.0\r\n" );
document.write( "\r\n" );
document.write( "We want to end up with no negative numbers on the\r\n" );
document.write( "bottom row.  We take the most negative number in\r\n" );
document.write( "the bottom row (these are called \"indicators\")\r\n" );
document.write( "and call the column which it's in \"the pivot column\"\r\n" );
document.write( "\r\n" );
document.write( "CHOOSE THE PIVOT COLUMN:\r\n" );
document.write( "We could choose either one of the -3's as the most\r\n" );
document.write( "negative indicator.  We will choose the -3 in the\r\n" );
document.write( "column 1 as the most negative indicator. So column 1\r\n" );
document.write( "is the pivot column.\r\n" );
document.write( "\r\n" );
document.write( "CHOOSE THE PIVOT ROW:\r\n" );
document.write( "To the side, divide each of the positive numbers in the \r\n" );
document.write( "pivot column INTO the number on the same row in the \r\n" );
document.write( "rightmost column (headed \"k\"):\r\n" );
document.write( "\r\n" );
document.write( " <u> 1</u>     <u> 5</u>      <u> 3</u>\r\n" );
document.write( "2)2    1)5     2)6\r\n" );
document.write( "\r\n" );
document.write( "We find that the least of these is 1, which was obtained\r\n" );
document.write( "when we divided the 2 in the pivot column row 1 into the \r\n" );
document.write( "2 at the far right, so we call row 1 \"the pivot row\", and we \r\n" );
document.write( "call the element 2 \"the pivot element\".  So we have a \r\n" );
document.write( "pivot column, a pivot row and a pivot element.\r\n" );
document.write( "\r\n" );
document.write( "Now we will do what is called \"pivoting\" on an element.\r\n" );
document.write( "1.  Divide the pivot row through by the pivot element.\r\n" );
document.write( "This causes the pivot element to become 1.\r\n" );
document.write( "2.  Multiply the new pivot row by whatever is necessary\r\n" );
document.write( "so that when it is added to the other rows there will be\r\n" );
document.write( "0's everywhere else in the pivot column.\r\n" );
document.write( "\r\n" );
document.write( " 1.0  0.5  0.5 | 0.5  0.0  0.0 | 0.0 | 1.0\r\n" );
document.write( " 0.0  1.5  2.5 |-0.5  1.0  0.0 | 0.0 | 4.0 \r\n" );
document.write( " 0.0  1.0  0.0 |-1.0  0.0  1.0 | 0.0 | 4.0    \r\n" );
document.write( "------------------------------------------\r\n" );
document.write( " 0.0  0.5 -1.5 | 1.5  0.0  0.0 | 1.0 | 3.0\r\n" );
document.write( "\r\n" );
document.write( "That's the second tableau.  It is not the final tableau\r\n" );
document.write( "because it has a negative indicator of -1.5 at the bottom\r\n" );
document.write( "of column 3.  So the pivot column is column 3.\r\n" );
document.write( "\r\n" );
document.write( "CHOOSE THE PIVOT ROW:\r\n" );
document.write( "To the side, divide each of the positive numbers in the \r\n" );
document.write( "pivot column INTO the number on the same row in the \r\n" );
document.write( "rightmost column (headed \"k\"):\r\n" );
document.write( "\r\n" );
document.write( "   <u>1.6</u>     <u> 2</u>      \r\n" );
document.write( "2.5)4   0.5)1    \r\n" );
document.write( "\r\n" );
document.write( "Since 1.6 is smaller than 2, the pivot row is row 2.\r\n" );
document.write( "The pivot element is the 1 on the second row.\r\n" );
document.write( "\r\n" );
document.write( "Now we pivot again.\r\n" );
document.write( "1.  Divide the pivot row through by the pivot element.\r\n" );
document.write( "(That's not necessary because the pivot element is already 1)\r\n" );
document.write( "2.  Multiply the pivot row by whatever is necessary\r\n" );
document.write( "so that when it is added to the other rows there will be\r\n" );
document.write( "0's everywhere else in the pivot column.\r\n" );
document.write( "\r\n" );
document.write( "The final tableau is\r\n" );
document.write( "\r\n" );
document.write( " 1.0  0.2  0.0 |  0.6 -0.2  0.0 | 0.0 | 0.2\r\n" );
document.write( " 0.0  0.6  1.0 | -0.2  0.4  0.0 | 0.0 | 1.6\r\n" );
document.write( " 0.0  1.0  0.0 | -1.0  0.0  1.0 | 0.0 | 4.0\r\n" );
document.write( "-------------------------------------------\r\n" );
document.write( " 0.0  1.4  0.0 |  1.2  0.6  0.0 | 1.0 | 5.4 \r\n" );
document.write( "\r\n" );
document.write( "It is the final tableau because there are no negative\r\n" );
document.write( "numbers on the bottom row.  Now we convert back to \r\n" );
document.write( "equations:\r\n" );
document.write( "\r\n" );
document.write( " \r\n" );
document.write( " 1.0x + 0.2y + 0.0z + 0.6s1 - 0.2s2 + 0.0s3 + 0.0P = 0.2\r\n" );
document.write( " 0.0x + 0.6y + 1.0z - 0.2s1 + 0.4s2 + 0.0s3 + 0.0P = 1.6\r\n" );
document.write( " 0.0x + 1.0y + 0.0z - 1.0s1 + 0.0s2 + 1.0s3 + 0.0P = 4.0\r\n" );
document.write( "--------------------------------------------------------\r\n" );
document.write( " 0.0x + 1.4y + 0.0z + 1.2s1 + 0.6s2 + 0.0s3 + 1.0P = 5.4\r\n" );
document.write( "\r\n" );
document.write( "Simplifying:\r\n" );
document.write( "\r\n" );
document.write( "x + 0.2y + 0.6s1 - 0.2s2 + 0.0s3 = 0.2\r\n" );
document.write( "0.6y + z - 0.2s1 + 0.4s2 + 0.0s3 + 0.0P = 1.6\r\n" );
document.write( "y - s1 + s3 = 4.0\r\n" );
document.write( "---------------------------------------------\r\n" );
document.write( "1.4y + 1.2s1 + 0.6s2 + P = 5.4\r\n" );
document.write( "\r\n" );
document.write( "Solve the bottom equation for P\r\n" );
document.write( "\r\n" );
document.write( "P = 5.4 - 1.4y - 1.2s1 - 0.6s2\r\n" );
document.write( "\r\n" );
document.write( "So obviously P takes on its maximum value when nothing is\r\n" );
document.write( "subtracted from the 5.4.  This will be when y, s1, and s2 are\r\n" );
document.write( "all 0.   Substituting 0 for these three variable in the\r\n" );
document.write( "above, and simplifying:\r\n" );
document.write( "\r\n" );
document.write( "x = 0.2\r\n" );
document.write( "z = 1.6\r\n" );
document.write( "s3 = 4.0\r\n" );
document.write( "---------------------------------------------\r\n" );
document.write( "P = 5.4\r\n" );
document.write( "\r\n" );
document.write( "So P has the maximum value of 5.4 when x=0.2, y=0, z=1.6\r\n" );
document.write( "\r\n" );
document.write( "Edwin</PRE> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );