suppose we have the following linear program max{$c^Tx+z: Ax=b, x \geq0$} and that B is an optimal basis with $\bar{x}$ being the basic feasible solution corresponding to B. How would I be able to prove that $y=A_B^{-T}c_B$ is a certificate of optimality for $\bar{x}$?
I know that I have to show
1) $A^Ty \geq c$
2) $c^Tx=y^Tb$
I have been able to show 2) but am struggling on showing 1)
From $y=A_B^{-T}c_B$ you multiply with $A_B^T$ to get $A_B^Ty = c_B$.
The tableau is optimal, so $c_B^T A_B^{-1} A_N - c_N^T \geq 0$, so $y^T A_N \geq c_N^T$.
Combining the two you get $A^Ty \geq c$.