Departamento de Ciencias de la Computación e Inteligencia Artificial E.T.S. de Ingeniería Informática UNIVERSIDAD DE GRANADA NUEVOS CRITERIOS DE PARADA EN ALGORITMOS DE OPTIMIZACIÓN TESIS DOCTORAL Edmundo Rubén Vergara Moreno Granada - España 1999 NUEVOS CRITERIOS DE PARADA EN ALGORITMOS DE OPTIMIZACIÓN MEMORIA QUE PRESENTA Edmundo Rubén Vergara Moreno PARA OPTAR AL GRADO DE DOCTOR EN MATEMÁTICAS Mayo de 1999 DIRECTOR José Luis Verdegay Galdeano DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN E INTELIGENCIA ARTIFICIAL E.T.S. de INGENIERÍA INFORMÁTICA UNIVERSIDAD DE GRANADA ESPAÑA La memoria titulada Nuevos Criterios de Parada en Algoritmos De Optimización, que presenta D. Edmundo Rubén Vergara Moreno para optar al grado de Doctor, ha sido realizada en el departamento de Ciencias de la Computación e Inteligencia Artificial de la Universidad de Granada bajo la dirección de D. José Luis Verdegay Galdeano. Granada, Mayo de 1999 El Doctorando El Director E. R. Vergara J. L. Verdegay NUEVOS CRITERIOS DE PARADA EN ALGORITMOS DE OPTIMIZACIÓN Edmundo Rubén Vergara Moreno AGRADECIMIENTOS En estos momentos en que termino de escribir la presente Memoria, invaden mi mente los nombres de todas las personas e instituciones que de una u otra forma me han facilitado alcanzar este anhelo, y a quienes estoy muy agradecido. Sin embargo quiero hacer expreso mi agradecimiento a aquellos que en forma directa me han brindado su ayuda. Mi gratitud al Gobierno Español, quien a través de la Agencia Española de Cooperación Internacional, me otorgó una Beca ICI por el período de tres cursos. Asimismo, a la Facultad de Ciencias Físicas y Matemáticas de la Universidad Nacional de Trujillo-Perú, por haberme concedido la licencia correspondiente, y al Departamento de Ciencias de la Computación e Inteligencia Artificial de la Universidad de Granada por su acogida y por haberme brindado todo el apoyo para llevar a cabo esta Memoria. Mis agradecimientos al Dr. José Luis Verdegay Galdeano por la confianza que depositó en mí, prestándome su asesoramiento y dirección, que durante este tiempo se vio reflejado en sus orientaciones expertas y supervisión constante. Mis agradecimientos al Dr. Salomón Espinoza Quiroz por su apoyo constante y al Dr. Pedro Lavalle, quienes me dieron amplio apoyo para hacer posible mi viaje a España. ÍNDICE ÍNDICE................................................................................................................................. i INTRODUCCIÓN................................................................................................................. vi Capítulo 1: PROGRAMACIÓN LINEAL DIFUSA 1.1Introducción................................................................................................................ 1 1.2Modelos de la PLD...................................................................................................... 5 1.2.1 Modelos con el conjunto factible (restricciones difusas).................................. 5 1.2.2 Modelos con metas difusas................................................................................ 6 1.2.3 Modelos con coeficientes de la función objetivo difusos................................... 7 1.2.4 Modelos con coeficientes tecnológicos y recursos difusos................................. 7 1.2.5 Modelos completamente difusos........................................................................ 7 1.3Métodos de la PLD...................................................................................................... 8 1.3.1 Métodos de solución de modelos con restricciones difusas.............................. 8 1.3.1.1Aproximación de Tanaka, Okuda y Asai.............................................. 9 1.3.1.2Aproximación de Verdegay.................................................................... 10 1.3.2 Métodos de solución de modelos con función objetivo y restricciones difusas.................................. 11 1.3.2.1Aproximación de Zimmermann............................................................. 12 1.3.2.2Aproximación de Chanas....................................................................... 14 1.3.2.3Aproximación de Werners...................................................................... 14 1.3.3 Métodos de solución de modelos con coeficientes de la función objetivo difusos.................................. 15 1.3.3.1 Aproximación de Verdegay ................................................................. 16 1.3.3.2 Aproximación de Tanaka, Ichihashi y Asai........................................ 17 1.3.3.3 Aproximación de Rommelfanger, Hanusheck y Wolf ........................ 18 1.3.4 Métodos de solución de modelos con coeficientes tecnológicos y recursos difusos.................... 19 1.3.4.1 Aproximación de Tanaka, Ichihashi y Asai........................................ 20 1.3.4.2 Aproximación de Delgado, Verdegay y Vila........................................ 21 1.3.5 Métodos de solución de modelos completamente difusos................................. 22 1.3.5.1Aproximación de Tanaka y Asai............................................................ 22 i ÍNDICE 1.3.5.2Aproximación de Carlsson y Korhonen............................................... 25 1.4 Extensiones y aplicaciones de la PLD........................................................................ 27 14.1 Extensiones multiobjetivo................................................................................. 28 14.2 Extensiones uniobjetivo..................................................................................... 32 1.4.2.1Problemas de transporte difusos........................................................... 32 1.4.2.2Dualidad y análisis de sensibilidad....................................................... 35 1.4.2.3Programación entera difusa................................................................... 39 1.4.3 Otras extensiones y aplicaciones de la PLD..................................................... 42 1.4.3.1Programación lineal difusa interactiva................................................. 42 1.4.3.2Programación estocástica difusa........................................................... 43 1.4.3.3Aplicaciones específicas de la PLD........................................................ 44 1.4.4 Extensiones y aplicaciones recientes................................................................ 46 1.4.4.1Programación lineal difusa en gran escala........................................... 46 1.4.4.2El problema de la mochila difuso.......................................................... 57 Capítulo 2: CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL 2.1 Introducción................................................................................................................. 61 2.1.1 Estructura de un algoritmo............................................................................... 63 2.1.2 Criterios de parada clásicos................................................................................ 64 2.1.3 Criterios de parada difusos................................................................................ 65 2.2 Criterios de parada difusos en el algoritmo simplex................................................. 68 2.3 Criterios de parada difusos en el algoritmo de Karmarkar...................................... 78 2.3.1 Introducción........................................................................................................ 78 2.3.2 Ideas básicas....................................................................................................... 78 2.3.3 Algoritmo de Karmarkar................................................................................... 81 2.3.3.1Forma estándar de Karmarkar de programas lineales........................ 81 2.3.3.2Procedimientos de solución.................................................................... 82 2.3.3.3Aplicación en los problemas de PL........................................................ 85 2.3.4 El criterio de parada difuso en el algoritmo de Karmarkar............................ 88 2.4 Criterios de parada difusos en algoritmos modificados de Karmarkar.................... 94 2.4.1 Introducción........................................................................................................ 94 ii ÍNDICE 2.4.2 Modificación propuesta por Vanderbei, Meketon y Freedman........................ 96 2.4.3 Modificación propuesta por Barnes................................................................... 98 2.5 Criterios de parada difusos en algoritmos de puntos interiores.............................. 101 2.5.1 Introducción....................................................................................................... 101 2.5.2 Ideas básicas..................................................................................................... 102 2.5.3 Algoritmos de puntos interiores....................................................................... 105 2.5.3.1 Algoritmo primal................................................................................. 106 2.5.3.2 Algoritmo dual..................................................................................... 106 2.5.3.3 Algoritmo primal-dual....................................................................... 108 2.5.4 Criterio de parada difuso en algoritmos de puntos interiores........................ 109 2.6 Ejemplos numéricos comparativos............................................................................ 113 Capítulo 3: CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PROBLEMA DE LA MOCHILA Y DEL VIAJANTE DE COMERCIO 3.1 Introducción................................................................................................................ 119 3.2 El problema de la mochila ......................................................................................... 119 3.2.1 Formulación y tipos de problemas de la mochila............................................ 121 3.2.2 Cotas superiores del problema de la mochila.................................................. 124 3.2.2.1 Cotas obtenidas mediante relajación................................................. 124 3.2.2.1.1 Relajación continua............................................................. 125 3.2.2.1.2 Relajación lagrangiana....................................................... 127 3.2.2.2 Cota obtenida mediante enumeración parcial................................... 129 3.2.3 Algoritmos de solución del problema de la mochila......................................... 130 3.2.3.1 Algoritmos de aproximación............................................................... 131 3.2.3.1.1 El algoritmo de tipo voraz.................................................. 131 3.2.3.1.2 Algoritmo aproximado de Sahni........................................ 134 3.2.3.2 Algoritmos de ramificación y acotación en PM.................................. 135 3.2.3.3 Algoritmos de la programación dinámica en PM.............................. 142 3.2.3.4 Algoritmo de reducción de Martello y Toth....................................... 148 3.2.4 Criterios de parada difusos en los algoritmos del PM..................................... 151 3.2.4.1 Criterios de parada difusos en los algoritmos de RA en el PM.......... 154 iii ÍNDICE 3.2.4.2 Criterios de parada difusos en los algoritmos de PD en el PM......... 155 3.2.5 Experimentos computacionales........................................................................ 156 3.3 El problema del viajante de comercio........................................................................ 159 3.3.1 Formulación y tipos de TSP.............................................................................. 160 3.3.2 El método de ramificación y acotación en TSP................................................ 163 3.3.2.1 El algoritmo LMSK............................................................................. 166 3.3.3 Cotas del valor óptimo de un TSP.................................................................... 168 3.3.3.1 Cota superior....................................................................................... 169 3.3.3.2 Cota inferior ....................................................................................... 170 3.3.4 Criterios de parada difusos en algoritmos del TSP.......................................... 171 3.3.4.1 El criterio de parada difuso en el algoritmo LMSK.......................... 173 3.3.4.2 Ejemplo numérico............................................................................... 174 COMENTARIOS FINALES........................................................................................... 177 CONCLUSIONES............................................................................................................. 178 LÍNEAS FUTURAS........................................................................................................... 181 BIBLIOGRAFÍA.............................................................................................................. 183 iv INTRODUCCIÓN El hombre es el único ser sobre la faz de la tierra que ha luchado y lucha no sólo por su supervivencia sino para que su estancia sea cada día más placentera. Aunque muchos pasajes de la historia de la humanidad se han caracterizado por la lucha para lograr vivir mejor el presente y lograr la complacencia individual propia, la lucha incesante y de mayor predominancia ha sido por lograr el bienestar futuro y de la sociedad en general. Desde las épocas más remotas en que inicialmente los medios de supervivencia eran la recolección, la caza y la pesca, el hombre no sólo se ha limitado a consumir lo que la naturaleza le ha brindado sino que ha utilizado su inteligencia para aprovecharla de la mejor manera. Al usar su inteligencia fabricó y fabrica aún hoy las herramientas para mejorar sus capacidades, descubrió la agricultura para no esperar que la tierra produjera de manera accidental, descubrió y sigue descubriendo las leyes naturales para luego usar aquellas que son beneficiosas o bien para evitarlas si son perjudiciales. Todo ello es lo que ahora se llama ciencia y tecnología. Como producto de la ciencia y la tecnología, hoy en día, la humanidad cuenta con unas poderosas herramientas y entre ellas están los ordenadores. Los ordenadores son herramientas con capacidades programables ilimitadas en su esencia. Las limitaciones se dan en la programación y en los accesorios necesarios para una determinada tarea. Pueden ejecutar tareas muy simples y repetitivas, tareas arriesgadas u operaciones matemáticas materialmente imposibles para el hombre e incluso actividades de razonamiento propias de la mente humana. Actualmente debido a esas capacidades, los ordenadores constituyen instrumentos de ayuda imprescindibles para los gestores de diversos tipos de instituciones industriales, comerciales, de servicios, etc. en la solución de diversos problemas. Al hablar de las ayudas que proporcionan los ordenadores a los gestores no nos referimos a la ayuda como simples almacenes de documentos personales importantes v