3.4.3. Restoring the Objective Function

To convert \(P'\) into an equivalent LP \(P^{(0)}\) that has \(B''\) as a basis, it remains to replace the objective function of \(P'\) with an equivalent one in which every basic variable has coefficient \(0\). Let \(B'' = \bigl(j''_1, \ldots, j''_m\bigr)\) and let the \(i\)th equality constraint of \(P'\) be

\[b''_i = \sum_{j=1}^{m+n}a''_{ij}z_j.\]

Then

\[z_{j_i''} = b''_i - \sum_{j \notin B''} a''_{ij}z_j\]

for all \(1 \le i \le m\).

By substituting the right-hand side of this equality for \(z_{j_i''}\) into the objective function of \(P'\), for all basic variables \(z_{j_1''}, \ldots, z_{j_m''}\), we obtain an equivalent objective function in which only non-basic variables have non-zero coefficients.