Algoritmo de punto interior y direcciones factibles FDIPA en problemas de programación lineal de gran escala

Abstract

La presente tesis estudia el algoritmo de punto interior y dirección factible FDIPA de programación no lineal adaptado a problemas de programación lineal de gran escala con restricciones de desigualdad. El desarrollo inicia con la formulación del problema lineal a restricciones de desigualdad, seguido de métodos presolver y técnicas de reacondicionamiento que analizan la infactibilidad y mal condicionamiento, el problema es sometido a las condiciones Karush Kuhn Tucker (KKT) que por el método de Newton determina una dirección de descenso a partir de un punto interior inicial, la factibilidad de la siguiente iteración es determinada por el tamaño de paso óptimo que se obtiene analizando las filas de la matriz de restricciones con la dirección de descenso encontrada, obteniendo una sucesión de puntos interiores convergiendo a una solución del problema. Además, se estudian las hipótesis y condiciones de convergencia del problema. El nuevo algoritmo ha sido nombrado algoritmo FDIPA-LP. Los problemas test de gran escala son tomados de la librería NETLIB, los resultados obtenidos son muy buenos teniendo comparaciones de hasta orden 10-10, también es aplicado en resolución de problemas de transporte que comparado con el método de la esquina noroeste y la aplicación de software WINQSB, ha mostrado resultados similares a los encontrados. El algoritmo FDIPA-LP es sencillo de implementar, eficiente y eficaz, siendo una alternativa al método simplex y otros métodos de punto interior que puede ser aplicado en casos de gran complejidad y otras áreas afines.

This paper studies the FDIPA feasible direction and interior point algorithm for nonlinear programming adapted to large-scale linear programming problems with inequality constraints. The development starts with the formulation of the linear problem with inequality constraints, followed by presolver methods and reconditioning techniques that analyse infeasibility and illconditioning, the problem is subjected to the Karush Kuhn Tucker (KKT) conditions that by Newton’s method determines a direction of descent from an initial interior point, the feasibility of the next iteration is determined by the optimal step size which is obtained by succession of interior points converging to a solution of the problem. In adittion, the hypotheses and convergence conditions are studied. The new algorithm has been named the FDIPA-LP algorithm. The large-scale test problems are taken from the NETLIB library, the results obtained are very good with comparisons of orden 10-10, it is also applied to transport problems which compared to the nortwest corner method and the application of WINQSB software, has shown similar results to those found. The FDIPA-LP algorithm is simple to implement, efficient and effective, being an alternative to the simplex method and other interior point methods that can be applied in cases of high complexity and other related areas.