线性规划是运筹学中研究较早、发展较快、应用广泛的一个重要分支,它是辅助人们进行科学管理的一种数学方法。线形规划是在满足线性约束下实现目标值最优的数学理论和方法。目前线性规划已经广泛应用军事、经济、管理、工程等方面,为决策者在有限的人力、物力、财力的情况下做出决策提供可靠的科学依据。因此,如何更快并准确的计算线性规划问题成为一个很有吸引力的,也很有必要的课题。1947年,G.B.Dantzig首次提出了求解线性规划问题的单纯形算法。单纯形算法由于其规则简便,且能很好的解决线性规划问题,成为了线性规划问题的经典算法。自此之后,线性规划问题的算法大致可以分为两类:一类是传统的沿着可行域的可行边方向前进,从一个极点到邻接的另一个极点,最终得到规划问题的最优解;另一类则是不按照传统的迭代方法,即不严格的按照可行下降(上升)边方向迭代,而是从可行域的内部或者外部行进,而多数的算法是选择从可行区域内部行进,从而最终找到最优解。在第一类算法中,主要的工作是主元的选择规则上,目前得到较多认可的除了单纯形算法的主元规则,还有基于最钝角的选主元规则,以及最陡边的列主元规则。而在第二类算法中,主要是通过选择不同于可行下降(上升)边方向的可行方向来实现可行域的内部穿越,从而最终实现最优解的寻找。这类算法对于求解大规模的线性规划问题有着一定的优势,因为该类算法往往能够避开很多极点,从而减少迭代次数,但内点法一旦问题即将达到最优解时,将显示出其收敛速度慢的劣势,而第一类的单纯形算法却在初期的迭代中耗费太长时间。本文将要描述的算法是一种基于组合方向的算法,该算法从一个极点出发,通过一个组合方向,使该基本可行解迭代到可行域的一个高维界面,然后通过纯化过程(即通过降维),使该高维界面上的可行解逐渐迭代成一个基本可行解,如此反复使最后得到的基本可行解满足最优解的判定标准,这样也就得到了一个最优解。使用该类算法即能够减少迭代次数,同时尽可能的规避内点法的一些弱点,如后期迭代收敛速度过低的情况。而针对线性问题规模扩大后,极有可能出现退化产生的停驻现象,引入潘平奇教授的亏基思想,并提出了基于组合方向的亏基单纯形算法;同时基于对组合方向的考虑,提出了基于组合方向的对偶单纯形算法。