document.write( "Question 1044529: use linear programming to maximize z=10x+15y subject to\r
\n" ); document.write( "\n" ); document.write( "x+4y < 360\r
\n" ); document.write( "\n" ); document.write( "2x+y<300\r
\n" ); document.write( "\n" ); document.write( "x>0, y>0\r
\n" ); document.write( "\n" ); document.write( "all signs are equal to
\n" ); document.write( "

Algebra.Com's Answer #659828 by KMST(5328)\"\" \"About 
You can put this solution on YOUR website!
The constraints are
\n" ); document.write( "\"system%28x%2B4y+%3C=+360%2C%0D%0A2x%2By%3C=300+%2C%0D%0Ax%3E=0%2C+y%3E=0%29\" . That is the quadrilateral limited by the lines \"system%28blue%28x%2B4y=360%29%2Cgreen%282x%2By=300%29%2Cred%28x=0%29%2Cred%28y=0%29%29\" : .
\n" ); document.write( "Sketching a graph is very helpful.
\n" ); document.write( "It allows you to \"see\" the feasible region you are working with.
\n" ); document.write( "In this case, it is the region below both blue an green lines,
\n" ); document.write( "above the x-axis, and
\n" ); document.write( "to the right of the y-axis.
\n" ); document.write( "The feasible region is obviously the quadrilateral \"OABC\" .
\n" ); document.write( "It is easy to see that shrewdly selected test point \"I%281%2C1%29\" ,
\n" ); document.write( "within \"OABC\" , meets the requirement of all the constraints,
\n" ); document.write( "and if you move away from that point crossing over any boundary line,
\n" ); document.write( "you cease to meet all requirements.
\n" ); document.write( "
\n" ); document.write( "The line \"red%28x=0%29\" is the y-axis.
\n" ); document.write( "The line \"red%28y=0%29\" is the x-axis.
\n" ); document.write( "Those two lines intersect at \"O%280%2C0%29\" , the origin.
\n" ); document.write( "
\n" ); document.write( "To graph \"green%282x%2By=300%29\" , I connected with a straight line its x- and y-intercept.
\n" ); document.write( "I found those intercepts by solving
\n" ); document.write( "\"system%28green%282x%2By=300%29%2Cred%28y=0%29%29\"--->\"system%282x=300%2Cx=0%29\"--->\"system%28x=150%2Cy=0%29\" to get point \"A%28150%2C0%29\" ,
\n" ); document.write( "and
\n" ); document.write( "\"system%28green%282x%2By=300%29%2Cred%28x=0%29%29\"--->\"system%28y=300%2Cx=0%29\" to get point \"P%280%2C300%29\" .
\n" ); document.write( "
\n" ); document.write( "To graph \"blue%28x%2B4y=360%29%29\" , I did the same.
\n" ); document.write( "I found its x- and y-intercepts by
\n" ); document.write( "solving
\n" ); document.write( "\"system%28blue%28x%2B4y=360%29%2Cred%28y=0%29%29\"--->
\n" ); document.write( "\"system%28x=360%2Cred%28y=0%29%29\"--->\"system%28x=0%2Cy=0%29\" to get point \"Q%28360%2C0%29\" ,
\n" ); document.write( "and
\n" ); document.write( "\"system%28blue%28x%2B4y=360%29%2Cred%28y=0%29%29\"--->
\n" ); document.write( "\"system%284y=360%2Cred%28x=0%29%29\"--->\"system%28x=0%29%2Cy=90%29\" to get point \"C%280%2C90%29\" .
\n" ); document.write( "
\n" ); document.write( "I also had to find the point where \"blue%28x%2B4y=360%29%29\" and \"green%282x%2By=300%29\" intersect.
\n" ); document.write( "I did it by solving
\n" ); document.write( "\"system%28blue%28x%2B4y=360%29%2Cgreen%282x%2By=300%29%29\" to get point \"B%28120%2C60%29\" .
\n" ); document.write( "There are many ways to salve that. Here is one:
\n" ); document.write( "\"system%28blue%28x%2B4y=360%29%2Cgreen%282x%2By=300%29%29\"-->\"system%28blue%28x=360-4y%29%2Cgreen%282x%2By=300%29%29\"-->\"system%28blue%28x=360-4y%29%2C2%28360-4y%29%2By=300%29\"-->\"system%28blue%28x=360-4y%29%2C720-8y%2By=300%29\"-->\"system%28blue%28x=360-4y%29%2C720-7y=300%29\"-->\"system%28blue%28x=360-4y%29%2C720-300=7y%29\"-->\"system%28blue%28x=360-4y%29%2C420=7y%29\"-->\"system%28blue%28x=360-4y%29%2Cy=60%29\"-->\"system%28x=360-4%2A60%2Cy=60%29\"-->\"system%28x=360-240%2Cy=60%29\"-->\"system%28x=120%2Cy=60%29\"
\n" ); document.write( "
\n" ); document.write( "Finally, we need to maximize \"z=10x%2B15y\" , a function of \"x\" and \"y\" , within that feasible region.
\n" ); document.write( "Because the boundaries and the function are linear,
\n" ); document.write( "the maximum will be
\n" ); document.write( "either at one of the vertices of the feasible region,
\n" ); document.write( "or all along one of the edges of that region.
\n" ); document.write( "
\n" ); document.write( "It could have been obvious to us from the start that the maximum would be at point \"B%28120%2C60%29\" (see note below),
\n" ); document.write( "but the recipe usually taught to solve this kind of problems involves calculating the value of the function \"z%28x%2Cy%29=10x%2B15y\" at every vertex.
\n" ); document.write( "The idea may be the educational value of
\n" ); document.write( "encouraging practice,
\n" ); document.write( "valuing hard work, and
\n" ); document.write( "helping you visualize the situation.
\n" ); document.write( "So, we worked hard to get to this point, and we continue along the expected path.
\n" ); document.write( "
\n" ); document.write( "At \"O%280%2C0%29\" :
\n" ); document.write( "\"z%280%2C0%29=10%2A0%2B15%2A0=0\" , obviously no maximum.
\n" ); document.write( "At \"A%28150%2C0%29\" :
\n" ); document.write( "\"z%28150%2C0%29=10%2A150%2B15%2A0=1500\"
\n" ); document.write( "At \"B%28120%2C60%29\" :
\n" ); document.write( "\"z%28120%2C60%29=10%2A120%2B15%2A60=1200%2B900=2100\"
\n" ); document.write( "At \"C%280%2C90%29\" :
\n" ); document.write( "\"z%280%2C90%29=10%2A0%2B15%2A90=1350\" .
\n" ); document.write( "
\n" ); document.write( "The maximum is \"highlight%28z=2100%29\" at point \"highlight%28B%28120%2C60%29%29\" .
\n" ); document.write( "
\n" ); document.write( "NOTE:
\n" ); document.write( "Versions of this type of problem are very popular.
\n" ); document.write( "You have \"system%28x%3E=0%2Cy%3E=0%29\" , telling you the feasible region is in quadrant I.
\n" ); document.write( "There are two boundary line constraints: \"system%28Lx%2BMy%3C=N%2CPx%2BQy%3C=R%29\" ,
\n" ); document.write( "with all positive coefficients,
\n" ); document.write( "telling you that the feasible region is below two lines with positive x- and y-intercepts.
\n" ); document.write( "and the function to maximize, \"z=Rx%2BSy\" , has positive coefficients.
\n" ); document.write( "To make you work harder, hey make the maximum be at the intersection of the two lines,
\n" ); document.write( "by making the slope of the lines \"Z=constant\" , \"-R%2FS\" ,
\n" ); document.write( "be in between the slopes, \"-M%2FL\" and \"-Q%2FP\" , of the two slanted boundary lines.
\n" ); document.write( "So, in this case, we could immediately see that
\n" ); document.write( "the boundary line slopes are \"-1%2F4\" and \"-2%2F1=-2\" ,
\n" ); document.write( "with the slope of any \"z=constant\" line,
\n" ); document.write( "\"-10%2F15=-2%2F3\" , in between them \"-2%3C-2%2F3%3C-1%2F4\" .
\n" ); document.write( "That tells us that the maximum is at the intersection of the two slanted boundary lines,
\n" ); document.write( "\"system%28blue%28x%2B4y=360%29%2Cgreen%282x%2By=300%29%29\" ---> point \"B%28120%2C60%29\" .
\n" ); document.write( "So the maximum is \"z%28120%2C60%29=10%2A120%2B15%2A60=1200%2B900=2100\" .
\n" ); document.write( "
\n" );