PDF de programación - DISEÑO E IMPLEMENTACIÓN DE UN SISTEMA INTERACTIVO PARA RESOLVER PROBLEMAS DE OPTIMIZACIÓN FUZZY

UNIVERSIDAD DE GRANADA

FACULTAD DE CIENCIAS



Departamento de Ciencias de la Computación

e Inteligencia Artificial



DISEÑO E IMPLEMENTACIÓN

DE UN SISTEMA INTERACTIVO PARA

RESOLVER PROBLEMAS DE

OPTIMIZACIÓN FUZZY



TESIS DOCTORAL



José Manuel Cadenas Figueredo



Granada, 1993



DISEÑO E IMPLEMENTACIÓN DE UN SISTEMA INTERACTIVO

PARA RESOLVER PROBLEMAS DE OPTIMIZACIÓN FUZZY

Jose Manuel Cadenas Figueredo

DISEÑO E IMPLEMENTACIÓN DE UN SISTEMA INTERACTIVO

PARA RESOLVER PROBLEMAS DE OPTIMIZACIÓN FUZZY

MEMORIA QUE PRESENTA

JOSE MANUEL CADENAS FIGUEREDO

PARA OPTAR AL GRADO DE DOCIOR EN CIENCIAS (SECCIÓN INFORMÁTICA)

MAYO 1993

DIRECTOR

DR. D. JOSE LUIS VERDEGAY GALDEANO

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACI ÓN E INTELIGENCIA ARTIFICIAL

FACULTAD DE CIENCIAS

UNIVERSIDAD DE GRANADA

La memoria titulada “Diseño e

Implementación de un Sistema Interactivo

para resolver Problemas de Optimización Fuzzy” que presenta José Manuel Cadenas

Figueredo, para optar al grado de DOCTOR en Ciencias (Sección Informática), ha

sido realizada en el Departamento de Ciencias de

la Computación e

Inteligencia

Artificial de la Universidad de Granada, bajo la dirección del Dr. D. José Luis

Verdegay Galdeano, Catedrático del Departamento en el que

se ha realizado la

memoria.

Granada, Mayo de

1993

Fdo: José Manuel Cadenas Figueredo

Fdo: Dr. D. José Luis Verdegay Galdeano

A mi familia

AGRADECIMIENTOS

Mi agradecimiento a quienes, de un modo u otro, han hecho posible la realización

de esta tesis, especialmente a José Luiz Verdegay Galdeano, sin cuyas ideas, dirección y

entusiasmo esta memoria jamás habría visto la luz y a Francisco Herrera por sus

consejos, apoyo, confianza y hospitalidad. A Fernando Martín que con su constante

aliento y comprensión me ha facilitado enormemente

el desarrollo

de

todo

el

trabajo. A los miembros del Departamento de Ciencias de

la Computación e

Inteligencia Artificial

de

la Universidad

de Granada y a los

compañeros del

Departamento de Informática y Automática de la Universidad de Murcia, al cual

pertenezco, por la ayuda recibida y el grato ambiente de de trabajo.

ÍNDICE

INTRODUCCI ÓN GENERAL

1. CONCEPTOS B ÁSICOS

1.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Métodos de Comparación de Números Fuzzy . . . . . . . . . . . . . . . . . . . .

1.2.1.

Introducción al Concepto de Conjunto Fuzzy . . . . . . . . . . . . . . . .

1.2.2. Números Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3. Formas de Comparar Números Fuzzy . . . . . . . . . . . . . . . . . . . . .

1.2.3.1. Métodos Basados en la Definición de una Función Ordenadora .

VII

1

3

3

4

6

8

9

1.2.3.2. Métodos Basados en la Comparación de Alternativas

. . . . . .

13

1.2.3.3. Métodos Basados en una Relación de Preferencias . . . . . . . .

14

1.3. Programación Lineal Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

1.3.1. Programación Lineal con Restricciones Fuzzy . . . . . . . . . . . . . . . .

18

1.3.2. Programación Lineal con Costos Fuzzy . . . . . . . . . . . . . . . . . . . .

19

1.3.3. Programación Lineal con Números Fuzzy en la Matriz Tecnológica . . . .

20

1.4. Métodos de Resolución para Problemas de PL Paramétrica . . . . . . . . . . . .

21

1.4.1. Programación Lineal con Coeficientes Intervalares en la Función Objetivo

21

1.4.2. Programación Lineal con Parámetros Grey . . . . . . . . . . . . . . . . .

26

ii

2. UN MODELO TE ÓRICO GENERAL DE PLF

31

2.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.2. Programación Lineal Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.2.1. Problemas de Programación Lineal con Restricciones Fuzzy . . . . . . . .

35

2.2.2. Problemas de Programación Lineal con Coeficientes Fuzzy . . . . . . . . .

38

2.2.3. Problemas de Programación Lineal con Costos Fuzzy . . . . . . . . . . . .

39

2.3. Un Modelo General de Programación Lineal Fuzzy . . . . . . . . . . . . . . . . .

41

2.4. Método de Resolución del Modelo General de Programación Lineal Fuzzy . . . .

43

2.4.1. Resolución del Modelo General

. . . . . . . . . . . . . . . . . . . . . . . .

45

2.4.1.1. Funciones Homogéneas Lineales Fuzzy . . . . . . . . . . . . . . .

46

2.4.1.2. Funciones Ordenadoras Lineales en el Objetivo . . . . . . . . . .

50

2.4.1.3. Funciones Ordenadoras no Lineales en el Objetivo . . . . . . . .

53

2.4.1.4. β-cortes en el Objetivo . . . . . . . . . . . . . . . . . . . . . . .

54

3. MÉTODOS DE RESOLUCI ÓN EN PLF

59

3.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.2. Modelos con Restricciones Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.2.1. Aproximación de Tanaka . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.2.2. Aproximación de Zimmermann . . . . . . . . . . . . . . . . . . . . . . . .

62

3.2.3. Aproximación de Verdegay . . . . . . . . . . . . . . . . . . . . . . . . . .

64

3.3. Modelos con Costos Fuzzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

3.3.1. Métodos de Resolución que utilizan el Teorema de Representación . . . .

67

3.3.1.1. Aproximación multiobjetivo.

. . . . . . . . . . . . . . . . . . . .

67

3.3.1.2. Haciendo uso de la Aritmética Intervalar. . . . . . . . . . . . . .

71

3.3.1.3. Aproximación Posibilística.

. . . . . . . . . . . . . . . . . . . . .

74

3.3.1.4. Aproximación por Reducción Estratificada a Trozos. . . . . . . .

76

3.3.2. Métodos de Resolución que se basan en la Comparación de Números Fuzzy 80

ÍNDICE

iii

3.3.2.1. Métodos de Alternativas Optimales

. . . . . . . . . . . . . . . .

81

3.3.2.2. Funciones Ordenadoras Lineales . . . . . . . . . . . . . . . . . .

83

3.3.2.3. Funciones Ordenadoras No Lineales . . . . . . . . . . . . . . . .

87

3.3.2.4. Usando una relación de preferencias . . . . . . . . . . . . . . . .

88

3.4. Dualidad en Programación Lineal Fuzzy . . . . . . . . . . . . . . . . . . . . . . .

92

3.5. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

4. PROBO: UN SISTEMA INTERACTIVO

DE AYUDA A LA DECISI ÓN

101

4.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.2. Análisis y Diseño de Probo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.2.1. Herramientas de programación . . . . . . . . . . . . . . . . . . . . . . . . 108

4.2.2. Manejo del Sistema

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.2.3. Estructura de PROBO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.2.3.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.2.3.2. Núcleo Principal del programa. Procedimientos y Funciones . . . 116

Núcleo Principal del Programa PROBO . . . . . . . . . . . . . . 116

Procedimientos y Funciones del Módulo Inicial

. . . . . . . . . . 121

Procedimientos y Funciones del Módulo CLASIC . . . . . . . . . 149

Procedimientos y Funciones del Módulo COS-DIF . . . . . . . . 152

Procedimientos y Funciones del Módulo RES-DIF . . . . . . . . 161

Procedimientos y Funciones del Módulo GEN-DIF . . . . . . . . 170

COMENTARIOS FINALES

BIBLIOGRAFÍA

APÉNDICE

175

179

189

Programas de ordenador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

INTRODUCCI ÓN GENERAL

INTRODUCCI ÓN GENERAL

vii

Los conceptos tradicionales de optimalidad, fundamentalmente los referidos al caso de

M ax f (x) con x ∈ X, están caracterizados por esquemas escalares basados en la unicidad
de sus soluciones y en una hipótesis de información completa. Son, por tanto, más que limitados

para captar la riqueza y la complejidad del modo de resolver y plantear los problemas de deci-

sión y optimización de los seres humanos. Sin embargo, inexplicablemente, todos esos conceptos

siguen anclados en sus definiciones clásicas en los respectivos campos de aplicación de la Inge-

niería, la Economía, las Matemáticas, la Inteligencia Artificial y demás disciplinas directamente

relacionadas con la optimización.

Conceptualmente, el modelo tradicional de optimización es simple e inambiguo. No obstante,

y a pesar de que a menudo se le usa como representación bien estructurada de realidades mal

estructuradas, las personas, como decisores en general, cotidianamente tratan la realidad con

toda la complejidad que ésta tiene, recurriendo muy de vez en cuando a tales mecanismos de

representación simplificada, que para casi nada le son necesarios dado el sentido común que

poseen.

viii

¿Que es la optimización? Cualquier problema bien estructurado tiene una solución uni-

dimensional bien estructurada: el más corto, el más seguro o el más beneficioso camino a través

del laberinto. Encontrar tal camino (solución) puede resultar sencillo o difícil, pero siempre es

deducible de la estructura dada (el laberinto), es decir, esa solución siempre está ahí, esperando

a ser calculada, y por tanto, en este sentido, por optimización entenderíamos búsqueda. Pero,

por otro lado, ¿qué es el camino optimal entre A y B? ¿Es simplemente el mejor camino entre

los ya existentes (que, incluyendo al mejor, podrían ser bastante malos), o nos referimos a la

construcción de un nuevo camino que resultara optimal? ¿Quién es el optimizador? ¿Es una

persona que elige lo mejor entre lo que le dan? ¿O es una persona que construye o crea lo mejor

“de novo”?

Como es fácil apreciar, todas estas preguntas y sus correspondientes respuestas, están pla-

gadas de conceptos ambiguos, con múltiples posibilidades inter