A pseudo-feasible point method for linear programming is proposed in this paper. The method is different from the well-known simplex method and Karmarkar interior point method for linear programming. A point is called a pseudo-feasible point if certain conditions are satisfied. Let F is contained in R~n be the feasible region of a given linear programming. A set P is contained in R~n is called a pseudo feasible region of the linear programming if F intersect P not = #psi# and optimal solution(s) of the objective function in the set P exists. A pseudo feasible region is called proper if F is contained in P or there exists optimal solution of the linear programming in P. The proposed method generates a sequence of pseudo feasible regions satisfying P_1 contains P_2 contains ... contains P_k contains..., and the sequence of iterative points is formed from the optimal solutions of the objective function in the sets P_k, k=1,2, .... The method determines either that the linear programming has no solution or that the optimal solution of the objective function in some pseudo feasible region is just the optimal solution of the linear programming after finite many iterations. It is proved that if the initial pseudo feasible region is proper, then the method either finds the optimal solution of the linear programming or shows an empty feasible region in finite many iterations. The choice of initial pseudo feasible region, generation of the pseudo feasible region sequence {P_k} and method for finding optimal solution of the objective function in set P_k are presented. Numerical experiments are implemented and the results are compared with the simplex method on some practical linear programming problems. The comparisons show that the pseudo feasible point method is superior to the simplex method and superiority is increased with increased problem dimension.
展开▼
