English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (2): 121-126.

• 运筹学 • 上一篇    

基于部分基变量的LP问题矩阵算法

周康1，陈金1，邱江1，解智1   

  1. 1. 武汉工业学院数学与计算机学院，武汉，430023
  • 收稿日期:2011-03-23 修回日期:2011-11-15 出版日期:2012-06-15 发布日期:2012-06-15
  • 通讯作者: 周康 E-mail:zhoukang_wh@yahoo.com.cn
  • 基金资助:

    国家自然科学基金项目(No:61179032); 湖北省教育厅科学技术研究项目(重点)(No:D20111702); 湖北省自然科学基金项目(No:2011CDB229); 湖北省建设厅建设科技计划项目(No:2011-29); 湖北省教育科学"十一五"规划课题项目(No:2010B290); 住房和城乡建设部研究开发项目(No. 2012-K5-9)

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

PDF

1148

被引次数

4

摘要： 基于部分基变量提出了LP问题的矩阵算法. 该算法以最优基矩阵的一个充分必要条件为基础，首先将一个初始矩阵转化为右端项和检验数均满足要求的矩阵，再转为检验数满足要求的基矩阵，最后转化为最优基矩阵.该算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现的优势.矩阵算法的核心运算是求逆矩阵的运算，提出了矩阵算法的求逆问题，讨论并给出了求逆快速算法，该算法充分利用了矩阵算法迭代过程中提供的原来的逆矩阵的信息经过简单的变换得到新的逆矩阵，该算法比直接求逆法计算效率更高.

关键词: LP问题, 矩阵算法, 部分基变量, 最优基矩阵, 求逆快速算法

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