Chapter 3, Problem 35RE

It is not necessary to check all corner points in a linear programming problem. This exercise illustrates an alternative procedure, which is essentially an expansion of the ideas illustrated in Example 1 of Section 3.2.

$\begin{array}{ll}\text{Maximize}\hfill & z=3x+4y\hfill \\ \text{subject to:}\hfill & 2x+y\le 4\hfill \\ \hfill & -x+2y\le 4\hfill \\ \hfill & x\ge 0\hfill \\ \hfill & y\ge 0.\hfill \end{array}$

1. (a) Sketch the feasible region, and add the line z = 8. (Note: 8 is chosen because the numbers work out simply, but the chosen value of z is arbitrary.)
2. (b) Draw a line parallel to the line z = 8 that is as far from the origin as possible but still touches the feasible region.
3. (c) The line you drew in part (b) should go through the point (4/5, 12/5). Explain how you know the maximum must be located at this point.