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

A Dual Simplex Algorithm on the Objective Hyperplane

作　　者：高培旺[1] GAO Pei-wang(Department of Mathematics,Minjiang University,Fuzhou 350121,China)

机构地区：[1]闽江学院数学系,福州350121

出　　处：《重庆工商大学学报（自然科学版）》2018年第5期60-65,共6页Journal of Chongqing Technology and Business University:Natural Science Edition

基　　金：国家社会科学基金项目(15BTJ011);广西自然科学基金项目(0728260)

摘　　要：提出求解第一阶段线性规划问题的对偶单纯形算法.首先,将具有最优值的辅助目标函数作为新约束加入第一阶段问题中;然后,以该约束所在行为枢轴行进行旋转变换产生辅助超平面上的一个极顶点,如果这个点可行,第一阶段对偶单纯形算法结束,否则,迭代固定在辅超平面上极行;接下来,以右手项取负值的所有约束之和为目标(约束),通过对偶迭代使右手边的值单调增加,同时保持右手项为非负的约束仍然可行,一旦右手边取负值的约束变为可行,就将其从目标约束中删除,直至获得一个可行解或者得到原问题无可行解的结论;最后,从NETLIB和MIPLIB测试数据库中选取一些标准的中大规模算例,通过MATLAB编程在计算机上实现数值试验,初步计算结果表明与经典单纯形算法相比,提出的算法在大部分问题上使用更少的迭代次数和执行时间,因而具有更高的计算效率.This paper presents a new dual simplex algorithm for solving phase 1 linear programming problems. In the algorithm, first, the equation with the auxiliary objective function at the optimality as a new constraint is added to phase 1, and then a pivot is performed to generate one vertex on the associated objective hyperplane. This vertex may be feasible or not feasible. If it is feasible, the phase 1 simplex algorithm ends,otherwise, is proceed with the successive iterations fixed on the objective hyperplane. Next, taking the sum of the constraints with the right-hand-side negative as the objective, we use the dual pivot to make the value of the right-hand-side monotonically increased, and meanwhile keep the constraints with the right-hand-side positive or zero still feasible. Once a constraint with the right-hand-side negative is changed feasibly,it would be deleted from the sum until a feasible solution or the situation with no solution is achieved. Finally, computational study is done to test the efficiencies of the algorithm comparing to the ordinary simplex algorithm on some standard test problems from NETLIB and MIPLIB, showing that our algorithm uses fewer iterations and spends less executive time on most instances, thus is more efficient in computation.

关 键 词：线性规划 第一阶段辅助问题 单纯形算法 对偶单纯形算法 目标超平面 

分 类 号：O221.1[理学—运筹学与控制论]