The row pivoting method for linear programming

Yanwu Liu, Yan Tu and Zhongzhen Zhang

Omega, 2021, vol. 100, issue C

Abstract: Solving linear programming is essentially to solve a special system of linear inequalities. Unlike other pivoting methods, we find that row geometry can fully and effectively exploit huge potential of Farkas Lemma in solving systems of linear inequalities and is a feasible way to solve linear programming. Therefore, we develop the row pivoting method for solving linear programming. The central idea of this method is to solve a system of linear inequalities corresponding to constraints of linear programming while keeping the optimality condition true all the time. In the proposed method, any linear programming problem can be solved without imposing redundancy or consistency assumptions, equations and inequalities in the constraints can be directly expressed in row vector form free of any auxiliary variables. The method can identify inconsistency and redundancy of constraints inherently, start with an arbitrary basic solution directly, eliminate equation constraints efficiently, and treat lower and upper bounds on any inequality constraint simultaneously. The proof of existence and convergence guarantees that the method can determine whether there exists an optimal solution to linear programming in finitely many steps.

Keywords: The row pivoting method; Linear programming; Farkas lemma (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048320307088
Full text for ScienceDirect subscribers only

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:eee:jomega:v:100:y:2021:i:c:s0305048320307088

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2020.102354

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().