3.4.2. Dropping \(\boldsymbol{s}\)

As already said, we obtain an LP \(P'\) equivalent to \(P\) by removing \(s\) from \(Q''\) and using \(P\)'s objective function as the objective function of \(P'\). Removing \(s\) entails removing it from the right-hand side of every equality constraint and removing its non-negativity constraint. This implies that the basis \(B''\) of \(Q''\) is almost a basis of \(P'\): The \(i\)th basic variable has coefficient \(1\) in the \(i\)th equality constraint and coefficient \(0\) in every other equality constraint, but it may have a non-zero coefficient in the objective function. Also, since \(\bigl(\tilde z, \tilde s\bigr)\) is the BFS of \(Q''\) and \(s\) is not in the basis \(B''\) of \(Q''\), \(\tilde z\) is the BFS of \(P'\).

This construction of \(P'\) from \(Q''\) is trivial, but is \(P'\) really equivalent to \(P\)? They have the same objective function and therefore clearly assign the same objective function value to any solution. To see that \(P\) and \(P'\) have the same set of solutions, observe once again that the equality constraints \(b'' = A''z + r''s\) in \(Q''\) are obtained from the equality constraints \(b = Az - 1s\) in \(Q\) using elementary row operations. The same elementary row operations transform the equality constraints \(b = Az\) of \(P\) into the equality constraints \(b'' = A''z\) of \(P'\). Therefore, by Lemma 3.2, \(P\) and \(P'\) have the same set of solutions and are thus equivalent.