On use of assignment algorithms to reconstruct inverse matrices

G. I. Zabinyako

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, RUSSIA

Abstract: We consider the questions of reconstruction for the matrices inverse to the basis matrices of the revised simplex method. In order to choose the indices of pivots we use certain rules to form an auxiliary matrix from the basis matrix. The list of pivots results from solving assignment problems for the auxiliary matrix. On numerical examples of high dimension we analyze the efficiency of algorithms for solving assignment problems.

Keywords: revised simplex method, sparse matrices, assignment problems.

UDC: 519.852.6

Received: 22.07.2010

Bibliographic databases:

•