Algoritmo para la optimización del tiempo de ejecución en la situación de problemas de programación lineal

Abstract

En la presente investigación construimos un algoritmo para la optimización del tiempo de ejecución en la situación de problemas de programación lineal, este algoritmo está basado en una de las variantes del método de puntos interiores para programación lineal, este algoritmo evoluciona por el interior de la región factible a diferencia del algoritmo Simplex, que evoluciona por sus extremos, disminuyendo considerablemente el tiempo de ejecución en la solución de los problemas. Los algoritmos de puntos interiores surgen, con el trabajo de Karmarkar, como una alternativa de complejidad polinomial al bien establecido método de simplex, para el caso de programación lineal. En 1987 Kojima-Misuno-Yoshise presentan un algoritmo de puntos interiores, llamado Primal-Dual, que seguido del trabajo de Mehrotra en 1992, fundamentan las bases de algunos de los algoritmos existentes más eficientes para programación lineal. Este algoritmos combina de otras técnicas numéricas, tales como el método de newton, lagrange y penalización interna, funcionando estas tres técnicas resulta el algoritmos para la optimización del tiempo de ejecución en la situación de problemas de programación lineal. Se hizo la implementación de las tres técnicas numéricas así como la implementación del algoritmo principal en un software y experimentos computacionales que corroboran la eficacia frente a problemas de grandes dimensiones, se generó problemas de programación lineal de 90 restricciones y 110 variables, 220 restricciones y 320 variables, que fueron resueltos con el algoritmo principal.