Accession Number : ADA181498

Title :   The Equivalence of Dantzig's Self-Dual Parametric Algorithm for Linear Programs to Lemke's Algorithm for Linear Complementarity Problems Applied to Linear Programs.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Lustig,Irvin J

PDF Url : ADA181498

Report Date : May 1987

Pagination or Media Count : 26

Abstract : Dantzig has asserted that his self-dual parametric algorithm for solving a linear program is equivalent to Lemke's method for solving a linear complementary problem when the latter is applied to solve a linear program. This paper formally proves that Dantzig's assertion is correct--specifically that the point reached along the solution path after 2t iterations of Lemke's method is identical with the point reached after t iterations of Dantzig's method. Keywords: Linear programming; Lemke's method; Self dual parametric algorithm; Linear complementarity problems.

Descriptors :   *LINEAR PROGRAMMING, ALGORITHMS, PARAMETRIC ANALYSIS, ITERATIONS, PATHS, SOLUTIONS(GENERAL)

Subject Categories : Operations Research
      Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE