\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: Introduction}
\author{Paul Koester}
\institute{University of Kentucky}
\date{April 16, 2014}

\begin{document}

\maketitle

\begin{frame}[t]{Intro to Linear Programming}
\begin{itemize}
  \item [] A \emph{linear programming problem} consists of \vfill
  \item a linear \emph{objective function}  \vfill
  \item a collection of \emph{constraints,} each in the form of a linear equality or linear equality. \vfill
  \item [] The goal of a linear programming problem is to maximize or minimize the objective function, while satisfying all of the constraints. \vfill
\end{itemize}
\end{frame}

\begin{frame}[t]{A very simple linear programming problem}
\begin{itemize}
  \item A farmer has \(100\) acres of land.  \vfill
  \item The farmer can use the land to grow corn or wheat. \vfill
  \item For each acre of corn, the farmer earns \(\$651\). \vfill
  \item For each acre of wheat, the farmer earns \(\$523\).  \vfill
  \item In order to maximize his revenue, how many acres should be used for corn, and how many acres for wheat? \vfill
\end{itemize}
\end{frame}

\begin{frame}[t]{The solution}
\begin{itemize}
  \item [] We can find the answer to \emph{this} problem without using any fancy techniques.  \vfill
  \item The farmer earns more from corn than from wheat, so farmer should devote all available land to corn. \vfill
  \item Thus, 100 acres, all devoted to corn, \(\$651\) per acre, so maximum revenue is \(\$65,100\)  \vfill
  \item Not all LPs are this straightforward, so lets look at a more robust method.  \vfill
\end{itemize}
\end{frame}

\begin{frame}[t]{Setting up the simple linear programming problem}
\begin{itemize}
  \item Let \(C\) denote number of acres of corn, \(W\) the number of acres of wheat. \vfill
  \item The \textbf{objective function} is \( R = 651\cdot C + 523\cdot W. \)  \vfill
  \item There are three \textbf{constraints}:  \vfill
  \begin{itemize} 
    \item \(C \geq 0\) \vfill
    \item \(W \geq 0\)  \vfill
    \item \(C + W \leq 100\)  \vfill
  \end{itemize} 
\end{itemize}
\end{frame}

\begin{frame}[t]{Solving the linear programming problem}
\begin{itemize}
\item []
\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 $\x0$};
    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (10,0) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $C$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $W$};
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2,12) -- (12, -2);
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
\end{tikzpicture}
\end{itemize}
\end{frame}

\begin{frame}[t]{Method of Corners}
We are trying to optimize (maximize or minimize) a linear objective function.  
The linear objective function is constrained to a bounded convex polygonal region.   
\textbf{The Method of Corners} guarantees that the objective function attains its maximum value at one of the corners
and its minimum value at one of the corners.
\vfill

\begin{itemize}
  \item This method does not apply if the region is unbounded
  \item This method does not apply if the region is not convex
  \item This method does not apply if the region is not polygonal
  \item This method does not apply if the objective function is non-linear--in this case calculus must be used to identify local extrema 
            in the interior of the region.
\end{itemize}

\end{frame}

\begin{frame}{A less simple linear programming problem}
\begin{itemize}
  \item A farmer has \(100\) acres of land to grow corn or wheat.  \vfill
  \item Farmer earns \(\$651\) for each acre of corn and \(\$523\) for each acre of wheat. \vfill
  \item Harvesting the corn requires \(20\) hours of labor per acre.   \vfill
  \item Harvesting the wheat requires \(12\) hours of labor per acre. \vfill
  \item The farmer has enough workers for \(1500\) hours of labor. \vfill
  \item In order to maximize his revenue, how many acres should be used for corn, and how many acres for wheat. \vfill
\end{itemize}
\end{frame}

\begin{frame}{Setting up the linear programming problem}
\begin{itemize}
  \item [] The ``use all 100 acres for corn'' is no longer a valid solution, as this would require \(2000\) hours of labor, 
    but the farmer only has \(1500\) hours available.  \vfill

  \item Let \(C\) denote number of acres of corn, \(W\) the number of acres of wheat.  \vfill
  \item The \textbf{objective function} is \( R = 651\cdot C + 523\cdot W. \)  \vfill
  \item There are four \textbf{constraints}:  \vfill
  \begin{itemize} 
    \item \(C \geq 0\)   \vfill
    \item \(W \geq 0\)   \vfill
    \item \(C + W \leq 100\)  \vfill
    \item \(20\cdot C + 12 \cdot W \leq 1500\)  \vfill
  \end{itemize} 
\end{itemize}
\end{frame}

\begin{frame}{Solving the linear programming problem}
\begin{itemize}
\item []
\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
  \foreach \x in {1,2,3,4,5,6,7,8,9}  {
    \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x0$};
    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (3.75, 6.25) -- (7.5,0) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $C$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $W$};
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2,12) -- (12,-2);
  \draw[<->] (0.3,12) -- (8, -0.8);
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,0)}] node[left] {\footnotesize $(0,0)$};
  \draw[shift={(-2,10)}] node[left] {\footnotesize $(0,100)$};
  \draw[shift={(7,-0.5)}] node {\footnotesize $(75,0)$};
  \draw[shift={(6,6.5)}] node {\footnotesize $(37.5,62.5)$};
\end{tikzpicture}
\end{itemize}
\end{frame}


\begin{frame}{The Method of Corners}
\begin{itemize}
  \item Graph the feasible set.   \vfill
  \item Find the coordinates of all of the corner points of the feasible set.   \vfill
  \item Evaluate the objective function at each corner.   \vfill
  \item Theorems 1 and 2 from Chapter 3 of the text guarantee that the objective function reaches a maximum at one of these corner points, 
        and a minimum at another corner point, provided the feasible set is bounded and the feasible set has corners.  \vfill
\end{itemize}
\end{frame}


\begin{frame}[t]{Applied Problem}
Mr. and Mrs. Garcia have a total of \(\$200,000\) that can be invested in stocks and bonds.  \\
The stocks have a rate of return (RoR) of \(12\%\)/year and bonds pay \(5\%\)/year.   \\
Since the stocks carry more risk than the bonds, the Garcia's stipulate that the amount invested in bonds must 
be at least \(40\%\) of the amount invested in stocks. \\
Income generated by stocks is taxed at \(15\%\) and interest generated by bonds is taxed at \(30\%.\) \\
The Garcia's stipulate that their total taxes paid on investment income should not exceed \(\$3,200\).
How should the Garcia's invest their money between stocks and bonds in order to maximize their pre-tax investment income?  
\end{frame}

\begin{frame}[t]{Applied Problem}
Let \(S\) and \(B\) denote the total amounts invested in stocks and bonds, respectively.  
First constraint is the Garcia's total capital.
\begin{equation}
  S + B \leq \$200,000
\end{equation}
Notice we do not require equality. 
Second constraint is ``risk'' constraint:  \( B \geq 40\% S \), or   
\begin{equation}
  0.40S - B \leq 0
\end{equation}
For the third constraint, note that taxes are paid only on the earnings, not the amount invested.  Taxes paid on stocks is then 
\(  15\%(12\% S) = 0.018 S\).  Taxes paid on bonds is \(30\%(5\%B) = 0.015B\).  The tax constraint is therefore
\begin{equation}
  0.018 S + 0.015 B \leq \$3,200
\end{equation}
The last two constraints impose that the amounts invested must be non-negative:
\begin{equation}
  S \geq 0 \qquad B \geq 0
\end{equation}

\end{frame}

\begin{frame}[t]{Applied Problem}
The goal is then to maximize 
\[  P(S, B) = 0.12 S + 0.05B \]
subject to the constraints
\begin{align*}
  S + B & \leq 200000 \\
  0.4S - B& \leq  0 \\
  0.018S + 0.015B& \leq  3200 \\
   S &\geq  0 \\
   B &\geq  0 \\ 
\end{align*}

\end{frame}

\begin{frame}{Solving the linear programming problem}
\begin{itemize}
\item []
\begin{tikzpicture}[x = 0.4cm, y = 0.4cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9}  {
%   \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x0$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
%  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (3.33, 6.67) -- (6.67,2.67) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $S$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $B$};
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->] (-2,12) -- (12,-2);
  \draw[<->] (-1,11.87) -- (9.73, -1);
  \draw[<->] (-1,-.4) -- (11, 4.4);
  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,0)}] node[left] {\footnotesize $(0,0)$};
  \draw[shift={(-2,10)}] node[left] {\footnotesize $(0,200)$};
  \draw[shift={(3.5,7)}] node[right] {\footnotesize $(66.6667,133.33333)$};
  \draw[shift={(8,2)}] node[below] {\footnotesize $(133.3333,53.33333)$};

\end{tikzpicture}
\end{itemize}
\end{frame}

\begin{frame}[t]{Finishing the problem}
Next class, we'll talk about how to find the corner points.  For now, we'll see how to finish the problem, given the corner points.

The maximum return is actualized at one of the four corner points, 
so we need only evaluate \(P(S, B) = 0.12S + 0.05B\) at each of the corner points.

\begin{small}
\[
\begin{array}{|c|c|c|}  \hline
S	&	B	&	P	\\ \hline
0	&	0	&	0.12\cdot 0 + 0.05\cdot 0 = 0 \\ \hline
0	& 200000	& 0.12\cdot 0 + 0.05\cdot 200000 = 10000 \\ \hline
66666.67	& 133333.33	& 0.12\cdot 66666.67 + 0.05\cdot 133333.33 = 14666.66 \\ \hline
133333.33 & 53333.33 &  0.12\cdot 133333.33 + 0.05\cdot 53333.33 = 18666.66 \\ \hline
\end{array}
\]
\end{small}

The Garcia's maximum investment return (satisfying all of their constraints) is \$18,666.66.
This is realized by investing \(\$133333.33\) in stocks and \(\$53,333.33\) in bonds.  
\end{frame}



\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
\begin{itemize}
  \item Maximize \textbf{objective function} is \( R = 651\cdot C + 523\cdot W. \)  \vfill
  \item Subject to four constraints
  \begin{itemize} 
    \item \(C \geq 0\)   \vfill
    \item \(W \geq 0\)   \vfill
    \item \(C + W \leq 100\)  \vfill
    \item \(20\cdot C + 12 \cdot W \leq 1500\)  \vfill
  \end{itemize} 
  \item Why must maximum be at a corner?  \vfill

  \item Lets pick a point in the interior of the region, say \(C = 50\) and \(W = 10\).  
  \item The corresponding revenue is \(R(50,10) = \$37,780\)
\end{itemize}
\end{frame}

\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
Graph the line \(651C + 523W = 37780\)
\begin{itemize}
\item []
\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9}  {
%   \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x0$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
%  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (3.75, 6.25) -- (7.5,0) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $C$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $W$};
  \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,12) -- (12,-2);
  \draw[<->,color=black, line width = 1pt] (0.3,12) -- (8, -0.8);
  \draw[<->,color=red, line width = 1pt] (-1,8.5) -- (6.6, -1);

  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,0)}] node[left] {\footnotesize $(0,0)$};
  \draw[shift={(-2,10)}] node[left] {\footnotesize $(0,100)$};
  \draw[shift={(7,-0.5)}] node {\footnotesize $(75,0)$};
  \draw[shift={(6,6.5)}] node {\footnotesize $(37.5,62.5)$};
  \draw[fill, color=blue] (5,1) circle [radius=2pt];
  \draw[shift={(5,1)}] node[left] {\footnotesize $(50,10)$};
  \draw[fill, color=yellow] (2,4.7) circle [radius=2pt];
  \draw[shift={(2,4.7)}] node[left] {\footnotesize $(20,47)$};
\end{tikzpicture}
\end{itemize}
All points on the red line yield the same revenue.  
The red-line is called an ``iso-profit curve''  (although in this particular application, ``iso-revenue'' would be more appropriate.\\
For example, \(C = 20\) and \(W = 47.34\) acres is on this iso-profit curve.  
\end{frame}


\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
Moving along the red line does not change the value of R.  \\
The perpendicular direction to the red line is the direction of fastest increase / fastest decrease, so it is usually best to move in this direction.\\
(Moving in the direction of greatest increase is called the \textbf{Gradient Ascent Method}.  
Generally, calculus is needed to determine direction of greatest increase.)

For our purposes, we'll move in a direction that is a bit easier to compute.  
Specifically, since \(R = 651C + 523W\) has a positive slope coefficient in front of the W, we can increase R by holding C fixed and increasing W.\\
(Could do this for C as well, since coefficient of C is also positive.)\\

Keep increasing W:  
\[(C,W) = (50,10)  \rightarrow (50,20) \rightarrow (50, 30) \rightarrow (50,40)\]
until we run into the boundary.  
\end{frame}


\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9}  {
%   \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x0$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
%  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (3.75, 6.25) -- (7.5,0) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $C$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $W$};
  \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,12) -- (12,-2);
  \draw[<->,color=blue, line width = 1pt] (0.3,12) -- (8, -0.8);
%  \draw[<->,color=red, line width = 1pt] (-1,8.5) -- (6.6, -1);

  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,0)}] node[left] {\footnotesize $(0,0)$};
  \draw[shift={(-2,10)}] node[left] {\footnotesize $(0,100)$};
  \draw[shift={(7,-0.5)}] node {\footnotesize $(75,0)$};
  \draw[shift={(6,6.5)}] node {\footnotesize $(37.5,62.5)$};
  \draw[fill, color=blue] (5,1) circle [radius=2pt];
  \draw[shift={(5,1)}] node[left] {\footnotesize $(50,10)$};
  \draw[fill, color=blue] (5,2) circle [radius=2pt];
  \draw[shift={(5,2)}] node[left] {\footnotesize $(50,20)$};
  \draw[fill, color=blue] (5,3) circle [radius=2pt];
  \draw[shift={(5,3)}] node[left] {\footnotesize $(50,30)$};  
  \draw[fill, color=red] (5,4) circle [radius=2pt];
  \draw[shift={(5,4)}] node[left] {\footnotesize $(50,40)$};  
  \end{tikzpicture}

When we get to the red point, we can no longer increase \(W\), unless we give up some of \(C\).  But there's a trade-off.
Do we want to increase W and decrease C, or do we want to decrease W and increase C?\\

\end{frame}


\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
The red point lies on the line \( 20C + 12W = 1500\), which can be rewritten as \( C = 75 - 0.6W \).  \\

Plug this into R:
\[  R = 651C + 523W = 651(75 - 0.6W) + 523W = 48825 + 132.4W \]

The slope of R with respect to W is positive, so it is still in the farmer's best interest to increase W (even though the farmer has to decrease C
to do this.)\\

Therefore, we can increase R by moving to the left and up along the blue line.\\

However, we can't keep increasing W forever.  Eventually, we'll hit the next constraint (green line) and in particular, points too high on the 
blue line (like the yellow point) are out of reach.

\end{frame}

\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}
\begin{tikzpicture}[x = 0.3cm, y = 0.3cm]
%  \foreach \x in {1,2,3,4,5,6,7,8,9}  {
%   \draw[shift={(\x,-1)},color=black] node[below] {\footnotesize $\x0$};
%    \draw[shift={(-1,\x)},color=black] node[left] {\footnotesize $\x0$};
%  }
  \draw[fill,opacity=0.5,gray] (0,0) -- (0,10) -- (3.75, 6.25) -- (7.5,0) -- cycle (0,0);
  \draw[shift={(12,0)},color=black] node[right] {\footnotesize $C$};
  \draw[shift={(0,13)},color=black] node {\footnotesize $W$};
  \draw[<->,color=black, line width = 1pt] (-1.5,0) -- (12,0);
  \draw[<->,color=black, line width = 1pt] (0,-1.5) -- (0,12);
  \draw[<->,color=green, line width = 1pt] (-2,12) -- (12,-2);
  \draw[<->,color=blue, line width = 1pt] (0.3,12) -- (8, -0.8);
%  \draw[<->,color=red, line width = 1pt] (-1,8.5) -- (6.6, -1);

  \draw[opacity=0.5,help lines] (-1,-1) grid[step=1] (11,11);
  \draw[shift={(-2,0)}] node[left] {\footnotesize $(0,0)$};
  \draw[shift={(-2,10)}] node[left] {\footnotesize $(0,100)$};
  \draw[shift={(7,-0.5)}] node {\footnotesize $(75,0)$};
  \draw[shift={(3.75,6.25)}] node[right] {\footnotesize $(37.5,62.5)$};
  \draw[fill, color=red] (3.75,6.25) circle [radius=2pt];
  \draw[fill, color=blue] (5,4) circle [radius=2pt];
  \draw[shift={(5,4)}] node[left] {\footnotesize $(50,40)$};  
  \draw[fill, color=yellow] (2,9) circle [radius=2pt];
  \draw[shift={(2,9)}] node[right] {\footnotesize $(20,90)$};  

  \end{tikzpicture}

In this way, we have converged to the corner point \( (C,W) = (37.5, 62.5)\).\\

This does not imply that \((37.5, 62.5)\) is the optimal solution.   
The above argument only showed that if we start with a non-corner point like (50,10), we can increase \(R\) by moving towards a corner.\\
\end{frame}

\begin{frame}[t]{Appendix:  Intuition behind the Method of Corners}

If we repeated the above argument, but starting at a different interior point, we may have ended up at a different corner.  

Thus the above argument only tells us that the maximum occurs at some corner.  
To determine which corner, we can just plug each corner into \(R\) and pick the one which gives the highest value of \(R\).



\end{frame}

\end{document}
