Dual simplex algorithm

The dual simplex algorithm keeps the objective row dual feasible while repairing negative basic values. In a maximization dictionary $x_B=b+{\sum }_j{a}_j{x}_j$ with $b<0$ and nonbasic objective coefficients $d_j\le 0$, eligible entering columns have $a_j>0$; choose one minimizing $(-d_j)/a_j$. The pivot restores progress toward primal feasibility without losing the objective bound.