\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:  Introducing the Simplex Algorithm}
\author{Paul Koester}
\institute{University of Kentucky}
\date{April 23, 2014}

\begin{document}

\maketitle

\begin{frame}{Standard Linear Programming Problem}
A standard Linear Programming Problem is one in which \vfill
  \begin{itemize}
  \item The objective function is to be \textbf{maximized}  \vfill
  \item All of the variables in the problem are \textbf{non-negative}  \vfill
  \item All other linear constraints can be written so that the expression involving the variables is less than or equal to 
        a nonnegative constant.  \vfill
  \end{itemize}
\end{frame}

\begin{frame}{Slack Variables}
\begin{itemize}
  \item Basic idea:  \emph{equalities} are easier to deal with than \emph{inequalities} \vfill
  \item We will convert \emph{inequalities} into \emph{equalities}.   \vfill
  \item HOW?  Consider the inequality \(x + y \leq 100\), with \(x \geq 0\) and \(y \geq 0\). \vfill 
  \item Lets introduce another variable, say \(z\), with \(z\geq 0\).  
        \(z\) measures the extent to which \(x + y\) is below \(100\).  Then 
        \[
          x + y + z = 100
        \]
        and \(x \geq 0\), \(y \geq 0\), \(z \geq 0\) is equivalent to the original inequality involving \(x\) and \(y.\)\vfill
  \item \(z\) is called a \textbf{slack variable.}\vfill
\end{itemize}
\end{frame}

\begin{frame}{More on Slack Variables}
\begin{itemize}
  \item Slack variables are not just abstract mathematical creations.  They measure useful things! \vfill
  \item Farmer has 100 acres to plant corn and wheat.   \vfill
  \item \(x\) is number of acres of corn, \(y\) number of acres of wheat. \vfill  
  \item \(x + y \leq 100\) says total of corn and wheat cannot exceed the total amount of land.  \vfill
  \item \(x + y + z = 100\)?  In this case, \(z\) measures the amount of unused land.  \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
Winston Furniture Company manufactures tables and chairs.  
Each table requires 40 board feet of wood and 3 labor-hours.  
Each chair requires 16 board feet of wood and 4 labor-hours.
Profit for each table is \(\$45\) and profit for each chair is \(\$20\).
In a certain week, the company has \(3200\) board feet available and \(520\) labor-hours available.
How many tables and how many chairs should they produce to maximize their profit?
\end{frame}


\begin{frame}{Inequality version}
\begin{itemize}
  \item Let x denote number of tables, y number of chairs. \vfill
  \item Board feet:  \(40x + 16y \leq 3200\)  \vfill
  \item Labor-hours:  \(3x + 4y \leq 520\)  \vfill
  \item Reality check:  \(x \geq 0, y \geq 0\) \vfill
  \item Objective:  Maximimize \(P = 45x + 20y\)  \vfill
\end{itemize}
\end{frame}

\begin{frame}{Slack version}
\begin{itemize}
  \item Let \(u\) denote unused board feet, \(v\) unused labor. \vfill
  \item Board feet:  \(40x + 16y + u = 3200\)  \vfill
  \item Labor-hours:  \(3x + 4y +v =  520\)   \vfill
  \item Reality check:  \(x \geq 0, y \geq 0, u \geq 0, v \geq 0\) \vfill
  \item Objective:  Maximimize \(P = 45x + 20y\) \vfill
\end{itemize}
\end{frame}

\begin{frame}{Building a simplex-tableaux}
\begin{itemize}
  \item We put the two linear constraints (Board-feet and Labor-hours) and profit into an augmented matrix  \vfill
  \item \[ \left[ \begin{array}{rrrrr|r} 
           40 &  16 &  1 &  0 &  0 &  3200 \\
            3 &   4 &  0 &  1 &  0 &   520 \\
          -45 & -20 &  0 &  0 &  1 &     0 \\
         \end{array}\right] \]  \vfill
  \item The bottom row corresponds to \(P = 45x + 20y\), but rewritten as \(-45x - 20y + P = 0.\)  \vfill
  \item Currently, \(x\) and \(y\) are \alert{Non-basic} variables and \(u\), \(v\) and \(P\) are \alert{Basic} variables.  \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
\begin{itemize}
  \item The corner points correspond to setting the \alert{Non-basic} variables to \(0\). \vfill
  \item Currently, set \(x = 0\) and \(y = 0\).   \vfill
  \item Above matrix tells us \(u = 3200\), \(v = 520\) and \(P = 0\).  \vfill  
  \item This tells us that if we make NO tables and NO chairs, then we will have \(3200\) board feet of wood left over, 
        \(520\) unused labor, and we earn \(0\) profit.    \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
\begin{itemize}
  \item KEY IDEA of the Simplex Algorithm:  Perform row operations to change which variables are \alert{basic} and which variables are \alert{non-basic}. \vfill
  \item Do this in a smart way, so that profit \emph{increases}, and all of the variables remain nonnegative. \vfill
  \item How to choose row operation:  Look at profit row and identify entry with most negative value.   
        (If all values in profit row are nonnegative, then you are done.)  \vfill
  \item \[ \left[ \begin{array}{rrrrr|r} 
           40 &  16 &  1 &  0 &  0 &  3200 \\
            3 &   4 &  0 &  1 &  0 &   520 \\
          -45 & -20 &  0 &  0 &  1 &     0 \\
         \end{array}\right] \]
  \item In this case, we look at column 1.  (One additional table brings in \(\$45\) of profit compared to \(\$20\) of profit from one additional chair.) \vfill
  \end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
\begin{itemize}
  \item Now choose which row.  How to decide?   \vfill
  \item Look at the rows, excluding the bottom row.  From these, select the rows with positive entries in the pivot column.   \vfill
  \item For each of the selected rows, divide the entry on the right hand side by the corresponding entry in the pivot column.  \vfill
  \item \[ \left[ \begin{array}{rrrrr|r} 
           40 &  16 &  1 &  0 &  0 &  3200 \\
            3 &   4 &  0 &  1 &  0 &   520 \\
          -45 & -20 &  0 &  0 &  1 &     0 \\
         \end{array}\right] \] \vfill
  \item In this case, \(3200/40 = 80\) and \(520/3 = 173.33\).  We use the first row to pivot, since the ratio is smaller.  
        (Reasoning: ``If we increase number of tables, we will run out of wood before we run out of labor")  \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
So, first row, first column will be our pivot entry.   \vfill
{\scriptsize\[ \left[ \begin{array}{rrrrr|r} 
           40 &  16 &  1 &  0 &  0 &  3200 \\
            3 &   4 &  0 &  1 &  0 &   520 \\
          -45 & -20 &  0 &  0 &  1 &     0 \\
         \end{array}\right] 
         \xrightarrow{R_1 \mapsto R_1/40}
         \left[ \begin{array}{rrrrr|r} 
            1 & 0.4 & 0.025 &  0 &  0 &  80 \\
            3 &   4 &     0 &  1 &  0 & 520 \\
          -45 & -20 &     0 &  0 &  1 &   0 \\
         \end{array}\right]
         \]
         \[ 
         \xrightarrow[R_2 \mapsto R_2 - 3R_1]{R_3 \mapsto R_3 + 45 R_1}
         \left[ \begin{array}{rrrrr|r} 
            1 & 0.4 &  0.025 &  0 &  0 &   80 \\
            0 & 2.8 & -0.075 &  1 &  0 &  280 \\
            0 &  -2 &  1.125 &  0 &  1 & 3600 \\
         \end{array}\right] 
        \]}
\begin{itemize}
  \item Now \(x\), \(v\) and \(P\) are the \alert{basic} variables, and \(y\) and \(u\) are \alert{non-basic} variables.  \vfill
  \item Set \alert{non-basic} to zero and solve for \alert{non-basic}:  \(x = 80\), \(v = 280\), \(P = 3600\).    \vfill
  \item In plain english:  ``Make \(80\) tables, \(0\) chairs, earn \(\$3600\) in profit.  
        We have \(0\) unused board feet of wood and \(280\) unused labor hours."  \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
\begin{itemize}
  \item Is this best possible?   NO, there is still a negative entry in the profit row. \vfill
  \item The next pivot entry will correspond to the most negative entry in the profit row, in this case, column 2.       \vfill
  \item How to decide which row?  Select each row with positive entry in new pivot column, and divide the right hand side of 
        these rows by the entries in the pivot column.  \vfill
  \item \[ \left[ \begin{array}{rrrrr|r} 
            1 & 0.4 &  0.025 &  0 &  0 &   80 \\
            0 & 2.8 & -0.075 &  1 &  0 &  280 \\
            0 &  -2 &  1.125 &  0 &  1 & 3600 \\
         \end{array}\right] 
        \]
  \item In this case, \(80/0.4 = 200\) and \(280/2.8 = 100\).  We use the second row to pivot, since the ratio is smaller.  
        (Reasoning: ``If we increase number of chairs, we will run out labor before we run out of tables") \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
So, second row, second column will be our pivot entry.   \vfill
{\scriptsize\[\left[ \begin{array}{rrrrr|r} 
            1 & 0.4 &  0.025 &  0 &  0 &   80 \\
            0 & 2.8 & -0.075 &  1 &  0 &  280 \\
            0 &  -2 &  1.125 &  0 &  1 & 3600 \\
          \end{array}\right]
         \] \[
         \xrightarrow{R_2 \mapsto R_2/2.8}
         \left[ \begin{array}{rrrrr|r} 
            1 & 0.4 &   0.025 &       0 &  0 &   80 \\
            0 &   1 & -0.0268 &  0.3571 &  0 &  100 \\
            0 &  -2 &   1.125 &       0 &  1 & 3600 \\
         \end{array}\right] 
        \] \[
         \xrightarrow[R_1 \mapsto R_1 - 0.4R_2]{R_3 \mapsto R_3 + 2 R_2}
         \left[ \begin{array}{rrrrr|r} 
            1 &  0 &  0.0357 & -0.1429 &  0 &   40 \\
            0 &  1 & -0.0268 &  0.3571 &  0 &  100 \\
            0 &  0 &  1.0714 &  0.7143 &  1 & 3800 \\
         \end{array}\right] 
        \]}
\begin{itemize}
  \item Now \(x\), \(y\) and \(P\) are the \alert{basic} variables, and \(v\) and \(u\) are \alert{non-basic} variables.   \vfill
  \item Set \alert{non-basic} to zero and solve for \alert{basic}:  \(x = 40\), \(y = 100\), \(P = 3800\).     \vfill
  \item In plain english:  ``Make \(40\) tables, \(100\) chairs, earn \(\$3800\) in profit.  
        We have \(0\) unused board feet of wood and \(0\) unused labor hours."   \vfill
\end{itemize}
\end{frame}

\begin{frame}{Example of Simplex Algorithm}
\begin{itemize}
  \item Is this best possible?    \vfill
  \item YES.     \vfill
  \item WHY?     \vfill
  \item Bottom row can be interpreted as 
        \[
            P = 3800 - 1.0714u - 0.7143v
        \]
        \(P\) can only be increased if \(u\) or \(v\) are decreased.  But \(u\) and \(v\) are currently 0, so they cannot be decreased any further.   \vfill
  \item Therefore, 40 tables, 100 chairs, \(\$3800\) profit, no unused wood or labor gives the best solution.   \vfill
\end{itemize}
\end{frame}

\begin{frame}{Why use simplex algorithm?}
\begin{itemize}
  \item The ease of the method of corners relies on having few variables, which results in low dimensional geometry.\vfill
  \item  Simplex algorithm doesn't directly use the geometry, so simplex algorithm can be used regardless of the number of variables.\vfill
  \item  Method of Corners requires us to look at ALL corners.  Simplex Algorithm can find the optimal corner without visiting every corner.  \vfill
  \item Simplex Algorithm returns more information: it tells us which resources were not fully used.  
           This extra information can be very useful in management decisions.\vfill
\end{itemize}
\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}
