Métodos espacio imagen para programas lineales dispersos

Abstract

Se presentan dos técnicas dispersas novedosas para dar solución al problema de la aplicabilidad de métodos non-simplex de conjunto activo para problemas de programación lineal (PL) grandes, pues si bien realizan menos iteraciones que los métodos simplex (que a su vez aventajan en ciertos casos a los de punto interior), el mantenimiento de una factorización dispersa adecuada para ellos no estaba resuelto, Ambas técnicas están basadas en actualizar factorizaciones ortogonales para disponer (explícita o implícitamente) de una base del espacio imagen de la matriz de trabajo; una de ellas permite resolver una sucesión de sistemas compatibles y la otra una sucesión de problemas mínimo-cuadráticos lineales. De esta manera se pueden llevar a cabo implementaciones tanto de gradiente proyectado como reducido de los métodos de tipo non-simplex en general. También se desarrolla una metodología para PL novedosa basada en la interpretación geométrica del métodos simplex dual, a partir de un nuevo método non-simplex para problemas en forma estándar. El análisis de las diferentes fases iniciales para el mismo da lugar a diferentes opciones algorítmicas, algunas de ellas con convergencia asegurada; además, se aporta una nueva demostración constructiva del conocido lema de Farkas aplicando el algoritmo NNLS de fomra no habitual. Las pruebas computacionales se realizan (en Matlab) con PLs de comprobación tanto clásicos como Netlib frente a una depurada implementación comercial dispersa del método simplex primal, obteniéndose una clara ventaja en cuanto a iteraciones realizadas, calidad de las soluciones y tiempo de ejecución.