Un método símplex en programación lineal multiobjetivo

Abstract

En este Trabajo Final de Grado se estudia el algoritmo símplex multiobjetivo propuesto por Ehrgot en [1] para calcular las soluciones eficientes de un problema de optimización lineal multiobjetivo. El Capítulo 1 contiene de forma resumida el conocido método símplex introducido por Dantzig en 1947 para resolver problemas de optimización lineales. Además del algoritmo símplex y su variante de las dos fases, se estudian resultados y definiciones de programación lineal que luego serán utilizados para el método símplex que se expondrá en el Capítulo 3. En el Capítulo 2, se hace una introducción a los problemas de optimización mulitobjetivo, es decir, problemas donde se tiene más de una función para optimizar simultáneamente. Se muestra que los puntos eficientes son las "soluciones" de este tipo de problemas y los puntos no dominados son lo análogo a los valores óptimos de las funciones objetivo en los problemas de optimización uniobjetivo. También se explica el método escalar de suma ponderada que permite resolver problemas de optimización multiobjetivo resolviendo en su lugar uno con un solo objetivo. Este capítulo concluye con la exposición de otros métodos para resolver problemas de optimización multiobjetivo entre los que destaca el método de Benson. En el Capítulo 3 se estudian los problemas de optimización lineales multiobjetivo. Tras definir este tipo de problemas y sus puntos eficientes y no dominados, se introducen y demuestran los principales teoremas que permiten justificar el método símplex multiobjetivo. Se explicará el algoritmo símplex multiobjetivo que permite calcular las soluciones eficientes básicas de un problema de optimización lineal multiobjetivo. Este algoritmo se basa en tres fases. En la primera se determina si el problema es o no factible, si es factible, en la segunda fase se determina si el conjunto de puntos eficientes es vacío o no. Por último, si el conjunto de puntos eficientes no es vacío se calculan todas las bases eficientes para caracterizar dicho conjunto. También se ve un ejemplo de resolución de un problema mediante el uso de dicho algoritmo. Por último, en el Capítulo 4 se implementa el algoritmo símplex multiobjetivo con el sofware Xpress. Se comprueba su funcionamiento con varios problemas test y se exponen las conclusiones de dichas pruebas.