 Dual feasibility

For minimization with constraints $Ax=b$, $x\ge 0$, a dual-feasible vector $y$ obeys $A^{T}y\le c$, so $b^{T}y$ is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix $B$, the associated vector is $y^T=c_B^T{B}^{-1}$. Its basic reduced costs are zero and its nonbasic reduced costs are $c_N^T-c_B^T{B}^{-1}{A}_N$. Thus nonnegative reduced costs are exactly dual feasibility in this minimization convention; basic primal values may still be negative, as in the dual simplex algorithm.