Dual simplex method for GUB problems

DOI10.1007/BF00940817MaRDI QIDQ790706zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1985

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00940817

zbMATH Keywords

dual simplex methodgeneralized upper boundratio testrow update formula

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

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.

Recommendations

• Dual simplex algorithm with implicit representation of variable upper bounds
• A generalized dual phase-2 simplex algorithm.
• A practical guide to the dual theorem
• The long step rule in the bounded-variable dual simplex method: Numerical experiments
• Implementation of a Double-Basis Simplex Method for the General Linear Programming Problem

Cited in

(1)

• Computational study of the GDPO dual phase-1 algorithm

This page was built for publication: Dual simplex method for GUB problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790706)