PDF de programación - NUEVOS CRITERIOS DE PARADA EN ALGORITMOS DE OPTIMIZACIÓN

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.1 Introducción................................................................................................................ 1
1.2 Modelos 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.3 Métodos de la PLD...................................................................................................... 8
1.3.1 Métodos de solución de modelos con restricciones difusas.............................. 8
1.3.1.1 Aproximación de Tanaka, Okuda y Asai.............................................. 9
1.3.1.2 Aproximació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.1 Aproximación de Zimmermann............................................................. 12
1.3.2.2 Aproximación de Chanas....................................................................... 14
1.3.2.3 Aproximació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.1 Aproximación de Tanaka y Asai............................................................ 22

i

ÍNDICE

1.3.5.2 Aproximació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.1 Problemas de transporte difusos........................................................... 32
1.4.2.2 Dualidad y análisis de sensibilidad....................................................... 35
1.4.2.3 Programación entera difusa................................................................... 39
1.4.3 Otras extensiones y aplicaciones de la PLD..................................................... 42
1.4.3.1 Programación lineal difusa interactiva................................................. 42
1.4.3.2 Programación estocástica difusa........................................................... 43
1.4.3.3 Aplicaciones específicas de la PLD........................................................ 44
1.4.4 Extensiones y aplicaciones recientes................................................................ 46
1.4.4.1 Programación lineal difusa en gran escala........................................... 46
1.4.4.2 El 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.1 Forma estándar de Karmarkar de programas lineales........................ 81
2.3.3.2 Procedimientos de solución.................................................................... 82
2.3.3.3 Aplicació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 I