A simplex algorithm for a class of Leontief flow problems

P. H. Ng, D. K. Wagner

    Research output: Contribution to journalArticlepeer-review

    1 Scopus citations

    Abstract

    A matrix N is Leontief if it has exactly one positive entry per column and there exists a nonnegative x such that Nx > 0. A Leontief flow problem is a linear-programming problem of the form min{c(T)x | Nx = b;x ≤ 0}, where N is a certain type of Leontief matrix. It is shown that for b > 0 this problem can be solved in O(n2Ulog npU) pivots by the simplex method using Dantzig's rule for choosing the entering variable, where n is the number of variables, p is the largest entry of N in absolute value, and U is a valid upper bound on any extreme-point solution. Classes of problems where this is a strongly polynomial bound axe identified.

    Original languageEnglish (US)
    Pages (from-to)69-75
    Number of pages7
    JournalMathematical and Computer Modelling
    Volume24
    Issue number7
    DOIs
    StatePublished - Oct 1996

    Keywords

    • Computational complexity
    • Leontief matrices
    • Linear programming
    • Network flows
    • Simplex algorithm

    Fingerprint Dive into the research topics of 'A simplex algorithm for a class of Leontief flow problems'. Together they form a unique fingerprint.

    Cite this