\be
	\item For each of the following LPs, write the LP
	in the standard matrix form
		\begin{align*}
	\mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to} \\
	\left[A | I_m \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb  \\
	\vecx, \vecs &\geq \zerovec.
	\end{align*}
	Then determine all basic solutions, expressing each solution in vector form and indicating whether it is also basic feasible. Label each basic feasible
	solution next to its corresponding point on the feasible region graph.
    \be
       \item
        \begin{align*}
        \mbox{maximize } z &=6x_1+4x_2  \\
	\mbox{ subject to} \\
	2x_1 + 3x_2 & \leq 9 \\
	x_1 \phantom{ +20y} &\geq 4 \\
	\phantom{ +20x} x_2  &\leq 6  \\
	x_1,x_2 &\geq 0\notag
    % Unique solution
	\end{align*}

        \item \begin{align*}
		 \mbox{minimize } z &=-x_1+4x_2  \\
		\mbox{ subject to} \notag\\
		x_1 +3x_2 &\geq 5 \notag\\
		x_1+x_2 &\geq 4  \notag\\
		x_1-x_2 &\leq 2 \notag \\
		x_1,x_2 &\geq 0\notag
		\end{align*}
    \ee
    \item Show that in the \LP LP that no basic solution exists for which $x_1$ and $s_1$
    are nonbasic. This result underscores the importance of the linear independence
        condition in Definition \ref{Th:LP_BFS_basic_solution_def}.

    \item The following LP has its feasible region given by the segment connecting the points
    $\ds \vecx=\begin{bmatrix} 3 \\ 4 \end{bmatrix}$ and $\ds \vecx=\begin{bmatrix} 4 \\ 2 \end{bmatrix}$:
           \begin{align*}
		 \mbox{maximize } z &=3x_1+2x_2  \\
		\mbox{ subject to} \notag\\
		x_1 \phantom{ +20x_2} &\leq 4 \notag\\
		x_1+3x_2 &\leq 15  \notag\\
		2x_1+x_2 &= 10\notag \\
		x_1,x_2 &\geq 0.\notag
		\end{align*}

        \be
        \item By rewriting the third constraint as the combination of two others, express the LP in matrix inequality form. Then express it in standard matrix form.
        \item The standard matrix form has four slack variables, two of which correspond
        to the third constraint. Show that when these two are chosen as nonbasic, the resulting system
        of equations in the basic variables infinitely many solutions, which correspond to the segment
        connecting $\ds \vecx=\begin{bmatrix} 3 \\ 4 \end{bmatrix}$ and $\ds \vecx=\begin{bmatrix} 4 \\ 2 \end{bmatrix}$.
        \ee
	
	\item According to Definition \ref{Th:BFS}, a basic feasible solution is a basic solution in which
	all basic variables are nonnegative. An LP is said to be \emph{degenerate} if it has a basic
	feasible solution in which at least one basic variable equals zero. Experiment and construct an example
	of a degenerate LP. (Hint: Start with the \LP LP and add a constraint, whose boundary line intersects the original LP at one of its basic feasible solutions.)
	\item A subset $V$ of $\R^n$ is said to be \emph{convex} if whenever two points belong to $V$, so does the
	line segment connecting them. In other words, $\vecx_1, \vecx_2 \in V$, implies that
	$\ds t\vecx_1 + (1-t)\vecx_2 \in V$ for all $0 \leq t \leq 1$.
\be
\item Use the
	matrix inequality form of an LP to show that the feasible region of an LP is convex.
\item Show that if $\vecx_1$ and $\vecx_2$ are solutions of an LP, so is
$\ds t\vecx_1 + (1-t)\vecx_2$ for any $0 \leq t \leq 1$.
\ee


\item Given a set of vectors $V= \left\{\vecx_1, \vecx_2, \ldots, \vecx_p \right\}$ in $\R^n$, a
	\emph{convex combination} of the vectors is any linear combination of the form
		\[ \sum_{i=1}^p \sigma_i \vecx_i = \sigma_1 \vecx_1 + \sigma_2 \vecx_2 +\cdots + \sigma_p \vecx_p,\]
	where the weights $\sigma_i$ satisfy $\sigma_i \geq 0$ for all $i$ and where $\ds \sum_{i=1}^p \sigma_i=1$.
The set of all convex combinations of vectors in $V$ is referred to as
	\emph{convex polyhedron}, or \emph{convex hull}, generated by $V$. Suppose that the
	feasible region of the LP is the convex polyhedron generated by its basic feasible
    solutions, $V= \left\{\vecx_1, \vecx_2, \ldots, \vecx_p \right\}$. Show that if the LP has
    an optimal solution, then it has a basic feasible solution that is also optimal. (Hint: Start with
    an LP having optimal solution $\tilde{\vecx}$. Express  $\tilde{\vecx}$
    as a convex combination of the basic feasible solutions and show that the objective function
    evaluated at one of the basic feasible solutions is at least as large as the objective function
     evaluated at $\tilde{\vecx}$.)
	\ee
\endinput
