Exercise 3.24

Let $y_k$ be an artificial variable that becomes nonbasic at some iteration. This has two immediate consequences:

1.

As a nonbasic variable, its value is now $y_k=0$.

2.

The $k$-th constraint of the auxiliary problem, $a_k^{\prime }x+y_k=b_k$, is now satisfied as $a_k^{\prime }x=b_k$ by the current solution. The purpose of $y_k$—to serve as an initial basic variable for this constraint—has been fulfilled.

The objective of Phase I is to minimize $\sum <!--\; FUNCTION\; APPLICATION\; -->y_i$. Any subsequent pivot that would cause $y_k$ to re-enter the basis would require making its value positive. This would necessarily increase the objective function, moving the algorithm further from its goal of reaching a cost of zero.

Since re-introducing $y_k$ into the basis is always counterproductive to the goal of Phase I, we can adopt a pivoting rule that forbids selecting nonbasic artificial variables as entering variables. Under this rule, the column for $y_k$ plays no further role and can be eliminated from the tableau to simplify computations, without affecting the outcome of Phase I.