单纯形算法的两种部分定价策略

根据Hu和Johnson的原始一对偶单纯形算法原理，提出了两种部分定价策略．给定一组原始一对偶可行解，首先，选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量，再用Dantzig准则的单纯形算法求解该原始子问题．其次，针对原始退化问题，选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价，然后应用Bland准则的单纯形算法求解原始子问题，以克服退化可能引起的循环现象．最后，对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验，结果表明，与经典单纯形算法相比，提出的算法具有更好的计算表现．

几种单纯形法定价策略的计算比较

基于Maros的一般定价方案和Pan,Li,Cao的部分定价策略,衍生出两种单纯形变式.变式一以完全基为换基变换执行嵌套定价,变式二以完全基为换基变换,将所有非基列分成两段,在两段交替执行嵌套定价.然后与Dantzig完全定价准则的经典单纯形算法进行计算比较.对来自NETLIB和MIPLIB的25个典型算例的数值试验结果表明,与经典单纯形算法相比,变式一和变式二在某些算例中需要更多的迭代次数,但在所有算例上却耗费少得多的计算工作量,尤以变式二的计算性能体现得更好.

Partial Pricing Rule Simplex Method with Deficient Basis

A new partial pricing column rule is proposed to the basis-deficiency-allowing simplex method developed by Pan.Computational results obtained with a set of small problems and a set of standard NETLIB problems show its promise of success.