An improved general Phase-I method in linear programming (Q1107440)

Problems of finding a feasible basic solution in linear programming are studied. The feasible range of the problem is determined by the conditions: \(Ax=b\), \(bu_ i\leq x_ i\leq b\ell_ i\) \((i=1,...,n)\), where A is an (m,n)-matrix with rank m; x and b are corresponding vectors. Various schemes and algorithms based on the Maros' method are suggested. It is shown theoretically and computationally that the efficiency of these schemes can be significant.