
Accession Number : ADA181498
Title : The Equivalence of Dantzig's SelfDual 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 selfdual 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 correctspecifically 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