\input epsf
\nopagenumbers
\magnification=\magstep1

\noindent {\bf Problem statement} A {\it linear programming}\/ problem
is a max-min problem of a somewhat different character from those we
encounter in Math 251.  In the simplest case of such a problem we want
to maximize and/or minimize a linear function of $x$ and $y$, that is,
a function $f(x,y)=ax+by$, over a polygonal region like the region $R$
below.  (There are many real applications with problems of this sort,
and many more than two variables may be involved -- perhaps
thousands.)

\bigskip

\input pictex
 \centerline{\beginpicture
 \setcoordinatesystem units <0.4truein,0.3truein> point at 0 0
 \setplotarea x from -1 to 8, y from -1 to 6
 \axis left shiftedto x=0 ticks short out from 1 to 5 by 1 /
 \axis bottom shiftedto y=0 ticks short out from 1 to 7 by 1 /
 \setlinear
% \plot -1 0 8 0 /
 \put {$x$} [tl] at  7.5 -0.3
% \plot 0 -1 0 6 /
 \put {$y$} [br] at -0.3 5.5
 \setplotsymbol ({$.$})
 \plot 1 2 1.5 5 3 6 5 5 6 3 4 0.5 2 1 1 2 /
 \put {$R$} at 3 3
\endpicture}
  
\bigskip

\noindent Suppose now that the function whose extrema we want to find
is $f(x,y)=x+2y$.

\medskip

\noindent a) Find all critical points of $f$ (pretty easy, yes?).
What does this result tell you about where the extreme values of $f$
in $R$ occur?

\medskip

\noindent b) Draw a region $R$ that looks something like the above
(the picture is not critical) and on the same figure sketch and label
some level curves of the function $f$, including some that cross $R$.
From your picture, explain why the maximum and minimum values of $f$
in $R$ will be taken on at vertices (corners0 of the region $R$, and
how you would determine the relevant vertices graphically.

\medskip

\noindent c) Suppose now that we consider a region $R$ (not
the one in the picture!) consisting of the points $(x,y)$ which satisfy
all of these inequalities: 

$$y\ge3-x,\quad 2y\ge x,\quad y\le 3x-1,\quad y\ge2x-6,\quad 3y\le17-x.$$

\noindent Make a {\it careful}\/ sketch of $R$, finding the coordinates
of all the vertices.  By adding some level curves of $f$, determine at
which vertices of $R$ the maximum and minimum of $f$ occur, and from
this find these extreme values.  Check your analysis by evaluating $f$
at all the vertices.


\vfil\eject\end