一种求解LP问题的两阶段基点迭代转移方法

刘道建　黄天民　陈勇

摘要：利用线性规划的线性、几何平面这一两面性结构特点，定义了LP问题的一种特殊基点转移矩阵及其转移运算，并建立了单纯形基点的定向迭代转移模型，从而提出了一种求解LP问题的两阶段基点定向转移搜索方法.另外，借助新提出的可行域局部ε正则化方法，将退化基点迭代转移转化为非退化基点迭代转移，彻底消除了基点退化对极点转移搜索过程的不利影响.

关键词：线性规划； 基点转移矩阵；退化的；局部正则化；算法

中图分类号：O221.1 文献标识码：A

当今，尽管学术界将LP算法划分成三大类型[1-4]：单纯形类算法、椭球类算法和内点类算法，但它们具有一个共同特征，即均属于迭代算法，根本区别在于迭代方式不同，这也导致了它们在搜索效率上的差异.单纯形类算法的优点在于迭代过程通过 “换基”实现，所以迭代运算均为线性的.缺点是在迭代过程中目标函数值的非严格单调性，当然，出现目标函数值的非严格单调性的内在因素在于退化基点的“一解多基”现象，这一缺陷可能导致迭代过程中的基循环问题.而椭球类算法与内点类算法却恰好相反，它们的优点是在迭代过程中目标函数值的严格单调性，缺点是主要的迭代运算是非线性的，每次迭代的计算量巨大.也正因为这一缺陷，虽然它们是多项式时间的，但实际使用效果并非十分理想，甚至搜索效率还不如单纯形类算法.那么，是否存在迭代运算为线性的，而迭代过程的目标函数值严格单调的LP算法？回答是肯定的，摄动单纯形法[1]就是这样的LP算法.

所谓摄动单纯形法，实为一种先将普通的LP问题转化为无退化现象的LP问题，再利用单纯形法求解的LP算法.从理论上看，摄动单纯形法是一种理想的LP算法，它同时具备上述提到的两个优良特性.然而，在实践中，因为摄动项的添加，相当于要解一个双倍于原LP问题规模的新问题，导致迭代过程的计算量呈爆炸性增长.因此，这种算法的实用性大大降低了.

线性、几何平面特性为线性规划的两大基本结构特性.椭圆类算法、内点类算法都是从非线性规划中移植过来的，属于非线性化方法.自然地，这些算法无法充分反映与利用好线性规划的以上两大结构特性.而传统的单纯形类算法（包括摄动单纯形法）的运算平台是单纯形表，该平台的线性特征十分明显，但几何平面特征明显不足，这也导致了传统单纯形类算法的功能缺陷.

鉴于以上情况，本文欲实现的主要研究目标如下：1）利用线性规划的结构特性，构建更能反映线性规划线性、几何平面这一两面性结构特点的LP新解算模型；2）从分析退化基点的转移机理入手，找到退化基点的转移性缺陷，并制定有效的应对之策；3）在以上两方面研究成果的基础上，提出迭代运算为线性、目标函数值严格单调的LP迭代算法，这也是本文欲达成的最终之研究目标.

1单纯形基点的定向迭代转移模型

至此，通过构建单纯形（包括LP问题的可行域、线性不等式组的解空间）的基点定向转移矩阵，在单纯形的基点与数字矩阵之间建立起了一种对应关系.在矩阵的各功能块中，基解列代表基点，而其方向块的各列代表基点的迭代转移方向（即该超多面体顶点的极方向），强迫性价值系数列代表该基点转移的目标参考方向.本研究的目标之一在于，通过对基点定向转移矩阵的负旋转迭代（等价于基点的迭代转移），最终找到单纯形的一个优化极点.

实际上，依据上述性质1，仅解决了单纯形非退化基点的转移问题.要想利用基点定向转移矩阵的负旋转迭代运算来搜索单纯形的优化极点，还必须解决单纯形退化基点的转移问题.为此，引入下列定义及有关命题：

定义4若单纯形基点定向转移矩阵的基解列中所含零元素的个数大于决策变量数与剩余变量数之和，则称该基点定向转移矩阵对应的基点是退化的，将方向块中非单位行对应的基解列的零元素称为该基点的退化零元素，并称单纯形在该退化基点处具有局部非正则性.

定义5 将“用无穷小量正参数ε替代退化基点的所有退化零元素”的操作称为一次单纯形局部小量正参数ε正则化；若单纯形的极点都是非退化的，则称该单纯形具有正则性（也称LP问题是正则的LP问题）.

性质2只要小量正参数ε足够小，可行域的局部小量正参数ε正则化就不会改变LP问题的最优基.

性质3只要小量正参数ε足够小，经过局部小量正参数ε正则化的基点定向转移矩阵，不论通过多少次负旋转迭代运算，所得矩阵的ε零化矩阵（即，令其中的ε值为零而得到的矩阵）仍然为原LP问题的人工强迫性LP问题可行域基点的转移矩阵.

实际上，之所以要对单纯形进行局部小量正参数ε正则化处理，目的就是让可行域退化的基点非退化化，将退化基点的转移问题转化为非退化极点的转移问题，彻底消除基点退化对迭代搜索的不利影响.

2两阶段基点迭代转移算法

2.1基本思路与构想

先利用单纯形基点的定向迭代转移模型，从线性不等式组（6）的初始基点定向转移矩阵出发，通过负旋转迭代运算，求得线性不等式组（6）的一个可行基点及其基点定向转移矩阵，从而，利用这一矩阵，可以求得LP问题（1）的一个可行基点及其基点定向转移矩阵（它的基解列、转移控制列中不含人工变量值分量，而价值系数列中也不含强迫性无穷大正参数M），再利用单纯形基点的定向迭代转移模型求解之，最终求得原LP问题的最优解.新算法的整个寻优过程可分为如下两个阶段：

1）定解阶段：判断原LP问题的可行域（即约束不等式组的解空间）是否非空？

2）寻优阶段：在可行域非空的情况下，利用单纯形基点的定向迭代转移模型求出原LP问题的最优解.

对照分析新算法的运算平台为基点转移矩阵，相比单纯形类算法的运算平台——单纯形表， 基点转移矩阵这一新平台的结构化程度更高，不仅线性特征明显，而且几何平面特征也十分突出，更能反映LP模型之结构特点.另外，单纯形类算法之基点转移，因“换基”中的基退化问题而极易发生基循环现象.而利用新算法求解LP问题时，因为使用了可行域局部 正则化方法处理基点退化转移问题，求解过程中的基点转移总在非退化情况下进行，所以，从根本上消除了基循环现象发生之可能.

4结论

1）在求解LP问题的过程中，由于新算法对退化极点采取了可行域局部小量正参数ε正则化处理，确保了整个寻优过程均在非退化情形下完成，消除了退化问题对极点迭代转移过程的不利影响，所以，新算法很好地解决了算法运行中的基循环问题.

2）新算法是以单纯形之极点的极方向为迭代方向的一种极点迭代算法，它采用择优函数确定迭代方向，并通过矩阵初等变换来实现极点的迭代转移，

操作简便快捷，便于程序化处理，避免了诸如椭圆法与内点法中繁杂的迭代运算，搜索效率显著提高.

3）基点定向转移矩阵作为新的LP问题算法平台，与传统的单纯形表比，它的结构化程度高，且充分反映了线性规划的几何平面特性，为解决LP的解算问题找到了一种新的数学工具.

4） 单纯形法是利用换基的方式来实现基点迭代转移的，转移过程极易受退化现象的影响（即易发生基循环问题）.新算法的基点转移，本质上，已经回归到了传统的点向式转移方式，整个搜索过程始终在非退化的情形下完成，没有出现基循环的可能.

5）新算法的迭代运算是线性的，且迭代过程中目标函数值严格单调，但与摄动单纯形算法比较，它的计算量得到大大减少，所以，本研究基本达到了先期预设的研究目标.

6）对求解退化的LP问题，新算法继承了摄动单纯形算法的优点（即始终保持迭代中目标函数值的严格单调性），也克服了因摄动项的添加，使计算量猛然增加的缺陷.不过，与单纯形算法类似，新算法也存在变量爆炸性难题，这也是在今后研究中需要重点突破与解决的问题.

参考文献

[1]胡清淮，魏一鸣. 线性规划及其应用[M]. 北京：科学出版社，2004. 20-46.

[2]DANTZIG G B. Linear programming extensions [M]. Princeton： Princeton University Press， 1963. 79-87.

[3]KHACHIYAN L G. A polynomial algorithm for linear programming [J].Soviet Mathematics Doklady， 1979， 20（3）：191-194.

[4]KARMARKAR N K. A new polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]颜红彦，潘平奇. 线性规划的无比值检验CrissCross算法[J]. 合肥工业大学学报：自然科学版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改进的哈奇扬算法求解线性不等式组问题[J]. 科学技术与工程，2009，10（19）：5752-5754.

[8]曾梅清，田大钢. 线性规划问题的算法综述[J]. 科学技术与工程，2010，10（1）：152-159.

[9]孙中波，段复建.不等式约束优化的非单调可行信赖域SQP算法[J].应用数学学报，2011，34（4）：655-670.

[10]刘道建， 黄天民. 一种线性不等式组的矩阵变换定解方法[J]. 上海交通大学学报：自然科学版，2012，46（10）：1701-1706.

4结论

1）在求解LP问题的过程中，由于新算法对退化极点采取了可行域局部小量正参数ε正则化处理，确保了整个寻优过程均在非退化情形下完成，消除了退化问题对极点迭代转移过程的不利影响，所以，新算法很好地解决了算法运行中的基循环问题.

2）新算法是以单纯形之极点的极方向为迭代方向的一种极点迭代算法，它采用择优函数确定迭代方向，并通过矩阵初等变换来实现极点的迭代转移，

操作简便快捷，便于程序化处理，避免了诸如椭圆法与内点法中繁杂的迭代运算，搜索效率显著提高.

3）基点定向转移矩阵作为新的LP问题算法平台，与传统的单纯形表比，它的结构化程度高，且充分反映了线性规划的几何平面特性，为解决LP的解算问题找到了一种新的数学工具.

4） 单纯形法是利用换基的方式来实现基点迭代转移的，转移过程极易受退化现象的影响（即易发生基循环问题）.新算法的基点转移，本质上，已经回归到了传统的点向式转移方式，整个搜索过程始终在非退化的情形下完成，没有出现基循环的可能.

5）新算法的迭代运算是线性的，且迭代过程中目标函数值严格单调，但与摄动单纯形算法比较，它的计算量得到大大减少，所以，本研究基本达到了先期预设的研究目标.

6）对求解退化的LP问题，新算法继承了摄动单纯形算法的优点（即始终保持迭代中目标函数值的严格单调性），也克服了因摄动项的添加，使计算量猛然增加的缺陷.不过，与单纯形算法类似，新算法也存在变量爆炸性难题，这也是在今后研究中需要重点突破与解决的问题.

参考文献

[1]胡清淮，魏一鸣. 线性规划及其应用[M]. 北京：科学出版社，2004. 20-46.

[2]DANTZIG G B. Linear programming extensions [M]. Princeton： Princeton University Press， 1963. 79-87.

[3]KHACHIYAN L G. A polynomial algorithm for linear programming [J].Soviet Mathematics Doklady， 1979， 20（3）：191-194.

[4]KARMARKAR N K. A new polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]颜红彦，潘平奇. 线性规划的无比值检验CrissCross算法[J]. 合肥工业大学学报：自然科学版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改进的哈奇扬算法求解线性不等式组问题[J]. 科学技术与工程，2009，10（19）：5752-5754.

[8]曾梅清，田大钢. 线性规划问题的算法综述[J]. 科学技术与工程，2010，10（1）：152-159.

[9]孙中波，段复建.不等式约束优化的非单调可行信赖域SQP算法[J].应用数学学报，2011，34（4）：655-670.

[10]刘道建， 黄天民. 一种线性不等式组的矩阵变换定解方法[J]. 上海交通大学学报：自然科学版，2012，46（10）：1701-1706.

4结论

1）在求解LP问题的过程中，由于新算法对退化极点采取了可行域局部小量正参数ε正则化处理，确保了整个寻优过程均在非退化情形下完成，消除了退化问题对极点迭代转移过程的不利影响，所以，新算法很好地解决了算法运行中的基循环问题.

2）新算法是以单纯形之极点的极方向为迭代方向的一种极点迭代算法，它采用择优函数确定迭代方向，并通过矩阵初等变换来实现极点的迭代转移，

操作简便快捷，便于程序化处理，避免了诸如椭圆法与内点法中繁杂的迭代运算，搜索效率显著提高.

3）基点定向转移矩阵作为新的LP问题算法平台，与传统的单纯形表比，它的结构化程度高，且充分反映了线性规划的几何平面特性，为解决LP的解算问题找到了一种新的数学工具.

4） 单纯形法是利用换基的方式来实现基点迭代转移的，转移过程极易受退化现象的影响（即易发生基循环问题）.新算法的基点转移，本质上，已经回归到了传统的点向式转移方式，整个搜索过程始终在非退化的情形下完成，没有出现基循环的可能.

5）新算法的迭代运算是线性的，且迭代过程中目标函数值严格单调，但与摄动单纯形算法比较，它的计算量得到大大减少，所以，本研究基本达到了先期预设的研究目标.

6）对求解退化的LP问题，新算法继承了摄动单纯形算法的优点（即始终保持迭代中目标函数值的严格单调性），也克服了因摄动项的添加，使计算量猛然增加的缺陷.不过，与单纯形算法类似，新算法也存在变量爆炸性难题，这也是在今后研究中需要重点突破与解决的问题.

参考文献

[1]胡清淮，魏一鸣. 线性规划及其应用[M]. 北京：科学出版社，2004. 20-46.

[2]DANTZIG G B. Linear programming extensions [M]. Princeton： Princeton University Press， 1963. 79-87.

[3]KHACHIYAN L G. A polynomial algorithm for linear programming [J].Soviet Mathematics Doklady， 1979， 20（3）：191-194.

[4]KARMARKAR N K. A new polynomialtime algorithm for linear programming[J]. Combinatorica， 1984， 4（5）：373-395.

[5]LI Wei. New variable of artificialfree algorithm for linear programming problem[J]. J of Math（PRC）， 2008， 28（9）： 243-248.

[6]颜红彦，潘平奇. 线性规划的无比值检验CrissCross算法[J]. 合肥工业大学学报：自然科学版，2009，32（12）：1949-1952.

[7]刑金萍，樊彩霞. 改进的哈奇扬算法求解线性不等式组问题[J]. 科学技术与工程，2009，10（19）：5752-5754.

[8]曾梅清，田大钢. 线性规划问题的算法综述[J]. 科学技术与工程，2010，10（1）：152-159.

[9]孙中波，段复建.不等式约束优化的非单调可行信赖域SQP算法[J].应用数学学报，2011，34（4）：655-670.

[10]刘道建， 黄天民. 一种线性不等式组的矩阵变换定解方法[J]. 上海交通大学学报：自然科学版，2012，46（10）：1701-1706.