A new algorithm for solving linear programming problems

Un nuevo algoritmo para la solución de problemas de programación lineal

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.

Introducción

La programación lineal (PL) data de 1939, cuando Leonid Kantarovich expresó por primera vez un problema de economía en forma lineal (Bazaraa et al., 1998). Sin embargo, la PL como área de estudio se atribuye a George Dantzig, que también desarrolló el método simplex en 1947 (Cottle, 2006). El LP ha sido ampliamente estudiado en programas de ingeniería, gestión, matemáticas y otros campos debido a su aplicabilidad.

Desde su publicación, el método simplex (y sus variantes) fue la principal herramienta para resolver problemas lineales hasta 1980, cuando Khachiyan propuso un algoritmo elipsoidal (Khachiyan, 1982). Aunque su implementación práctica no era muy eficiente, sin embargo sirvió de base para diseñar el algoritmo de puntos interiores (IPA) de Karmarkar, que es computacionalmente eficiente para resolver problemas de gran tamaño (Karmarkar, 1984) y computacionalmente menos complejo que el método simplex (Powell, 1993); Desde entonces se han hecho muchas contribuciones adicionales, por ejemplo, un algoritmo simplex primal-dual (Norman y Curet, 1993) que utiliza menos bases que el simplex primal-dual original, otro resuelve el primal-dual partiendo de un punto interior no factible (Mizuno, 1994), un algoritmo simplex proyectivo que utiliza la descomposición LU (Pan, 2000), una extensión del IPA de Karmarkar que tiene una mayor velocidad de convergencia (Naseri y Valinejad, 2007) y un IPA primal-dual adaptativo (Kim, Lee y Cho, 2009). Más recientemente, se ha desarrollado una propuesta de IPA basada en una nueva dirección de búsqueda (Zhang y Xu, 2011) y otro método basado en una nueva función barrera (Cho, 2011).

Teniendo en cuenta el gran número de áreas en las que se puede aplicar el LP y la importancia de contar con algoritmos eficientes para resolver problemas de LP, cualquier contribución que se haga al LP es muy relevante. En consecuencia, en este trabajo se presenta un nuevo método para resolver problemas de LP.