# Simplex method state after first phase

I'm implementing a simplex method solver for a standard problem \begin{aligned} \operatorname{minimize} \qquad&c^T x\\ \operatorname{subjected to} \qquad&Ax = b\\ &x \geq 0\\ \end{aligned} To find basic feasible solution I'm adding new variables $y$ and solving additional problem \begin{aligned} \operatorname{minimize} \qquad&\sum y\\ \operatorname{subjected to} \qquad&Ax + y = b\\ &x \geq 0\\ \end{aligned} The last $m$ rows of matrix $(A\;E)$ form the basis. When the additional problem is solved the matrix $(A\;E)$ along with right hand side $b$ and set of basis rows are changed.

May the set of basis vaiables in the updated simplex tableau contain additional variables $y$? I've seen an example of such case if $A$ has incomplete rank, so assumming that $\operatorname{rank} A = m$.

## 1 Answer

Assume that you have $n$ decision variables in the original LPP. i.e. $x=(x_1,\dots,x_n)^T$ and $m < n$. Then $A \in M_{m\times n}(\Bbb R)$. Since you assume that $\operatorname{rank} A = m$, $A$ has $m$ linearly independent columns. Since you have $m$ constraints, $b \in \Bbb R^m$. Therefore, $b$ can be represented by columns of $A$. In other words, $Ax=b$ has feasible solution. This shows that the additional problem

\begin{align} \operatorname{minimise} \qquad&\sum y\\ \operatorname{subjected to} \qquad&Ax + y = b \label{add} \tag{*} \\ &x,y \geq 0 \end{align}

has a feasible solution (with $y=0$). Since $y\ge0$ and we are minimising $\sum y$, we've shown that the additional problem has a unique basic feasible optimal solution.

To sum up, after solving the additional problem \eqref{add}, you'll have its optimal solution. The paragraph above showed that \eqref{add} has unique optimal feasible solution. Therefore, when the additional problem is solved, the set of basis variables in the updated simplex tableau doesn't contain additional variables $y$.