کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7542978 | 1489160 | 2011 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving linear program as linear system in polynomial time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) Minctxsubject toAx=b,xâ¥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 Ax=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(n3). 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Mathematical and Computer Modelling - Volume 53, Issues 5â6, March 2011, Pages 1056-1073
Journal: Mathematical and Computer Modelling - Volume 53, Issues 5â6, March 2011, Pages 1056-1073
نویسندگان
Syamal K. Sen, Suja Ramakrishnan, Ravi P. Agarwal,