Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (2): 121-126.

• Original Articles • Previous Articles    

Matrix Algorithm for LP Problem Based on Partial Basic Variables

 ZHOU  Kang1, CHEN  Jin1, QIU  Jiang1, XIE  Zhi1   

  1. 1. School of Math and Computer, Wuhan Polytechnic University, Wuhan 430023, China
  • Received:2011-03-23 Revised:2011-11-15 Online:2012-06-15 Published:2012-06-15

Abstract: Matrix algorithm for LP problem based on partial basic variables is put forward, which is based on a necessary and sufficient condition of optimal basic matrix.  At first the initial matrix of algorithm is transformed into the matrix meeting the requirements of   right-constant and test number; then the matrix is transformed into basic matrix meeting the requirements   of test number; finally the matrix is transformed into optimal basic matrix. Matrix algorithm has the  advantages of wide usage, small calculation scale, simplified calculation process, easy realization and    so on. The operation of finding inverse matrix is the key operation of matrix algorithm, so finding     inverse matrix problem of matrix algorithm is put forward, and a fast algorithm finding inverse matrix is discussed and given. The fast algorithm can find inverse matrix by utilizing inverse    matrix in the last iteration. The computational efficiency of the fast algorithm is higher than   that of direct inversion method.

Key words: linear programming problem (LP problem), matrix algorithm, partial basic variables, optimal basic matrix, fast algorithm finding inverse matrix