A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) Min c(t)chi subject to A chi = b, chi >= 0. The iterative part - a variation of Karmarkar pro...
详细信息
A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) Min c(t)chi subject to A chi = b, chi >= 0. The iterative part - a variation of Karmarkar projective transformation algorithm - is essentially due to Barnes only to the extent of detection of basic variables of the LP taking advantage of monotonic convergence. It involves much less number of iterations than those in the Karmarkar projective transformation algorithm. The shrunk linear system containing only the basic variables of the solution vector x resulting from A chi = b is then solved in the mathematically non-iterative part. The solution is then tested for optimality and is usually more accurate because of reduced computation and has less computational and storage complexity due to smaller order of the system. The computational complexity of the combination of these two parts of the algorithm is polynomial-time O(n(3)). The boundedness of the solution, multiple solutions, and no-solution (inconsistency) cases are discussed. The effect of degeneracy of the primal linear program and/or its dual on the uniqueness of the optimal solution is mentioned. The algorithm including optimality test is implemented in Matlab which is found to be useful for solving many real-world problems. (C) 2010 Elsevier Ltd. All rights reserved.
暂无评论