	\be
    \item Use the simplex algorithm to verify that the LP given by
    \begin{align*}
		 \mbox{minimize } z &=2x_1+6x_2  \\
		\mbox{ subject to} \notag\\
		x_1 +3x_2 &\leq 6 \notag\\
		\phantom{x1+} x_2 &\leq 1  \notag\\
		x_1,x_2 &\geq 0, \notag
		\end{align*}
    has alternative optimal solutions.
    \item State a rule that can be used to determine from a tableau whether an LP minimization
	problem is unbounded.
    \item The tableau given in (\ref{Ta:Special_cases_variable_entry_tableau}) corresponds to that obtained in the process of using the simplex algorithm
 to solve an LP whose objective is to maximize a function of $x_1$ and $x_2$. Assume that
the variables $s_1$ and $s_2$ are nonbasic.

\begin{table}[h]
\caption{Tableau for Exercise 3}
\label{Ta:Special_cases_variable_entry_tableau}
\begin{tabular}{|c|c|c|c|c|c|} \hline
$z$ & $x_1$ & $x_2$ &$s_1$ & $s_2$ & RHS \\ \hline
1 & 0 & 0 & a & 3 & 10 \\ \hline
0 & 1 & 0 & -1 & -1 & 3 \\ \hline
0 & 0 & 1 & b & 1 & 2 \\ \hline
\end{tabular}
\end{table}
	\be
	\item Suppose the current basic solution is not optimal but that the LP is bounded. After the next iteration
	of the simplex algorithm, what are the new values of the decision variables and objective function in terms of $a$ and/or $b$?
	\item Suppose the current basic solution is optimal but that the LP has alternative optimal
	solutions. Determine another such solution in terms of $a$ and/or $b$.
	\item If the LP is unbounded, what can be said about the signs of $a$ and $b$?
	\ee

	\item Table \ref{Ta:Exercises_Special_cases_problem2} results after two iterations of the simplex
    algorithm are applied to
	a maximization problem having objective function, \newline
    $z=f(x_1,x_2)=x_1+3x_2$.
	
	\begin{table}[h]
    \caption{Tableau for LP having objective function $z=f(x_1,x_2)=x_1+3x_2$}
    \label{Ta:Exercises_Special_cases_problem2}
	\begin{tabular}{|c|c|c|c|c|c|} \hline
	$z$ & $x_1$ & $x_2$ &$s_1$ & $s_2$ & RHS \\ \hline
	1 & 0 & 0 & -5 & 4 & 19 \\ \hline
	0 & 0 & 1 & -1 & 1 & 5 \\ \hline
	0 & 1 & 0 & -2 & 1 & 4 \\ \hline
	\end{tabular}
	\end{table}
	
	Assume that the variables $x_1$ and $x_2$ are basic.
		\be
		\item Explain why this LP is unbounded.
		\item For each one unit increase in $s_1$, by how much will $x_1$ increase? By how much will $x_2$ increase?
		\item Use your previous result to express $x_2$ as a linear function of $x_1$, valid for
		$s_1 \geq 0$.
		\item Sketch the current decision variable values as a point in the $x_1x_2$-plane. Draw
		a ray from this point, which falls upon the graph of the linear function from (c).
		\item What must be the values of $x_1$ and $x_2$ along this ray so that $z=1000$? What
        is the corresponding value of $s_1$?
		\ee		
	\item An LP involving maximization of a linear function in two decision variables has its feasible region shown in Figure
    \ref{Fi:Special_cases_degenerate_exercise}.
		\begin{figure}[h]
		\centering
			  \includegraphics[width=.7\linewidth]{images/f03x04x03.eps}
\caption{Feasible region for Exercise 5.}
 \label{Fi:Special_cases_degenerate_exercise}
		\end{figure}
			\be
			\item List the basic solutions to this LP in vector form,
			$\ds \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$, where $\vecx$ and $\vecs$
        denote vectors of decision and slack variables, respectively. Explain why the LP is degenerate.
			\item What is the smallest possible number of iterations required to obtain
        a basic variable equal to zero? What is the largest possible number of iterations? What attribute of the objective function determines this outcome.
			\ee
	\ee 