目标超平面上的一种对偶单纯形算法*

高 培 旺

(闽江学院 数学系，福州 350121)

0 引 言

考虑如下形式的线性规划问题：

(LP) maxcTx

s.t.Ax=b

x≥0

这里，A∈Rm×n(m

为了应用单纯形算法求解上述问题(LP)，首先需要构造辅助线性规划问题(ALP)来获得一个初始基本可行解.在等式约束中引入人工变量y=0产生第一阶段问题：

(ALP) maxeTAx

s.t.Ax+y=b

x≥0，y≥0

这里，e=(1，…，1)T∈Rm，对问题(ALP)的求解几乎占到整个单纯形法计算工作量的一半[1]，因此，研究第一阶段问题的求解方法和计算性能也是有价值的课题.相比第二阶段单纯形法，第一阶段单纯形算法能产生更多的信息，诸如目标最优值既定、人工变量都在初始基中，必须旋转出去，如何充分利用这些已知信息，值得探讨.

显然，(ALP) 有一个基本可行解x=0，y=b，可以应用Dantzig[2]的经典单纯形算法直接求解.另外，Arsham[3-4]提出了一种有趣的无人工单纯形类型方法，其意图是避免使用人工变量，且通过逐列搜寻入基的决策变量来尽快旋出人工变量.但Enge和Huhn[5]随后指出这种方法其实包含人工变量，只不过字面上没有写出来，并通过一个反例说明逐列搜寻不能保证产生一个完全基，还可能带来指数时间的计算工作量.为了使Arsham方法正常运行，Gao[6]对其进行了重要改进，取得很好的计算效果.其实一些方法，如Terlaky[7-8]的有限criss-cross方法，虽然能防止退化产生的循环，但对实际问题的求解效率太低，没有应用价值.

注意到问题(ALP)的可行解(如果存在)位于目标超平面eTAx=eTb上，其最优值为eTb.根据这一特征，将人工变量ym+1从目标超平面对应的约束eTAx+ym+1=eTb中旋转出去，然后将迭代运动固定在目标超平面上，则所有变量的简约价值系数恒保持为零，即对偶可行.此时，(ALP)的求解过程仅在于获得其原始可行性，应用经典对偶单纯形算法求解[9]，不需要计算行系数与简约价值系数的检验比，节省计算工作量，但对偶退化易于产生迭代循环.Samaras[10]等曾提出的一种原始-对偶外点算法，通过不断缩小对偶缝隙来达到快速收敛的目标，实际上，该方法是对偶单纯形算法的一种变式，它利用变动的原始可行点来确定枢轴行，但它必须有一个原始可行点和一个对偶可行基来启动，实现这个初始启动要耗费巨大的计算工作量[11]，得不偿失.

讨论第一阶段辅助问题(ALP)的求解，提出一个单纯形变式，将迭代过程固定在目标超平面上，保持对偶可行性.为了尽可能避免对偶退化带来的循环，Anstreicher和Terlaky[12]设计了一种MBU单纯形算法准则，它以右手项取负值的某个约束为目标(约束)，通过对偶迭代使该目标约束的右手项的值单调增加，直至变成非负，则右手项取负值的约束数量减少至少一个，依此下去，可达到问题的原始可行性，在保持问题对偶可行的前提下，该原始可行解就是问题的一个最优解.这种方法具有明确的理论意义，但实际的计算效果不好[13]，主要是右手项取负值的约束数量较多时，需要求解多个只包含右手项为非负的约束子规划，而且迭代数与选取目标约束的顺序有关.为了克服MBU单纯形算法的上述缺陷，本文以右手项取负值的所有约束之和为目标(约束)，同时保持右手项为非负的约束仍然可行，一旦右手边取负值的约束变为可行，就将其从目标约束中删除，直至获得一个可行解或者得到原问题无可行解的结论.显然，本文提出的算法只需求解一系列子规划问题，在理论上与第一阶段原始单纯形算法求解整个(ALP)问题相比，每次迭代所耗费的计算工作量要少.为了验证本算法的计算性能，从NETLIB[14]和MIPLIB[15]测试数据库中选取一些标准的中大规模算例，通过MATLAB编程在计算机上实现数值试验，初步计算结果表明，与经典单纯形算法相比，本文提出的算法在大部分问题上使用更少的迭代次数和执行时间，因而具有更高的计算效率.

孙庆雨,孙喆禹,邢文超,等.掺Ge氧化硅薄膜波导制备工艺与应力研究[J].光子学报，2018，47(12)：1231003

1 目标超平面上第一阶段对偶单纯形算法

如果原问题可行，辅助线性规划问题(ALP)具有一个已知的目标最优值eTb，亦即(ALP)的最优解位于目标超平面eTAx=eTb上.于是，将eTAx+ym+1=eTb作为一个新约束加入(ALP)中，构造一个与(ALP)等价的辅助问题如下：

(AALP) maxeTAx

s.t.Ax+y=b

eTAx+ym+1=eTb

x≥0，y≥0，ym+1≥0

其中，y=0，ym+1=0为人工变量.为了叙述方便，仍用A表示(AALP)的约束系数矩阵，用c表示(AALP)的价值系数向量，Ai为A的第i行，Aj为A的第j列.

命题1 如果(AALP)没有原始可行解，则(LP)是不可行的.

s.t.Aix+yi=bi，i∈I+

x≥0，yi≥0，i∈I+

这里，I-={i|(B-1b)i<0}，I+={i|(B-1b)i≥0}.

根据上述原理，给出具体的算法步骤如下：

步骤1 选择指标s=argmax{eTA}，如果cm+1，s=(eTA)s≤0，则(LP)无可行解或只有唯一零解，算法结束；否则，以cm+1，s为枢轴主元进行旋转变换，且一旦人工变量ym+1离基后就删除其所在列，转下一步.

在上述算法步骤3中，如果没有遇到退化产生的循环现象，本文提出的算法通过有限步迭代就可获得(LP)的一个可行解，或者(LP)无可行解的结论.

2 数值计算研究

为了验证提出的算法的计算性能，从线性规划标准测试库NETLIB[14]和混合整数规划标准测试库MIPLIB[15]中选取了24个典型算例，其中，问题air01，enigma，lp41，mod010属于整数规划问题，只求解其相应的线性规划松弛问题的解，这些算例具有稀疏、退化的特征.接下来，使用MATLAB V7.1语言对经典单纯形算法和本文的目标超平面上的对偶单纯形算法进行了编程，在Lenovo PentiumM计算机上执行数值试验，求解这些算例的第一阶段辅助问题，以对两种算法的计算效率进行比较.数值试验的环境是完全相同的，计算结果如表1所示，其中，Iters表示求解线性规划问题所需要的枢轴(迭代)数，Time表示所耗费的总的计算时间(s).这里需要说明的是，Anstreicher和Terlaky的对偶MBU单纯形准则必须要给定一个对偶可行基的前提下才能应用，而这些算例的第一阶段辅助问题一般不存在eTA≥0，bi<0的情形，因此，本文没有对Anstreicher和Terlaky的对偶MBU单纯形算法进行编程计算.

表1 经典单纯形算法和目标超平面上的对偶单纯形算法的计算比较Table 1 Computation comparison of dual simplex algorithm on objective hyperplane and classic simplex algorithm

从表1看到，本文提出的算法在14个问题上比经典的单纯形算法所用的迭代次数少，在4个问题上与经典的单纯形算法所用的迭代次数持平，从24个问题所用的总的迭代次数来看，本文的目标超平面上的对偶单纯形算法与经典单纯形算法的迭代次数之比为4 153/4 547=0.913 3.尤其是从计算所耗费的CPU时间来看，本文提出的算法只在1个问题(scsd1)上比经典的单纯形算法所用的时间多，验证了每次迭代比第一阶段原始单纯形算法所耗费的计算工作量要少.可见，目标超平面上的对偶单纯形算法在大部分问题上所用的迭代次数更少，计算时间更短，因而计算效率更高.

3 结 论

提出的算法具有如下显著特征：首先，它可以从既不是原始可行也不是对偶可行的初始点启动，增加了启动的方便性；其次，在目标超平上的迭代产生对偶可行性，此时，枢轴准则的设计只需考虑如何尽快获得问题的原始可行解，当所有变量的简约价值系数保持为零时，枢轴列的选择是非常灵活的.因此，本文提出的算法仅仅是目标超平面上的一种单纯形算法变式.

本方法把Anstreicher和Terlaky的MBU单纯形算法思想用于目标超平面上的迭代，在保持对偶可行性的前提下使原始可行约束的数量单调增加.为了克服驱动目标行太多可能导致的计算效率较低的缺陷，本文引入右手项取负值的所有约束之和作为驱动目标，以右手项为非负的所有约束为约束构造子规划问题，然后应用Dantzig经典单纯形算法求解子问题，这样每次迭代耗费的计算工作量就比求解整个辅助问题要少.从上一节表1给出的计算结果来看，与经典单纯形算法相比，本方法对大部分算例求解所用的迭代数要少，即使有些问题用了较多的迭代数，但耗费的执行时间却更短，这初步验证了本算法具有较高的计算效率.

在取得目标超平面上的可行解之后，在约束行中也许能找到取零值的人工基变量，为了求解第二阶段问题，需要将这些人工基变量旋转出去.此时，应用其他一些单纯形算法变式，如cosine单纯形方法选择“好”的非基变量入基[16-17]，可以得到一个更接近(LP)最优顶点的基本可行点.