\documentclass{amsart}[11pt]
\usepackage{graphicx}

\addtolength{\textwidth}{1.4in}                          
\oddsidemargin=0in                          
\evensidemargin=0in       

\newtheorem{example}{Example} 
\newtheorem{question}[example]{Question}
\newtheorem{definition}[example]{Definition}
\newtheorem{theorem}[example]{Theorem}
\newtheorem{notation}[example]{Notation}
\newtheorem{fact}[example]{Fact}

\begin{document}

\title{Math 242, Lecture 16}
\maketitle

\subsection{ Multiple linear inequalities}  

Many familiar shapes can be described algebraically using
multiple linear inequalities.  

\begin{definition}
The solution set of a system of linear inequalities is the set of all
points which satisfy all of the inequalities.  
\end{definition}

\begin{example}
Graph the solution set for the system of inequalities:
$$
\begin{cases}
x + y \geq 1\\
x + y \leq 3 \\
2x - y < 2   
\end{cases}
$$
\end{example}

Some basic terminology:

\begin{definition}
The {\em boundary lines} for a system of inequalities
are the lines defining by replacing  inequalities by equalities.  
The {\em boundary points} are points on the boundary lines
which lie next to the solution set.  
The {\em corner points} of a system are those boundary points
which lie on more than one of the boundary lines.  
\end{definition}


\begin{example}
Graph the solution set, and identify the corner points for the systems: 
$$
A: \begin{cases}
x - y \geq -1\\
x + y \leq 2 \\
y \geq -1  
\end{cases}
B:
\begin{cases}
x - y \geq 2\\
x + y \geq 5 \\
x, y \geq 0  
\end{cases}
$$
\end{example}

 

One more piece of terminology: 
\begin{definition}
A solution set is bounded if it is contained in some
(larger) rectangle.     If there is no such rectangle, 
then it is unbounded.  
\end{definition}

Informally, an unbounded region has points which 
go to infinity in some direction.   



\section{ Linear programming}  

Linear programming is the subject of optimizing 
linear functions over constraint regions.     
In a single variable, the theory is a very simple case of
problems we studied in Math 241.  

\begin{example}
Find the maximum and minimum of the function 
$f(x) = 2x + 3$ over the interval from $-1$ to $3$.  
\end{example}

Our results in this example are consistent with what we saw
in optimization of single-variable functions using calculus.  
The main theorem was that maxima and minima occurred either  
at critical points   (where the derivative of the function 
in question is zero or does not exist)   or at the endpoints
of the interval.     Since a linear function has a constant, usually
non-zero derivative, the maxima and minima must occur at
the endpoints of the interval.  

Remarkably, the same basic principal applies in many variables!! 

\begin{theorem}[Main theorem of linear programming]
A linear function obtains its maxima and minima, if they exist, 
at one or more of the corners of the constraint region,    as well
as the edges (faces, in higher dimensions) between corners with the same
maximum/minimum value.    
If the constraint
region is bounded, maxima and minima both exist.  
\end{theorem}

We will see how this main theorem works in an example,   formalize
the process of applying the theorem,   and develop intuition
as to why the theorem holds.  

\begin{example}
Maximize the function $F(x,y) = x - y$ subject to the constraints
$\begin{cases} x \geq 1 \\ y \geq 0 \\ 2x + 3y \leq 6 \end{cases}$.  
\end{example}

Before we go further, a little terminology is helpful.  

\begin{definition}
In a linear programming problem, the linear function to be maximized
is often called the objective function,   and the region over which 
the optimization occurs is often called the feasible region.  
\end{definition}

In general, we follow these steps to solve a linear programming 
problem (in two variables):  
\begin{itemize}
\item (For word problems) Identify the objective function and feasible region.
\item Sketch the feasible region.    (This is in some sense optional, 
and isn't possible in more than two or three variables, but very helpful
when we first see these problems).  
\item Find the corner points of the feasible region.  
\item Evaluate the objective function at the corner points.  
\item If the constraint region is bounded, take the biggest and smallest
values at corner points; those are the maxima and minima, and they
are achieved at those corner points as well as edges which connect
optimal corner points with the same value.  
\item If the constraint region is unbounded, one must understand values
at boundary points which ``go to infinity''.    If these values are greater
than the max of corner values or less than the min of corner values, 
then the max or min does not exist.  
\end{itemize}

\begin{example}
Maximize $F(x,y) = x + 2y$ subject to 
$$\begin{cases} x + y \leq 5 \\ 2x + y \leq 8 \\ x \geq 0; y \geq 0. 
\end{cases}$$    Maximize $3x - 2y$ subject to the same constraints.  
\end{example}



Linear programming, and our steps for finding maxima and minima,
are applicable in a number of kinds of applied
optimization problems.    

\begin{example}
Farmer Lynn raises chickens and goats.      She wants to raise no more than 16 animals,
including no more than 10 chickens.     She spends \$5 to raise a chicken and \$15 to raise a goat.
She has \$180 available to spend.      Each chicken generates \$6 in profit and each goat \$20.
How many of each animal should she raise in order to maximize profits?  
\end{example}




\end{document}

Before doing applications, we pause to reflect on why the main theorem,
and thus our techniques for optimization, are valid.  

The first thing to do is to graph the function, a technique that will be 
crucial in studying functions in two variables in general.  
The graph of a two-variable function $F(x,y)$ is the set of all
points $(x,y,z)$ in three-dimensional space such that $z = F(x,y)$.  
It is helpful to think of how this fits with the definition of graph of a 
single-variable function.      The maximum and minimum values of
a function will be the highest and lowest points on the graph.  

The computer is efficient at graphing
two-variable functions.     For the linear objective functions we look at,
the graphs are {\em planes} in three-space.     But planes increase and decrease
steadily, and never ``turn over''.     So the maximum and minimum must
occur on the edge of the constraint region.   

Another helpful justification is to look at {\em lines of constant value}.   
In our first example, we may look at the lines where $x- y = 0$ or $-1$  
or $1$ or $2$   or $3$ or $4$ or...    We see that the function takes on
its optimum values when the lines of constant value hit only the 
edge of the feasible region.  


 