The dependency diagram of a linear programme

H. Paul Williams

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: The Dependency Diagram of a Linear Programme (LP) shows how the successive inequalities of an LP depend on former inequalities, when variables are projected out by Fourier–Motzkin Elimination. It is also explained how redundant inequalities can be removed, using the method attributed to Chernikov and to Kohler. Some new results are given. The procedure also leads to a transparent explanation of Farkas’ Lemma, LP Duality, the dual form of Caratheodory’s Theorem as well as generating all vertices and extreme rays of the Dual Polytope.

Keywords: linear programming; projection; Fourier–Motzkin Elimination (search for similar items in EconPapers)
JEL-codes: J50 (search for similar items in EconPapers)
Date: 2015-09-16
References: View complete reference list from CitEc
Citations:

Published in Journal of the Operational Research Society, 16, September, 2015, 67(3), pp. 450-456. ISSN: 0160-5682

Downloads: (external link)
http://eprints.lse.ac.uk/65979/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:65979

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().