第一阶段单纯形法的一种分段定价策略

A Sectional Pricing Strategy for the Phase-1 Simplex Method

提出第一阶段单纯形法的一种分段定价策略,而在此策略下可产生两种单纯形算法变式.根据Cheng的判断准则将所有非基变量分成四段,其中一段由最优基本解中的非基变量构成,在迭代过程中对另外三段非基变量依其保持非基的可能性程度先后交替定价.第一种算法从迭代开始就根据Cheng的两个判断准则对四段非基变量不断调整,这虽极大节省了定价计算的工作量,但两个判断准则的计算需要耗费大量时间,导致该算法计算效率很低.第二种算法对第一种算法作了改进,当目标当前值超过最优值的2/3时,开始对非基变量分段,然后只根据Cheng的一个较简单的判断准则对定价后的非基变量进行调整.对来自NETLIB和MIPLIB的27个典型算例的初步试验结果表明,改进的算法不仅比经典单纯形算法所用的总迭代次数要少,在所有算例上所搜寻的非基列数也少,所耗费的计算时间更少,其计算性能高效而稳定.

The paper presents a sectional pricing strategy for the phase-1simplex algorithm.Based on this,two variants are derived.Firstly,all nonbasic variables are partitioned into four sections,one of which includes the nonbasic variables in an optimal solution.In the iterative process,pricing is implemented alternatively in turns in other three sections according to the possibility of those variables remaining nonbasis.Variant 1uses Cheng's two criteria to change the composition of components in four sections at the outset of the iteration.So it greatly decreases the amount of pricing computation,but spends much more time than the classical simplex algorithm.Variant 2starts section when the objective value arrives at two third of the optimum value,and changes sections by only one of Cheng's criteria.A preliminary test is accomplished on a set of 27 standard instances from NETLIB and MIPLIB.The computational results show that variant 2uses fewer iterations in total,probes fewer columns,and spend much less computational time than the classical simplex algorithm.Therefore,variant 2is of the interest in computational performance.