线性规划的算法研究从几何上主要可以分为三种类型:一种是单纯形类算法,即沿着可行域的边界按照一定的旋转规则,从一个顶点(基本可行解)移动到另一个更好的顶点;第二种是内点算法,即迭代路径是在可行域的内部进行。第三种是外点法,即迭代点从可行域的外部收敛到原问题的最优解。沿边界点迭代的经典算法是Dantzig的单纯形算法。1998年,PAN.P.Q创造性的提出了一种全新的算法—亏基单纯形算法,该算法拓展了基的概念,不再要求基为方阵。在此基础上,本文提出了一种求解线性规划问题的亏基一阶段大M算法,该算法只需要引入一个人工变量,大大的减少了问题的规模,并且在迭代过程中还可以提前判断原问题是否可行,计算实例表明新算法比Dantzig的单纯形在判别原问题可行性时更加有效。此外,通过修改进基变量的规则,提出亏基单纯形算法的改进形式,提高了算法的效率并通过实例进行了验证。内点法是求解线性规划问题的多项式时间算法,主要有三类:Karmarkar投影尺度算法、仿射尺度算法、路径跟踪法。1990年,印度学者V.CH VENKAIAH阐述了一种新的内点算法,该算法每一步迭代都采用同一个投影矩阵,但有反例说明投影矩阵不变的内点算法只能保证收敛到问题的可行解而非最优解。本文通过分析投影矩阵的特点,结合势函数法的思想,构造了一种新的投影矩阵不变的内点算法,该算法可以保证收敛到最优解,实例验证了算法的有效性。基于对数罚函数法的思想,文中提出了一种新的组合方向内点算法。新的组合方向内点算法在每一步迭代中也是组合目标函数的最速下降方向和“对中方向”,但是各方向的权系数是随机变化的而不是固定不变的,其中最速下降方向是投影矩阵不变的内点算法得到的可行下降方向,而对中方向则是通过势函数法得到的,并且新的组合算法的投影矩阵只需要计算一次,从而减少了算法的计算量,提高了算法的效率。初步的实例验证了算法的正确性和有效性。1993年,Konstantinos Paparrizos阐述了一种外点单纯形算法。外点法的两个主要的计算不足之处是:(1)未明确选择一个“好的移动方向”;(2)不知是否存在一条通向可行域内部的路径。而一个“好的移动方向”更多的依赖于对偶初始可行基的选择。对于初始的内点可行解本文主要是通过两阶段投影矩阵不变内点算法求得,而对于对偶可行基对应的正则解,则主要是基于最钝角的思想,构造了对偶一阶段算法,该算法采用了无比值原则来确定出基变量,减少了算法的计算量,最后获得一个较好的对偶可行基对应的正则解,从而得到了一种有效地外点单纯形算法。