Font Size: a A A

Strongly Polynomial Algorithm For Linear Programming

Posted on:2003-12-04Degree:MasterType:Thesis
Country:ChinaCandidate:M PengFull Text:PDF
GTID:2120360062490297Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
In this paper a normal direction elimination process and a minimal normal direction elimination process for solving simultaneous algebraic equations have been advanced which is equivalent to successive projections of point and normal vectors of planes. Based on it an order construction on the equality constraint plane has been established so that we can get a new theory and strongly polynomial algorithm with complexity less than O(mn3) to directly compute all optimal solutions of a linear programming problem.My works are as following:1. Based on my engineering experience I suggested that theory and algorithm of Optimization should pay a good deal of attention to the optimal solution set but not to only an individual optimal solution.2. I suggested that when judge whether a n-m-k(0 ^ k ^ n-m) dimensional plane in Rn is nonfeasible it is enough to do projection often only some times greatly less than n-m by examination of only those coordinate hyperplanes with zero projection vector of corresponding coordinate vector but not need project finally to a point.3. I got the method to express any point in the optimal set by the tangent basis of the set.4. I desighed the flow diagram and the compute program by it I computed some examples.
Keywords/Search Tags:Linear programming, Order construction, Direct method, Strongly polynomial algorithm, Set of optimal solutions
PDF Full Text Request
Related items