On improvement of Reid’s basis updating method for large sparse linear programming problems

This paper intends to investigate some inherent characteristics of Reid’s basis updating method (Reid method) for linear programming problems and to improve an efficiency of the method. Reid method is explained in detail and then seven lemmas concerned in its characteristics are clarified. An improved basis updating method (improved Reid method) is developed by making good use of its characteristics. A theorem which indicates differences of efficiency between Reid method and improved Reid method is proved. An example which was already used in Reid’s paper is taken up to consider a validity of improved Reid method. Some computational experiments using random linear programming problems are also made for the same purpose. As a result, it is confirmed that improved Reid method is better than Reid method concerned in the efficiency of basis updating procedure. [In Japanese.]