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 min{cTx Ax=b, x≥0}, 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 into 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.