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.

A simplex dictionary expresses the basic variables and the objective as affine functions of the nonbasic variables in a linear program. Setting the nonbasic variables to zero gives a basic feasible solution when all basic values are nonnegative. A simplex algorithm pivot exchanges one basic and one nonbasic variable. For maximization, a feasible dictionary with all nonbasic objective coefficients nonpositive certifies optimality.