On the existence of a short pivoting sequence for a linear program

• We show that given a feasible primal–dual pair of linear programs in canonical form, there exists a sequence of pivots, whose length is bounded by the minimum dimension of the constraint matrix, leading from the origin to the optimum. The sequence of pivots give a sequence of square and nonsingular submatrices of the constraint matrix. Solving two linear equations involving such a submatrix give primal–dual optimal solutions to the corresponding linear program in canonical form.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Linear program

Pivoting method

Short sequence of pivots

Matrix algebra

Canonical form

Dual pairs

Linear programs

Nonsingular

Optimal solutions

Sub-matrices

Submatrix

Linear programming

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)