Dual simplex method for GUB problems

J. Matsumoto, L. W. Mays

Research output: Contribution to journalArticlepeer-review


The dual simplex method for generalized upper bound (GUB) problems is presented. One of the major operations in the dual simplex method is to update the elements of the rth row, where r is the index for the leaving basic variable. Those updated elements are used for the ratio test to determine the entering basic variabble. A very simple formula for the rth row update for the dual simplex method for a GUB problem is derived, which is similar to the formula for the standard linear program. This derivation is based on the change key operation, which is to exchange the key column and its counterpart in the nonkey section. The change key operation is possible because of a theorem that guarantees the existence of such a counterpart.

Original languageEnglish (US)
Pages (from-to)113-122
Number of pages10
JournalJournal of Optimization Theory and Applications
Issue number1
StatePublished - Jan 1 1985


  • Generalized upper bounds
  • algorithms
  • dual simplex method

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics


Dive into the research topics of 'Dual simplex method for GUB problems'. Together they form a unique fingerprint.

Cite this