\documentstyle{article}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
\addtolength{\textwidth}{3cm}
\addtolength{\oddsidemargin}{-1.5cm}

\newcommand{\nn}{\nonumber}
\newcommand{\beas}{\begin{eqnarray*}}
\newcommand{\eeas}{\end{eqnarray*}}
\newcommand{\bd}{\begin{displaymath}}
\newcommand{\ed}{\end{displaymath}}
\newcommand{\mb}{\mbox}
\newcommand{\ba}{\begin{array}}
\newcommand{\ea}{\end{array}}

\newcommand{\D}{\displaystyle}
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}
\newcommand{\ti}{\tilde}
\newcommand{\bs}{\backslash}



\author{Gerald Teschl}
\title{The Simplex Method on the TI85}
\date{}

\begin{document}

\maketitle


A craftsman makes two kinds of jewelry boxes for craft shows. The oval box requires 30
minutes of machine work and 20 minutes of finishing. The square box requires 20 minutes of
machine work and 40 minutes of finishing. Machine work is limited to 600 minutes per day
and finishing to 800 minutes. If there is \$3 profit on the oval box and \$4 on the square
box, how many of each should be produced to maximize profit?\\[3mm]
{\bf Solution.} Let $x_1$ denote the number of square boxes and $x_2$ the number
of oval boxes. The constraints read
\beas
30 x_1 + 20 x_2 &\le& 600 \qquad \mb{(time for machine work)},\\
20 x_1 + 40 x_2 &\le& 800 \qquad \mb{(time for finishing)},
\eeas
and the objective function is
\bd
z = 3x_1 + 4 x_2 \qquad \mb{(profit)}.
\ed
Clearly we can divide our constraints by a {\em positive} number without altering them.
If we divide the first by 10 and the second by 20 we get
\beas
3 x_1 + 2 x_2 &\le& 60,\\
x_1 + 2 x_2 &\le& 40.\\
\eeas
This little trick simplifies the problem considerably.

The corresponding initial simplex tableau reads
\bd
\hspace*{1mm} \left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} x_1 & x_2 & s_1 & s_2 & z\\
3 & 2 & 1 & 0 & 0 &\vline& 60 \\ 1 & 2 & 0 & 1 & 0 &\vline& 40\\
\hline -3 & -4 & 0 & 0 & 1 &\vline& 0 \ea$}
\left. \rule[-5mm]{0pt}{10mm}\right].
\ed
Now you need to observe one important thing: The position of each column is only
important in the sense that the location gives you the corresponding variable. That is,
the first column corresponds to $x_1$, the second to $x_2$, the third to $s_1$, the fourth
to $s_2$, and the fifth to $z$. If we keep track of this information we can of course
interchange columns.

Hence we can rearrange our tableau according to
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} s_1 & s_2 & z & x_1 & x_2\\
1 & 0 & 0 & 3 & 2 &\vline& 60 \\ 0 & 1 & 0 & 1 & {\bf 2} &\vline& 40\\
\hline 0 & 0 & 1 & -3 & -4 &\vline& 0 \ea$}
\left. \rule[-5mm]{0pt}{10mm}\right].
\ed
Notice that the columns correspond to $s_1,s_2,z,x_1,x_2$, respectively. Type this matrix
into your TI85 and save it as ``$\tt A$''.

Now locate the pivot element as usual; in this case it is the 2,5 entry (the entry printed
bold). Next, exchange column 2 and 5 (since the pivot element is the 2,5 entry) on your
calculator by typing  ``{\tt rSwap(A${}^{\tt T}$,2,5)${}^{\tt T}$}'' (to get ``{\tt
rSwap(}'' on your TI85 press
$MATRX \to F4 \to MORE \to F2$ and to get ``${}^{\tt T}$'' ({\tt A${}^{\tt T}$}
is called transpose of {\tt A}) on your TI85 press $MATRX \to F3 \to F2$)
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} s_1 & x_2 & z & x_1 & s_2\\
1 & 2 & 0 & 3 & 0 &\vline& 60\\ 0 & {\bf 2} & 0 & 1 & 1 &\vline& 40\\
\hline 0 & -4 & 1 & -3 & 0 &\vline& 0 \ea$}
\left. \rule[-5mm]{0pt}{10mm}\right]
\ed
and note that the columns now correspond to $s_1,x_2,z,x_1,s_2$. Next,
compute the reduced echelon form by typing ``{\tt rref Ans}''
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} s_1 & x_2 & z & x_1 & s_2\\
1 & 0 & 0 & {\bf 2} & -1 &\vline& 20\\ \rule[-1.5mm]{0pt}{3mm} 0 & 1 & 0 & \frac{1}{2} &
\frac{1}{2} &\vline& 20\\
\hline 0 & 0 & 1 & -1 & 2 &\vline& 80\ea$}
\left. \rule[-5mm]{0pt}{10mm}\right]
\ed
Since there is still a negative entry in the last row we are not done yet. The new pivot
element is the 1,4 entry (again printed bold) and hence we are going to swap column 1 and
4 on the calculator by typing ``{\tt rSwap(Ans${}^{\tt T}$,1,4)${}^{\tt T}$}''
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} x_1 & x_2 & z & s_1 & s_2\\
{\bf 2} & 0 & 0 & 1 & -1 &\vline& 20\\ \rule[-1.5mm]{0pt}{3mm} \frac{1}{2} & 1 & 0 & 0 &
\frac{1}{2} &\vline& 20\\
\hline -1 & 0 & 1 & 0 & 2 &\vline& 80\ea$}
\left. \rule[-5mm]{0pt}{10mm}\right]
\ed
Again, note that the columns correspond to $x_1,x_2,z,s_1,s_2$. Computing the reduced
echelon form by typing ``{\tt rref Ans}'' gives
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} x_1 & x_2 & z & s_1 & s_2\\
1 & 0 & 0 & \frac{1}{2} & -\frac{1}{2} &\vline& 10\\ \rule[-1.5mm]{0pt}{3mm} 0 & 1 & 0 &
-\frac{1}{4} & \frac{3}{4} &\vline& 15\\
\hline \rule{0pt}{3.5mm} 0 & 0 & 1 & \frac{1}{2} & \frac{3}{2} &\vline& 90\ea$}
\left. \rule[-5mm]{0pt}{10mm}\right]
\ed
Since there are no negative entries in the last row we are done. Now we can rearrange the
tableau in such a way that the columns correspond to $x_1,x_2,s_1,s_2,z$ as at the
outset
\bd
\left[ \rule[-5mm]{0pt}{10mm}\right. 
\raisebox{2mm}{$\ba{ccccccc} x_1 & x_2 & s_1 & s_2 & z\\
1 & 0 & \frac{1}{2} & -\frac{1}{2} & 0 &\vline& 10\\ \rule[-1.5mm]{0pt}{3mm} 0 & 1 &
-\frac{1}{4} & \frac{3}{4} & 0 &\vline& 15\\
\hline \rule{0pt}{3.5mm} 0 & 0 & \frac{1}{2} & \frac{3}{2} & 1 &\vline& 90\ea$}
\left. \rule[-5mm]{0pt}{10mm}\right].
\ed
This is the final simplex tableau. Setting $s_1=0$, $s_2=0$ and solving for the remaining
variables we get $x_1=10$, $x_2=15$ and $z=90$.

\end{document}
