李东方
广州工商学院基础教学部 （广东 佛山 三水 528138）
摘要：本文通过近年来对求线性规划初始可行基的一些常规方法和的主要研究成果，进行归纳、简介和总结，并加以类比以及分析，给出各种方法的优势与不足．以便读者在解决具体问题时，根据所探讨问题的实际情况，找出相应的方法，以使达到方便解决所研究的问题．
关键词：线性规划；初始可行基；单纯形法；解法
1. 近年来求线性规划初始可行基的一些方法
[1] 外点法：外点法的基本原理：外点法具体作法是在可行域L 的外部先选出一个点，一般选原点，然后按照一定的准则在可行域的外部进行迭代，每次迭代得到一个新外点，该点更靠近可行域的某个顶点，如此继续，直到在某一时刻达到可行域的某个顶点即单纯形法中的初始基本可行解为止．
外点法步骤：1)写出约束条件中的线性方程组的增广矩阵形式；2)找出系数矩阵中形成单位矩阵的子矩阵的列向量所对应的变量为基变量，其余变量为非基变量得初始点，若中无单位矩阵的子矩阵，则取原点为初始点；3)设外点处无基变量的行指标集为G，非基变量的下标集为H ，若，停止运算，否则转；4)求，再求以为主元素进行旋转运算得到新矩阵，相应得到新外点，若与在同一行即相同，则，数量不变，但距离变小了，否则比 多一个基变量，，的数目也相应减少，如此继续，直到运算结束，此时即为所求的初始基本可行解[5] ．
[2] 最小比值旋转迭代法：最小比值旋转迭代法的基本原理：利用最小比值规则在全局范围内（不包括基变量所在行）选取主元．
最小比值旋转迭代法的计算步骤：1）建立的初始旋转迭代表；2）在表中若存在一行，对于所有的有且或者所有的j均有但另有，则问题无可行解，停止计算；3）考察所有正数项，利用最小比值规则，确定主元素．以为主元作旋转迭代的运算；4）如果还没有得到一个可行基，则考察 下方出现的基变量所在行以外的所有数，转入2）：如果得到一个可行基，则以下按单纯形法计算检验数，并求最优解[4]．
[3] 初等变换法：初等变换法的基本原理：找出个基变量的方法是：对线性方程组的增广矩阵做行初等变换．在座行初等变换的过程中，由于每一步要求常数项皆为非负，因而对行的初等变换有所限制，这是问题的关键．
初等变换法算法：1)在增广矩阵中，用所有变量的正系数分别去除所在行的常系数，比值最小值的除数作为主元，并用方框框上；2)对单纯形矩阵作行初等变换：以主元所在行作为基准行，先将主元化为1，再将主元所在列其余主元化为0．于是把主元为系数的变量作基变量；3)在新的增广矩阵中，去掉主元所在列，用所有变量的正系数分别去除所在行的常数项，若比值最小者的除数与原主元不在同一行，则比值最小者的除数作为新主元，也用方框框上，并重复2的算法，把以新主元为系数的变量也选作基变量：若比值最小值的除数于主元在同一行，则去掉比值最小者的除数所在列，继续运用上述做法寻求新主元．
重复上述步骤，如果找出位于不同行的个主元，则得到由个相应基变量构成的初始可行变量构成的初始可行基，则不存在初始可行解：如果找不到位于不同行的个主元，即得不到个基变量，则不存在初始可行基，说明线性规划问题无初始可行解．[3]—[16]
[4] 预备表法：预备表法的基本原理：第一部分是对预备表实施行初等变换球第一个可行基，第二部分是在第一张单纯形表上运用单纯形法求最优解．
预备表法算法：1）以增广矩阵为基础建立“第1张预备表”．2）在预备表上实施行次初等变换，直到得到（LP）.的第一个可行基． 3）在第张预备表基础上计算非基变量的检验数，做出单纯形表，然后再按照一定的方法求最优解[2]．
[5] 广义单纯形法: 广义单纯形法的基本原理：从所有列(不包括基变量所在列)作和结果中从左至右选取第一个非负元素为主元．
广义单纯形法的步骤：1）建立初始表，此时列是空的;2）若对于所有的，则转4）：否则转3）．如果存在一些k使得，那么将是一个基变量;3)根据规则确定主元像单纯形的迭代一样对本表迭代一次，返回2）;4）若，此时无可行解，停止运算：若，那么，此时表中将包含个线性无关单位列向量，我们已经获得一个初始可行解，这时，在列对应位置上填写．在这张表中计算，，并将替换为；5）若所有的，得到最优解：否则，若存在，以下按单纯性法计算．[6]—[8]
2. 对以上方法进行比较
以上介绍的五种常用的方法，它们的共同特点是，不需要引入人工变量，并且各有其特色。
外点法的特点：从所有列（不包括基变量所在行）作和中的非负元素中，选出最小的作为主元．而且在求解过程中，可以判断是否有可行解，以及有无穷多解的情况．
最小比值迭代法的特点：不需要引入人工变量，在全局范围内（不包括基变量所在行）选取主元，一进基变量不会出基，迭代次数少．一般比初等变换法有效．
初等变换法的特点：不需要引入人工变量，在全局范围内(不包括基变量所在列)选取主元，己进基变量不会出基，迭代次数少．对于学过线性代数的人来说，该法易懂、易接受．
预备表法的特点：不需要引入人工变量，在选主元时总是从第一列开始，然后按列依次顺序进行，不保证已进基变量不出基，迭代次数较少．
广义单纯形法的特点：不需要引入人工变量，它的主元是从所有列(不包括基变量所在列)作和结果中从左至右选取第一个非负元素，不保证已进基变量不出基，可以在解题过程中判断问题是否有可行解．
综上所述，介绍的这五种方法是对常规方法的一个重要的补充，在解现实中的线型规划问题时，其发挥的作用尤为突出，使得一些常规方法虽能解决，但在数值计算方面增大数值计算量或增加计算机存储量的问题得以解决．
参考文献
[1] 李东方.求解线性规划初始可行基的常规算法.
[2] 杨富贵,梁邦助.求线性规划初始基本可行解的一种直接方法[J],天津商学学报,2002(03):21-25.
[3]周誓达.线性规划问题求初始可行基一种新的解法[J],首都师范大学学报,1996(04):11-15.
[4]曹细玉.求解线性规划问题的新方法及影子价格[J],华中师范大学学报,2000(01):4-8.
[5]孟俊婷.求单纯形法中初始基本可行解的新方法-外点法[J],内蒙古科技与经济,2000(02):39-241.
[6]肖蓬.求第一个可行基的一种不同的方法[J],福建师范大学学报,2002(02):20-23.
[7]王章雄,陈耀辉.线性规划初始基可行解的一种直接算法[J],数学杂志,1996(02):217-222.
[8]吴延东.求线性规划问题可行基的一种方法[J],运筹与管理,1999(01):41-45.
[9]孙可钦.寻求线性规划初始可行基的一种新算法[J],云南师范大学学报,1999(04):17-20.
[10]严文利.一类线性规划问题初始可行基产生的新方法[J],运筹与管理,2001(02):79-85.