Variantes del algoritmo simplex en problemas de programación lineal con estructura especial

Recio Valcarce, Carmen
Calvete Fernández, Herminia Inmaculada (dir.)

Universidad de Zaragoza, CIEN, 2017
Métodos Estadísticos department, Estadística e Investigación Operativa area

Graduado en Matemáticas

Abstract: El algoritmo simplex es un algoritmo fundamental para resolver problemas de programación lineal. Está basado en recorrer soluciones factibles básicas (puntos extremos) adyacentes hasta que se verifica la condición de optimalidad sobre los costes marginales o se detecta que existe una dirección extrema para la que se cumple la condición de no acotación del problema. En este trabajo se estudian algunas implementaciones especiales y variantes del algoritmo simplex. Estas variantes tratan de mejorar algunos aspectos como el coste computacional o la estabilidad numérica. Se utilizan para resolver problemas de gran dimensión y problemas de optimización entera. En el primer capítulo se explica el método simplex revisado, una forma sistemática de implementar los pasos del algoritmo simplex que permite ahorrar espacio de almacenamiento al utilizar una tabla de menor tamaño. El algoritmo simplex revisado almacena únicamente la información indispensable para continuar con la siguiente iteración. El algoritmo simplex calcula todos los costes marginales de las variables no básicas para determinar la variable que debe entrar en la base así como todas las columnas asociadas a las mismas; en cambio el algoritmo simplex revisado sólo calcula la columna asociada a la variable no básica que se ha seleccionado para entrar en la base y, una vez determinado el índice de la variable básica que deja la base, esta columna es eliminada y se repite el proceso para la nueva tabla. En el caso del algoritmo simplex, en cada iteración es necesario calcular la inversa de la base; esto puede hacerse de una forma mucho más eficiente si se utilizan operaciones con matrices elementales. Para actualizar la tabla del algoritmo es conveniente utilizar la forma producto de la inversa de una matriz, pues agiliza los cálculos que requiere el pivotaje. Sin embargo en problemas de gran dimensión y problemas sparse (es decir, con pocos coeficientes distintos de cero), es mejor utilizar la factorización LU debido a la mayor precisión y estabilidad numérica de la estrategia de triangulación Gaussiana en la que se basa. En el segundo capítulo se estudia el método simplex para problemas con variables acotadas. En problemas de este tipo el método más directo para tratar las restricciones sobre la acotación de las variables sería introducir variables de holgura. Sin embargo, esto supondría incrementar en gran medida el número de variables, por lo que no es un método eficiente. El método simplex para variables acotadas trata estas restricciones sin aumentar la dimensión del problema, de forma análoga a la manera en que el método simplex trata las restricciones de no negatividad. En el tercer capítulo se estudia el principio de descomposición lineal. Éste se refiere a la aplicación de las técnicas de relajación Lagrangiana, de Dantzig-Wolfe o de Benders, que son equivalentes entre sí para problemas de programación lineal. En el caso de problemas de gran dimensión, el objetivo es estructurarlos en uno o más problemas de menor tamaño. Una vez conseguido que el tamaño sea asequible, si algunas de las restricciones poseen una estructura especial, se separa el problema en uno con estructura general y otro con estructura especial de manera que en el segundo se pueda aplicar un método más eficiente. Las restricciones de problemas lineales se dividen en dos tipos: restricciones generales y restricciones con estructura especial. La estrategia del principio de descomposición es trabajar con dos problemas lineales por separado: el problema principal, que tiene las restricciones generales, y el subproblema, que tiene las restricciones con estructura especial. El problema principal transfiere un nuevo conjunto de coeficientes de la función objetivo al subproblema y recibe del subproblema la información sobre la variable que debe entrar en la base en forma de una nueva columna basada en estos coeficientes. Si planteamos el problema en términos de los puntos extremos y las direcciones extremas, como se verá en más detalle en este capítulo, la idea subyacente del principio de descomposición es encontrar una solución óptima sin necesidad de calcular explícitamente todos los puntos extremos y todas las direcciones extremas. Una versión especial del principio de descomposición es aquella que se aplica a problemas con una cierta estructura llamada diagonal por bloques o angular. En este tipo de problemas hay un conjunto de restricciones que afectan a todas las variables mientras que otros conjuntos de restricciones sólo afectan a algunos bloques de variables. En el capítulo se explica en detalle este caso. Además, se estudia la descomposición de Benders para problemas enteros mixtos; la estrategia en este caso es descomponer el problema en la parte continua y la parte entera. En este capítulo también se da una idea general del método de generación de columnas. Este método se suele utilizar en problemas con un número muy grande de variables. Mientras que el método simplex identifica la variable que entra en la base calculando todos los costes marginales, este procedimiento permite la identificación de la variable sin necesidad de calcular todos ellos. Existen muchas variantes de esta técnica general (la descomposición de Dantzig-Wolfe entre ellas). En el capítulo se explica con especial atención una variante que involucra columnas retenidas. En dicha variante del método, el algoritmo almacena en la memoria todas o algunas de las columnas que han sido generadas en el pasado y procede en términos de problemas lineales restringidos que involucran únicamente las columnas almacenadas (retenidas). El problema de corte de piezas es un ejemplo clásico de la aplicación de la técnica de generación de columnas. En el capítulo se plantea y se desarrolla este problema y en el apéndice 1 se resuelve un ejemplo numérico del mismo. En el cuarto capítulo se estudian dos artículos recientes en los que se aplican métodos de generación de columnas. El primero está relacionado con la determinación de rutas escolares de autobuses y el segundo con la determinación del lugar óptimo para la construcción de un número fijo de clínicas en África. Ambos problemas son problemas enteros con un número muy grande de variables por lo que se propone el uso del método de generación de columnas para su resolución. En el apéndice 1 se resuelven ejemplos numéricos de los métodos descritos en los capítulos de este trabajo, con el fin de facilitar la comprensión de los mismos. Estos problemas no están resueltos en la literatura estudiada. El primer ejemplo es un problema de programación lineal de máximo en el que se plantea su resolución mediante el uso de la forma producto de la inversa y el método simplex revisado. El segundo ejemplo es un problema de programación lineal de máximo con variables acotadas en el que se utiliza el método simplex para variables acotadas. En el tercer ejemplo se resuelve un problema lineal de máximo mediante el principio de descomposición para un caso en que las regiones son acotadas. Por último se resuelve un problema de corte de piezas utilizando el método de generación de columnas. El trabajo acaba con el apéndice 2 en el cual se realiza una revisión más general de las aplicaciones de estos métodos en el mundo real, dando ejemplos y analizando su presencia en los trabajos de investigación actuales.

Tipo de Trabajo Académico: Trabajo Fin de Grado