Revised simplex method

Problem formulation

For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:

where A ∈ R^m×n. Without loss of generality, it is assumed that the constraint matrix A has full row rank and that the problem is feasible, i.e., there is at least one x ≥ 0 such that Ax = b. If A is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

Optimality conditions

For linear programming, the Karush–Kuhn–Tucker conditions are both necessary and sufficient for optimality. The KKT conditions of a linear programming problem in the standard form is

where λ and s are the Lagrange multipliers associated with the constraints Ax = b and x ≥ 0, respectively. The last condition, which is equivalent to s_ix_i = 0 for all 1 < i < n, is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex x of the feasible polytope can be identified by being a basis B of A chosen from the latter's columns. Since A has full rank, B is nonsingular. Without loss of generality, assume that A = [B N]. Then x is given by

where x_B ≥ 0. Partition c and s accordingly into

To satisfy the complementary slackness condition, let s_B = 0. It follows that

which implies that

If s_N ≥ 0 at this point, the KKT conditions are satisfied, and thus x is optimal.

Pivot operation

If the KKT conditions are violated, a pivot operation consisting of introducing a column of N into the basis at the expense of an existing column in B is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in c^Tx. Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.

Select an index m < q ≤ n such that s_q < 0 as the entering index. The corresponding column of A, A_q, will be moved into the basis, and x_q will be allowed to increase from zero. It can be shown that

i.e., every unit increase in x_q will results in a decrease by −s_q in c^Tx. Since

x_B must be correspondingly decreased by Δx_B = B⁻¹A_qx_q subject to x_B − Δx_B ≥ 0. Let d = B⁻¹A_q. If d ≤ 0, no matter how much x_q is increased, x_B − Δx_B will stay nonnegative. Hence, c^Tx can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index p = argmin_1≤i≤m {x_i/d_i | d_i > 0} as the leaving index. This choice effectively increases x_q from zero until x_p is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing A_p with A_q in the basis.

Numerical example

Consider a linear program where

Let

initially, which corresponds to a feasible vertex x = [0 0 0 10 15]^T. At this moment,

Choose q = 3 as the entering index. Then d = [1 3]^T, which means a unit increase in x₃ will results in x₄ and x₅ being decreased by 1 and 3, respectively. Therefore, x₃ is increased to 5, at which point x₅ is reduced to zero, and p = 5 becomes the leaving index.

After the pivot operation,

Correspondingly,

A positive s_N indicates that x is now optimal.

Degeneracy

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in c^Tx, and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.

Basis representation

Two types of linear systems involving B are present in the revised simplex method:

Instead of refactorizing B, usually an LU factorization is directly updated after each pivot operation, for which purpose there exist several strategies such as the Forrest−Tomlin and Bartels−Golub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.