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

\noi The \LP LP, (\ref{E:Prototype_Standard_Form_FuelPro_LP}), has as its optimal solution, $x_1=4$ and $x_2=10$, which corresponds
to an objective value of $z=46$. The feasible region for the LP, labeled with the optimal
solution, is shown in Figure \ref{Fi:f02x03x01}.

\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\psfrag{solution}[Bc][Bc]{$(4,10)$}
\includegraphics[width=.7\linewidth]{images/f02x03x01.eps}
\caption{Feasible region for \LP LP.}\label{Fi:f02x03x01}
\end{figure}

\noi
We see that
the feasible region has five\index{corner points|see{linear programming problem!corner points}} ``corner points'' or ``extreme points,'' one\index{extreme points|see{linear programming problem!extreme points}} of which is the optimal solution. This result holds true in general. Namely, for the LP (\ref{E:LPStandardMatrixInequalityForm}) having a unique optimal solution, the optimal solution occurs at an ``extreme point'' of
the feasible region in $\R^n$. The \emph{simplex algorithm}\index{simplex algorithm}, which we develop in Section \ref{S:Simplex}, is a linear-algebra based
method that graphically
corresponds to starting at one extreme point on the boundary of the feasible region, typically $(0,0)$,
and moving to adjacent extreme points through an iterative process until an optimal solution is obtained. The purpose of this
section is to lay a foundation for this algorithm by developing appropriate terminology that connects
the underlying ideas of systems of equations to those of the feasible region and its extreme points.

\newpage
\noi
The \LP LP (\ref{E:Prototype_Standard_Form_FuelPro_LP}) is given by\index{FuelPro LP}
	
\begin{align*}
 \mbox{maximize } z &=4x_1+3x_2   \\
	\mbox{ subject to} \notag\\
	x_1 \phantom{ +20x_2} &\leq 8 \notag\\
	2x_1+2x_2 &\leq 28  \notag\\
	3x_1+2x_2 &\leq 32 \notag \\
	x_1,x_2 &\geq 0.\notag
	\end{align*}		
	
\newpar
Because systems of equations are a familiar setting from linear algebra, we introduce
additional variables, called \emph{slack variables}\index{slack variables}, corresponding to these three inequalities. Labeling these
variables as $s_1$, $s_2$, and $s_3$, we then have

\begin{align}\label{E:petrol_LP_standard_form}
 \mbox{maximize } z =4x_1+3x_2 \\
	\mbox{  subject to} \notag \\
    x_1 \phantom{+ 2x_2} + s_1 \ph \ph &= 8 \notag \\
    2x_1 + 2x_2 \ph +s_2 \ph &= 28 \notag \\
    3x_1 + 2x_2 \ph \ph +s_3 &= 32 \notag \\
	x_1,x_2, s_1, s_2, s_3  &\geq 0. \notag
	\end{align}

\newpar
We will use the terminology that (\ref{E:petrol_LP_standard_form})
is the original LP (\ref{E:LP_Prototype_Standard_Form_FuelPro_LP}) expressed in \emph{standard form}. 	

\newpar
Note that requiring the slack variables to be nonnegative assures us that our three equations are
equivalent to the three inequalities from (\ref{E:LP_Prototype_Standard_Form_FuelPro_LP}). Recalling the matrix inequality form notation (\ref{E:LPStandardMatrixInequalityForm}) and denoting the vector of slack variables by
\[ \vecs = \begin{bmatrix}  s_1 \\ s_2 \\ s_3 \end{bmatrix}, \]
we can express the \emph{standard matrix form}\index{standard matrix form|see{linear programming problem!standard matrix form}} as follows:

\begin{align}\label{E:LP_BFS_Standard_Form_Matrix_Equation}
 \mbox{maximize } z &=\vecc \cdot \vecx  \\
	\mbox{ subject to} \notag\\
	\left[A | I_3 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb \notag \\
	\vecx, \vecs  &\geq \zerovec, \notag
	\end{align}
\noi where $I_3$ denotes the 3-by-3 identity matrix. Thus we have converted the $m=3$ inequalities in $n=2$ decision variables from the
original LP into a matrix equation, or system of equations, involving $m=3$ equations in $m+n=5$ unknowns. Note in particular that $\ds \left[A | I_3 \right]$ is a 3 by 5 matrix and that
$\ds \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$ belongs to $\R^5$.

\newpar
It is important to recognize connections between solutions to this system and
the problem at hand.

\begin{progress_ck} Before proceeding, explain why the matrix equation $\ds \left[A | I_3 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb$ has infinitely many solutions.
\end{progress_ck}

\newpar
We now seek to determine the set of solutions to $\ds \left[A | I_3 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb$, ignoring
momentarily the sign restrictions placed on the variables in the LP. Recall that the \emph{row space}\index{row space}, resp. \emph{column space}\index{column space} of a matrix
is the set of all linear
combinations of the row vectors (resp. column vectors) that comprise the matrix. The dimensions
of the row and column spaces are equal, having common value referred to
as the \emph{rank}\index{rank} of the matrix. In the \LP example,
\begin{equation*}
\left[A | I_3 \right] = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\
2 & 2 & 0 &1 &0 \\
3 & 2 & 0 & 0 & 1 \end{bmatrix},
\end{equation*}
which, as elementary row operations demonstrate, has pivots in three columns. Therefore
$\ds  \left[A | I_3 \right]$ has rank $m=3$.

\newpar
On the other hand, the \emph{null space}\index{null space} of $\ds  \left[A | I_3 \right]$ is the set of all solutions to
the homogeneous matrix equation $\ds  \left[A | I_3 \right]\vecv = \zerovec$. By
the Rank-Nullity Theorem (Theorem \ref{Th:RankNullityTheorem})\index{Rank-Nullity Theorem}, the sum of its dimension,
referred to as the \emph{nullity}\index{nullity},
and the rank equals the number of columns of
$\ds  \left[A | I_3 \right]$, which is $m+n=5$. Hence,
the dimension of the null space is $n=2$.

\newpar
Finally, we recall that the solution to a consistent
 matrix equation $\ds  \left[A | I_3 \right]\begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb$ can be written in the form
		\[ \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecv_h + \vecv_p ,\]
where $\vecv_h$ is the general solution to the homogeneous matrix equation
$\ds  \left[A | I_3 \right]\vecv = \zerovec$ and $\vecv_p$ is a particular solution to the nonhomogeneous equation $\ds  \left[A | I_3 \right]\vecv = \vecb$. Therefore if the null space of
$\ds  \left[A | I_3 \right]$ is dimension $n=2$,
we can expect
$\ds  \left[A | I_3 \right]\begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb$ to have $n=2$ free variables in its general solution, provided the matrix equation is consistent.

\begin{progress_ck} For the \LP LP, determine the general
solution to the matrix equation $\ds  \left[A | I_3 \right]\begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}
= \vecb$.
For each extreme point in Figure \ref{Fi:f02x03x02},
choose the free variables in a way that produces the given extreme point. Next to the extreme point, label the vector
$\ds\begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$ with all {\underbar{five}} of its entries.
\end{progress_ck}

\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f02x03x02.eps}
\caption{Feasible region for \LP LP.}\label{Fi:f02x03x02}
\end{figure}

\newpar
The solutions to the preceding matrix equation play a special role
in the context of the LP, in that they correspond to what we call \emph{basic solutions}.

\begin{definition}\label{Th:LP_BFS_basic_solution_def}
Consider an LP consisting of $m$ inequalities and $n$ decision variables, whose
matrix inequality form is given by (\ref{E:LPStandardMatrixInequalityForm}).
Then the constraints of the \emph{standard matrix form} of this LP are represented
by the matrix equation,
\begin{equation}\label{E:LP_BFS_standard_matrix_form_coefficient_matrix}
\left[A | I_m \right]\begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} = \vecb,
\end{equation}
where, $\vecx$ is an $n$-by-1 vector of decision variables and $\vecs$ is an $m$-by-1 vector
of slack variables.
A basic solution to the LP is formed by first setting to zero $n$ variables of
$\ds \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$. These variables
are referred to as the \emph{nonbasic variables}\index{nonbasic variables}. If the $m$ columns corresponding
to the remaining variables form a linearly independent set, then there exist unique
values for the remaining variables, which we call \emph{basic variables}\index{basic variables}. Taken together, these nonbasic and basic variables constitute a basic solution\index{basic solution} of LP (\ref{E:LPStandardMatrixInequalityForm}).
\end{definition}
\noi The fact that the basic variables, denoted by the vector
$\vecx'$, are uniquely determined in Definition \ref{Th:LP_BFS_basic_solution_def} follows from
the Invertible Matrix Theorem and the assumption that the $m$ columns form a linearly independent set. For when this occurs, these columns
yield an $m$ by $m$ invertible submatrix, $B$, of $\ds \left[A | I_m \right]$, so that
$\ds B\vecx'=\vecb$ has a unique solution.

\newpar
Here is the connection to commonly used terminology in linear algebra.
When solving a system of equations having infinitely many solutions, we
obtain two types of variables, those considered free\index{free variables} and those
considered basic. While there exist different possible ways to assign which
variables are free, their number must equal
the nullity of the matrix. The values of the free variables
uniquely determine the
basic variable values. In the terminology of Definition
\ref{Th:LP_BFS_basic_solution_def}, nonbasic variables can
be viewed as free variables all of which have been set to zero.

\newpar
Basic solutions correspond to intersection points of the constraints of the original LP. Unfortunately, this
definition is not precise in that it can also include points that lie outside
the LP's feasible region. In particular, observe that in the preceding Waypoint, intersection points outside
the feasible region corresponded to vectors $\ds \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix}$, in
which at least one entry is negative. We therefore refine our definition of basic solution as follows.
\begin{definition}\label{Th:BFS}\index{basic feasible solution}
A basic {\underbar{feasible}} solution (BFS) to an LP is a basic solution in which all basic variables are
nonnegative.
\end{definition}
\noi
For the \LP example, basic feasible solutions correspond to the points
$(0,0)$, $(8,0)$, $(8,4)$, $(4,10)$, and $(0,14)$.

\begin{progress_ck} Consider the minimization problem
\begin{align*}
	\mbox{minimize } z &=-5x_1+2x_2   \\
	\mbox{ subject to} \\
	3x_1+2x_2  &\leq 6  \\
	8x_1 + 3x_2 &\leq 12 \\
	x_1,x_2 &\geq 0.
	\end{align*}

	\be
	\item Sketch the feasible region for the LP. Label all extreme points.
	\item Introduce slack variables and express the LP in standard matrix form.
	\item Determine the basic feasible solutions for the LP. Complete this
	last task without actually performing elementary row operations. Instead use the extreme points
from (1).
	\item Graphically solve the LP by using contours of the objective function.
	\ee
\end{progress_ck}

\section*{Exercises Section \protect\ref{S:LP_BFS}}
\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_LP_BFS}	
\endinput

