In mathematical optimization, the revised simplex method is a variant of George Dantzig's simplex method for linear programming. The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a basis of the matrix representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.
Problem formulation For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:
minimize c T x subject to A x = b , x ≥ 0 {\displaystyle {\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}}
where A ∈ ℝ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.
Algorithmic description
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
A x = b , A T λ + s = c , x ≥ 0 , s ≥ 0 , s T x = 0 {\displaystyle {\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}}
where λ and s are the Lagrange multipliers associated with the constraints Ax = b and x ≥ 0, respectively. The last condition, which is equivalent to sixi = 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
x = [ x B x N ] = [ B − 1 b 0 ] {\displaystyle {\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}}
where xB ≥ 0. Partition c and s accordingly into
… excerpt ends here. Continue reading the full article.
