变量有广义界线性规划的叠累单纯形法

本文建立变量有广义界线性规划一个新的转轴算法,称之为叠累单纯形算法,新算法其有三个主要特征：１对于检验数为“坏”的非基变量 ｘｓ,进行一轮子转轴运算,使得ｘｓ进基,转轴中具有“好”的检验数的变量始终保持“好”的检验数;２ｘ．进基的子转轴所产生的基既不是原始可行基,也不是对偶可行基,但子转轴结束时产生的基是原始可行的;３目标函数值在整个转抽运算中是单调下降,从而算法可有限步终止．

A MONOTONIC BUILD-UP SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING WITH GENERALIZED BOUNDED VARIABLES

in this paper,a new pivoting algorithm for solving linear programming with generalized bounded variables is presented,it is called a monotonic build-up simplex algorithm. This new algorithm possesses three main properties :I For a nonbasic variable xs with"bad" reduced cost,the new algorithm produees a sequence of pivoting operation such that xs enters the basis, moreover, all variables with"good"reduced costs remain good reduced costs throughout the pivoting process; 2. The bases generated by the sequence of pivoting operation making Xs enter the basis are neither primal feasible nor dual feasible,but once xs enters the basis, the related basis returns to primal feasible; 3. The objective value is decreasing throughout the pivoting operation,hence the algorithm terminates in a finite number of pivots.