tailieunhanh - A slight modification of the first phase of the simplex algorithm

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, ., 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. | Yugoslav Journal of Operations Research 22 (2012), Number 1, 107-114 DOI: A SLIGHT MODIFICATION OF THE FIRST PHASE OF THE SIMPLEX ALGORITHM T. DIVNIĆ, Lj. PAVLOVIĆ Faculty of Science, Department of Mathematics, University of Kragujevac, Serbia tomadivnic@, pavlovic@ Received: June 2010 / Accepted: March 2012 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, ., 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. Keywords: Linear programming, simplex algorithm, canonical form, two phase simplex algorithm, new first phase simplex algorithm. MSC: 90C05 1. INTRODUCTION Let us consider the linear programming problem min ∑ nj =1 c j x j + z0 ∑ a x j = bi , n j =1 i , j x j ≥ 0, i = 1,., m (1) j = 1,., n where A = ( ai , j ) mxn is a given matrix, b ∈ R m and c ∈ R n are given vectors. Without loss of generality, we assume that rank A = m . The problem can be presented in the form of a table T. Divnic, Lj. Pavlovic / A Slight Modification of the First Phase 108 − z0 c1 c2 b1 a1,1 a1,2 b2 a2,1 a2,2 M bm M am,1 M am ,2 cn K K a1,n a2,n L O L M am , n having m + 1 rows and n + 1 columns. It is called the linear programming table (LP). We denote and c j = a0, j , j = 1,., n, bi = ai ,0 , i = 1,., m and z0 = a0,0 . Recall that we can apply the simplex algorithm to problem (1) when the corresponding table is a simplex table (ST), that is, it has m different basic columns A. j = (a0, j , a1, j ,., am, j ) =