A slight modification of the first phase of the simplex algorithm

Abstract

In this paper we give a modification of the first phase procedure for transforming the linear programming problem, given in the standard form to the canonical form, i.e., to the form with one feasible primal basis where standard simplex algorithm can be applied directly. The main idea of the paper is to avoid adding m artificial variables in the first phase. Instead, Step 2 of the proposed algorithm transforms the problem to the form with m-1 basic columns. Step 3 is then iterated until the m-th basic column is obtained, or it is concluded that the feasible set of LP problem is empty.