\section{Basic Feasible Solutions}\label{S:ExerciseSolutions_LP_BFS}
\setcounter{progress_ck_counter}{0}

\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 and basic feasible solutions, expressing each solution in vector form. Label each
	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*}

\noi
Note that this LP is the same as that from Exercise 1a of Section 1.1, where
$\ds A= \begin{bmatrix} 2 &  3 \\ -1 & 0 \\ 0 & 1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 6 & 4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 9 \\ -4 \\ 6 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.
Since there are three constraints, $\ds \vecs=\begin{bmatrix} s_1 \\ s_2 \\ s_3 \end{bmatrix}$.

\newpar
In this case, the matrix equation,
\begin{equation}\label{E:Exercises_LP_BFS_MatrixEquation}
\left[A | I_m \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb
\end{equation}
has at most $\ds \begin{pmatrix} 5 \\ 2 \end{pmatrix}=10$ possible basic solutions. Each
is obtained by setting two of the five entries of $\ds \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$
to zero and solving (\ref{E:Exercises_LP_BFS_MatrixEquation}) for the
remaining three, provided the system is consistent. Of the ten possible cases to consider, two
lead to inconsistent systems. They arise from setting $x_1=s_2=0$ and from setting
$x_2=s_3=0$. The eight remaining consistent systems yield the following results:

\be
\item $\ds x_1=0,x_2=0,s_1=9,s_2=-4,s_3=6$ (basic, but not basic feasible solution)
\item $\ds x_1=0,x_2=3,s_1=0,s_2=-4,s_3=3$ (basic, but not basic feasible solution)
\item $\ds x_1=0,x_2=6,s_1=-9,s_2=-4,s_3=0$ (basic, but not basic feasible solution)
\item $\ds x_1=4.5,x_2=0,s_1=0,s_2=.5,s_3=6$ (basic feasible solution)
\item $\ds x_1=4,x_2=0,s_1=1,s_2=0,s_3=6$ (basic feasible solution)
\item $\ds x_1=4,x_2=1/3,s_1=0,s_2=0,s_3=17/3$ (basic feasible solution)
\item $\ds x_1=-4.5,x_2=6,s_1=0,s_2=-8.5,s_3=0$ (basic, but not basic feasible solution)
\item $\ds x_1=4,x_2=6,s_1=-17,s_2=0,s_3=0$ (basic, but not basic feasible solution)
\ee

\noi
The feasible region is that from Exercise 1a of Section 1.2, and the solution
is $x_1=4.5$ and $x_2=0$ with $z=27$.


\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*}

Note that this LP is the same as that from Exercise 1d of Section 1.1, where
$\ds A= \begin{bmatrix} -1 & -3 \\ -1 & -1 \\ 1 & -1 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} 1 & -4 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} -5 \\ -4 \\ 2 \end{bmatrix}$, and
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$
Since there are three constraints, $\ds \vecs=\begin{bmatrix} s_1 \\ s_2 \\ s_3 \end{bmatrix}$.

\newpar
As in the previous exercise, there are ten possible cases to consider. In this situation, all ten
systems are consistent. The results are as follows:

\be
\item $\ds x_1=0,x_2=0,s_1=-5,s_2=-4,s_3=2$ (basic, but not basic feasible solution)
\item $\ds x_1=0,x_2=5/3,s_1=0,s_2=-7/3,s_3=11/3$ (basic, but not basic feasible solution)
\item $\ds x_1=0,x_2=4,s_1=7,s_2=0,s_3=6$ (basic feasible solution)
\item $\ds x_1=0,x_2=-2,s_1=-11,s_2=-6,s_3=0$ (basic, but not basic feasible solution)
\item $\ds x_1=5,x_2=0,s_1=0,s_2=1,s_3=-3$ (basic, but not basic feasible solution)
\item $\ds x_1=4,x_2=0,s_1=-1,s_2=0,s_3=-2$ (basic, but not basic feasible solution)
\item $\ds x_1=2,x_2=0,s_1=-3,s_2=-2,s_3=0$ (basic, but not basic feasible solution)
\item $\ds x_1=7/2,x_2=1/2,s_1=0,s_2=0,s_3=-1$ (basic, but not basic feasible solution)
\item $\ds x_1=11/4,x_2=3/4,s_1=0,s_2=-1/2,s_3=0$ (basic, but not basic feasible solution)
\item $\ds x_1=3,x_2=1,s_1=1,s_2=0,s_3=0$ (basic feasible solution)
\ee


\noi The feasible region is that from Exercise 1c of Section 1.2, and the solution
is $x_1=3$ and $x_2=1$ with $z=1$.
\ee

\item The constraint equations of the standard form of the \LP LP are given by

 \begin{align}\label{E:ExerciseSolutions_LP_BFS_FuelPro}
    x_1 \phantom{+ 2x_2} + s_1 \ph \ph &= 8 \\
    2x_1 + 2x_2 \ph +s_2 \ph &= 28 \notag \\
    3x_1 + 2x_2 \ph \ph +s_3 &= 32 \notag
	\end{align}

If $x_1$ and $s_1$ are nonbasic, then both are zero. In this case
(\ref{E:ExerciseSolutions_LP_BFS_FuelPro}) is inconsistent. Observe
that if $x_1=s_1=0$, that the coefficient matrix corresponding to
(\ref{E:ExerciseSolutions_LP_BFS_FuelPro}) is given by
$\ds M=\begin{bmatrix} 0 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 0 & 1 \end{bmatrix}$,
which is not invertible.


 \item The LP is given by
           \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 The third constraint is the combination of $2x_1+x_2 \leq 10$ and
        $-2x_1-2x_2 \leq -10$. Thus, the matrix inequality form of the LP
        has $\ds A= \begin{bmatrix} 1 & 0 \\ 1 & 3 \\ 2 & 2 \\ -2 & -2 \end{bmatrix}$
        and $\ds \vecb=\begin{bmatrix} 4 \\ 15 \\ 10 \\ -10 \end{bmatrix}$.
        \item Since
        there are four constraints, there are four corresponding slack variables,
        $s_1$, $s_2$, $s_3$, and $s_4$, which lead to the matrix
        equation
        \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*}
        where $\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$
        and $\ds \vecs= \begin{bmatrix} s_1 \\ s_2 \\ s_3 \\ s_4 \end{bmatrix}$. If $s_3$ and
        $s_4$ are nonbasic, then both are zero. In this case, the preceding matrix equation
        becomes
        \begin{equation*}
        \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 3 & 0 & 1 \\ 2 & 1 & 0 & 0 \\ -2 & -1 & 0 & 0 \end{bmatrix}
        \begin{bmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \end{bmatrix}
        =\vecb.
        \end{equation*}

        \noi
        The solution to this matrix equation yields
        $x_1=4-t$, $x_2=2+2t$, $s_1=t$, and $s_2=5-5t$, where $t$ is a free quantity. A simple
        calculation shows that for $x_1$, $x_2$, $s_1$, and $s_2$ to all remain nonnegative, it
        must be the case that $0 \leq t \leq 1$. Note that if $t=0$, then
        $\ds \vecx = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 4 \\ 2 \end{bmatrix}$; if $t=1$, then $\ds \vecx = \begin{bmatrix} 3 \\ 4 \end{bmatrix}$. As $t$ increases from 0 to 1,
        $\vecx$ varies along the line segment connecting these two points.

        \ee
	
	\item The \LP LP has basic feasible solutions corresponding to the five points
    \begin{equation*}
     \vecx=\begin{bmatrix} 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 8 \\ 0 \end{bmatrix},
     \begin{bmatrix} 8 \\ 4 \end{bmatrix},\begin{bmatrix} 4 \\ 10 \end{bmatrix},
     \mbox{ and } \begin{bmatrix} 0 \\ 14 \end{bmatrix}.
     \end{equation*}
     Suppose we add a constraint that does not change the current feasible region but passes through
     one of these points. While there are countless such examples, a simple choice
     is to add $x_2 \leq 14$. Now consider the original \LP LP, with this new constraint
     added, and let $s_4$ denote the new corresponding slack variable. In the original LP,
     $\ds \vecx=\begin{bmatrix} 0 \\ 14 \end{bmatrix}$ corresponded to a basic feasible solution
     in which the nonbasic variables were $x_1$ and $s_2$. In the new LP, any basic solution
     is obtained by setting two of the six variables, $x_1$, $x_2$, $s_1$, $s_2$,
     $s_3$, and $s_4$, to zero. If we again choose $x_1$ and $s_2$ as nonbasic, then the resulting
     system of equations yields a basic feasible solution in which $s_4$ is a basic variable
     equal to zero. Thus, the LP is degenerate.

	
\item A subset $V$ of $\R^n$ is said to be \emph{convex} is 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 Suppose that the LP is expressed in matrix inequality form as
\begin{align}\label{E:Exercises_LP_BFS_ConvexFeasible}
 \mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to} \notag \\
	A \vecx &\leq \vecb  \notag \\
	\vecx &\geq \zerovec. \notag
	\end{align}

\noi
If $\vecx_1$ and $\vecx_2$ are feasible then $\ds A \vecx_1 \leq \vecb$ and
$\ds A \vecx_2 \leq \vecb$. Thus, if $0 \leq t \leq 1$, then
\begin{align*}
A\left( t\vecx_1 + (1-t)\vecx_2\right) &= tA\vecx_1 + (1-t) \vecx_2 \\
&\leq t\vecb + (1-t) \vecb \\
&= \vecb.
\end{align*}
By similar reasoning, if $\vecx_1,\vecx_2 \geq \zerovec$, then
 $\ds t\vecx_1 + (1-t)\vecx_2 \geq \zerovec$ whenever $0 \leq t \leq 1$.

\noi
This shows that if $\vecx_1$ and $\vecx_2$ satisfy the matrix inequality and sign conditions in (\ref{E:Exercises_LP_BFS_ConvexFeasible}), then so does
$\ds t\vecx_1 + (1-t)\vecx_2 \geq \zerovec$ for $0 \leq t \leq 1$. Hence, the feasible region
is convex.

\item If $\vecx_1$ and $\vecx_2$ are solutions of LP (\ref{E:Exercises_LP_BFS_ConvexFeasible}), then both are feasible. By the previous result, $\vecx=\ds t\vecx_1 + (1-t)\vecx_2$
    is also feasible if $0 \leq t \leq 1$. Since, $\vecx_1$ and $\vecx_2$ are both solutions of the LP,
    they have a common objective value $z_0=\vecc \cdot \vecx_1=\vecc \cdot \vecx_2$.
    Now consider the objective value at $\vecx$:
    \begin{align*}
    \vecc \cdot \vecx &= \vecc \cdot \left( t\vecx_1 + (1-t)\vecx_2\right) \\
    &= t \vecc \cdot \vecx_1 + (1-t) \vecc \cdot \vecx_2 \\
    &= tz_0 + (1-t)z_0 \\
    &= z_0.
    \end{align*}

\noi
Thus, $\vecx=\ds t\vecx_1 + (1-t)\vecx_2$ is also yields an objective value of $z_0$. Since $\vecx$
is also feasible, it must be optimal as well.

 \ee

\item Suppose the matrix inequality form of the LP
is given by
\begin{align}\label{E:ExerciseSolutions_LP_BFS_convexhull}
 \mbox{maximize } z &=\vecc \cdot \vecx   \\
	\mbox{ subject to}  \notag \\
	A \vecx &\leq \vecb  \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align}
and let $\tilde{\vecx}$ denote an optimal solution. Since $\tilde{\vecx}$
belongs to the convex hull generated by the set of basic feasible solutions,
\begin{equation*}
\tilde{\vecx}= \sum_{i=1}^p \sigma_i \vecx_i,
\end{equation*}
where the weights $\sigma_i$ satisfy $\sigma_i \geq 0$ for all $i$ and $\ds \sum_{i=1}^p \sigma_i=1$
and where $\ds \vecx_1,\vecx_2,\ldots,\vecx_p$
are the basic feasible solutions of (\ref{E:ExerciseSolutions_LP_BFS_convexhull}).
Relabeling the basic feasible solutions if necessary, we may assume
that $\vecc \cdot \vecx_i \leq \vecc \cdot \vecx_1$, for $1 \leq i \leq p$. Now consider the objective
value corresponding to $\tilde{\vecx}$. We have
\begin{align*}
\vecc \cdot \tilde{\vecx} &= \vecc \cdot \left(\sum_{i=1}^p \sigma_i \vecx_i \right) \\
&= \sum_{i=1}^p \vecc \cdot\left( \sigma_i \vecx_i \right) \\
&= \sum_{i=1}^p  \sigma_i \left( \vecc \cdot \vecx_i \right) \\
&\leq \sum_{i=1}^p  \sigma_i \left( \vecc \cdot \vecx_1 \right) \\
&= \left( \vecc \cdot \vecx_1 \right) \sum_{i=1}^p  \sigma_i  \\
&= \vecc \cdot \vecx_1.
\end{align*}

\noi
Thus the objective value corresponding to $\vecx_1$ is at least as large as that corresponding to the optimal solution, $\tilde{\vecx}$, which implies that $\vecx_1$ is also a solution of
(\ref{E:ExerciseSolutions_LP_BFS_convexhull})

\ee

% WAYPOINT SOLUTIONS

\hrulefill

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint} The matrix equation
\begin{equation*}
\left[A | I_3 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb
\end{equation*}
has a solution given by $\vecx=\zerovec$ and $\vecs=\vecb$. Since the corresponding system
has more variables then equations, it must have infinitely many solutions.
\end{waypoint}

\begin{waypoint}
To solve the given matrix equation, we row reduce the augmented matrix
\begin{equation*}
\left[  \begin{matrix} 1 & 0 & 1 & 0 & 0 \\
2 & 2 & 0 & 1 & 0 \\
3 & 2 & 0 & 0 & 1
\end{matrix}
\left| \begin{matrix} 8 \\ 28 \\ 32 \end{matrix} \right. \right].
\end{equation*}

\noi
The result is given by
\begin{equation*}
\left[  \begin{matrix} 1 & 0 & 0 & -1 & 1  \\
0 & 1 & 0 & 3/2 & -1 \\
0 & 0 & 1 & 1 & -1
\end{matrix}
\left| \begin{matrix} 4 \\ 10 \\ 4 \end{matrix} \right. \right].
\end{equation*}

If we let $s_2$ and $s_3$ denote the free variables, then we may write $s_2=t$, $s_3=s$, where $t,s \in \R$. With this notation, $x_1=4+t-s$, $x_2=10-\frac{3}{2}t+s$, and $s_1=4-t+s$. We obtain the five extreme points as follows:
\be
\item $t=28$ and $s=32$ yield $\ds \vecx=\begin{bmatrix} 0 \\ 0 \end{bmatrix}$
and $\ds \vecs=\begin{bmatrix} 8 \\ 28 \\ 32 \end{bmatrix}$
\item $t=12$ and $s=8$ yield $\ds \vecx=\begin{bmatrix} 8 \\ 0 \end{bmatrix}$
and $\ds \vecs=\begin{bmatrix} 0 \\ 12 \\ 8 \end{bmatrix}$
\item $t=4$ and $s=0$ yield $\ds \vecx=\begin{bmatrix} 8 \\ 4 \end{bmatrix}$
and $\ds \vecs=\begin{bmatrix} 0 \\ 4 \\ 0 \end{bmatrix}$
\item $t=s=0$ yields $\ds \vecx=\begin{bmatrix} 4 \\ 10 \end{bmatrix}$
and $\ds \vecs=\begin{bmatrix} 4 \\ 0 \\ 0 \end{bmatrix}$
\item $t=0$ and $s=4$ yield $\ds \vecx=\begin{bmatrix} 0 \\ 14 \end{bmatrix}$
and $\ds \vecs=\begin{bmatrix} 8 \\ 0 \\ 4 \end{bmatrix}$
\ee

\noi
These extreme points may then be labeled on the feasible region.
\end{waypoint}

\begin{waypoint}
\be
\item The feasible region and various contours are shown
in Figure \ref{Fi:w01x3x1}

\begin{figure}[h]
\centering
\psfrag{x1axislabel}[Bc][Bc]{$x_1$}
\psfrag{x2axislabel}[Bc][Bc]{$x_2$}
\psfrag{ctr1}[Bc][Bc]{$z=0$}
\psfrag{ctr2}[Bc][Bc]{$z=-3$}
\psfrag{ctr3}[Bc][Bc]{$z=-5$}
\psfrag{ctr4}[Bc][Bc]{$z=-7.5$}
\includegraphics[width=1\linewidth]{ExerciseSolutions/images/waypoints/w01x03x03.eps}
\caption{Feasible region with contours $z=0$, $z=-3$, $z=-5$ and $ z=-7.5$.}
\label{Fi:w01x3x2}
\end{figure}

\noi The extreme points are given by the $\ds \vecx_1=\begin{bmatrix} 0 \\ 0 \end{bmatrix}$,
$\ds \vecx_2=\begin{bmatrix} 3/2 \\ 0 \end{bmatrix}$, $\ds \vecx_3=\begin{bmatrix} 6/7 \\ 12/7 \end{bmatrix}$,
and $\ds \vecx_4=\begin{bmatrix} 0 \\ 4 \end{bmatrix}$.

\item If $\ds \vecc=[-5,2]$, $\ds A=\begin{bmatrix} 3 & 2 \\ 8 & 3 \end{bmatrix}$,
$\ds \vecb=\begin{bmatrix} 6 \\ 12 \end{bmatrix}$,
$\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$, and
$\ds \vecs=\begin{bmatrix} s_1 \\ s_2 \end{bmatrix}$,
then the standard matrix form is given by

\begin{align*}
 \mbox{maximize } z &=\vecc \cdot \vecx  \\
	\mbox{ subject to} \notag\\
	\left[A | I_2 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb \notag \\
	\vecx, \vecs  &\geq \zerovec, \notag
\end{align*}

\item The two constraint equations can be expressed as $3x_1+2x_2=6$ and
$8x_1+3x_2=12$. Substituting $x_1=x_2=0$ into this equations yields the basic solution
$x_1=0$, $x_2=0$, $s_1=6$ and $s_2=16$. Performing the same operations using
the other three extreme points from (1) yields the remaining three
basic feasible solutions:
\be
\item $x_1=1.5$, $x_2=0$, $s_1=1.5 $ and $s_2=0$
\item $x_1=\frac{6}{7}$, $x_2=\frac{12}{7}$, $s_1=0$ and $s_2=0$
\item $x_1=0$, $x_2=3$, $s_1=0$ and $s_2=16$
\ee

\item The contours in Figure \ref{Fi:w01x3x1} indicate the optimal solution occurs
at the basic feasible solution $\ds \vecx=\begin{bmatrix} 1.5 \\ 0 \end{bmatrix}$,
where $z=-7.5$.
\ee

\end{waypoint}

\endinput 