The simplex method solves a standard-form linear program by changing a simplex basis. A feasible basis expresses basic coordinates and the objective in terms of nonnegative nonbasic variables. An improving reduced cost selects a candidate entering variable, and the simplex ratio test chooses the largest step preserving nonnegative basic coordinates.
If this step is positive, the objective improves along an edge. Under degeneracy in linear programming, the step can be zero: the basis changes while the basic feasible solution and objective remain fixed. A negative reduced cost alone therefore does not promise strict improvement in that pivot. If the improving direction has no finite ratio limit, it gives an unbounded feasible ray.
When all reduced costs have the optimal sign, the simplex optimality criterion proves global optimality. Two-phase simplex supplies an initial feasible basis or an infeasibility certificate. A rule such as the Bland pivoting rule prevents cycling; arbitrary improving pivot choices need not terminate, and even terminating rules can require exponentially many steps on a Klee-Minty cube.
New to topics? Read the docs here!