Yugoslav Journal of Operations Research 2012 Volume 22, Issue 1, Pages: 107-114
Full text ( 216 KB)

A slight modification of the first phase of the simplex algorithm

Divnić Tomica, Pavlović Ljiljana

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.

Keywords: linear programming, simplex algorithm, canonical form, two phase simplex algorithm, new first phase simplex algorithm