\documentclass[t]{paulslides}
\usepackage{pgf,tikz}
\usepackage{enumerate}
\usetikzlibrary{arrows}
\usepackage{amsthm}

\definecolor{UniBlue}{RGB}{83,121,170}
\setbeamercolor{block title}{use=structure,fg=white,bg=blue!75!black}
\setbeamercolor{block body}{use=structure,fg=black,bg=blue!10!white}

\title{MA162: Finite mathematics}
\subtitle{Linear Programming: More on Method of Corners}
\author{Paul Koester}
\institute{University of Kentucky}
\date{April 21, 2014}

\begin{document}

\maketitle

\begin{frame}[t]{Overview}
\begin{itemize}
  \item Last class, we introduced the method of corners.
  \item Today, we look at the four main steps
    \begin{enumerate}
      \item Step 1: Graph the lines
      \item Step 2: Deal with inequalities
      \item Step 3: Find the corners
      \item Step 4: Evaluate objective on the corners      
    \end{enumerate}
  \item We will look at a rather lengthy example.  
            We will illustrate the basic flavor of each of the above steps, but we will skip over a lot of the computations.
            The computations are included in this set of notes.   To get the most out of this example,
    \begin{itemize}
      \item After class, try to complete all of the steps on your own.
      \item Refer to these slides for the details
    \end{itemize}            
  \item We will also talk about the advantages and disadvantages of the method of corners.
\end{itemize}
\end{frame}



\begin{frame}[t]{Example}
Maximize the linear function
\[  f(x,y)  = 2x + 3y -1\]
subject to the constraints
\[ 3x - y \geq -1 \]
\[   x  + y  \leq 7\]
\[   x + 2y \leq 10\]
\[  -x + 4y  \geq 0 \]
\[   x  -   y  \leq 3\]
\[   x \geq 0 \]
\[  0 \leq y \leq  4 \]
\end{frame}


\begin{frame}[t]{Step 1:  Graph each equality}
For an individual inequality, start with the equality:
\[   3x -  y = -1\]
Since this line is not vertical, not horizontal, nor passes through \((0,0)\), we should find its x and y intercepts.\\
\(x\)-intercept:  \(y = 0\) implies  \(3x - 0 = -1\) implies \(x = -1/3\). \\
\(y\)-intercept:  \(x = 0\) implies  \(3\cdot 0 - y = -1\) implies \(y=1\).\\


\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,-1)}] node[left] {\footnotesize $(-1/3,0)$};
  \draw[shift={(-2,1)}] node[left] {\footnotesize $(0,1)$};
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y = -1$};
\end{tikzpicture}
\end{frame}

\begin{frame}[t]{Step 1:  Graph each equality}
The fourth constraint is \( -x + 4y \geq 0\).  The corresponding equality is \(-x + 4y = 0\).
The x and y intercepts are each 0.  This is insufficient information to plot the line.
Instead, rewrite as \(y = (1/4)x\).  This is a line through the origin and with slope \(1/4\).

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y = -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y = 0$};
\end{tikzpicture}
\end{frame}

\begin{frame}[t]{Step 1:  Graph each equality}
In a similar way, we graph each of the remaining constraints.

\begin{tikzpicture}[x = 0.5cm, y = 0.5cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[<->] (-1,8) -- (9, -2);
  \draw[<->] (-1,5.5) -- (12, -1);
  \draw[<->] (2,-1) -- (12, 9);  
  \draw[<->] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y = -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y = 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y = 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y = 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y = 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y = 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y = 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x = 0$};  
\end{tikzpicture}
\end{frame}


\begin{frame}[t]{Step 2:  Deal with the  INequalites}

\begin{tikzpicture}[x = 0.5cm, y = 0.5cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[<->] (-1,8) -- (9, -2);
  \draw[<->] (-1,5.5) -- (12, -1);
  \draw[<->] (2,-1) -- (12, 9);  
  \draw[<->] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}


\begin{frame}[t]{Step 2:  Deal with the  INequalites}
There are two different methods we can use to graph the inequalities.\\
Method 1:  Algebraically solve the inequalities\\
I find this useful for some of the simpler inequalities.\\
\(x \geq 0\) implies we want the right side of the line \(x = 0\).\\
\(y \geq 0\) implies we want the region above \(y = 0\).\\
\(y \leq 4\) implies we want the region below \(y =4\).\\

\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (11.5,0) -- (0,0) -- (0, 4) -- (11.5,4);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[<->] (-1,8) -- (9, -2);
  \draw[<->] (-1,5.5) -- (12, -1);
  \draw[<->] (2,-1) -- (12, 9);  
  \draw[<->,blue, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Step 2:  Deal with the  INequalites}
This also works well for inequalities in which the coefficients of \(x\) and \(y\) are both positive.\\
\( x + y \leq 7\) implies region on bottom left of \(x + y = 7\)\\
\( x + 2y \leq 10\) implies region on bottom left of \(x + 2y = 10\)

\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (7,0) -- (0,0) -- (0, 4) -- (2,4) -- (4,3)-- cycle (7,0);

  \draw[<->,color=red, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (9, -2);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (12, -1);
  \draw[<->] (2,-1) -- (12, 9);  
  \draw[<->,red, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Step 2:  Deal with the  INequalites}
If the coefficients of x and y have opposite signs, solve for y. 
\(x - y \leq 3\) implies  \( y \geq x - 3\).  Think of this as saying \(y\) is large.  
We want region above \(x - y = 3\).

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (3,0) -- (0,0) -- (0, 4) -- (2,4) -- (4,3) -- (5,2)-- cycle (3,0);

  \draw[<->,color=red, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->] (-1,-.25) -- (12, 3);
  \draw[<->, red, line width = 1 pt] (-1,8) -- (9, -2);
  \draw[<->, red, line width = 1 pt] (-1,5.5) -- (12, -1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (12, 9);  
  \draw[<->,red, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Step 2:  Deal with the  INequalites}
Similarly, \(-x  +  4y \geq 0\) rearranges to \(y \geq x/4\).  \\
Think of this as saying \(y\) is large, so we want region above \(x - 4y = 0.\)

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,0) -- (0, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=red, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2/3,-1) -- (11/3, 12);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (12, 3);
  \draw[<->, red, line width = 1 pt] (-1,8) -- (9, -2);
  \draw[<->, red, line width = 1 pt] (-1,5.5) -- (12, -1);
  \draw[<->, red, line width = 1pt ](2,-1) -- (12, 9);  
  \draw[<->,red, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Step 2:  Deal with the  INequalites}
Finally, \(3x - y \geq -1\) rearranges to \( y \leq 3x + 1\).\\
Think of this as saying y should be small, so want region below \(y = 3x + 1\).

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=red, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (11/3, 12);
  \draw[<->, red, line width = 1 pt]  (-1,-.25) -- (12, 3);
  \draw[<->, red, line width = 1 pt] (-1,8) -- (9, -2);
  \draw[<->, red, line width = 1 pt] (-1,5.5) -- (12, -1);
  \draw[<->, red, line width = 1pt ](2,-1) -- (12, 9);  
  \draw[<->,red, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Step 2:  Deal with the  INequalites}
We have found the correct region.  The next step is to find the corners of the region.

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (11/3, 12);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (12, 3);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (9, -2);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (12, -1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (12, 9);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
\end{tikzpicture}
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners}
Since we have a nice computer generated plot and all of the corners appear to have integer coefficients,  
we can easily read off the corners.\\
However, we won't always have such nice graphs, so how can we find the corner points in general?\\

Each corner point arises by intersecting a pair of the lines.   \\

Notice, however, that not all intersection points are corners of the shaded region.\\

Use the shaded region to help determine \emph{which} pairs of lines need to be intersected.

\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, First Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, red, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, red, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=red] (4,3) circle [radius = 3pt];
\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{scriptsize}
\[
  \begin{array}{ccccc}
    x   &  +  &   y  &   =  &    7 \\
    x   &  +  &  2y  &  =  &  10 \\ 
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 & 1 &   7 \\
    1 & 2 & 10 \\
    \end{array}
  \right]
  \xrightarrow{R_2\mapsto R_2 - R_1}
  \left[
    \begin{array}{cc|c}
    1 & 1 & 7 \\
    0 & 1 & 3 \\
    \end{array}  
  \right]
  \xrightarrow{R_1 \mapsto R_1 - R_2}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 4 \\
    0 & 1 & 3 \\
    \end{array}  
  \right]
\]
\end{scriptsize}
So the red corner point is \( (x,y) = (4,3)\)
\end{frame}


\begin{frame}[t]{Step 3: Finding the Corners, Second Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, red, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, red, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=red] (5,2) circle [radius = 3pt];
\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
    x   &  +  &   y  &   =  &    7 \\
    x   &  -  &   y  &  =  &  3 \\ 
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 & 1 &  7 \\
    1 & -1 & 3 \\
    \end{array}
  \right]
  \xrightarrow{R_2\mapsto R_2 - R_1}
  \left[
    \begin{array}{cc|c}
    1 & 1 & 7 \\
    0 & -2 & -4 \\
    \end{array}  
  \right]
  \xrightarrow{R_2 \mapsto R_2/-2}
  \left[
    \begin{array}{cc|c}
    1 & 1 & 7 \\
    0 & 1 & 2 \\
    \end{array}  
  \right]
  \xrightarrow{R_1 \mapsto R_1 - R_2}
  \left[
    \begin{array}{cc|c}
    1 &  0& 5 \\
    0 & 1 & 2 \\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (5,2)\)
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, Third Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, red, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, red, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=blue] (5,2) circle [radius = 3pt];
  \draw[fill, color=red] (4,1) circle [radius = 3pt];

\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
    x   &  -  &   y  &  =  &  3 \\ 
    -x   &  +  &  4 y  &   =  &   0 \\
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 & -1 &  3 \\
    -1 & 4 & 0 \\
    \end{array}
  \right]
  \xrightarrow{R_2\mapsto R_2 + R_1}
  \left[
    \begin{array}{cc|c}
    1 & -1 & 3 \\
    0 & 3 & 3\\
    \end{array}  
  \right]
  \xrightarrow{R_2 \mapsto R_2/3}
  \left[
    \begin{array}{cc|c}
    1 & -1 & 3 \\
    0 & 1 & 1 \\
    \end{array}  
  \right]
  \xrightarrow{R_1 \mapsto R_1 + R_2}
  \left[
    \begin{array}{cc|c}
    1 &  0& 4 \\
    0 & 1 & 1 \\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (4,1)\)
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, Fourth Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, red, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=blue] (5,2) circle [radius = 3pt];
  \draw[fill, color=blue] (4,1) circle [radius = 3pt];
  \draw[fill, color=red] (0,0) circle [radius = 3pt];

\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
    x   &   &   &  =  &  0\\ 
    -x   &  +  &  4 y  &   =  &   0 \\
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 &  0 &  0 \\
    -1 & 4 & 0 \\
    \end{array}
  \right]
  \xrightarrow{R_2\mapsto R_2 + R_1}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 0 \\
    0 & 4 & 0\\
    \end{array}  
  \right]
  \xrightarrow{R_2 \mapsto R_2/4}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (0,0)\)
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, Fifth Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=red, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, red, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, blue, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=blue] (5,2) circle [radius = 3pt];
  \draw[fill, color=blue] (4,1) circle [radius = 3pt];
  \draw[fill, color=blue] (0,0) circle [radius = 3pt];
  \draw[fill, color=red] (0,1) circle [radius = 3pt];
  
\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
    x   &   &   &  =  &  0\\ 
   3x   &  -  &   y  &   =  &   -1 \\
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 &  0 &  0 \\
    3 & -1 & -1 \\
    \end{array}
  \right]
  \xrightarrow{R_2\mapsto R_2 - 3R_1}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 0 \\
    0 & -1 & -1\\
    \end{array}  
  \right]
  \xrightarrow{R_2 \mapsto -R_2}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 0 \\
    0 & 1 & 1 \\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (0,1)\)
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, Sixth Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, red, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, blue, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, red, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=blue] (5,2) circle [radius = 3pt];
  \draw[fill, color=blue] (4,1) circle [radius = 3pt];
  \draw[fill, color=blue] (0,0) circle [radius = 3pt];
  \draw[fill, color=blue] (0,1) circle [radius = 3pt];
  \draw[fill, color=red] (1,4) circle [radius = 3pt];  
\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
   3x   &  -  &   y  &   =  &   -1 \\
     0   &   &  y &  =  &  4\\ 
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    3 & -1 & -1 \\
    0 &  1 &  4 \\
    \end{array}
  \right]
  \xrightarrow{R_1\mapsto R_1 + R_2}
  \left[
    \begin{array}{cc|c}
    3 & 0 & 3 \\
    0 & 1 & 4\\
    \end{array}  
  \right]
  \xrightarrow{R_1 \mapsto R_1/3}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 1 \\
    0 & 1 & 4 \\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (1,4)\)
\end{frame}

\begin{frame}[t]{Step 3: Finding the Corners, Seventh Point}

\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,blue] (0,0) -- (0,1) -- (1, 4) -- (2,4) -- (4,3) -- (5,2)-- (4,1) -- cycle (0,0);

  \draw[<->,color=blue, line width = 1pt] (-1.5,0) -- (8,0);
  \draw[<->,color=blue, line width = 1pt] (0,-1.5) -- (0,8);
  \draw[<->, blue, line width = 1 pt] (-2/3,-1) -- (7/3, 8);
  \draw[<->, blue, line width = 1 pt]  (-1,-.25) -- (8, 2);
  \draw[<->, blue, line width = 1 pt] (-1,8) -- (8, -1);
  \draw[<->, red, line width = 1 pt] (-1,5.5) -- (8, 1);
  \draw[<->, blue, line width = 1pt ](2,-1) -- (8, 5);  
  \draw[<->, red, line width = 1 pt] (-1,4) -- (8, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (7,7);
  \draw[shift={(2.5,8)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(8,2)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(8,-1)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(8,1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(8,5)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(8,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(8,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,8)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[fill, color=blue] (4,3) circle [radius = 3pt];
  \draw[fill, color=blue] (5,2) circle [radius = 3pt];
  \draw[fill, color=blue] (4,1) circle [radius = 3pt];
  \draw[fill, color=blue] (0,0) circle [radius = 3pt];
  \draw[fill, color=blue] (0,1) circle [radius = 3pt];
  \draw[fill, color=blue] (1,4) circle [radius = 3pt];  
  \draw[fill, color=red] (2,4) circle [radius = 3pt];  
\end{tikzpicture}

The red corner is obtained by intersection the red lines, 

\begin{tiny}
\[
  \begin{array}{ccccc}
    x   &  +  &  2 y  &   =  &   10 \\
     0   &   &  y &  =  &  4\\ 
  \end{array}
\]
\[
  \left[
    \begin{array}{cc|c}
    1 &  2 & 10 \\
    0 &  1 &  4 \\
    \end{array}
  \right]
  \xrightarrow{R_1\mapsto R_1 - 2R_2}
  \left[
    \begin{array}{cc|c}
    1 & 0 & 2 \\
    0 & 1 & 4\\
    \end{array}  
  \right]
\]

\end{tiny}
So the red corner point is \( (x,y) = (2,4)\)
\end{frame}

\begin{frame}[t]{Step 4: Finishing the Method of Corners}
Now that we have all of the corners, we need only plug all the corners into the profit function and pick the one that gives the largest profit.
Recall our goal was to maximize \(f(x,y) = 2x + 3y -1\).

\[
\begin{array}{|c|c|c|}  \hline
  \mathbf{x} & \mathbf{y} & \mathbf{f(x,y)}  \\ \hline
         4	   &         3        &    2\cdot 4 + 3 \cdot 3 - 1 = 16  \\ \hline
         5	   &         2        &   2\cdot 5 + 3 \cdot 2 - 1 = 15  \\ \hline  
         4	   &         1        &   2\cdot 4 + 3 \cdot 1 - 1 = 10   \\ \hline
         0	   &         0        &   2\cdot 0 + 3 \cdot 0 - 1 =  -1  \\ \hline
         0	   &         1        &   2\cdot 0 + 3 \cdot 1 - 1 =   2  \\ \hline  
         1	   &         4        &   2\cdot 1 + 3 \cdot 4 - 1 = 13  \\ \hline
         2	   &         4        &   2\cdot 2 + 3 \cdot 4 - 1 = 15  \\ \hline
\end{array}
\]
The objective function is maximized at the point \((x,y) = (4,3)\) and the maximum value is 16.

\end{frame}

\begin{frame}[t]{Method of Corners: Pros and Cons}
\begin{Large}
  Disadvantages:
\end{Large}
\begin{itemize}
  \item The geometric intuition is applicable mainly for the case with 2 variables.  3 variables requires using 3-dimensional polyhedra.
             More than 3 variables requires working with higher dimensional polytopes, which cannot be directly visualized.
  \item Method of corners requires checking every single corner point.  If there are lots of equations and/or lots of variables, just finding all 
            of the corner points can take too long.  Finding all of the corners in a problem with 100 
             variables and 200 constraints  (and realistic business problems can be this large) is beyond the power of modern supercomputers.
\end{itemize}
\end{frame}

\begin{frame}[t]{Method of Corners: Pros and Cons}
\begin{Large}
  Advantages:
\end{Large}
\begin{itemize}
  \item Despite being computationally tedious, the underlying idea of the computations are rather intuitive.  This is in contrast to the Simplex
            Algorithm, which runs much faster than the Method of Corners but the underlying process is not a intuitive.  
\end{itemize}
\end{frame}



\begin{frame}[t]{Appendix:  Alternate approach to Step 2}
Instead of algebraically solving each inequality as we did, you can instead choose a sample point from each region,
then test the sample points until you determine a region that satisfies all of the constraints.   \\
To illustrate, we only look at three regions, but in practice you may need to pick a sample point from every single region.\\

\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
%  \draw[fill,opacity=0.3,blue] (11.5,0) -- (0,0) -- (0, 4) -- (11.5,4);

  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->,color=black, line width = 1pt] (-2/3,-1) -- (11/3, 12);
  \draw[<->,color=black, line width = 1pt] (-1,-.25) -- (12, 3);
  \draw[<->,color=black, line width = 1pt] (-1,8) -- (9, -2);
  \draw[<->,color=black, line width = 1pt] (-1,5.5) -- (12, -1);
  \draw[<->,color=black, line width = 1pt] (2,-1) -- (12, 9);  
  \draw[<->,color=black, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[shift={(5,8)}] node[right] {\footnotesize $(5,8)$};    
  \draw[fill, color=black] (5,8) circle[radius = 2pt];      
  \draw[shift={(10,1)}] node[right] {\footnotesize $(10,1)$};    
  \draw[fill, color=black] (10,1) circle[radius = 2pt];      
  \draw[shift={(1,2)}] node[right] {\footnotesize $(1,2)$};    
  \draw[fill, color=black] (1,2) circle[radius = 2pt];        
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Appendix:  Alternate approach to Step 2}
For example, plug \((5,8)\) into each constraint:
\[ 3x - y \geq -1  \:\:???  \qquad  3\cdot 5 - 8 = 7 \geq -1 \qquad  \mbox{TRUE} \]
\[   x  + y  \leq 7  \:\: ??? \qquad   5 + 8 = 13 \leq 7 ??? \qquad \mbox{ FALSE!!!}\]

This tells us the pink region is NOT the desired solution.
\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,pink] (10/3,11) -- (1.5,5.5) -- (3, 4) -- (7,4) -- (11,8)--(11,11)--(10/3,11);

  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->,color=black, line width = 1pt] (-2/3,-1) -- (11/3, 12);
  \draw[<->,color=black, line width = 1pt] (-1,-.25) -- (12, 3);
  \draw[<->,color=black, line width = 1pt] (-1,8) -- (9, -2);
  \draw[<->,color=black, line width = 1pt] (-1,5.5) -- (12, -1);
  \draw[<->,color=black, line width = 1pt] (2,-1) -- (12, 9);  
  \draw[<->,color=black, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[shift={(5,8)}] node[right] {\footnotesize $(5,8)$};    
  \draw[fill, color=black] (5,8) circle[radius = 2pt];      
  \draw[shift={(10,1)}] node[right] {\footnotesize $(10,1)$};    
  \draw[fill, color=black] (10,1) circle[radius = 2pt];      
  \draw[shift={(1,2)}] node[right] {\footnotesize $(1,2)$};    
  \draw[fill, color=black] (1,2) circle[radius = 2pt];        
\end{tikzpicture}

\end{frame}



\begin{frame}[t]{Appendix:  Alternate approach to Step 2}
In fact, 
\[   x  + y  \leq 7  \:\: ??? \qquad   5 + 8 = 13 \leq 7 ??? \qquad \mbox{ FALSE!!!}\]
This tells us that (5,8) is on the wrong side of \(x + y = 7\), so the entire yellow region is out.


\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9,10}  {
%    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x$};
%  }
  \draw[fill,opacity=0.3,yellow] (-1,11) -- (-1,8) -- (8, -1) -- (11,-1) -- (11,11)--(-1,11);

  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->,color=black, line width = 1pt] (-2/3,-1) -- (11/3, 12);
  \draw[<->,color=black, line width = 1pt] (-1,-.25) -- (12, 3);
  \draw[<->,color=blue, line width = 1pt] (-1,8) -- (9, -2);
  \draw[<->,color=black, line width = 1pt] (-1,5.5) -- (12, -1);
  \draw[<->,color=black, line width = 1pt] (2,-1) -- (12, 9);  
  \draw[<->,color=black, line width = 1 pt] (-1,4) -- (12, 4);  
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(4,12)}] node[right] {\footnotesize $3x - y \geq -1$};
  \draw[shift={(12,3)}] node[right] {\footnotesize $-x + 4y \geq 0$};
  \draw[shift={(9,-2)}] node[right] {\footnotesize $x + y \leq 7$};
  \draw[shift={(12,-1)}] node[right] {\footnotesize $x + 2y \leq 10$};
  \draw[shift={(12,9)}] node[right] {\footnotesize $x - y \leq 3$};
  \draw[shift={(12,4)}] node[right] {\footnotesize $y \leq 4$};  
  \draw[shift={(12,0)}] node[right] {\footnotesize $y \geq 0$};  
  \draw[shift={(0,12)}] node[right] {\footnotesize $x \geq 0$};  
  \draw[shift={(5,8)}] node[right] {\footnotesize $(5,8)$};    
  \draw[fill, color=black] (5,8) circle[radius = 2pt];      
  \draw[shift={(10,1)}] node[right] {\footnotesize $(10,1)$};    
  \draw[fill, color=black] (10,1) circle[radius = 2pt];      
  \draw[shift={(1,2)}] node[right] {\footnotesize $(1,2)$};    
  \draw[fill, color=black] (1,2) circle[radius = 2pt];        
\end{tikzpicture}

\end{frame}

\begin{frame}[t]{Appendix:  Alternate approach to Step 2}
In this manner, you keep plugging in sample points and ruling out regions until you find a point that satisfies all of the constraints.\\
This method is fast if you are lucky to find such a point early on.\\
However, when many regions are involved, this method can take a very long time\\




\end{frame}



\end{document}
