Dual simplex method for GUB problems
type: Item
instance of: scholarly article
title: Dual simplex method for GUB problems
zbMATH Open document ID: 0534.90057
DOI: 10.1007/BF00940817
author: N. E. Zubov
published in: Journal of Optimization Theory and Applications
publication date: 1985-01-01T00:00:00Z
review text: 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. Those updated elements are used for the ratio test to determine the entering basic. 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3848966
zbMATH Keywords: row update formula
zbMATH Keywords: dual simplex method
zbMATH Keywords: generalized upper bound
zbMATH Keywords: ratio test
MaRDI profile type: Publication
cites work: Q3844775
cites work: Q5630824
description: scientific article; zbMATH DE number 3848966