求线性规划初始基可行解的叠累型转轴方法

Monotonic Build-Up Pivotal Methods for Finding an lnitial Basic Feasible Solution to Linear Programming

建立两种新的叠累型转轴方法。不引进任何人工变量和罚因子以及辅助线性规划，从任何一个基（既非原始，也非对偶可行）出发，在原模型上施行转轴运算，对原始（对偶）可行性进行叠累，即在转轴中，非负变量（简约价格）始终保持其非负性，且非负个数不断得以增加，因此，可在有限次转轴后获得原始（对偶）基可行解。本文第一种转轴方法属于阶段Ⅰ型，即不考虑目标函数值的变化。第二种方法是组合两阶段型，即将初始化和最优化过程兼顾考虑。

This paper presents two new kind of monotonic build-up pivotalmethods. These methods don't introduce any artificial variables, penalty parameter andauxiliary linear programming, they are taken only on the primal model beginning with abase (neither primal, nor dual feasible ), the primal (dual) feasibility is built up in pivotalopertions,that is,the nonnegative varibles (reduced cost) always maintain nonnegativityand the number of varibles with nonnegative value is increased. Thus a primal (dual) basicfeasible solution is obtained in a finite number of pivots. The pivotal methods Ⅰ and Ⅱ isthis paper belong to the type of phase i, i.e., the change of the objective value isn't consid ered. The piyolal methody Ⅲ and Ⅳare kind of combined two phases, i.e., the initializationand opuimizations are considerd at the same time.