Published
A new algorithm for solving linear programming problems
Un nuevo algoritmo para la solución de problemas de programación lineal
DOI:
https://doi.org/10.15446/ing.investig.v32n2.31949Keywords:
linear programming, optimisation, orthogonal projection, parametric equation (en)programación lineal, optimización, proyecciones ortogonales, ecuaciones paramétricas (es)
Linear programming (LP) is one of the most widely-applied techniques in operations research. Many methods have been developed and several others are being proposed for solving LP problems, including the famous simplex method and interior point algorithms. This study was aimed at introducing a new method for solving LP problems. The proposed algorithm starts from an interior point and then carries out orthogonal projections using parametric straight lines to move between the interior and polyhedron frontier defining the feasible region until reaching the extreme optimal point.
La programación lineal (PL) es una de las herramientas de mayor aplicación en la investigación de operaciones. Se han desarrollado y se siguen proponiendo varios métodos para la resolución de problemas de este tipo, desde el famoso simplex hasta los algoritmos de punto interior. Este trabajo tiene como propósito principal presentar la propuesta de un nuevo procedimiento para la solución de problemas PL que, partiendo de un punto interior, realiza proyecciones ortogonales mediante rectas paramétricas y se mueve iterativamente entre el interior y la frontera del poliedro que define la región factible hasta llegar al punto extremo óptimo.
References
Bazaraa, M. Jarvis, J. & Sherali, H. Programación lineal y flujo en redes, 2 ed en español, México, Limusa, 1998.
Cho, G. An interior-point algorithm for linear optimization based on a new barrier function. Applied Mathematics and Computation, Vol 218, No 2, 2011, pp. 386-395.
Cottle, R W. George B. Dantzig: a legendary life in mathematical programming. Mathematical Programming, Vol 105, No 1, 2006, pp. 1-8.
Karmarkar, N. New Polynomial-Time algorithm for linear programming. Combinatorica, Vol 4, No 4, 1984, pp. 373-395.
Khachiyan, L. On the exact solution of systems of linear inequalities and linear programming problems. URSS Computational mathematics and Mathematical Physics, Vol 22, No 4, 1982, pp. 239-242.
Kim, M. Lee, Y. Cho, G. An adaptive-step primaldual interior point algorithm for linear optimization. Nonlinear Analysis, Vol 71, 2009, pp. 2305-2315.
Mizuno, S. A predictor-corrector infeasible-interior-point algorithm for linear programming. Operations Research Letters, Vol 16, No 2, 1994, pp. 61-66.
Naseri, R. Valinejad, A. An extended variant of Karmarkar's interior point algorithm. Applied Mathematics and Computation, Vol 184, 2007, pp. 737-742.
Norman D. Curet, N. A primal-dual simplex method for linear programs. Operations Research Letters, Vol 13, No 4, 1993, pp. 233-237.
Pan, P. A projective Simplex algorithm using LU descomposition. Computers and mathematics with applications, Vol 39, 2000, pp. 187-208.
Powell, M.J.D. On the number of iterations of Karmarkar's algorithm for linear programming. Mathematical Programming, Vol 62, 1993, pp. 153-197.
Winston, W. Investigación de Operaciones, aplicaciones y algoritmos, 4 ed en español, México, Thompson, 2005, pp. 597-604.
Zhang, L. Xu, Y. A full-Newton step interior-point algorithm based on modified Newton direction. Operations Research Letters, Vol 39, 2011, pp. 318-322.
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2012 Andrés Leonardo Ramírez Leal, Oscar Yecid Buitrago Suescún, Rodrigo Alberto Britto Agudelo
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
