Polynomial Methods in Linear Programming

F. P. Vasilyev and A. Yu. Ivanitskiy
Additional contact information
F. P. Vasilyev: Moscow State University
A. Yu. Ivanitskiy: Chuvash State University

Chapter Chapter 6 in In-Depth Analysis of Linear Programming, 2001, pp 229-293 from Springer

Abstract: Abstract As we have shown, the simplex method refers to the so-called finite methods which allow one to find a solution for any problem of linear programming or to prove its unsolvability performing a finite number of elementary operations (addition, subtraction, multiplication, division, comparison of two real numbers). It stands to reason that the number of operations depends on the dimension (n, m) of the problem (n is the number of variables, m is the number of equality and inequality constraints). The practice of solving linear programming problems has shown that the simplex method and its modifications are very effective. It is accepted as a fact that in the majority of linear programming problems the number of elementary operations which are necessary for their solution is of the order O(n 2 m + m 2 n) [1, 91]. Here and in the sequel we denote by O(a) the quantities for which |O(a)| ≤ C(a), where C is a positive constant independent of a. We have found out that there exist “poor” linear programming problems in which the amount of elementary operations required for their solution by the simplex method is estimated by the number which exponentially depends on n and m.

Keywords: Linear Programming Problem; Simplex Method; Elementary Operation; Polynomial Method; Vertex Point (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-94-015-9759-3_6

Ordering information: This item can be ordered from
http://www.springer.com/9789401597593

DOI: 10.1007/978-94-015-9759-3_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().