3.1 Reduced costs and the optimality test
Consider the standard-form problem: minimise \(c^{\mathsf T}x\) subject to \(Ax = b\), \(x \geq 0\), and a BFS with basis matrix \(B\), so that \(x_B = B^{-1}b \geq 0\) and \(x_N = 0\). Every solution of \(Ax = b\) satisfies \(Bx_B + Nx_N = b\), so \[ x_B = B^{-1}b - B^{-1}Nx_N, \qquad c^{\mathsf T}x = c_B^{\mathsf T}B^{-1}b + \sum _{j \in N}\bar c_jx_j, \qquad \bar c_j = c_j - c_B^{\mathsf T}B^{-1}A_j . \] The number \(\bar c_j\) is the reduced cost of the non-basic variable \(x_j\): the rate at which the objective changes when \(x_j\) is increased from \(0\) and the basic variables adjust to keep \(Ax = b\). (Sharma, following a common textbook convention for maximisation, writes \(c_j - z_j\) with \(z_j = c_B^{\mathsf T}B^{-1}A_j\); it is the same quantity.)
Theorem 3.1.1 (Optimality test). If \(\bar c_j \geq 0\) for every non-basic \(j\), the BFS is optimal.
Proof. For any feasible \(y\), \(y_N \geq 0\), so by the identity above \(c^{\mathsf T}y = c_B^{\mathsf T}B^{-1}b + \sum _{j \in N}\bar c_jy_j \geq c_B^{\mathsf T}B^{-1}b = c^{\mathsf T}x\). □
If some \(\bar c_j < 0\), increasing \(x_j\) improves the objective. Put \(u = B^{-1}A_j\); increasing \(x_j\) to \(\theta \) changes the basic variables to \(x_B - \theta u\). They stay non-negative as long as \(\theta \leq x_{B(i)}/u_i\) for every \(i\) with \(u_i > 0\), which gives the ratio test \[ \theta ^* = \min \Bigl \{\frac {x_{B(i)}}{u_i} : u_i > 0\Bigr \} . \]
Theorem 3.1.2 (A pivot). Let \(\bar c_j < 0\).
- (i)
- If \(u = B^{-1}A_j \leq 0\), the LP is unbounded: \(x + \theta d\) is feasible for all \(\theta \geq 0\), where \(d_j = 1\), \(d_B = -u\) and \(d\) is \(0\) elsewhere, and its cost \(c^{\mathsf T}x + \theta \bar c_j \to -\infty \).
- (ii)
- Otherwise, let the minimum in the ratio test be attained at row \(\ell \). Replacing the basic variable \(x_{B(\ell )}\) by \(x_j\) gives a new basis, the new BFS is \(x + \theta ^*d\), and its cost is \(c^{\mathsf T}x + \theta ^*\bar c_j \leq c^{\mathsf T}x\), with strict inequality if \(\theta ^* > 0\).
Proof. \(Ad = A_j - Bu = 0\), so \(A(x + \theta d) = b\), and \(x + \theta d \geq 0\) for \(0 \leq \theta \leq \theta ^*\) by the ratio test (for all \(\theta \geq 0\) in case (i)); its cost is \(c^{\mathsf T}x + \theta (c_j - c_B^{\mathsf T}u) = c^{\mathsf T}x + \theta \bar c_j\). In case (ii), at \(\theta = \theta ^*\) the variable \(x_{B(\ell )}\) becomes \(0\). The new columns are independent: \(A_j = Bu\) with \(u_\ell > 0\), so \(A_j\) is not in the span of the other basic columns. So the new point is a BFS. □
Theorem 3.1.3 (Finite termination). If every BFS is non-degenerate, the simplex method stops after finitely many pivots, either with an optimal BFS or with a proof of unboundedness.
Proof. Without degeneracy every \(\theta ^* > 0\), so each pivot strictly decreases the cost. Hence no basis is visited twice, and there are at most \(\binom nm\) bases. □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.