0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.