Simplex algorithm

Remarks

Feasible basic solutions are exactly the vertices of the feasible region, and several bases can give the same vertex when it is degenerate. One step moves along an edge to an adjacent vertex, or stays at the same vertex in a degenerate step, and it never decreases $c^T x$. With an anti-cycling choice of $j$ and $i$, such as Bland's rule of taking the smallest eligible index, the algorithm stops after finitely many steps.

Example: maximize $x_1 + x_2$ subject to $x_1 + 2x_2 + s_1 = 4$, $3x_1 + x_2 + s_2 = 6$ and all variables $\ge 0$. Start with $B = \set{s_1, s_2}$, the point $x_1 = x_2 = 0$; both reduced costs are $1$. Let $x_1$ enter; then $d = (1, 3)$, the ratios are $4$ and $2$, so $s_2$ leaves, giving $x_1 = 2$, $s_1 = 2$ and value $2$. Now $x_2$ has reduced cost $2/3$; it enters, the ratio test removes $s_1$, and the new point is $x_1 = 8/5$, $x_2 = 6/5$. There the objective equals $14/5 - \frac25 s_1 - \frac15 s_2$, so all reduced costs are negative and $14/5$ is optimal.

Non-example: in the first step, letting $s_1$ leave instead of $s_2$ ignores the ratio test. It gives $x_1 = 4$ and $s_2 = 6 - 12 = -6 < 0$, which is not a feasible basis.

A first feasible basis can be found by solving an auxiliary linear program, the phase one problem.