\be
	\item In light of the discussion in this section, explain why it is appropriate to say that the
	goal of the simplex algorithm is to solve a feasible LP by means of determining a feasible solution
	to its dual.
    \item Consider the LP
    \begin{align*}
		 \mbox{maximize } z &=3x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		x_1 \x &\leq 4 \notag\\
		x_1+3x_2 &\leq 15  \notag\\
		-x_1+2x_2 &\geq 5 \notag \\
		x_1-x_2 &\geq 9 \notag \\
		x_1+x_2&=6 \notag \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}
    By rewriting the fifth constraint as a combination of two inequalities, express this
    LP in the matrix inequality form (\ref{E:Duality_primal}). Then construct the corresponding dual LP and demonstrate explicitly, without appealing to Table \ref{Ta:Duality_general_dual_formulation}, how it possesses a variable that is unrestricted in sign.
\item Prove that the dual of the dual of LP (\ref{E:Duality_primal}) is the original LP.
(Hint: Transpose properties may prove useful.)
\item Simplex algorithm
iterations applied to an LP result in the tableau (\ref{Ta:Exercises_Duality_Tableau2}).
		\begin{table}[h]
        \caption{Tableau for Exercise 4}
        \label{Ta:Exercises_Duality_Tableau2}
		\begin{tabular}{|c||c|c|c|c|c|c|c||c|}
		\hline
		$z$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
		\hline \hline
		1 & 0 & 0 & 0  & 8 & -7 & 13 & 9 & 20 \\ \hline
		0 &  1 & 0 & 0  & 7 & -3 & 6 & 15 & 12\\ \hline
		0 &  0 & 0 & 1  & 10 & 0 & 4 & 2 & 14\\ \hline
		0 &  0 & 1 & 0  & 4 & -2 & 13 & 7 & 18\\ \hline
		\end{tabular}
		\end{table}	
		\be
		\item How many constraints and decision variables are in the dual of this LP?
		\item If the basic variables in the tableau are
		given by $\left\{x_1,x_2,x_3\right\}$, what information does Weak Duality
provide about the objective value in the solution of the dual LP?
    \ee
	\item Consider the LP
\begin{align*}
		 \mbox{maximize } z &=2x_1-x_2  \\
		\mbox{ subject to} \notag\\
		x_1-x_2 &\leq 1 \notag\\
		x_1-x_2 &\geq 2  \notag\\
		x_1,x_2 &\geq 0.\notag
		\end{align*}
Show that both this LP and its corresponding dual are infeasible.

	\item An LP has as its objective, maximization of the expression $z=2x_1+3x_2$. Simplex algorithm
iterations applied to the LP result in Table (\ref{Ta:Exercises_Duality_Tableau1}).
		\begin{table}[h]
        \caption{Tableau for Exercise 6}
        \label{Ta:Exercises_Duality_Tableau1}
		\begin{tabular}{|c|c|c|c|c|c|c|}
		\hline
		$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
		\hline \hline
		1 & $\bs$           & $\bs$ & 1                 & 0 & 0  & $\bs$ \\ \hline
		0 &  $-\frac{2}{3}$ & 1     & $\frac{1}{3}$     &  0 & 0 & 6\\ \hline
		0 &  3              & 0     & $-\frac{1}{2}$    &  1 & 0 & 3\\ \hline
		0 &  $\frac{14}{3}$ & 0     & $-\frac{1}{3}$    &  0 & 1 & 10\\ \hline
		\end{tabular}
		\end{table}	
		\be
		\item What are the constraints of the LP? (Hint: Use the matrix, $M^{-1}$, where
        $M$ is as given in Theorem \ref{Th:Paritioned_Matrix_View_Simplex}.)
		\item Fill in the entries marked $\bs$ in the tableau.
		\item Determine the solutions of both the LP and its corresponding dual.
		\ee
%	\item Simplex algorithm
%iterations applied to the LP result in tableau (\ref{Ta:Exercises_Duality_Tableau2}).
%		\begin{table}[h]
%		\centering
 %       \caption{Tableau for Exercise 7}
  %      \label{Ta:Exercises_Duality_Tableau2}
	%	\begin{tabular}{|c||c|c|c|c|c|c|c||c|}
%		\hline
%		$z$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
%		\hline \hline
%		1 & 0 & 0 & 0  & 8 & -7 & 13 & 9 & 20 \\ \hline
%		0 &  1 & 0 & 0  & 7 & -3 & 6 & 15 & 12\\ \hline
%		0 &  0 & 0 & 1  & 10 & 0 & 4 & 2 & 14\\ \hline
%		0 &  0 & 1 & 0  & 4 & -2 & 13 & 7 & 18\\ \hline
%		\end{tabular}
%		\end{table}	
%		\be
%		\item How many constraints and decision variables are in the dual of this LP?
%		\item If the basic variables in the tableau above are
%		given by $\left\{x_1,x_2,x_3\right\}$, what can you conclude about the solution to
%		the dual LP? Explain.
%		\ee
%	\item When solving the dual of the \LP LP, we noted that the values of the excess variables
%	were the negative of the decision variable solutions to the primal LP. Use properties of
%	partitioned matrix multiplication to prove this result.
	\item Solve the LP
	\begin{align*}
		 \mbox{maximize } z &=x_1+5x_2  \\
		\mbox{ subject to} \\
		-x_1+ x_2  &\leq 4 \\
		\phantom{-x_1+} x_2 &\leq 6  \\
		2x_1+3x_2 &\leq 33  \\
		2x_1+x_2 &\leq 24  \\
		x_1,x_2 &\geq 0,
		\end{align*}
    by first formulating and then solving its corresponding dual LP.
    % Solution (1,6)
	\item
	Consider an LP in the form of (\ref{E:Duality_primal}), in which
    \begin{equation*}
    \vecc= \begin{bmatrix} 5 & 1 & 1 & 4 & 1 & 2 \end{bmatrix} \mbox{,  }
	A=\begin{bmatrix} 1 & 2 & 4 & 3 & 4 & 6 \\
	7 & -5 & 2 & 1 & 3 & 3 \\
	4 & 5 & -2 & 1 & 6 & -2 \\
	7 & 8 & -3 & 5 & 2 & 4 \\
	\end{bmatrix} \mbox{, and }
	\ds \vecb = \begin{bmatrix} 2 \\ 4 \\ 5 \\ 3 \end{bmatrix}.
    \end{equation*}
     Suppose that
    \begin{equation*}
    \vecx_0 = \begin{bmatrix} \frac{8}{17} \\ 0 \\ \frac{5}{17} \\ \frac{2}{17} \\ 0 \\ 0
    \end{bmatrix}.
    \end{equation*}
    Without performing the simplex algorithm, show that $\vecx_0$ is the optimal
    solution of the LP and determine the corresponding dual solution. (Hint: Let $\ds \vecy_0=\begin{bmatrix} y_1 & y_2 & y_3 & y_4  \end{bmatrix}$. Calculate both
    $\vecy_0 A -\vecc$ and $\vecb-A\vecx_0$ and apply Theorem
    \ref{Th:Duality_complementary_slackness} to construct a system of equations in the variables $y_1$, $y_2$, $y_3$, and $y_4$.)
    \item Determine the mixed strategy Nash equilibrium for a two-player, zero-sum matrix game having payoff matrix,
    \begin{equation*}
    A=\begin{bmatrix} 2 & -3 \\ -1 & 4 \end{bmatrix}.
    \end{equation*}
   \item Suppose $\vecc$, $\vecb$, and $A$ are as given in (\ref{E:Duality_primal}).
   Define the matrix
   \begin{equation*}
   M = \begin{bmatrix} 0_{m \times m} & -A & \vecb \\
   A^t & 0_{m \times n} & -\vecc^t \\
   -\vecb^t & \vecc & 0
   \end{bmatrix}.
   \end{equation*}
   \be
   \item Verify that $M$ is a square matrix having $m+n+1$ rows. Then show that
   $M^t=-M$. (A square matrix, whose transpose equals its additive inverse,
   is said to be \emph{skew-symmetric}.)\index{skew-symmetric matrix}
   \item Suppose that both (\ref{E:Duality_primal}) and (\ref{E:Duality_dual}) are feasible
   and have optimal solutions, $\vecx_0$ and $\vecy_0$. Show that the matrix inequality $M \vecw \geq \zerovec$ has a solution, $\vecw=\vecw_0$, for some  $\vecw_0$ belonging to $\R^{m+n+1}$ and satisfying $\vecw_0 \geq \zerovec$ and
   $[\vecw_0]_{m+n+1}>0$.
   \item Now assume that the matrix inequality $M\vecw_0 \geq \zerovec$ holds for
   some vector $\vecw_0$ belonging to $\R^{m+n+1}$ and satisfying both $\vecw_0 \geq \zerovec$ and
   $[\vecw_0]_{m+n+1}>0$. Show that both (\ref{E:Duality_primal}) and (\ref{E:Duality_dual}) are feasible and have optimal solutions, $\vecx_0$ and $\vecy_0$, that can be expressed in terms of $\vecw_0$. (Hint: Let $\vecy$ be the row vector in $\R^m$ formed
   using the first $m$ components of $\vecw_0$, and let $\vecx$ be formed using
   the next $n$ components, $\ds [\vecw_0]_{m+1}, [\vecw_0]_{m+2}, \ldots, [\vecw_0]_{m+n}$.
   If $\kappa= [\vecw_0]_{m+n+1}$, which is positive, define
   $\ds \vecx_0 = \frac{1}{\kappa} \vecx$ and $\ds \vecy_0 = \frac{1}{\kappa} \vecy$.)
   \ee
   \ee

