李东方
广州工商学院基础教学部 （广东 佛山 三水 528138）
摘要：本文通过对求线性规划初始可行基的一些常规方法和近年来的主要研究成果进行归纳，简介和总结，并加以比较，给出各种方法的优势与不足．以便读者在解决具体问题时根据自身的实际情况，找出相应的方法，以使达到方便解决所研究的问题．
关键词：线性规划；单纯形法；解法
1. 求线性规划初始可行基的一些的常规算法
[1] 单纯形法：单纯形解法最初是在20世纪40年代由George Dantzig研究出来的．它的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则来判断这个基可行解是否是最
优解，如果不是最优解,则转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解．
单纯形法是求解线性规划最基本，最常用的方法，通常情况下，大多数的线性规划问题都可以得以解决。但不足之处在于单纯形法必须在己知一个基本可行解(初始点)既线性规划的约束方程为G-J方程组的前提下才能进行求解．然而在大多数情况下，线性规划问题并没有明显的初始基本可行解，于是，很多人就提出了多种新的解决思路，给出了求初始基本可行解的许多算法，这些算法各有所长所短．归纳起来，具有代表性的是下面介绍的几种。
[2] 大M法：此方法系在目标函数中，加上人工变元与一个很大很大的正数M的积（此称罚函数），这样，当基本可行解中人工变元非0时，此人工变元项将是一个大数，因它在目标函数中被加上，从而此解不可能最优（注意目标函数求极小）．
换言之，在迭代中，人工变元会很快出基．
说明：若原来的问题为（Ⅰ），而用大M法构造的新方法为（Ⅱ），则（1）设（Ⅱ）有最优解，其中为人工变元：若，则问题（Ⅰ）有最优解;若，则问题无解．（2）设（Ⅱ）有无界解：若，则问题（Ⅰ）也有无界解;若，则问题（Ⅰ）无解．
还有一点要说明的是：在实际运算中（计算机程序）大M法里的M需适当赋值，若M赋值过大，则容易引起计算误差：而M赋值过小，则影响求解过程的实施．
[3] 两阶段法：对一般的线性规划，往往很难找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划．二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空：第二阶段在得到的基可行解基础上求解原问题．
方法如下：第一阶段：人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和．该线性规划一定有最优解，设为：．则可能有三种情形：1）若：在最优解的基变量中，不存在人工变量，即人工变量都是非基变量．则的前个分量便是（LP）的一个基可行解．可进入第二阶段；2）若：在最优解的基变量中，包括某些人工变量，并且最优值．则（LP）的可行域为空，（LP）无解；3）若在最优解的基变量中，包括某些人工变量，但最优值，此时为基变量的人工变量都取值为0．设是一个人工变量的基变量，其在最优解的单纯形表中对应第行，设是非人工变量中非基变量的下标集．如果单纯形表的第行中，所有的，()此示原约束中第行为其余行的线性组合，即是个多余的约束，应当删去；如果存在()，则无论是正还是负，以它为变换轴心，进基，离基．如果新表中的基变量中还有人工变量，重复以上步骤，有限次可得到1）的情形．
第二阶段：1）以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零；2）以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划；通常认为，上述两方法相比较，手算时大M法比两阶段法简单，但在编制计算机程序时，由于大M法的赋值成了制约该方法的障碍（赋值太大，引起大误差，太小起不到惩罚作用）．
若把大M法中的M视为参数，另在求解过程中把检验数向量分成两部分（且把M看成一个大数），先来考虑人工变元的影响，则大M法实际上已化为两阶段法了．
[4] Khachyian多项式算法：该算法又称椭球算法，它是在原苏联学者肖尔关于非线性规划椭球算法基础上提出来的．Khachyian算法可求解线性不等式方程组：，其中是矩阵，和是列向量．没有任何非负约束，也不存在在任何限定的极大化或极小化目标函数，因此，首要的问题是把线性规划问题转换为等价的与（LP）有相同解的不等式方程组，两者都有相同的解．
第一步迭代时，以原点为球心，取一个较大的正数为半径（把所有的可行点包括在内）得到一个超球面围成的可行域，选定的被违反的约束方程．超平面通过当前中心原点，与第一个约束的平面平行，割去初始的左半部分．新的椭球体积变小但包含了留下的右半椭球及可行域．重复迭代，直到椭球中心点收敛于可行域．[1]
[5] Karmarkar多项式算法：1984年Karmarkar提出了解LP问题的另一个由多项式时间的算法．从理论上讲，Karmarkar算法比Khachyian算法的阶有所降低，实算效果也较好．
它的基本思想是：不沿可行域多面体（如单纯形法那样）搜索，而是直接穿过多面体每部的某个点开始（解）．
Karmarkar算法每次迭代次数上界是(nl)，这里l是问题的输入规模（问题转换成数码0，1的个数）：此外算法中变换了系数矩阵，运用矩阵计算技巧，使每步迭代（矩阵求逆）的计算是约为()，从而使总算法时间复杂性为（）．
此方法的完善与改进，极为人们所关注，且有许多新的方法派生：．投影方法；．仿射均衡尺度法；．路径跟踪法；．仿射均衡势函数方法等．[3]
参考文献
[1] 杨富贵,梁邦助.求线性规划初始基本可行解的一种直接方法[J],天津商学学报,2002(03):21-25.
[2]吴振奎.运筹学[M].北京:中国人民大学出版社,2005:37-46.
[3]于庆年,王晓辉.用预备表法寻找线性规划问题第一可行基[J],丹东师专学报,1995(03):8-10.
[4]周誓达.线性规划问题求初始可行基一种新的解法[J],首都师范大学学报,1996(04):11-15.
[5]曹细玉.求解线性规划问题的新方法及影子价格[J],华中师范大学学报,2000(01):4-8.
[6]孟俊婷.求单纯形法中初始基本可行解的新方法-外点法[J],内蒙古科技与经济,2000(02):39-241.
[7]肖蓬.求第一个可行基的一种不同的方法[J],福建师范大学学报,2002(02):20-23.
[8]安中华,周树民,安琼.线性规划初始基本可行解的新算法[J],武汉理工大学学报,2004(07):72-74.
[9]王章雄,陈耀辉.线性规划初始基可行解的一种直接算法[J],数学杂志,1996(02):217-222.
[10]吴延东.求线性规划问题可行基的一种方法[J],运筹与管理,1999(01):41-45.
[11]孙可钦.寻求线性规划初始可行基的一种新算法[J],云南师范大学学报,1999(04):17-20.
[12]严文利.一类线性规划问题初始可行基产生的新方法[J],运筹与管理,2001(02):79-85.