= Dual feasibility
{title2=$A^Ty\leq c$}
For minimization with constraints $Ax=b$, $x\geq0$, a dual-feasible vector $y$ obeys $A^Ty\leq c$, so $b^Ty$ 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^TB^{-1}$. Its basic reduced costs are zero and its nonbasic reduced costs are $c_N^T-c_B^TB^{-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>.
Back to article page
