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):

Report Date:

1987-05-01

Pagination or Media Count:

26.0

Abstract:

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

Subject Categories:

  • Operations Research
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE