Revised Simplex Variants of the Primal and Dual Simplex Methods and Sensitivity Analysis

Katta G. Murty ()
Additional contact information
Katta G. Murty: University of Michigan

Chapter Chapter 6 in Optimization for Decision Making, 2010, pp 297-392 from Springer

Abstract: Abstract Consider an LP in standard form in n nonnegative variables subject to m equality constraints that the variables are required to satisfy, in which we assume that the rank of the coefficient matrix is m, without any loss of generality. So, n ≥ m. In LP models to be solved in practice, typically n will be much larger than m. The original form of the primal simplex method developed in 1947, discussed in LP textbooks (e.g., see Chap. 4 of Murty (2005b) of Chap. 1), is a wonderful educational tool to explain the principles behind the method to beginners. Starting with a primal feasible basic vector, this method goes through a series of steps, in each step one GJ pivot step is carried out to replace one basic variable in the basic vector by a specially selected nonbasic variable. All the work in a step of this method is also discussed in our Sects. 4.9 and 4.12. But as a computational method for solving LP models in practice, this original form of the primal simplex method is highly inefficient as it updates every one of the n + 1 column vectors in the canonical tableau in every pivot step to solve the LP under consideration. In this chapter, we will discuss the much more efficient revised simplex variants of the primal simplex method that are based on the same fundamental theory, but in these variants we only need to update a smaller number, m + 2, column vectors of the basis inverse in every pivot step. We will discuss several of the early (developed in 1950s and 1960s) variants of this method to describe the ideas used to make the simplex method a practically valuable tool to solve LP models in decision making.

Date: 2010
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:isochp:978-1-4419-1291-6_6

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

DOI: 10.1007/978-1-4419-1291-6_6

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().