徐州工程学院学报（自然科学版）2016，Vol.31Issue(4)：21-26,6.
第一阶段单纯形法的一种分段定价策略
A Sectional Pricing Strategy for the Phase-1 Simplex Method
摘要
Abstract
The paper presents a sectional pricing strategy for the phase-1 simplex 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 alter-natively in turns in other three sections according to the possibility of those variables remaining nonbasis. Variant 1 uses 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 2 starts section when the obj ective 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 2 uses fewer iterations in total,probes fewer columns,and spend much less computational time than the classical simplex algorithm.Therefore,variant 2 is of the interest in computational performance.关键词
线性规划/单纯形法/定价准则/分段定价/计算效率Key words
linear programming/simplex method/pricing rule/sectional pricing/computational effi-ciency分类
数理科学引用本文复制引用
高培旺..第一阶段单纯形法的一种分段定价策略[J].徐州工程学院学报（自然科学版）,2016,31(4):21-26,6.基金项目
闽江学院人才引进基金资助课题(MJU2012001) （MJU2012001）
广西自然科学基金项目(0728260) （0728260）
国家星火计划项目(2013GA690426) （2013GA690426）
