G.B.Dantzig于1947年开创的线性规划理论及其单纯形算法,是影响最深远和应用最广泛的数学工具之一.它在国民经济、科学技术、管理和工程等诸多领域有着广泛的应用.在线性规划诸算法中,G.B.Dantzig的单纯形算法,Khachiyan的椭球算法以及Karmarkar的内点算法可谓为三大里程碑.本文的贡献主要在线性规划的主元算法这一领域,包括以下内容:一.在潘平奇教授提出的亏基理论的框架下,本文首次将亏基理论推广到带有界约束的线性规划求解,建立了有界变量单纯形算法的理论基础.在亏基单纯形算法的基础上,进一步提出了亏基有界变量线性规划单纯形算法,证明了算法的收敛性,并建立了一个相应的简洁的一阶段算法.二.在亏基概念及最钝角规则的基础上,本文利用最钝角法则,在亏基的框架下建立了一个新的求原始可行解的一阶段单纯形算法.由于亏基的引入,在很大的程度上克服了退化带来的困难;而最钝角法则的应用,则使我们能每次简单地选取恰当的变量进基,从而使新算法具有简单易行且计算量小的特点.三.Criss-cross算法的主要优点是其简洁优美.它可从任一个基本解开始,仅用一个阶段在有限步内就可求解一般线性规划问题,且求解的过程具有对称性.但可惜其实际计算效率不高.本文提出一种新的有限的criss-cross算法,利用重排下标的技巧,一方面保持了criss-cross算法原有的优点,另一方面提高了计算效率.同时,新算法的有限性也得到了证明.四.线性规划的主元算法(如单纯形算法)最后可以到达一个精确的最优解,但在计算过程中会受到退化现象的严重干扰.内点法虽没有这个缺陷,但通常只能产生一个∈最优解.要获得精确最优解,必须要有一个计算量不小的所谓的纯化过程.本文将内点算法与主元算法的技巧有机的结合起来,建立了一个混合算法.该算法具有两者的优点.它不仅克服了退化现象带来的困难,还可获得一对精确的原始与对偶的最优解.五.潘平奇教授提出的求解线性规划的射影单纯形算法,尽管在实践中非常有效,却仍然没有完全摆脱由于退化而带来的停顿现象.本文提出一个修正的射影单纯形算法.在确定搜索方向时,求解一个增广的最小二乘问题,从而完全避免了退化的影响,在不做任何非退化假设的前提下证明了算法的有限性.六.本文就一些国内外学者所提出的线性规划新算法给出了若干反例.