Dual-simplex invariant and Farkas infeasibility certificate

Fix an eligible pivot $(i,j)$ and put $q=A_B^{-\mathsf{T}}{e}_i$. With $\alpha ={\bar{c}}_j\mathrm{/}{d}_{ij}\le 0$, the vector $y^{\mathrm{\prime }}=y+\alpha q$ satisfies $a_j^{\mathsf{T}}{y}^{\mathrm{\prime }}=c_j$, so the entering column has new reduced cost zero. The leaving basic column $a_{B_i}$ has $q^{\mathsf{T}}{a}_{B_i}=1$, hence its new reduced cost is $-\alpha \ge 0$.

If no nonbasic column has $d_{ij}<0$, then $A^{\mathsf{T}}q\ge 0$: the basic columns give the coordinates of $e_i$, and every nonbasic column has nonnegative $i$th transformed entry. Also $b^{\mathsf{T}}q=e_i^{\mathsf{T}}{A}_B^{-1}b=x_{B_i}<0$. By [F3], $q$ is a Farkas infeasibility certificate; any feasible $x\ge 0$ would give $b^{\mathsf{T}}q=x^{\mathsf{T}}{A}^{\mathsf{T}}q\ge 0$, a contradiction.

For any other nonbasic $k$, write $d_{ik}=q^{\mathsf{T}}{a}_k$. Its new reduced cost is ${\bar{c}}_k^{\mathrm{\prime }}={\bar{c}}_k-\alpha d_{ik}$. If $d_{ik}\ge 0$, this is nonnegative because $\alpha \le 0$. If $d_{ik}<0$, the ratio rule gives ${\bar{c}}_j\mathrm{/}(-d_{ij})\le {\bar{c}}_k\mathrm{/}(-d_{ik})$, so ${\bar{c}}_k^{\mathrm{\prime }}=(-d_{ik})({\bar{c}}_k\mathrm{/}(-d_{ik})-{\bar{c}}_j\mathrm{/}(-d_{ij}))\ge 0$. Thus every new nonbasic reduced cost is nonnegative.

If the basis is primal feasible, its basic vector $x$ and dual-feasible $y$ satisfy $c^{\mathsf{T}}x=b^{\mathsf{T}}y$, because $c_B^{\mathsf{T}}{A}_B^{-1}b=y^{\mathsf{T}}b$. For every feasible $z$, $A^{\mathsf{T}}y\le c$ and $z\ge 0$ imply $c^{\mathsf{T}}z\ge b^{\mathsf{T}}y=c^{\mathsf{T}}x$, so $x$ is optimal. The algorithm's budget-exhausted branch asserts no further mathematical conclusion.