A Phase-I Algorithm For The Basis Deficiency Perturbation Dual Simplex Method

Perturbation algorithms proposed by Professor Ping-Qi Pan (1999,2000) can start with any basis, without introducing any artificial variables, related two-Phase algorithms are favorable in preliminary computational experiments. In order to overcome computational difficulties yielding from degeneracy, recently he introduced a new concept-deficient basis, and established deficient-basis simplex algorithms. Tests showed that these algorithms reduce advent effects of degeneracy, and low total number of iterations and running time.The purpose of this thesis is to combine the perturbation algorithm and deficient-basis algorithm to bring the advantages of the two types of algorithms into full play, consequenly offer a new Phase-1 procedure for the dual deficient-basis algorithm, and overcome the dificulties from degeneracy to a higher extent. Our computational experiments show that the proposed algorithms reduce total number of iterations significantly. New algorithms's efficiency is superior not only to the conventional simplex algorithm but the deficient-basis algorithm. So this is a very attractive new approach being full of promise.