Nuevos Criterios en Optimización Algorítmica
Nuevos Criterios en Optimización Algorítmica
Artificial
E.T.S. de Ingeniería Informática
UNIVERSIDAD DE GRANADA
TESIS DOCTORAL
Granada - España
1999
NUEVOS CRITERIOS DE PARADA
EN ALGORITMOS DE OPTIMIZACIÓN
Mayo de 1999
DIRECTOR
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.
El Doctorando El Director
E. R. Vergara J. L. Verdegay
NUEVOS CRITERIOS DE PARADA
EN ALGORITMOS DE OPTIMIZACIÓN
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
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
[Link] Aproximación de Tanaka, Okuda y Asai.............................................. 9
[Link] Aproximación de Verdegay.................................................................... 10
1.3.2 Métodos de solución de modelos con función objetivo
y restricciones difusas.................................. 11
[Link] Aproximación de Zimmermann............................................................. 12
[Link] Aproximación de Chanas....................................................................... 14
[Link] Aproximación de Werners...................................................................... 14
1.3.3 Métodos de solución de modelos con coeficientes
de la función objetivo difusos.................................. 15
[Link] Aproximación de Verdegay ................................................................. 16
[Link] Aproximación de Tanaka, Ichihashi y Asai........................................ 17
[Link] 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
[Link] Aproximación de Tanaka, Ichihashi y Asai........................................ 20
[Link] Aproximación de Delgado, Verdegay y Vila........................................ 21
1.3.5 Métodos de solución de modelos completamente difusos................................. 22
[Link] Aproximación de Tanaka y Asai............................................................ 22
i
ÍNDICE
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
[Link] Forma estándar de Karmarkar de programas lineales........................ 81
[Link] Procedimientos de solución.................................................................... 82
[Link] 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
iii
ÍNDICE
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
INTRODUCCIÓN
sino como sistemas complejos que involucran diversas acciones concertadas de órganos
con gran impacto potencial en la efectividad de las decisiones gerenciales.
El desarrollo e incluso la supervivencia o la quiebra de las grandes organizaciones
públicas y privadas dependen de las decisiones que deben tomar sus administradores;
decisiones que en muchos casos deben ser tomadas de una manera rápida e inteligente.
Durante muchos años se ha considerado que la toma de decisión era un arte, de tal
manera que se podía usar una gran variedad de estilos individuales en la solución
aproximada de problemas gerenciales similares. Estos estilos han estado basados
frecuentemente en la creatividad, el juicio, la intuición y la experiencia más que en
métodos sistemáticos cuantitativos o en aproximaciones científicas.
Sin embargo en la actualidad, en el ambiente rápidamente cambiante y cada vez
más complejo en que vivimos, la toma de decisiones se hace más difícil por dos razones:
primero, debido a las tecnologías y los sistemas de comunicación altamente
desarrollados, el número de alternativas disponibles es muy elevado, y segundo, porque
el costo de los errores cometidos puede ser muy grande como consecuencia de la
complejidad y la magnitud de operaciones, la automatización y la reacción en cadena que
un error puede generar en muchas partes de una organización. Por el contrario, los
beneficios pueden ser extremadamente grandes cuando las decisiones tomadas son
acertadas.
En un ambiente caracterizado por factores tecnológicos en constante crecimiento,
dentro de una estructura compleja, y en un mercado internacional de competición, la
toma de decisiones se hace cada vez más sofisticada y por tanto requiere del uso de las
tecnologías que se están desarrollando. Más aún, se requieren mejores tecnologías como
herramientas de ayuda en la toma de decisiones.
Las tecnologías de sistemas de ayuda a esa toma de decisiones que se están
desarrollando [197] son: Sistemas Soporte de Decisión (SSD), Sistemas Soporte de
Decisión en Grupo (SSDG), Sistemas de Información Ejecutiva (SIE), Sistemas Expertos
(SE), Redes Neuronales Artificiales (RNA) y Sistemas Soporte Híbridos (SSH). La
aplicación de estas tecnologías se denomina en conjunto "sistemas de ayuda en la
administración".
Según Simon [180], el proceso de la toma de decisión, en forma general, se realiza
en un rango continuo de decisiones que varía entre las estructuradas y las no
estructuradas, entendiéndose por una situación estructurada o llamada también
vi
INTRODUCCIÓN
programada aquella que tiene un contexto con elementos y relaciones entre ellos que son
o pueden ser completamente conocidos o determinados.
Según Gorry y Scott-Morton [76], para la toma de decisiones en un ambiente
estructurado es suficiente hacer uso de SIE, de modelos de investigación de operaciones,
etc. porque el carácter estructurado sólo está presente en administraciones de bajo nivel,
mientras que en el caso de situaciones semi-estructuradas o no estructuradas es
necesario el uso de SSD, SSDG, RNA o SSH, de acuerdo al caso; estas situaciones son
propias del nivel funcional de los altos ejecutivos y profesionales altamente
especializados en problemas complejos.
De entre los sistemas de ayuda a la toma de decisiones citados más arriba,
destacan por su importancia los SSD. El concepto involucrado en los SSD fue articulado
por primera vez en 1971 por Scott-Morton, quien los entendió como sistemas interactivos
basados en computación que ayudan al decisor a utilizar los datos y los modelos para
resolver problemas no estructurados. Otra definición de Keen y Scott-Morton [101] dice
que los SSD unen los recursos intelectuales de los individuos con las capacidades de los
ordenadores para mejorar la calidad de las decisiones en problemas semiestructurados o
no estructurados.
A partir de éstas y otras definiciones podemos resumir que un SSD es un sistema
de ayuda en la toma de decisiones en situaciones en el que los datos y/o sus relaciones no
son conocidos exactamente, o no pueden ser determinados con exactitud. Los
componentes básicos de un SSD [197] son el Sistema de Gestión de la Base de Datos
(SGBD), el Sistema de Gestión de la Base de Modelos (SGBM) y el Sistema de Gestión y
Generación de Diálogos (SGGD).
Un buen SSD será aquél en que cada uno de sus componentes tenga la mejor
capacidad posible y al mismo tiempo estén bien integrados entre sí. Decir que los
componentes de un SSD tengan la mejor capacidad posible significa que el SGBD debe
tener la capacidad de tratar una gran variedad de estructuras de datos que permitan el
manejo de datos probabilísticos, incompletos e imprecisos; que el SGBM sea capaz de
simular diversas situaciones reales y finalmente, que el SGGD tenga la suficiente
capacidad de admitir, transmitir y reportar todo tipo de información entre el usuario y el
SSD.
Un buen SGBM debe proporcionar la capacidad de implementar diversas
posibilidades de realizar análisis sofisticados y diversas capacidades de interpretación;
vii
INTRODUCCIÓN
viii
INTRODUCCIÓN
modelos y sus respectivos métodos de solución existentes dejan un campo abierto por
modelar y donde plantear los correspondientes métodos de solución. Porque los modelos y
métodos conocidos o bien no representan a la realidad o bien sus métodos de solución
presentan limitaciones muy serias.
De esta amplitud de problemas dentro de la asignación de recursos limitados y del
control de acciones cambiantes con el tiempo, vamos a prestar atención sólo a dos
situaciones:
1) cuando los datos no se conocen exactamente, es decir, cuando los datos son imprecisos
y se está en un ambiente semi-estructurado, y
2) cuando los métodos de solución existentes que sirven para casos simples presentan
limitaciones o simplemente no se pueden utilizar en casos complejos.
Estos dos aspectos del SGBM de un SSD, que son de trascendental importancia en
la actualidad, han captado nuestra atención y han constituido el motor de desarrollo del
presente trabajo cuya presentación hacemos en tres capítulos.
En el primer capítulo, se aborda una revisión de la Programación Lineal Difusa, en
la que se recogen los principales modelos y sus respectivos métodos de solución. Se
detallan dos o tres de los más importantes métodos y se hace un comentario de otros.
ix
INTRODUCCIÓN
x
INTRODUCCIÓN
xi
Capítulo 1
1.1 INTRODUCCIÓN
Dentro de una economía del bienestar, existe un problema simple pero de mucha
importancia cuando se tienen unas cantidades dadas de varios factores de producción y
cierto número de tareas a las que aquéllos se pueden destinar. Estos factores de
producción pueden ser asignados a las diferentes tareas, por lo general de muchas
maneras distintas, con resultados diversos.
1
PROGRAMACIÓN LINEAL DIFUSA
m
max z c jxj
j 1
m
sujeto a : a j 1
ij x j bi , i 1,..., m (1.1a)
xj 0, j 1,.., n
2
1.1 INTRODUCCIÓN
max z cx
s. a : Ax b (1.1b)
x0
donde
Uno de los problemas que sirvieron para explicar el procedimiento del método
simplex fue el problema de la dieta, planteado por Jerome Cornfield en 1941 (planteado
en un memorandum no publicado, pero resuelto por primera vez mediante la
programacíon lineal por Stigler, [54]). La importancia de este problema radica en su
aplicabilidad práctica dentro de la economía, como por ejemplo en la teoría del consumo.
Otros campos de la economía donde se aplica la PL son la teoría del equilibrio [54], el
análisis insumo-producto, etc. En general, la PL tiene su aplicación en todas aquellas
situaciones que se presentan tanto en empresas individuales como colectivas, nacionales
e internacionales, e incluso en otros ámbitos, en las que se desea determinar el mejor
plan para alcanzar unos objetivos determinados pero utilizando los recursos disponibles
muy limitados.
3
PROGRAMACIÓN LINEAL DIFUSA
Esto se debe a que la PL desarrollada por Dantzig opera con parámetros conocidos.
Sin embargo, en los problemas actuales no se conocen con precisión muchos parámetros,
y por tanto, no se pueden utilizar un modelo y un método diseñados sólo para abarcar
parámetros precisos. En el caso de seguir utilizando la PL cuando los parámetros no son
precisos tendríamos que presuponer que son exactos (lo cual no expresa la realidad), y
los resultados obtenidos de este modo no serían fiables.
El mismo Zadeh junto con Bellman [13] en 1970, desarrolló una primera aplicación
de la teoría difusa en la PL en su artículo “Toma de decisión en ambiente difuso”. Pero
fueron Tanaka, Okuda y Asai [190] en 1974, seguido por Zimmermann [222], Negoitia y
Sulari [147] en 1976, quienes publicaron los primeros trabajos de aplicación de la teoría
difusa en la PL, dando origen así a lo que se ha dado en llamar la programación lineal
difusa (PLD). Posteriormente se han hecho múltiples estudios sobre este nuevo campo.
4
1.2 MODELOS DE LA PLD
Los modelos de PLD se pueden clasificar con arreglo a muy diversos criterios, por
ejemplo, teniendo en cuenta la forma de los modelos, los métodos de solución, o el tipo de
parámetros. Al hacer una revisión de la literatura existente se ha elaborado una
clasificación de los modelos de PLD, basándonos fundamentalmente en la clasificación
que realizan Verdegay [204] y Lai y Hwang [105], en modelos con el conjunto factible
difuso, modelos con metas difusas, modelos con coeficientes de la función objetivo
difusos, modelos con coeficientes de la matriz tecnológica y recursos difusos, y modelos
completamente difusos.
Desde el punto de vista general, un conjunto difuso puede ser definido de diferentes
maneras. Sin embargo, en este contexto el conjunto factible difuso se deriva de
considerar los recursos imprecisos, es decir, debido a que los recursos no son conocidos
con precisión. En tal situación, para cada recurso, se considera una cantidad deseable b,
pero se acepta la posibilidad de que sea mayor hasta un tope máximo b+t (t es
denominado nivel de tolerancia). Un modelo que incluye las restricciones con estas
característica se representa de la siguiente forma:
max z cx
s. a Ax f b (1.2)
x0
donde el símbolo “f“ indica la imprecisión de las restricciones y significa que para cada
restricción i, dado el nivel de tolerancia ti, a cada punto(vector n-dimensional) x se le
asocia un número i(x) [0,1] denominado grado de cumplimiento de la restricción i
definido por:
1 ( Ax) i bi
i ( x) f i (( Ax) i ) bi ( Ax) i bi t i (1.3)
0 ( Ax) i bi t i
5
PROGRAMACIÓN LINEAL DIFUSA
donde f(.) [0,1], es una función continua y monótona no creciente. Si i = i(x), para
i=1,...,m, y x fijo, entonces min i es el grado de cumplimiento de las restricciones
i 1,..,n
Un modelo de PLD con meta difusa es aquel cuyo conjunto meta es difuso, es decir,
que admite que el valor de la función objetivo sea ligeramente inferior a la meta mínima
cuando se trata de un problema de maximización, y análogamente para el de
minimización. El modelo correspondiente se expresa de la siguiente manera:
ma~x z cx
s. a Ax b (1.4)
x 0
Si t0 es la cantidad máxima en que la función objetivo debe ser inferior a la meta mínima
c0, entonces a cada vector x se le asocia un número 0(x), que representa el grado en que
el decisor considera que se alcanza la meta, definido mediante la función siguiente:
1 cx c 0
0 ( x) f (cx) c 0 t 0 cx c 0 (1.5)
0 cx c 0 t 0
donde f(.) [0,1] es una función continua monótona no decreciente.
6
1.2 MODELOS DE LA PLD
donde el símbolo “ f ” es una relación de orden cuya expresión lingüística es “casi menor
o igual que” o “esencialmente menor que” entre números difusos, que es una extensión de
la relación de orden ““ definida en los número crips.
Estos modelos constituyen el caso general donde todos los parámetros son
imprecisos, su representación general es el siguiente:
7
PROGRAMACIÓN LINEAL DIFUSA
max z c~x
~ ~
s. a. A x f b (1.8)
x f
0
Las funciones de pertenencia de todos los números difusos que aparecen en estos
modelos que hemos citado, se especifican en el apartado siguiente (1.3) donde se abordan
los correspondientes métodos de solución.
Existen varios métodos de solución para cada uno de los modelos presentados en la
sección anterior. Las diferencias entre ellos se dan o bien en la forma de representación
de los parámetros difusos o bien en el procedimiento mismo. Como es natural, hacemos
revisión, con un poco de detalle, sólo de los métodos más importantes y comentamos
brevemente los otros. Puesto que la información en dichos modelos es imprecisa, también
la solución obtenida será imprecisa, obteniéndose en consecuencia, no soluciones en el
sentido tradicional, sino soluciones difusas.
8
1.3 MÉTODOS DE LA PLD
Este es el método que se utilizó por primera vez (1974) para resolver el modelo (1.2)
correspondiente a la PLD con restricciones difusas.
En esta aproximación, la función f mencionada en (1.3) es lineal, por lo que la
función de pertenencia quedaría reflejada de la siguiente manera:
1 ( Ax) i bi
(( Ax) i bi )
i ( x) 1 bi ( Ax) i bi t i (1.9)
ti
0 ( Ax) i bi t i
y cuya gráfica se muestra en la Figura 1.1
u(x)
1
0 ,5
0
b b+t
Ax
Esta aproximación concluye que la solución óptima del modelo (1.2) está dada por
la pareja
(*,x*) (0,1] x Rn,
tal que
* f ( x*) sup max f ( x)
xX
donde: f : Rn [0,1] es la función objetivo normalizada como sigue :
1 cx M
f ( x) cx ( 1.10)
M cx M
9
PROGRAMACIÓN LINEAL DIFUSA
con M el valor de solución óptima del modelo (1.2) sin considerar la difusidad de las
restricciones; y
X = { x n/ i i(x) }, [0,1].
2) Calcular: f k máx { f ( x) / x X k }
5) Hacer * k y determinar un óptimo x* n tal que f(x*) = max {f(x) / x X*}.
Lo ideal es hallar la solución óptima para i(x)=1, i=1,..,m; sin embargo, sería
aceptable obtener una solución para algún valor i(x) mayor que un entendida como
nivel de satisfactibilidad mínimo fijada a priori de acuerdo con la naturaleza del
problema, y lo que es fundamental, en interacción con el decisor.
10
1.3 MÉTODOS DE LA PLD
( Ax) i bi
1 o ( Ax) i b i (1 - )t i , i.
tt
x(r 1 ( ))
1
donde r (.) g ( f (.)) .
11
PROGRAMACIÓN LINEAL DIFUSA
Puesto que el valor de la función objetivo depende del dominio, conjunto factible en
este caso, su característica difusa puede ser debido a la imprecisión de las restricciones o
debido a la imprecisión de su meta. En consecuencia pueden darse dos situaciones, una
en que no se conoce a priori la meta ni su tolerancia, y otra, cuando se conoce la meta, la
tolerancia y la función de pertenencia; para el primer caso tenemos la aproximación de
Zimmermann y para el segundo caso tenemos por un lado la aproximación de Chanas y
por otro lado la aproximación de Werners.
donde las restricciones difusas están definidas por las funciones de pertenencia lineales
que se expresan a continuación:
1 si cx b0
(b cx)
0 ( x) 1 0 si b0 t 0 cx b0 (1.14)
t0
0 cx b0 t 0
si
12
1.3 MÉTODOS DE LA PLD
1 si ( Ax) i bi
(( Ax) i bi )
i ( x) 1 si bi ( Ax) i bi t i (1.15)
ti
0 si ( Ax) i bi t i
u(x) u(x)
1 1
0,5 0,5
0
b-t b
cx 0
b b+t
Ax
Fig. 1.2: Función de pertenencia de la función objetivo. Fig. 1.3: Funciones de pertenencia de las restricciones.
max
tal que cx b0 (1 )t 0
(1.17)
( Ax) i bi (1 )t i , i
x 0 y 0,1
un modelo paramétrico de tipo clásico, que se puede resolver mediantes métodos clasicos.
13
PROGRAMACIÓN LINEAL DIFUSA
Chanas (1983) [35] considera que, debido al poco conocimiento de la región factible
difusa, la meta b0 y la tolerancia t0 de la función objetivo difusa no podrían ser
especificadas inicialmente, por lo tanto se tendrían que determinar con la ayuda del
decisor. Para ello, primeramente hay que resolver (1.12), sin considerar la difusidad de la
función objetivo, es decir, hay que resolver el modelo equivalente a (1.11).
Si el modelo (1.11) tiene alguna solución factible, entonces para cada número ,
existe x*() (solución óptima), y una restricción con grado de cumplimiento 1-, es decir,
Luego, utilizando estas soluciones z(x*()) y x*(), el decisor podrá elegir la meta b0, la
tolerancia t0, y construir la correspondiente función de pertenencia que define la función
objetivo difusa dada en el modelo (1.12). Así, se obtiene dicha función de pertenencia, la
cual depende de , definida de la siguiente manera:
1 si cx * ( ) b0
(b cx * ( ))
0 ( x * ( )) 1 0 si b0 t 0 cx * ( ) b0 (1.19)
t0
0 cx * ( ) b0 t 0
si
14
1.3 MÉTODOS DE LA PLD
z0 = max cx z1 = max cx
s.a. (Ax)i bi i s.a. (Ax)i bi+ti i
x0 x0
15
PROGRAMACIÓN LINEAL DIFUSA
que por cierto tienen multiples formas, y de la forma como se relacionan éstas. La
diferencia entre los métodos de solución de modelos de la forma (1.6) propuestos radican
en estas dos características, que son la forma como se representan los coeficientes difusos
y la forma como se relacionan para representar la función objetivo difusa.
Sin embargo, de aquí en adelante, cuando se trabaja con los coeficientes que son
números difusos, se presentan algunas diferencias con los métodos anteriores debido a
que los números difusos no se conciben de una manera única. Esta situación conduce a la
existencia de métodos generales que engloban todas las concepciones, y otros métodos
particulares en las que se utilizan números difusos con caracterísiticas particulares.
Esta misma idea, Delgado, Verdegay y Vila [53], la aplican para el caso en que cada
coeficiente está definido por una función de pertenencia de la siguiente manera:
0 si x a j o x b j
j : R 0,1, j ( x ) h j ( x ) si a j x c j
h j ( x ) si c j x b j
16
1.3 MÉTODOS DE LA PLD
Puesto que
j ( x) 1 h j 1 (1 ) x h j 1 (1 )
max
c1 x, c 2 x, ..., c N x
sujeto a : Ax b, x 0 (1.22)
c k (d1 , d 2 ,..., d n ), k 1,..., N , N 2n
Esta aproximación considera que los coeficientes de la función objetivo son números
difusos triangulares. También la función objetivo se considera un número difuso y con la
función de pertenencia definida así:
17
PROGRAMACIÓN LINEAL DIFUSA
1 | 2 y ( a b ) x | (b a ) x , si x 0, y 0
( y ) 1 si x 0, y 0
0 si x 0, y 0
donde b = (b1, b2,..., bn) y a = (a1, a2,..., an) tal que (aj, cj, bj) es la representación
triangular del número difuso c~ j. j
de tipo clásico.
Estos autores representan los coeficientes difusos de la función objetivo por medio
intervalos anidados, determinados por los grados de pertenencia k(0,1], kM = {1, 2, ...
,p} como sigue:
c~ j c j k , c j k : k 0,1 , k M , j 1,..., n
(1.24)
tal que
1 , 2 0,1, 1 2 c j 1 , c j 1 c j 2 , c j 2 (1.25)
Sea D = { x n / Ax b, x 0 } y
z max c ( x max
*
) máx c x / x D ,
z min c ( x min
*
) mín c x / x D .
18
1.3 MÉTODOS DE LA PLD
Definamos ahora
c x z min
f 1 (c x )
si z min c x z max
z max z min
c x z min
f 2 (c x )
si z min c x z max
z max z min
max
sujeto a : f 1 (c x ) ; f 2 (c x ) (1.26)
Ax b, x 0, 0
Ax b, x 0, 0.
entonces,
f1 (c x* ) f 2 (c x* ) *
19
PROGRAMACIÓN LINEAL DIFUSA
Debido a que existen muchos métodos de ordenación de los números difusos, el uso
de cada uno en particular puede generar un modelo y un tipo de aproximación. Por otro
lado, aún dentro de cada relación de orden, el cumplimiento de las restricciones puede
tener o no una determinada tolerancia.
Para definir la relación de orden en el conjunto de los números difusos, hay que
especificar a priori un número (0,1] denominado grado de optimismo, y entonces, la
relación de orden sería la siguiente:
a~ b (a a ) r (b b ) r (a a ) r (b b) r r ,1
~
(1.28)
max : cx
s. a :
1 2 ai a i 2 ai a i x 1 2 bi b i 2 bi b i
(1.29)
1 2 ai ai 2 ai ai x 1 2 bi bi 2 bi bi
x0
20
1.3 MÉTODOS DE LA PLD
Si ~
ti es la tolerancia en la restricción i, interpretada como en la sección 1.3.1, y con
max z cx
n
~
s. a. a~ij x j f ti (1 ) i 1,...m
bi ~ (1.31)
j 1
x 0, 0,1
21
PROGRAMACIÓN LINEAL DIFUSA
Tanaka y Asai (1984) [187] proponen un método de solución para los problemas con
metas cuyos coeficientes son números difusos y, a su vez, las metas son también difusas.
Esta situación queda mejor expresada de la siguiente manera:
hallar x
que satisfaga las siguientes restricciones:
22
1.3 MÉTODOS DE LA PLD
o a las restricciones
~ ~
Y~1 B
~x A
1 0 11 x1 A1n x n 0,
f
~ ~
Y~2 B
~ x A
2 0 21 x1 A2 n x n 0
f
(1.34)
~ ~
Y~i B
~x A
i 0 i1 x1 Ain x n 0
f
~ ~
Y~M B
~ x A
M 0 M 1 x1 AMn x n 0
f
donde
~ ~
~ p i , i l ~ cij , i l
M l m, x 0 1, x j 0, Bi ~ y Aij ~ , i 1,2,..., M , j 1,..., n
bi l , i l a ij , i l
~ ~ ~ ~
Ai ( Bi Ai1 Ain ) { i ( i 0 in ) t , ci (ci 0 cin )}
~ ~
La expresión difusa Yi Ai x, está definida mediante la siguiente función de pertenencia:
y x t i
1 , si x 0,
ci t x
Yi ( y ) 1, si x 0, y 0, (1.36)
0, si x 0, y 0,
0, si ci t x y x t i
donde x ( x0 ,, xn ) t
Todos los números difusos que Tanaka y Asai consideran, son triangulares simétricos
representados por (,c) con soporte [-c,+c], mientras que la llamada condición de no
23
PROGRAMACIÓN LINEAL DIFUSA
negatividad difusa, que corresponde al término lingüístico "casi positiva", de los números
difusos en (1.34) o (1.35), la definen de la siguiente manera:
it x
Yi (0) 1 t
1 h, i t x 0, i 1,2, , M (1.38)
ci x
que equivale a
( i hci ) x 0, i 1, 2, , M (1.39)
luego el problema se reduce a hallar el mayor valor h y x que satisfagan (1.39), es decir,
(1.32) es equivalente a:
max h
s. a : ( i hci ) t x 0, i 1, 2, , M (1.40)
x 0, 0 h 1
Debido a que las restricciones son no lineales (por el producto h y x), Tanaka y Asai
proponen el siguiente algoritmo para resolverlas:
Algoritmo:
1) Determinar un valor inicial pequeño h tal que exista un conjunto factible que
satisfaga (1.40)
2) Sea >0 un pequeño incremento. Encontrar el más pequeño valor h+(k+1) no
compatible con (1.40), k = 0, 1, 2, ....
3) Para el valor h+k, en el sistema compatible (1.40), seleccionar la desigualdad más
interesante. Si eligió la desigualdad j, considere J=j1x1+...+jnxn, como función
objetivo auxiliar; luego, resolver:
24
1.3 MÉTODOS DE LA PLD
max J
s. a : ( i (h k )ci ) x 0, i 1,2,..., M (1.41)
x0
max z = cx
s. a: Ax b, x 0
Este resultado les permite considerar el problema (1.8), de tal manera que sus
parámetros difusos están definidos mediante funciones de pertenencia monótonamente
decrecientes.
En general, estas funciones de pertenencia pueden ser lineales o no lineales.
Carlsson y Korhonen prefieren una función de pertenencia exponencial, debido a que las
funciones exponenciales son muy flexibles, así si p representa a cualesquiera de los
parámetros difusos, su función de pertenencia es:
1 t p0
t p1
p (t ) a p 1 exp b p ( 0 )
1
p 0 t p1 (1.42)
p p
0 t p1
donde
1
ap y bp 0
1 exp(b p )
25
PROGRAMACIÓN LINEAL DIFUSA
c A b (1.43)
max c1 ( ) x
s.a. A1 ( ) x 1
b ( ) (1.44)
x 0, 0,1
Este modelo es un modelo paramétrico no lineal que puede resolverse usando para
parámetros fijos (que en este caso se transforma en un modelo lineal simple). Así se
genera un conjunto de soluciones con distintos valores del parámetro que constituyen un
conjunto de alternativas de solución para el decisor.
Al igual que para los otros modelos estudiados anteriormente, para los modelos
completamente difusos existen otros métodos que no son del todo diferentes a estos dos
métodos que acabamos de resumir. En la aproximación de Tanaka y Asai se utilizan los
números difusos triangulares, mientras que en el de Carlsson y Korhonen se abarcan
casos generales. Ramik y Rommelfanger [157] presentan un método que, comparado con
26
1.3 MÉTODOS DE LA PLD
el método propuesto por Tanaka y Asai viene a ser una extensión del mismo, y
comparado con el de Carlsson y Korhonen, constituiría una particularización del método
propuesto por estos autores. Ramik y Rommenlfanger proponen un método de solución
para el caso en el que los parámetros sean números difusos trapezoidales; desarrollando
este mismo método con mayor detalle para los números difusos trapezoidales rectos, e
introducen dos nuevos métodos de comparación de números difusos trapezoidales para
interpretar las restricciones difusas. Trabajos similares han realizado Nakamura y Gen
[143] quienes definen otras relaciones de igualdad y desigualdad de números difusos
trapezoidales y luego las utilizan para resolver problemas de PL completamente difusos
cuyos parámetros son números difusos trapezoidales.
Desde que en 1974 Tanaka, Okuda y Asai [190] empezaron a introducir la teoría
difusa en la programación matemática, la segunda mitad de la década 70 ha sido el
período inicial de construcción de la PLD. Algunos trabajos fundamentalmente resolvían
problemas aplicativos como los de Negoita y Sularia [147] (1976), Sularia [186] (1977).
Otros como Zimmerman [223] (1978) construyeron métodos generales para la PLD.
Los años 80 constituyeron sin duda alguna la década de oro de la PLD, esto
naturalmente desde el punto de vista de la construcción de diversos modelos y métodos
de solución, las mismas que hemos presentado y comentado en las secciones 1.2 y 1.3. En
esta década, también se continuaron con el estudio de aplicaciones y las extensiones.
27
PROGRAMACIÓN LINEAL DIFUSA
max Z ( x)
s. a. Ax b, (1.45)
x 0.
28
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Se observa que este problema es del tipo (1.4) dado en la sección 1.2, cuyos métodos
de solución se describe en la sección 1.3.2, con la diferencia de que en este caso existen
varias funciones objetivo.
Si cada función objetivo difusa (en el sentido de que tiene una meta difusa) está
definida por medio de la función de pertenencia lineal i(zi(x)), según Zimmermann [223],
utilizando la decisión difusa de Bellman y Zadeh, el problema (1.46) es equivalente a:
29
PROGRAMACIÓN LINEAL DIFUSA
este problema (1.49) tiene la función objetivo no lineal y por tanto no se puede resolver
mediante los métodos de la PL.
Posteriores trabajos son similares a los métodos propuestos por Zimmermann, pero
con algunas alteraciones que permiten mejorar los resultados. Así tenemos los trabajos
de Benson [15] , Delgado [49], Fedrizzi, Kacprzyk y Roubens [63], Feng Ying-Jun [65],
Ignizio [88] y Narasimhan [144, 145]. Los trabajos de Hannan [78] y Inuiguchi, Ichihashi
y Kume [91] utilizando funciones de pertenencia continuas y lineales a trozos, Yang e
Ignizio [212] y recientemente Li y Yu [119] utilizando funciones de pertenencia no
lineales aproximados por lineales a trozos, Leberling [114] utilizando ciertas funciones
de pertenencia no lineales al igual que Buckley [23], con la diferencia de que este último
las utiliza para un problema de programación cóncavo o convexo multiobjetivo.
Luhandjula [124] sustituye los operadores min y producto por el operador- y, para
efectos de la simplificación de cálculos, propone el uso del operador suma min-acotado.
Chanas [36] a diferencia de Zimmermann considera que no es necesario que el decisor
proporcione la función de pertenencia (meta difusa) de cada función objetivo, sino que
ésta se construye tomando como referencia el mínimo y el máximo valor que toma cada
una de las funciones objetivo en la región de factibilidad. Luego, las funciones objetivo se
ordenan y se resuelve después de transformar en un problema paramétrico. Mohamed
[138] utiliza el concepto de variables desviacionales para transformar el problema (1.46)
al modelo clásico.
30
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Existen casos en que las funciones objetivo no son precisamente lineales sino
cociente de funciones lineales. Estos casos son considerados también dentro de la PL y
son denominados problemas de programación multiobjetivo fraccionales (PMOF).
Luhandjula en [126] introduce por primera vez el uso de la PLD en PMOF, considerando
que las metas están dadas mediante variables linguísticas. Este método posteriomente
es mejorado por Dutta, Tiwari y Rao [56,58]. También Ohta y Yamaguchi [149]
utilizaron la PLD para resolver problemas de PMOF.
Las funciones objetivo de los problemas vistos hasta ahora son todas relativamente
independientes, sin embargo en los problemas reales esto casi no sucede porque, de una
u otra forma, existen interdependencias entre ellos. En los casos más simples pueden
tener sólo diferentes grados de importancia, y en otros casos muy complejos pueden
existir objetivos en conflicto. Para el caso de las funciones objetivo con diferentes grados
de importancia, es decir, cuando existen prioridades entre los objetivos, se han
desarrollado algunos métodos convencionales para resolverlos, como es el caso de Ignicio
[89]. Tiwari, Dharmar y Rao introducen la difusidad en los problemas de este tipo: en un
primer trabajo [192], utilizan una metodología similar a la de Ignizio, resolviendo
subproblemas difusos en las que las soluciones de los subproblemas con funciones
objetivo más prioritarios constituyen restricciones, y en [193] utilizan el modelo aditivo
con pesos. Cabe anotar también el trabajo de Rubin y Narasimhan [163] dentro de este
contexto. La propuesta de Chen [43] es una variación de las anteriores. Lee y Li [115]
estudian la PLDMO en que algunas de las funciones objetivo son de minimización y las
demás de máximización (el problema con estas características se denomina
programación de compromiso); introduciendo la solución ideal y la anti-ideal, obtienen la
solución de compromiso minimizando la distancia entre la solución ideal y la solución
deseada. Para hallar esta solución de compromiso, basándose en los resultados de
Zimmermann [223], Lee y Li proponen una aproximación en dos fases. En la primera
usan el operador mínimo y en la segunda, un operador compensatorio como es el
promedio aritmético. La aproximación de dos fases propuesta por Lee y Li es uno de los
métodos más simplificados para resolver la PLDMO, por ello otros autores han intentado
sacar el mejor provecho posible de ella, así Mohamed [138] relaja el método en el sentido
de que los pesos no necesariamente tienen que ser iguales, pero deben ser positivos para
generar una solución general eficiente. Por otro lado, Ida y Gen [87] mejoran el método
31
PROGRAMACIÓN LINEAL DIFUSA
Otro tipo de problemas de PLDMO son aquellos en los que los parámetros son
difusos. Aunque estos problemas ya habían sido tratados por Orlovski [153], Lee y Li
[115] utilizando los -cortes, proponen un método de solución diferente. Dentro de este
contexto se incluyen las aportaciones de Wang y Wang [206] que extienden, los métodos
desarrollados por Tong [196] para resolver la PL multiobjetivo con parámetros que son
intervalos, a la PLDMO con costos difusos.
Motivado por los diferentes artículos que aparecieron sobre la PLD, Óhéigeartaigh
[148] inicia la extensión y aplicación de los métodos de la PLD a problemas de transporte
con restricciones difusas. Sobre este trabajo inicial, Chanas, Kolodziejczyk y Machaj [38]
hacen las mejoras correspondientes y posteriormente Verdegay [201], Delgado, Verdegay
32
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
y Vila [51] y Chanas, Delgado, Verdegay y Vila [37] generalizan los resultados
anteriores.
donde:
~
a~i (ai , a i , ai , ai ), b j (b j , b j , b j , b j )
1 1 2 2 1 1 2 2
Teniendo en cuenta que las restricciones son difusas, es lógico que la función
objetivo (el costo total admisible) también sea difusa. Supongamos que está definida por
la siguiente función de pertenencia:
1 para x c 0
G~ ( x)
f ( x) para x c 0
donde f(x) es una función continua, decreciente y f(c0)=1. Un caso particular de f(x) es
una función lineal.
Haciendo un (1-)-corte en los números difusos de (1.50), para cada valor [0,1],
se obtiene el siguiente problema:
33
PROGRAMACIÓN LINEAL DIFUSA
m n
min cij xij
i 1 j 1
j 1
Se observa que tanto las ofertas como las demandas (restricciones) no son iguales a
un número sino que están comprendidas entre dos cantidades (pertenecen a un intervalo
de números). El problema (1.51) se puede reducir a un problema clásico de un solo
estado. Para ello se consideran los valores del extremo izquierdo de cada intervalo como
la demanda mínima o la oferta mínima respectivamente, que necesariamente debe ser
satisfecha en el caso de demanda, y necesariamente distribuida en el caso de oferta.
Luego la diferencia entre el extremo derecho y el izquierdo de cada intervalo, se debe
considerar como la demanda adicional, u oferta adicional, que no necesariamente debe
ser satisfecha o distribuida respectivamente. Esto supone la introducción de costos muy
elevados, o costos nulos, según si se quiere evitar o no los envíos desde determinados
orígenes hacia determinados destinos. Así, queda planteado un problema de transporte
paramétrico clásico, cuya solución es una función en términos del parámetro .
La solución, de acuerdo a la decisión en un ambiente difuso dada por Bellman y
Zadeh, se obtiene mediante:
max D~ ({xij ( )}) u G~ ({xij ( )}) (1 ) (1.52)
El operador usado en (1.52) puede ser sustituido por cualquier otro operador que
sea no decreciente con respecto a cada uno de sus componentes.
Trabajos posteriores son extensiones de los anteriores, como son los trabajos de Bit,
Biswal y Alam. En un primer trabajo [18], estos autores resuelven problemas de
transporte multiobjetivos (multicriterios) utilizando las técnicas de PLD mientras que en
un segundo trabajo [23], resuelven el problema de transporte sólido. Esta denominación
se da a aquellos problemas de transporte de objetos de distintos tipos, que implican el
uso de diferentes medios de transporte y que incluyen también múltiples objetivos. En
34
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Finalmente cabe destacar también los trabajos de Verma, Biswal y Biswas [205],
quienes utilizan las técnicas de PL para resolver problemas de transporte multiobjetivo
introduciendo metas difusas que definen mediante funciones de pertenencia no lineales,
en concreto, mediante funciones hiperbólicas y exponenciales.
35
PROGRAMACIÓN LINEAL DIFUSA
Considérese el problema:
Entonces, Verdegay [202] demuestra que su correspondiente problema dual difuso es:
36
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
con los coeficientes e (costos) difusos dados por (1.54). Y recíprocamente, si (1.55) es un
problema difuso (igual al modelo 1.6) su correspondiente problema dual es (1.53).
s. a. ai T x f bi , i 1,..., m1
(1.56)
d j T x b' j , j m1 1,..., m1 m 2 ,
x 0, m1 m 2 m.
donde c, ai, dj son vectores con n componentes y bi y b'j vectores con m1 y m2 componentes
respectivamente.
37
PROGRAMACIÓN LINEAL DIFUSA
max
s. a. p t p (I )
Ax t b, ( II )
(1.57)
t p ( III )
Dx b' ( IV )
R, x, t 0.
38
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
39
PROGRAMACIÓN LINEAL DIFUSA
Para resolver (1.62), Lai y Hwang [107] proponen el uso del método de ramificación y
acotación.
40
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
corresponden a bi y ti de (1.15).
El problema (1.65) se puede resolverse mediante los métodos clásicos, como por
ejemplo el método de ramificación y acotación. Sin embargo debido a que este método
41
PROGRAMACIÓN LINEAL DIFUSA
42
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
43
PROGRAMACIÓN LINEAL DIFUSA
Comenzamos con las aplicaciones propuestas por Chang, Bill y Hopkins [40],
quienes proponen esquemas para modelamiento de problemas complejos, incluyendo en
ellos las técnicas difusas para incrementar la flexibilidad, y luego presentan como
ilustraciones los problemas de la planificación del uso de las tierras, y el sistema de
tratamiento de las represas de agua en [Link]. Un trabajo parecido en la parte
aplicativa presenta Slowinski [181, 182] al utilizar las técnicas de la programación
difusa multiobjetivo en el sistema de desarrollo de la planificación de la distribución del
agua. Asimismo, Yamaguchi y Kono [211] presentan la aplicación de la PLD
44
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Campos [32] utiliza los modelos y los métodos de la PLD en el juego de la "suma-
cero" entre dos personas. Para cada jugador establece un problema de PLD donde,
durante el proceso de solución, considera distintos tipos de ordenación de los números
difusos para así obtener diferentes tipos de soluciones. El método de solución que
propone es una natural generalización de los métodos de solución convencionales de los
juegos clásicos.
45
PROGRAMACIÓN LINEAL DIFUSA
Como se ha visto, tanto las aplicaciones como los métodos desarrollados se han
dedicado a la PLD en la parte simple (pequeña escala) y a lo sumo sólo se ha llegado a la
programación multiobjetivo, prestándose escasa atención a la PL en gran escala o a
importantes problemas, como el de la mochila. En esta sección nos dedicamos a la
version difusa de la PL en gran escala y el problema de la mochila.
46
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Al igual que en el caso simple, es natural pensar que en situaciones reales los
parámetros de la PL-GE no siempre son conocidos con exactitud. Esto supone que en
muchos casos se tendrá un problema de PL-GE difusa (PLD-GE), para el cual se debe
tener los métodos de solución. Desde el punto de vista de las aplicaciones, las de mayor
importancia son los PLA-GE y consecuentemente tiene mayor importancia PLA-GE
difusa. El proceso de introducción de la teoria difusa en PLA-GE ha tenido la misma
evolución que el caso simple, es decir, los primeros trabajos han considerado la meta
difusa y las restricciones difusas (en el sentido de que se admiten violaciones tanto a las
restricciones como a las metas), luego se ha abordado el PLA-GE multiobjetivo difuso, y
finalmente, la PLA-GE con números difusos como parámetros.
47
PROGRAMACIÓN LINEAL DIFUSA
Iniciamos con la revisión de la más simple versión difusa del problema (1.66), como
es el caso de la flexibilidad en el cumplimiento de las restricciones y la meta.
Consideremos que la meta ideal para el decisor es que el costo sea menor o igual
que z01, pero es aceptable un costo mínimo menor o igual que z00, con el grado de
aceptación (función de pertenencia de la función objetivo) siguiente:
1, cx z 10
0 (cx) 0 cx 0 z 10 cx z 00 , (1.67)
cx z 00 .
0,
1, ( Ax) j z 1j
j (( Ax) j ) j ( Ax) j j z 1j ( Ax) j z 0j , j 1,..., s (1.68)
0 , ( Ax) j z 0j .
en (1.67) y (1.68):
1 z 0j
j y j , j 0,1,..., s. (1.69)
z 1j z 0j z 0j z 1j
48
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
s
donde w j 0 ( j 1,..., s ) y wj 1.
j 1
s
max w0 0 ci xi w j j ( Ai xi ) j
j 1
s.a. Bi xi bi , i 1,..., p (1.71)
xi 0.
Sakawa, Inuiguchi y Sawada [166] demuestran que si las p soluciones óptimas x'i
(i=1,..,p) de (1.71) satisfacen las siguientes desigualdades:
p
z 10 ci x' i z 00 , (1.72)
i 1
p
z 1j ( Ai x'i ) j z 0j , j 1,2,..., s (1.73)
i 1
49
PROGRAMACIÓN LINEAL DIFUSA
p
min ci xi
i 1
p
s.a. ( Ai xi ) j z 0j , j 1,2,..., s (1.76)
i 1
Bi xi bi , i 1,..., p
xi 0, i 1,..., p.
Finalmente, para calcular los pesos wj (j=0,1,...,s) que se han utilizado en (1.70) se
necesita que el decisor proporcione un valor ideal de entrada tanto para la meta como
para las restricciones difusas, notado tj <z0j (j=0,1,...,s). Luego
1
j (t j )
wj s
, j 0,1,..., s. (1.77)
1
u (t )
i 1 i i
50
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Consideremos el problema
min c1 x c11 x1 ... c1 p x p
min c 2 x c 21 x1 ... c 2 p x p
min c k x c k1 x1 ... c kp x p
s.a. Ax A1 x1 ... A p x p b0 , (1.78)
B1 x1 b1 ,
B1 x1 b p ,
xi 0, i 1,..., p,
donde los cij son ri-dimensional vectores fila y los demás igual que en (1.66).
51
PROGRAMACIÓN LINEAL DIFUSA
decisor para cada función objetivo (este valor inicial lo proporciona el decisor). En
consecuencia, una solución Pareto óptima de (1.78) deberá tener una función de
pertenencia muy cercana a dichos valores deseados, es decir, se debe resolver el siguiente
problema:
o equivalentemente
min
Paso 0: Obtener el valor mínimo individual zjmin y valor máximo individual zjmax de cada
función objetivo con las restricciones del problema inicial (1.78).
52
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Paso 1: El decisor determina las funciones de pertenencia que expresan las metas
difusas para cada función objetivo considerando el intervalo cerrado [zjmin ,zjmax].
Paso 2: El decisor proporciona la referencia inicial j* (j = 1,...,k).
Paso 3: Obtener una solución óptima de Pareto resolviendo el problema (1.80) y el
correspondiente problema test (1.81).
Paso 4: Si el decisor no se siente satisfecho con la solución obtenida en el paso 3,
modificar los valores de la referencia inicial y luego retornar al paso 3.
donde todos los coeficientes son como en (1.78) con la diferencia de que en (1.83) los
números en los vectores, matrices y constantes en general son difusos.
53
PROGRAMACIÓN LINEAL DIFUSA
En los métodos de solución que plantean Sakawa y Kato [168] y Sakawa, Kato y
Mizouchi [170] los números difusos que utilizan son los números introducidos por Dubois
y Prade [55].
El modelo (1.85) es del tipo clásico, pero debido a que en realidad los coeficientes no
son números específicos sino variables, no se puede aplicar el concepto de solución Pareto
óptima, por lo que es necesario generalizar este concepto para el caso como solución -
Pareto óptima. Un x*X(A*,B*,b*) se denomina solución -Pareto óptima de -PLDA-GE
54
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
(1.85) si y sólo si no existe otra xX(A,B,b), tal que cixc*ix*, i=1,...,k, y si se cumple la
desigualdad estricta para algún i.
Para generar la solución candidata a ser -Pareto óptima de (1.85), antes, al igual
que para la PLDA-GE multiobjetivo, el decisor debe proporcionar el nivel de referencia
inicial z'i, i=1,...,k. La solución -Pareto óptima será aquélla que esté lo más
cercanamente posible a dichos niveles de referencia, es decir, que sea la solución del
siguiente problema:
o equivalentemente
min
s.a. (ci x z 'i ) , , i 1,..., k
(1.87)
x X ( A, B, b),
~ ~ ~
( A, B, b, c) ( A, B , b , c~ ) .
Este problema (1.86), debido a que los parámetros son considerados como variables
de decisión tiene las restricciones no lineales. Pero dichos parámetros tienen los
intervalos de variación que son los respectivos -cortes, intervalos cerrados de la forma:
cL R
i , ci , A , A , B
L
R L
j , B Rj y b L
j ,
b Rj ,
55
PROGRAMACIÓN LINEAL DIFUSA
min
s.a. c1L c11 x1 ... c1 p x p z '1 ,
L L
c kL c kL1 x1 ... c kp x p z'k ,
L
(1.88)
AL x A1L x1 ... A pL x p b0R ,
B1L x1 b1R ,
B1L x1 b1R ,
x j 0, j 1,..., p.
Como aplicaciones del método aquí expuesto se han desarrollado algunos trabajos.
Comentamos dos casos especiales, uno de ellos se refiere a la solución de la programación
fraccional difusa multiobjetivo en gran escala con estructura angular de bloques
(PFADM-GE), desarrollado por Sakawa y Kato [169], y el otro, a la solución de
56
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Uno de los trabajos iniciales para resolver el problema de la mochila difuso ha sido
realizado por Okada y Gen [150] para el problema simple, es decir, con una sola
restricción. Los mismos autores en otro artículo [151] proponen un método de solución
para el problema difuso multidimensonal de la mochila:
n
max ~
z c~ j x j
j 1
n ~
s.a. a~ij x j f bi , i 1,..., m (1.90)
j 1
x j 0,1, j 1,..., n
57
PROGRAMACIÓN LINEAL DIFUSA
un número que indica el grado de desigualdad existente entre dichos números. Dicho
grado está dado por:
aR
min a ( x), B ( x)dx
~ aL
P (a~ f b ) aR
(1.91)
u a ( x)dx
aL
~ ~
donde: a~ ( a L , a M , a R ) y b (b L , b M , b R ) son números difusos triangulares, y B definido
Okada y Gen utilizan el eficiente método del gradiente para resolver el problema
(1.90). Primeramente fijan un grado mínimo en que las desigualdades de los números
difusos de las restricciones deben ser aceptadas. Este grado mínimo es dado por el
decisor. Los autores citados proponen un algoritmo que se compone de dos fases. La
primera fase consiste en generar un conjunto de soluciones factibles que cumplan con el
grado mínimo fijado en que las desigualdades se forman, y la segunda fase consiste en
elegir la mejor solución usando para ello la misma definición del grado en que se forma la
desigualdad entre dos números difusos.
58
1.4 EXTENSIONES Y APLICACIONES DE LA PLD
Evidentemente, las metas difusas tienen que estar definidas mediante una
función de pertenencia. El método que proponen los autores es para las funciones de
pertenencia que son lineales y que son definidas por el decisor. En la definición de esta
función, el decisor tendrá como referencia el máximo valor de cada función objetivo
dentro de la región factible, y el cero, que viene a ser el mínimo valor posible para dichas
funciones de pertenencia.
Abboud, Sakawa e Inuiguchi emplean una decisión convexa para transformar
todas las funciones objetivo en una sola, es decir, el problema equivalente al problema
(1.92) con metas difusas es:
q
max wl zl (k l x)
l 1
s.a. Rx b, (1.93)
x j 0,1, j 1,..., n
q 1 zl ( z la )
wj 1, w j 0 y wj , con z la el nivel de aspiración de la función
zl ( z la )
q
j 1 l 11
que es un problema clásico que puede resolverse mediante el eficiente método del
gradiente.
59
Capítulo 2
2.1 INTRODUCCIÓN
61
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
62
1.1 INTRODUCCIÓN
Ya hemos visto que un algoritmo es un proceso repetitivo que genera una sucesión de
elementos de acuerdo a un conjunto de instrucciones pre- escritas hasta cumplir con una
condición de parada. Además requiere de un elemento inicial generador de la sucesión. De
esto se desprende que en todo proceso algorítmico pueden distinguirse tres grandes etapas:
inicial, iterativa y final (Figura 2.1).
Etapa Inicial: Es la etapa en que, sobre la base de alguna regla, se elige un elemento
inicial para generar los demás valores de la sucesión en la etapa iterativa.
De acuerdo a la naturaleza de los problemas y del algoritmo que se
resuelve, dicho elemento inicial puede ser un elemento en particular, como
por ejemplo en el algoritmo simplex, en los algoritmos de la mochila, etc.
En otros casos, se utilizan reglas específicas para obtener el elemento
inicial, como ocurre por ejemplo en el algoritmo simplex de transporte
donde hay varias reglas distintas para obtener el elemento inicial. En
estos últimos casos, el conjunto L mencionado es no unitario.
Etapa Iterativa: Es la etapa operativa principal del algoritmo que genera los elementos
de la sucesión, elementos que constituyen soluciones aproximadas del
problema.
Etapa final: Esta etapa, que en lo sucesivo denominaremos criterio de parada, es la que
controla las repeticiones de la etapa iterativa. Está formada por un conjunto
de reglas que indican cuando el procedimiento algorítmico debe finalizar,
63
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
64
2.1 INTRODUCCIÓN
Los algoritmos en general son diseñados para resolver problemas, y sobre todo
problemas reales. Muchos de estos problemas reales son complejos y con dimensiones
grandes. En estos casos, los algoritmos -aún los que son polinomiales-, para satisfacer las
condiciones de parada requieren un número de iteraciones muy grande que es posible no
se puedan alcanzar en tiempo razonable; situaciones en las que aún los algoritmos más
eficientes pueden ser poco útiles. La situación es peor para los problemas NP-completos, los
cuales carecen de algoritmos con tiempos de ejecución polinomial. Para ellos, se han
desarrollado diversos algoritmos heurísticos que permiten determinar soluciones
aceptables. No obstante, esto ha supuesto descuidar la búsqueda de la posibilidad de
adaptar los algoritmos exactos de tal manera que nos permitan hallar soluciones
aceptables. Los algoritmos exactos, tal como están construidos, son poco flexibles ya que sus
criterios de parada están basados en análisis teóricos de los problemas y algoritmos, por
tanto el procedimiento de calculo hasta alcanzar la solución exacta para problemas de
grandes dimensiones, puede ser incluso varios años.
En el caso de problemas de decisión, en situaciones reales, cuando no se conoce
65
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
ninguna solución, y fuera imposible obtener una solución exacta en un tiempo razonable,
para el decisor será suficiente tener una solución aceptable. Esta categoría de aceptable
respecto de una solución no exacta, sólo la puede otorgar el decisor que está al frente de un
problema en particular que necesita resolver. En consecuencia, para los efectos de
aplicación en problemas reales y de dimensiones arbitrarias los algoritmos deben tener una
flexibilidad para adecuarse a situaciones muy particulares y también a los criterios del
decisor.
Debido a que la dinámica de todo algoritmo está en sus reglas de control, la
flexibilización se tiene que buscar en dichas reglas para obtener un algoritmo semejante,
pero con la finalidad de que sea capaz de proporcionar soluciones aceptables en un tiempo
de ejecución razonable.
Una herramienta que ha ayudado en la solución de problemas en diferentes campos
en los que los datos no se conocen con exactitud es la teoría de conjuntos difusos.
Particularmente, la programación lineal difusa ha tomado como fuente esta teoría, lo que
acredita la virtualidad aplicativa de la teoría de conjuntos difusos en otros ámbitos como
es el de la flexibilización de los criterios de parada, que se denominan criterios de parada
difusos.
Los criterios de parada difusos fueron introducidos por primera vez en el ámbito de
la programación matemática en 1995 por Verdegay [204], y luego por Herrera y Verdegay
[81] en 1996, particularmente en el algoritmo simplex de la PL. En este trabajo
desarrollamos esto con mayor amplitud, y lo extendemos a los algoritmos de Karmarkar y
de Puntos Interiores de la PL, así como a algunos algoritmos que sirven para resolver los
Problemas de la Mochila y del Viajante de Comercio.
(2.1)
Es evidente que una solución no óptima no cumple con la condición (2.1). Las soluciones no
exactas se obtendrán cuando g(xn) < c. Una solución no exacta será menos aceptable cuanto
mayor sea la diferencia con c, y será muy cercana al óptimo cuando g(xn) sea muy cercano
66
2.1 INTRODUCCIÓN
donde h(x) 0 (0,1) es una función continua creciente, y cuya representación gráfica se
muestra en la Figura 2.2.
(2.3
67
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
(2.4
o equivalentemente
(2
Herrera y Verdegay [81], utilizan como h una función lineal y sugieren que el valor
ä utilizado en (2.2) y á de (2.3) los debe proponer el decisor. En este trabajo proponemos que
el valor ä sea obtenido a partir de la etapa inicial del algoritmo o bien usando algún otro
método que permita obtenerlo fácilmente, y dicho valor ä obtenido le facilitará al decisor
el elegir á con mejor acierto. Asimismo, al definir la función de pertenencia en función de
la naturaleza de los algoritmos y los problemas, sugerimos el uso de diversos tipos de
funciones no lineales.
El algoritmo simplex diseñado por G. Dantzig [47], sirve para resolver el problema de
programación lineal estándar (PLE) siguiente:
max cTx
s.a. Ax = b (2.6)
x $ 0,
donde c y x (variable) son vectores columna n-dimensionales, A es una matriz mxn de rango
m, b es un vector columna m-dimensional de números reales. Por la expresión del modelo,
podemos suponer que se trata de un problema de producción en la que se quiere determinar
la máxima utilidad.
68
2.2 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO SIMPLEX
Si se resolviera el PLE (2.6) utilizando la “fuerza bruta”, se tendrían que hallar todos
los vértices de F resolviendo todas las combinaciones de la forma BxB = b que se pueden
formar de Ax = b, y luego seleccionar el vértice de mayor utilidad. Con este método se
presentan dos inconvenientes: uno, el que en el caso de un problema no acotado se llegaría
a elegir una utilidad como máxima cuando en realidad no lo es, y otro, el enorme trabajo
de tener que calcular el elevado número de vértices que tiene la región factible cuando n-m
es muy alto.
El algoritmo simplex evita el análisis de todos los vértices pues, partiendo de un
vértice inicial, recorre los vértices hasta llegar al óptimo pasando del vértice actual a otro
si éste es de mayor utilidad, recorrido en el que no necesariamente tiene que visitar todos
los vértices. La parte algebraica de este recorrido es muy simple: se utiliza la matriz base
B asociada al vértice actual; el siguiente vértice se obtiene sustituyendo una columna de la
base B por otra de la matriz A que no forma parte de B, eligiéndose la columna que ha de
ser sustituida y la que la sustituye bajo la condición de que el nuevo vértice tenga la mayor
utilidad de entre todos los intercambios posibles y a su vez, sea de mayor utilidad que el
actual; ésta es la etapa iterativa del algoritmo. El algoritmo finaliza cuando ninguno de los
vértices que restan por visitar tiene mayor utilidad que el vértice actual o cuando hay algún
indicativo de que el problema es no acotado o no tiene solución.
A continuación presentamos las etapas principales del algoritmo simplex, pero antes,
introduzcamos las notaciones y fórmulas que se usarán.
69
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
70
2.2 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO SIMPLEX
donde hj(.) es una función continua creciente tal que hj(-tj) = 0 y hj(0) = 1 y tj > 0 es el
margen de tolerancia del incumplimiento de la condición de parada óptima. La gráfica de
la función de pertenencia se muestra en la Figura 2.3.
Tanto la función hj como tj podrían ser dadas por el decisor como en [81], sin embargo
sería de mejor ayuda para el decisor que el mismo criterio de parada difuso incluyera el
mecanismo de construcción de la función de pertenencia así como el valor de tj. Conocida
esta referencia, el decisor podrá fijar el grado á0(0,1] de incumplimiento de la condición
71
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
de parada exacta para que una solución no óptima pueda ser aceptable; así, la condición de
parada (b) se modifica en el sentido de:
ìj(äj) $ á, á 0 (0,1], j = 1,...,n
equivalentemente
äj $ ìj-1(á), á 0 (0,1], j = 1,...,n (2.12)
Teniendo en cuenta que la condición ìj-1(á) > 0 no tiene mayor importancia adicional
en la solución sino es equivalente a ìj-1(á) $ 0, la condición (2.12) se puede escribir en la
siguiente forma:
äj $ hj-1(á), á 0 (0,1], j = 1,...,n. (2.13)
Por tanto el criterio de parada (b), del algoritmo simplex puede ser flexibilizado mediante
el siguiente
72
2.2 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO SIMPLEX
deseados.
Este último inconveniente se puede evitar de la siguiente manera:
1) Tengamos en cuenta que con el criterio difuso pretendemos ahorrarnos el mayor número
de iteraciones, deteniéndose las iteraciones cuando se haya alcanzado una solución
aceptable. Quiere decirse que, a mayor número de iteraciones tendremos una mejor
solución aceptable; por tanto, la convergencia de äj a la condición de parada exacta 0, en
cierto modo depende también del número de iteraciones, por lo que utilizaremos äj/u
como función medida para el criterio de parada difuso, donde u es el número de la
iteración actual correspondiente.
2) Por otro lado, se sabe que para problemas de mayores dimensiones el número de
iteraciones en el algoritmo simplex crece proporcionalmente al número de restricciones
m, y es poco sensible al número de variables de decisión [155]. Por lo tanto, para
compensar la división de äj entre u de tal manera que el criterio de parada no se
modifique sustancialmente es necesario también dividir hj-1(á) entre m.
De esta manera, tenemos el siguiente nuevo criterio de parada difuso, que llamamos
criterio de parada difuso balanceado:
73
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Con esta opción se está considerando que la solución inicial, de no ser óptima, es una
solución aceptable con el grado de cumplimiento cero.
Para definir la función de pertenencia, primero tenemos que decidir si usamos una
función hj(.) lineal o no lineal; si optamos por una función lineal, (2.14) será la condición de
parada difusa. Si preferimos que hj(.) sea no lineal, tendríamos que definirla. Una vez que
se tiene definida la función hj(.), como siguiente paso, el decisor tendrá que fijar el grado
mínimo á de aceptación de una solución no óptima.
74
2.2 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO SIMPLEX
condición de parada, una función no lineal convexa en [r0,0] proporcionará mejor solución
que una función lineal ó no lineal cóncava, para un mismo grado de pertenencia. Pues si h1
es convexa y h2 es cóncava en [r0,0], entonces h1-1(á) > h2-1(á), tal como se muestra en la
Figura 2.4; esto último implica que para alcanzar la condición de parada difusa (b”) se
necesitará mayor número de iteraciones cuando la función sea convexa que cuando la
función sea cóncava.
Dos ejemplos de funciones que se pueden utilizar para definir las funciones de
pertenencia, entre otros muchos, son los siguientes:
(2.17
Ejemplo:
Como ilustración resolvemos el siguiente problema:
75
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
h(t)=(e8+x-1)/(e8-1)
En los resultados de los cálculos que se muestran en la Tabla 2.1. se observa que,
76
2.2 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO SIMPLEX
cuando se utiliza una función h(t) convexa para definir la función de pertenencia de la regla
de parada difusa, para un mismo grado de aproximación á, se obtiene una solución mucho
más cercana a la óptima que cuando se utiliza una función lineal o una función cóncava.
Particularmente, para á=0.5, usando la función convexa, se ha obtenido la solución z=41.33
muy cercana a la solución óptima, mientras que usando la función lineal y usando la
función cóncava se obtiene z = 38, que es una solución no tan cercana a la óptima por tanto
con menor grado de aceptación que el anterior. Cuando se aumenta el grado de
aproximación a á = 0.8, en caso de usar la función convexa se ha obtenido la solución exacta,
mientras que en el caso lineal se mejora la solución no exacta pero no se ha mejorado en el
caso de usar una función cóncava.
77
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
2.3.1 Introducción
Desde que Khachiyan [102] en 1979 propuso el algoritmo elipsoidal para resolver un
problema de PL, se han buscado otros métodos, que no sólo ignoren la estructura
combinatoria sino que mejoren el tiempo de ejecución polinomial del algoritmo elipsoidal.
Así, en 1984 Karmarkar [99] propone un nuevo algoritmo de tiempo de ejecución
polinomial mucho más rápido que el algoritmo elipsoidal, por tanto un mejor competidor del
anterior algoritmo simplex, pero que al igual que el algoritmo elipsoidal ignora la
característica combinatoria. El algoritmo de Karmarkar, conocido también como el método
de transformación proyectiva, genera una sucesión de puntos interiores de la región factible
que con el aumento de las iteraciones se aproxima a los extremos hasta alcanzar el vértice
óptimo. Por presentar esta característica, el algoritmo de Karmarkar es un método de punto
interior.
Debido a que este algoritmo no es tan popular como el algoritmo simplex, hacemos
una revisión con mayor detalle incidiendo mayormente en la parte intuitiva y en los mismos
pasos del algoritmo en sí.
(2.20)
78
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
Para seguir la misma idea que en el caso anterior, ahora podemos considerar la
proyección cp de c sobre el hiperplano {x 0ún /ax=0}. Entonces -cp es la dirección del
decrecimiento más rápido de la función objetivo en D, y el punto mínimo es:
(2.21)
La solución obtenida será tanto mejor aproximación cuanto la región factible más se parezca
79
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
a un sólido esférico.
Para medir el grado en que se parece la región factible a un sólido esférico respecto
a un punto, se puede utilizar la relación entre el radio de la esfera contenida (de mayor
volumen), y el radio de la esfera (de menor volumen) que contiene a la región factible. Esta
relación se denomina medida de la redondez.
Si m es el valor mínimo buscado en (2.19), si w es el punto mínimo en el sólido esférico
E = S(z,r) (de mayor radio posible) contenido en D , y si E’ = S(z,kr) es el menor sólido
esférico que contiene a D ( E’ es k veces mas grande que E) [98], se tiene que:
Teniendo en cuenta que k $1, de (2.22) se deduce que cuanto mayor sea k, la
diferencia entre el mínimo valor de la función objetivo del problema (2.19) con el mínimo
en E (en w) es más cercana a la diferencia entre el mínimo y el valor en z, mientras que si
k es cercano a 1, w es muy cercano al punto mínimo en D.
En consecuencia el punto w sería una mejor aproximación al punto mínimo en D si
k es muy cercano a 1, pero esto sólo se cumple si:
C D es muy semejante a un círculo (polígono regular de n lados).
C z es el centro de D (en el caso de que sea un polígono regular z sería el centro de las
circunferencias inscrita E y circunscrita E’)
En este caso se diría que D es muy parecido a un círculo o que es un polítopo
redondeado.
80
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
Sea
, e = (1,1,...,1). (2.24)
min z = cx
s.a. x 0Ð = Ù1Ä (2.25)
x, z $ 0
o equivalentemente :
min z = cx
s.a. Ax = 0 (2.25')
x1+x2+...+xn = 1
x,z $ 0
81
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Por ello, elige a0 como punto inicial; a partir de este punto y siguiendo la dirección del
decrecimiento más rápido halla el punto mínimo a sobre una esfera de centro en este punto.
Si el punto mínimo así obtenido no es el punto mínimo global (con costo cero), repite el
procedimiento anterior utilizando el punto a. Es evidente que el punto a ya no es el centro
del simplex Ä, y por tanto no se puede repetir exactamente el mismo procedimiento. Para
superar este inconveniente, Karmarkar define una transformación proyectiva particular
Ta de tal manera que al punto a le hace corresponder con el punto a0. Por suerte la
transformación también cumple con la condición Ta(Ä) = Ä, y está definida de la siguiente
manera:
donde:
, eT = (1,1,...,1).
82
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
(2.30)
que es una función no lineal. Si el costo mínimo es cero, y teniendo en cuenta que la
minimización de (2.30) (una función racional) es sobre un polítopo, es suficiente minimizar
el numerador, que es lineal. Sin embargo, en el caso de que el mínimo no fuera cero no sería
correcto este procedimiento.
Para garantizar que este pequeño cambio no altera la idea del cálculo de b dentro de
una bola contenida en Ð’, Karmarkar elige la esfera S( a0,á/n) con (1/n) < r (r dado en
83
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Sea
Etapa Inicial: Sea x(0) = a0 = e/n y sea K = j2nL/äk (el número de iteraciones).
Cálculo de b = Ö(a):
Dado a 0 Ð , a > 0 y ca > 0, con c vector de costos hallar b = Ö(a) que está en Ð y b >0:
84
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
2. Sea c’ = Dc
(Ð’ = { x’/ Bx’ = e’ }, e’ tiene todos sus componentes nulos excepto el último que es 1.)
4. Sea cP = c’- BT(BBT)-1 Bc’ (la proyección de c’ sobre el espacio nulo de B)
7. Retornar:
8. FIN.
85
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
(MA)x’ = b
x’1 + x’2 +...+ x’l + x’l+1 = 1
x’ $ 0,
86
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
El punto a0 no es una solución factible del sistema (2.34). Para que lo sea, se agrega
una nueva variable ë en las ecuaciones del sistema dado en (2.34), y se transforma en:
Cx-ë(Ce) = 0
x1 + x2 +...+ xl + xl+1 + ë = 1 (2.35)
x,ë $ 0,
Ejemplo: Ilustramos con un ejemplo la forma como se construye una forma estándar de
Karmarkar a partir de un problema arbitrario:
Consideremos el modelo:
87
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Puesto que L = 20, se tienen x+y+z+u # 4(220) e introduciendo una variable de holgura
se tiene el nuevo problema:
Sustituyendo cada variable por 222 veces otra variable y luego procediendo a anular los
segundos miembros, y finalmente introduciendo ë (teniendo en cuenta todo el procedimiento
explicado arriba) se tiene
88
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
operaciones por segundo lo puede concluir en 6 segundos, mientras que, la misma máquina
para resolver el problema FIT2P [3] con n = 13525 y L = 3518352 necesitaría 3733204 años.
Como se ve, en problemas que aún no son el “peor caso”, el número de iteraciones es
muy elevado, de modo que en tiempo razonable no es posible obtener la solución. En estos
casos se hace necesario detener el proceso de solución cuando se haya obtenido una solución
razonablemente aceptable para el decisor, aún no siendo la óptima [81].
89
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Si el decisor, frente al problema nuevo, decide admitir como solución el caso en que
el costo tiene un grado de pertenencia no menor que á0(0,1], es decir, si ì(cx) $ á o g(cx)$á,
90
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
i) Si el costo óptimo (mínimo) es cero, la condición relajada (2.38) puede conducir a aceptar
una solución aproximada con muchos errores, como se puede observar en la Figura. 2.10-
(a).
ii) Si el costo óptimo es diferente de cero, existe la posibilidad de que el óptimo sea mayor
que g-1(á), como se ve en la Figura.2.10-(b). Esto conduciría a realizar todas las
iteraciones para obtener la solución.
Siempre sigue latente la dificultad de optar por uno u otro caso, cuando a priori no se
conoce si el mínimo es cero o positivo. En este caso la solución radica en realizar los ajustes
de la función objetivo durante el proceso de cálculo, utilizando la función siguiente:
91
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Ejemplo: En esta parte ilustremos el uso de criterios de parada difuso en dos problemas,
el primero con costo óptimo cero, y el segundo de costo óptimo mayor que cero,
en ambos casos la función objetivo es no negativa.
1) 2)
92
2.3 CRITERIOS DE PARADA DIFUSOS EN EL ALGORITMO DE KARMARKAR
Los resultados obtenidos resumidos en la Tabla 2.2, nos muestra de manera muy clara
una mejor aproximación cuando se utiliza la función no lineal.
93
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
aproximación.
En los dos ejemplos se observa que para tener una solución aproximada aceptable no
ha sido necesario realizar todas las iteraciones, que eran 6067 en el primer caso, y 20960
en el segundo caso.
2.4.1 Introducción
94
2.4 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS MODIFICADOS DE KARMARKAR
min cx
s.a. Ax = b (2.40)
x$0
95
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
donde A’ = [A ! b-AeT ] es una matriz de orden mx(n+1), x y c son (n+1)-vectores con cn+1
= M es un costo muy alto que asegura que la variable xn+1 tendrá valor cero en el óptimo.
96
2.4 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS MODIFICADOS DE KARMARKAR
esta misma característica proponen también Todd y Burrell [194] un algoritmo modificado,
pero siempre manteniendo la forma estándar de Karmarkar. El algoritmo propuesto por
Todd y Burrell es un poco más eficiente que el algoritmo inicial de Karmarkar.
d # g-1(á) (2.42)
Para ilustrar el criterio de parada difuso en el algoritmo K-VMF utilizamos los mismos
ejemplos de la sección anterior 2.3, para ambos ejemplos usamos dos funciones de
pertenencia, una lineal y otra no lineal en este último la función definida por (2.39) con
r=1/8. En el primer ejemplo d0 = 2.4 y en el segundo ejemplo d0 = 2.666... Los resultados se
muestran en las Tablas 2.4 y 2.5 respectivamente.
97
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Algoritmo K-Barnes:
98
2.4 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS MODIFICADOS DE KARMARKAR
Calcular:
(2.43)
Sea äk el máximo valor de entre las m menores componentes de | zk|, donde |.|
representa el valor absoluto de las componentes respectivamente. Sea ä0 el valor obtenido
99
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Igual que en los casos anteriores se recomienda utilizar funciones de la forma (2.39),
con cm = ä0 y 0 < r # 1.
En los mismos ejemplos de la sección 2.3 se ha utilizado este algoritmo, con ä0=0.9
para el primer ejemplo y ä0 = 1/3 para el segundo ejemplo. Para los dos ejemplos, en los
criterios de parada difusos, se utiliza por un lado la función lineal y por otro lado la función
no lineal (2.39) con r = 1/8. Los resultados se muestran en las Tablas 2.6 y 2.7
respectivamente.
100
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
2.5.1 Introducción
Como hemos visto en la sección anterior, Barnes [9], Gay [70], Vanderbei [199] y
101
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Como en todo algoritmo, debemos precisar los tres pasos fundamentales de los
algoritmos de puntos interiores que son:
i) Etapa inicial
ii) Etapa iterativa
iii) Criterio de parada.
Cada uno de estos pasos se aplicarán al PLE (2.40). Esta forma es obtenida a partir
de otras formas incluyendo variables de holgura y/o artificiales.
Etapa inicial
102
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
Etapa iterativa
Conociendo un punto interior factible x0, el paso iterativo permite generar un nuevo
punto factible que reduzca el costo actual.
Puesto que se desea minimizar una función dentro de la región factible, la dirección
del gradiente descendente nos proporciona los puntos de mejor decrecimiento. Por tanto,
para obtener el nuevo punto debemos desplazarnos en dicha dirección, y la longitud del
desplazamiento debe ser de tal manera que el nuevo punto sea punto interior factible.
Además, este desplazamiento debe ser lo más grande posible para alcanzar el punto óptimo
con el menor número de pasos. Para compatibilizar estas dos condiciones se utiliza una
circunferencia con centro en el punto conocido e inscrita en la región factible. Un
desplazamiento de longitud ligeramente menor que el radio garantiza la factibilidad.
Si x’1 = x’0 + dx’ es el nuevo punto, donde dx’ es el vector dirección de paso, la
condición de factibilidad requiere que Ax’1 = A(x’0 +dx’) = Ax’0 +Adx’1 = b, pero como Ax’0 =b,
103
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
entonces Adx’ = 0; esto último significa que el vector dirección dx debe pertenecer al espacio
nulo de la matriz A. Puesto que dicho vector sigue la dirección del gradiente descendente
de la función objetivo, este gradiente descendente -c debe ser proyectado ortogonalmente al
espacio nulo de A’ mediante el operador proyección P = In-A’T(A’A’T)-1A’, es decir, dx’=-P’c’.
Finalmente, para mantener la condición de punto interior el nuevo punto estaría dado por
x’1 = x’0 + ádx’ (2.45)
con á<1.
Este nuevo punto x’1 debe ser expresado en términos del sistema de coordenadas
iniciales. Esto se logra mediante una transformación afín. Debido a que se utiliza el proceso
de cambio de escala mediante una transformación afín, se denominan también algoritmos
“affine-scaling”.
z = c-ATy (2.47)
entonces
dx = -D2z (2.48)
finalmente
x = x0 + ádx (2.49)
es el nuevo punto factible con menor costo.
Sabemos que todo problema de PL tiene su respectivo problema dual. Una de las
ventajas del procedimiento que acabamos de explicar radica en el hecho de que en cada
iteración se obtiene una solución aproximada del problema primal, así como también para
el problema dual. Si el x dado en (2.49) es el nuevo punto factible o solución aproximada,
entonces el y dado en (2.46) es el punto factible del problema dual.
104
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
Criterio de parada
Dados los problemas primal (P) y su respectivo dual (D)
min cTx max bTy
(P) s.a. Ax = b (D) s.a. Aty # c (2.50)
x$0 y irrestrictas
por el teorema de la dualidad débil se tiene que cx$bTy, y por el teorema general de la
dualidad en el óptimo se cumple la igualdad. Por lo tanto para alcanzar la solución óptima
del problema primal y dual el procedimiento debe detenerse cuando se obtienen x*, y* tales
que cx*=bTy*. Sin embargo, debido a que en cada iteración se obtienen puntos interiores
mientras que el punto óptimo es de la frontera, el procedimiento no determina exactamente
el punto óptimo sino una sucesión de puntos que convergen al punto óptimo. En
consecuencia, el procedimiento se realiza hasta alcanzar un valor fijado como un umbral
para la diferencia entre los valores de las funciones objetivos primal y dual.
El criterio de parada que han sugerido muchos autores es:
105
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
Etapa Inicial:
Paso 0: Dado x0 > 0 un punto interior factible, hacer k=0, y x(k) = x0.
Etapa iterativa:
Paso 1: Definir: D(k) = diag(x(k)), la matriz de cambio de escala.
Paso 2: Calcular la estimación dual y(k), resolviendo [AD2(k)AT]y(k) = AD2c
Paso 3: Evaluar el vector costo reducido z(k) = c-ATy(k), luego dx(k) = -D2(k)z(k)
Paso 4: El siguiente vector solución está dado por:
x(k+1) = x(k) + ñádx(k)
donde
Criterio de Parada:
Paso 5: Si el criterio de parada se cumple, terminar el proceso. En el caso contrario
incrementar k e ir al paso 1.
106
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
y irrestrictas, z $ 0
Etapa inicial:
Paso 0: Dados y0, z0 vectores iniciales factibles, con z0 > 0, sean k = 0, y(k) = y0 y z(k)
= z0.
Etapa iterativa:
Paso 1: Definir D(k )= diag[1/z1(k),1/z2(k),...,1/zn(k)].
Paso 2: Hallar dy(k), resolviendo el sistema [AD2(k)AT]dy(k) = b.
Paso 3: Calcular: dz(k) = -Atdy(k).
Paso 4: Encontrar el siguiente costo reducido: z(k+1) = z(k) + ñádz
el vector dual y(k+1) = y(k) + ñády(k),
donde y 0<ñ<1
Criterio de parada:
Paso 5: Si el criterio de parada se cumple, terminar las iteraciones. En el caso contrario
incrementar k en una unidad e ir al paso 1.
107
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
(Pì) :
(Dì):
Los términos que contienen la función logaritmo no sólo obligan a las variables a ser
positivas sino a mantenerse en una posición central con respecto a los ejes para alcanzar la
optimalidad. El parámetro de barrera ì sirve para mantener la posición centrada de los
puntos interiores y al mismo tiempo la condición de reducción del costo.
Como podemos observar, los problemas (2.53) y (2.54) son no lineales, por tanto,
debemos aplicar los métodos para resolver problemas de optimización no lineales. Las
propuestas de Bayer y Legarias [10], De Gellinck y Vial [71], Iri e Imai [95], Lustig [129] y,
Montero y Adler [140] entre otros, han permitido desarrollar el algoritmo Primal-Dual,
cuyos pasos resumimos a continuación:
Etapa Inicial:
Paso 0: Sean x0,y0 y z0, puntos interiores factibles, es decir, que satisfacen las
restricciones de (2.53) y (2.54), con x0>0 y z0>0 . Hacer k=0 y x(k)=x0, y(k)=y0 y
z(k)= z0.
Etapa Iterativo:
Paso 1: Evaluar el parámetro barrera: ì=0.1zT(k)x(k)/n.
Paso 2: Definir las matrices diagonales de cambio de escala siguientes:
X(k) = diag[x(k)], Z(k) = diag[z(k)] y D2(k)=Z-1X.
Paso 3: Evaluar el vector auxiliar: í(ì)=ìe-XZe, e=(1,1,...,1)T.
Paso 4: Hallar el vector dirección de paso dual dy resolviendo el sistema:
108
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
[AD2(k)AT]dy(k) = -AZ-1í(ì)
Paso 5: Evaluar los vectores dirección de paso:
dz(k)=-ATdy(k) y dx(k)=[Z-1 - D2AT(AD2AT)-1AZ-1]í(ì)
Paso 6: Evaluar:
x(k+1) = x(k) + ñápdx(k), nuevo punto interior primal,
y(k+1) = y(k) + ñáddy(k), nuevo punto interior dual y
z(k+1) = z(k) + ñáddz(k), nuevo costo reducido.
Donde:
Criterio de parada:
Paso 7: Si el criterio de parada se cumple finalizar la iteración, en el caso contrario
aumentar en uno el valor de k e ir al paso 1.
Sin embargo debido a que estos algoritmos son de aproximación no es práctico imponer
esta condición de parada, por ello se ha establecido la condición (2.51). Esto nos dice que
la solución óptima, es decir, el punto de convergencia se puede obtener cuando ë se
encuentra entre 10-6 y 10-8. Evidentemente, otros umbrales inferiores a esos números
posiblemente proporcionarían soluciones más cercanas al óptimo pero no óptimas. La
109
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
diferencia entre el punto óptimo y la solución aproximada será menor cuanto menor sea el
umbral para ë.
Puesto que la condición de parada (2.55) (ë=0) es similar a la condición de parada del
algoritmo de Karmarkar, el criterio de parada difuso estaría dado por la expresión
lingüística “ë positivamente casi cero” es decir un número difuso con función de pertenencia
dado por (2.37). Igualmente la función g es la función definida por (2.39) con 0<r<1 y cm se
sustituye por ë0 (calculado según (2.51) o (2.55)) obtenido en la primera iteración.
Una vez introducida la condición de parada difusa, el decisor podrá fijar el grado á
(0<á<1) de tolerancia del incumplimiento de la regla de parada (2.55), es decir, el grado de
cercanía a cero de ë para considerar aceptable la solución que se obtenga. Con lo cual se
tiene el Criterio de Parada difuso:
ë # g-1(á)
esta condición debe ser utilizada en cada uno de los criterios de parada de los tres
algoritmos de puntos interiores, así se obtendrán dichos algoritmos con criterios de parada
difuso.
110
2.5 CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DE PUNTOS INTERIORES
Tabla 2.8: Grados de aproximación al costo óptimo 0 del ejemplo 1 de la sección 2.3.
111
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
0.977 0.0085 1.000625 0.999695 3 0.003 0.999991 0.9960991 5 0.0062 1.000625 0.99514 3
0.9976 0.0008868 0.000625 0.999695 3 0.00024 0.9999999 0.99952 59 0.00064 1.000031 0.99964 4
0.5 0.0014 1.000625 0.9996953 3 0.00039 0.9999998 0.99923 35 0.001 1.000031 0.99964 4
0.8 9.4594x10-7 1.0000018916 1-7.16x10-12 5545 0.00000025 1-7x10-14 0.9999995 61602 0.0000007 1.0000000039 0.9999999916 7
0.9 3.6954x10-9 1.0000000036 1.00 1310853 1.001x10-9 1.00 0.9999999992 15923095 2.68x10-9 1.0+1.9x10-11 0.99999999995 8
3
Tabla 2.9: Grados de aproximación al costo óptimo 1, del ejemplo 2 de la sección 2.3.
112
2.6 EJEMPLOS NUMÉRICOS COMPARATIVOS
Aplicando los algoritmos de puntos interiores con esta regla de parada difusa a los
mismos problemas utilizados en la sección 2.4 obtenemos los resultados mostrados en las
Tablas 2.8 y 2.9. En estos algoritmos, utilizando una función de pertenencia no lineal para
definir la regla de detención difusa se pueden emplear grados de tolerancias más realistas,
mientras que si se usa una función de pertenencia lineal se tienen que utilizar grados de
tolerancia muy altos pero aún así, se obtienen peores aproximaciones. Por otro lado, de
entre los tres algoritmos de puntos interiores, el algoritmo primal-dual requiere menor
número de iteraciones para alcanzar buenas aproximaciones, aunque el inconveniente
radica en la forma de obtener una solución inicial primal y dual simultáneamente.
Como dijimos al inicio de este capítulo, vamos a ilustrar las ventajas de utilizar el
criterio de parada difuso en los algoritmos de PL mediante dos ejemplos. El primer ejemplo
es el mismo que se ha utilizado en la sección 2.2 al ilustrar la versión difusa del algoritmo
simplex, el segundo, es el ejemplo de Klee-Minty [103] que muestra que el algoritmo simplex
es de tiempo de ejecución no polinomial y veremos allí que los algoritmos de puntos
interiores son más eficientes y, sobre todo, la ventaja de utilizar el criterio de parada difuso.
2.6.1 Ejemplo 1 :
Se trata de resolver:
113
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
error =
114
2.6 EJEMPLOS NUMÉRICOS COMPARATIVOS
á AS AK AVMF AB AP AD APD
error iteración error iteración error iteración error iteración error iteración error iteración error iteración
NO DIFUSO 0.00 4 0.00 5124000 5x10-6 19 0.00 9 5x10-8 9786 0.00 12232 0.00 9
DIFUSO-LINEAL
Tabla 2.10: Soluciones mediante algoritmos con y sin criterio de parada difuso.
Este logro, que constituye la mayor ventaja del uso de un criterio de parada difuso, se aprecia mejor en algoritmos menos eficientes,
115
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
como es el caso del algoritmo de Karmarkar original con respecto a las modificaciones del
mismo, como son los algoritmos de Vanderbei-Meketon-Freedman, Barnes y los tres
algoritmos de puntos interiores.
En la Tabla 2.10 al igual que en las Tablas anteriores se observa la ventaja de utilizar
una función de pertenencia no lineal y particularmente convexa con respecto a una función
de pertenencia lineal, ventaja que se hace más evidente en el algoritmo de Karmarkar.
Ilustramos los resultados de aplicar los algoritmos con criterio de parada difuso
estudiados en el ejemplo de Klee-Minty para n=6 (6 variables y 6 restricciones) en la Tabla
2.11. El ejemplo tal como está enunciado (n=6) es de tamaño 99, y expresado en su forma
estándar es de tamaño 147. Si combinamos el ejemplo con su dual y con la condición de
116
2.6 EJEMPLOS NUMÉRICOS COMPARATIVOS
igualdad de las funciones objetivo en el caso óptimo, se obtiene un sistema de tamaño 534.
Consecuentemente, la forma estándar de Karmarkar alcanza un tamaño 41.464, por lo cual
este algoritmo requeriría a lo sumo 12.936.768 de iteraciones para obtener la solución
óptima. Ya que es elevado el número de iteraciones que se requieren, no se ha intentado
resolver el ejemplo de Klee-Minty mediante el algoritmo de Karmarkar.
Todo lo expresado a la luz de los resultados mostrados en la Tabla 2.10 respecto del
primer ejemplo de esta sección se ve corroborado y aún reforzado con los resultados
mostrados en la Tabla 2.11. La nota más importante que recogemos de esta última Tabla
es el hecho de que el porcentaje del error promedio con respecto a la solución exacta es tan
sólo de 5.35, obtenido en tan sólo el 40.1727 % de iteraciones, cuando la función de
pertenencia es convexa y el grado de aceptación á=0.8. Proporciones semejantes se pueden
obtener también al trabajar con los datos de la Tabla 2.10.
Estos dos ejemplos son pequeñas muestras de las grandes bondades del uso de
criterios de parada difusos en los algoritmos denominados exactos. La ventaja de los
criterios de parada difusos se perciben mejor cuanto mayores sean las dimensiones de los
problemas de PL.
117
CRITERIOS DE PARADA DIFUSOS EN LA PROGRAMACIÓN LINEAL
á AS AVMF AB AP AD APD
error iteración error iteración error iteración error iteración error iteración error iteración
NO DIFUSO 0.00 63 0.00 52 0.00 302 0.00 2584 0.00 2586 0.00 12
DIFUSO-LINEAL
DIFUSO-NO
LINEAL
88.88 15 0.041 41 24.69 7 0.0014 7 0.186 6 0.058 5
0.5
23.46 44 0.00 46 8.64 13 0.00012 211 0.00029 93 0.00004 8
0.8
Tabla 2.11: Soluciones mediante algoritmos con y sin regla de parada difusa.
118
Capítulo 3
3.1 INTRODUCCIÓN
En el problema de la mochila se trata de llenar una mochila con todos los objetos
posibles que quepan de un total de n objetos, de tal manera que el valor de los objetos
transportados sea el mayor posible. Dicho en otras palabras, el objetivo es llenar la mochila
de tal manera que se maximice el valor de los objetos transportados respetando la limitación
de la capacidad impuesta.
El muy conocido problema del viajante de comercio, que brevemente se conoce como
TSP (Traveling Salesman Problem o Traveling Salesperson Problem) consiste en determinar
el programa de recorrido de una visita a cada una de n ciudades de tal manera que la
distancia total sea el menor y que no se repita ninguna de ellas por más de una vez.
El “problema de la mochila”, cuyo nombre apareció por primera vez en 1957 sugerido
por Dantzig [45] para referirse al problema que Bellman [12], unos años antes, denominó
como “problema de la carga”(loading problem), es un problema simple en su formulación,
como se puede observar, pero muy complejo para resolverlo, tal es así que constituye un
problema test para medir la eficiencia de diferentes algoritmos.
La importancia de este problema se puede percibir si lo reformulamos en otros
términos como por ejemplo, “se dispone de un capital c para financiar proyectos de inversión,
119
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
existen n proyectos candidatos que en total requieren capital muy superior al disponible. El
problema reside en seleccionar aquellos proyectos de tal manera que los beneficios sean los
mayores posibles.
A partir del enunciado anterior y de otros muchos alternativos, resulta evidente la
aplicabilidad del problema de la mochila en diversos problemas como los de selección de
proyectos y asignación de capital de inversión, los problemas de corte de stock (Cutting
Stock), o problemas de los de carga, etc. Un resumen y las correspondientes referencias de
estas y otras aplicaciones del problema de la mochila puede encontrarse en [175].
120
3.2 EL PROBLEMA DE LA MOCHILA
importantes para calcular las cotas superiores del problema de la mochila. En la 3.2.4 se
exponen las modificaciones que proponemos, la introducción de criterios de parada difusos
en los algoritmos que resuelven el problema de la mochila, y particularmente ilustramos
dichos criterios difusos en dos algoritmos de ramificación y acotamiento, y en dos algoritmos
de programación dinámica que estudiaremos en la sección 3.2.3. Finalmente en la sección
3.2.5 presentamos los resultados de experimentos numéricos, las comparaciones y las
conclusiones respectivas.
121
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Cualquier situación diferente se puede reducir siempre a este caso. Así por ejemplo,
si algunos parámetros son fracciones, multiplicamos por un factor apropiado. Si algún ítem
tiene valor negativo simplemente se descarta, y si tiene peso negativo pero con valor positivo
se selecciona; luego, se construye un nuevo problema excluyendo los ítems descartados y
admitidos inicialmente; y si la suma de los pesos es menor que la capacidad, la solución es
trivial pues todos los ítems son seleccionados para meter a la mochila.
Aunque en este trabajo fijaremos nuestra atención sólo en el problema clásico de la
mochila, no podemos dejar de mencionar los otros tipos de problemas de la mochila
derivados del problema clásico, también de importancia, que darían lugar a un posterior
trabajo ya que su estudio en profundidad desbordaría los límites de esta memoria. En
cualquier caso pueden destacarse los siguientes:
122
3.2 EL PROBLEMA DE LA MOCHILA
c) Un caso especial del PM se presenta cuando pj=wj (j=1,2,..,n), lo que se conoce como el
problema de subconjunto suma (subset-sum problem):
d) Si en el problema acotado de la mochila pj=1 (j=1,...,n) o bien todos los ítems tienen el
mismo valor, se obtiene el denominado problema de hacer cambios (change-making
problem):
123
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Cuando en este problema tanto el valor como el peso del ítem varía de acuerdo a la
mochila, estamos ante el problema de asignación generalizado.
A su vez, en cada uno de los casos anteriores, puede existir más de una función
objetivo. De ser así se originarían los correspondientes problemas de la mochila
multiobjetivo.
Sea z(PM) la función objetivo del problema de la mochila. Una cota superior de PM es
un número U tal que z(PM)#U. Para calcular una cota superior se han desarrollado
diferentes algoritmos, siendo de mayor importancia los derivados de la relajación continua
por una parte y por otra parte los de enumeración parcial. Revisaremos en esta sección las
cotas superiores obtenidas mediante la relajación y por enumeración parcial; todas ellas
tomadas de [134].
124
3.2 EL PROBLEMA DE LA MOCHILA
La relajación continua es una relajación natural y quizás por ello, fue la primera en
ser propuesta. Dicha relajación se ha denominado problema continuo de la mochila, que
denotaremos por C(PM), y se obtiene a partir de (3.1) reemplazando la condición de variable
binaria por variable con valores en el intervalo [0,1], es decir:
C(PM):
donde
125
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
(3.
Martello y Toth obtienen una cota superior mejor que la de Dantzig imponiendo la
condición de que la variable crítica xs sea entera. Así, se tienen:
126
3.2 EL PROBLEMA DE LA MOCHILA
donde
como consecuencia se obtiene una cota superior mejor, que es la conocida como cota superior
de Hudson-Fayard-Plateau:
con la notación
127
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
y luego, definiendo
J(ë) = { j: pj/wj > ë },
con los cuales el valor de la solución resulta:
viene a ser:
(3.17)
Esta cota es mejor que la cota de Dantzig, pero, en general, no es mejor que las cotas
U2 y U3, aunque en algunas situaciones se cumple que U 4 < U3 # U2 # U1.
siguiente manera:
Ahora sean
128
3.2 EL PROBLEMA DE LA MOCHILA
dada por:
Teniendo como referencia el ítem crítico s, Martello y Toth [133] propusieron otra
forma de determinar una cota superior del problema de la mochila. Para ello seleccionan
números r y t tales que 1 < r # s y s # t < n, y construyen una solución factible de PM
haciendo xj=1 para j<r, xj=0 para j>t y hallando la solución óptima del sub-problema PM(r,t)
definido por los ítems r,r+1,...,t con capacidad
La solución óptima del subproblema PM(r,t) se calcula mediante el árbol de decisión binaria
para j=r,r+1,...,t, generando pares de nodos de decisión haciendo xj = 1 y xj = 0 en cada
nodo k. Para cada nodo k del árbol resultante, sea f(k) el ítem que ha generado el nodo k
(haciendo xf(k) = 1 o xf(k) = 0). El conjunto de los nodos terminales (ramas) del árbol puede ser
particionado en:
(Ramas
129
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
(Ram
Luego para cada l 0 L1cL2, sea ul una cota superior de PM, definida de la siguiente manera:
donde:
Esta cota es mejor que las cotas anteriores excepto la cota de Dudzinsky y
Walukiewicz. Por tanto, la mejor cota de entre las seis cotas dadas es:
Para cada uno de los modelos presentados en la sección 3.2.1 y para otros casos
especiales existen muchos algoritmos de solución. Una muy buena recopilación de dichos
algoritmos puede encontrarse en [134]; también [175] recoge un buen número de algoritmos
para resolver particularmente el problema de la mochila en su caso más simple. Los
algoritmos que presentamos aquí se han recogido de estos dos libros.
130
3.2 EL PROBLEMA DE LA MOCHILA
construido los algoritmos más eficientes para resolver el PM, en este trabajo hemos elegido
dos algoritmos basados en el método de ramificación y acotación que veremos en la sección
[Link] y dos algoritmos basados en la programación dinámica que veremos en la sección
[Link]. Además, previamente en la sección [Link], revisamos un algoritmo aproximado y
una heurística de tipo voraz (greedy). Sobre cada uno de los algoritmos que estudiamos,
explicamos su metodología general y presentamos su procedimiento detallado en la forma
de pseudo-código-pascal, siguiendo la misma forma que utilizan Martello y Toth [134].
Los algoritmos voraces son los más fáciles de entender e implementar y típicamente
se utilizan para resolver problemas de optimización. Se puede decir que su procedimiento
se asemeja al de un “método de la fuerza bruta”, característica por la cual actúan de modo
inmediato basándose sólo en la información actual, y sin tener en cuenta los efectos futuros,
y sobre todo, no revisan (sino que olvidan) las decisiones tomadas anteriormente.
Los algoritmos voraces, pese a su simplicidad, aparecieron tardíamente -en 1971-
introducidos por Edmonds [59]. Por su tosquedad, son inaplicables en muchos casos, y
131
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
pueden proporcionar resultados erróneos, haciendo creer por ejemplo, que un problema no
tiene solución aún teniéndola. Generalmente las soluciones que proporciona no son óptimas.
A pesar de todas sus limitaciones en muchas circunstancias son algoritmos muy eficientes.
De ahí que sean frecuentemente utilizados como heurísticas en problemas NP-completos.
En este trabajo los utilizaremos como referencia en la definición de los criterios de parada
difusos.
Los algoritmos voraces aplicados al problema de la mochila dan lugar al algoritmo que
aquí llamaremos algoritmo voraz, cuya metodología de funcionamiento se basa en el más
elemental sentido común. Pués, sabiendo que los ítems están ordenados de mayor a menor
valor por unidad de peso, este algoritmo los introduce ordenadamente, desde el primero
hasta el último, excluyendo sólo el ítem que no quepa en el espacio restante de la mochila.
El algoritmo voraz, puede también entenderse como la modificación de la solución
continua (solución de la relajación de PM en programación lineal vista en [Link].1). Esta
modificación consiste en asignar valor cero a la única variable con valor fraccionario; luego
se asigna valor uno (si existe) a aquella variable que tiene valor cero y que corresponde a
un ítem cuyo peso no excede al espacio restante de la mochila; y así sucesivamente hasta
llenar la mochila o hasta terminar de verificar los ítems restantes. Basándonos en esto, el
algoritmo voraz para resolver el problema de la mochila, ordenado como en (3.2), podemos
resumirlo de la siguiente manera:
Etapa Inicial:
Determinar el ítem crítico s; luego, hacer:
Etapa Iterativa:
Naturalmente, la regla de parada implícita es j=n, por tanto el valor final de la función
132
3.2 EL PROBLEMA DE LA MOCHILA
objetivo es z*=zn.
Procedimiento Voraz:
for j:=1 to n do
begin
if then xj:=0
else
begin
end;
if pj>pj* then j*:=j
end;
if pj* > zg then
begin
z g :=pj*;
for j:=1 to n do xj:=0;
x j*:=1;
end;
end;
133
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Procedimiento S(k)
end;
134
3.2 EL PROBLEMA DE LA MOCHILA
Procedimiento GS
end;
135
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
partición del conjunto factible en subconjuntos, mientras que el término acotación se refiere
a la determinación de cotas para el valor de la función objetivo sobre cada uno de los
subconjuntos obtenidos en la partición.
136
3.2 EL PROBLEMA DE LA MOCHILA
a) En cada nodo se selecciona el ítem j con el máximo valor por unidad de peso de entre los
ítems que aún no están seleccionados y se generan dos nodos descendientes asignando
a xj respectivamente el valor 1 y 0.
b) La búsqueda continúa desde el nodo asociado con la selección del ítem j (condición xj=1),
es decir, siguiendo la estrategia del algoritmo voraz.
Cada una de las acciones indicadas arriba, las ejecuta como pasamos a relatar. Un
movimiento hacia adelante consiste en insertar el mayor número posible de nuevos ítems
consecutivos en la solución actual, y un movimiento de retroceso consiste en borrar el más
reciente ítem insertado de la solución actual. Cuando el movimiento hacia adelante es
exhaustivo, se calcula la cota superior U1 correspondiente a la solución actual para comparar
con la mejor solución obtenida. Se efectúa un movimiento hacia adelante si se obtiene una
mejora, y se retrocede en caso contrario. Cuando se ha analizado el último ítem se ha
completado la solución actual y entonces, se actualiza la mejor solución. El Criterio de
parada, que es lo que nos interesa, indica que el procedimiento de este algoritmo finaliza
cuando no se puede efectuar ningún retroceso.
137
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Procedimiento HS:
5. [Retrocede]
end;
138
3.2 EL PROBLEMA DE LA MOCHILA
represen
: ta al valor de la mejor solución actual.
Por otra parte el algoritmo de Martello y Toth (MT1) es una eficiente modificación del
algoritmo de HS, realizada por Martelo y Toth [132], en los siguientes:
a) Utiliza la cota superior U2 en lugar de U1.
b) El movimiento asociado con la selección del j-ésimo ítem se efectúa en dos fases:
i) Construcción de una nueva solución, y ii) Almacenamiento de la solución actual.
En la primera fase, si j es el ítem actual, se determina el conjunto Nj con el mayor
número de ítems consecutivos a partir del ítem j que pueden ser insertados en la mochila,
y también se determina la cota superior U2 correspondiente. Si esta cota superior es
menor o igual que el valor de la mejor solución obtenida se hace un movimiento de
retroceso; por el contrario, si es mayor se pasa a la siguiente fase. En la segunda fase,
existen dos posibilidades, una, que se haya obtenido la solución máxima en cuyo caso se
actualiza la mejor solución y no la solución actual para poder efectuar el retroceso en Nj,
y la otra, el caso contrario, en que sí se efectúa la inserción de N j en la solución actual.
c) La tercera modificación consiste en que se realiza un movimiento especial hacia adelante,
sobre la base del criterio de dominancia, siempre que después de un movimiento hacia
atrás sobre el ítem i, la capacidad residual no permita la inserción en la solución actual
de ningún ítem siguiente al i-ésimo. Esto se debe a que la solución actual puede ser
mejorada sólo si el ítem i es reemplazado por un ítem con el mayor valor y un peso
suficientemente pequeño, o cuando menos, mediante dos ítems que tengan peso global
no mayor que el peso i más la capacidad residual.
139
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Procedimiento MT:
1.[Inicialización]
continúa...........
140
3.2 EL PROBLEMA DE LA MOCHILA
5. [Retrocede]
end;
d) La cuarta y última modificación consiste en que las cotas superiores asociadas con los
nodos del árbol de decisión se calculan mediante una técnica paramétrica basada en el
almacenamiento de la información relacionada con la solución actual. Imaginémonos que
la solución actual ha sido construida insertando todos los ítems desde el j hasta r.
141
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Entonces, cuando se efectúa un retroceso sobre uno de los ítems, digamos item i ( j# i<r),
si no se han insertado los ítems precedentes al ítem j, es posible insertar cuando menos
los items i+1,...,r en la nueva solución actual. Con esta finalidad se introducen las
notaciones:
El procedimiento detallado del algoritmo MT1, con las mismas notaciones usadas
en el algoritmo anterior, se presenta en el Cuadro 2.5.
142
3.2 EL PROBLEMA DE LA MOCHILA
El objetivo de todo sistema de decisión es elegir la mejor decisión posible, lo que se refleja
cuando se consigue optimizar la medida de efectividad, es decir,
h(X) = opt(r(X,D)).
la salida de la k-ésima etapa con entrada Xk-1 , con decisión Dk y con transformación fk, y sea
143
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Rk=rk(Xk-1,Dk)
su correspondiente medida de efectividad.
Entonces el sistema de decisión inicial queda descompuesto en n etapas para k=1,2,...,n
respectivamente, lo que da base al principio de optimalidad de Bellman.
donde * representa alguna operación que está relacionada con el problema en concreto.
144
3.2 EL PROBLEMA DE LA MOCHILA
Bellman-Dantzig siguiente:
solución factible. Los estados dominados son aquellos estados para los cuales
calcularla ni reservarla.
145
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
notaciones:
s: número de estados en la etapa m-1; (3.23)
b: con valor 2m-1 (3.24)
W1i : peso total del i-ésimo estado (i=1,...,s) (3.25)
P1i: valor total del i-ésimo estado (i=1,...,s) (3.26)
X1i={xm-1,xm-2 ,...,x1} (3.27)
donde xj define el valor de la j-ésima variable en la solución óptima parcial del i-ésimo
estado, es decir,
Procedimiento PRODIN
end;
146
3.2 EL PROBLEMA DE LA MOCHILA
Procedimiento RECUR
end;
147
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
En los procedimientos se utilizan los índices i para revisar los estados de la etapa
actual y el índice k para guardar los estados de la nueva etapa. Cada estado actual puede
producir un nuevo estado de peso total y=W1i+wm; así los estados actuales son de peso total
W1h<y, y el nuevo estado se guarda en la nueva etapa siempre que sea no dominado por
algún estado ya guardado. Después de la ejecución de RECUR los valores (3.23) y (3.24) son
relativos a la nueva etapa, mientras que los nuevos valores de (3.25), (3.26) y (3.27) son
dados por (W2k), (P2k) y (X2k), respectivamente. Además, X1i y X2k, utilizados en los
procesos PRODIN y RECUR son números enteros cuya representación binaria es la
concatenación de los elementos del conjunto dado en (3.27), es decir, son números cuya
representación binaria es la concatenación de xm-1,xm-2,...,x1.
148
3.2 EL PROBLEMA DE LA MOCHILA
partición de N:
J1 = { j 0 N: xj = 1 en todas las soluciones exactas de PM }
J0 = { j 0 N: xj = 0 en todas las soluciones exactas de PM }
F=N\(J1cJ0).
Si se conoce tanto J1 y J0, el PM se transforma en el problema más simple siguiente:
donde
(respectivamente (3.28)
(3
149
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Procedimiento REDUC
end;
150
3.2 EL PROBLEMA DE LA MOCHILA
Dicha referencia que proponemos, estaría constituida por una cota inferior L0 y una
cota superior U0 para el valor z* de la solución óptima del problema de la mochila, es decir,
L0 # z* # U0.
151
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Estas cotas tienen que ser obtenidas para cada ejemplar que se pretenda resolver.
Como cota superior, por ejemplo, puede utilizarse cualquiera de las cotas superiores
estudiadas en la sección 3.2.2, y como cota inferior, por ejemplo, la solución obtenida
mediante el algoritmo voraz ó la suma de todos los valores menores que el ítem crítico. Es
recomendable utilizar la cota de Dantzig U1 para la cota superior mientras que para la cota
inferior se puede utilizar cualquiera de las formas sugeridas. Así, el tiempo de cálculo de L0
y U0 sería a lo sumo de O(n). Usar otras formas de cálculo de la cota superior sólo
incrementaría el tiempo de ejecución, que es precisamente lo que se quiere evitar con la
introducción del criterio de parada difuso.
Cuando se conocen solamente la cota inferior y superior del valor de la solución
óptima, este valor puede expresarse como un número difuso, mediante una función de
pertenencia, de la siguiente forma:
donde f(.) es una función continua no decreciente con valor entre [0,1].
a) Que el valor z* sea mayor que f-1(á), en cuyo caso se obtendrá una solución aceptable.
b) Que el valor óptimo z* sea menor o igual que f-1(á), en cuyo caso el criterio de parada
difusa no tendrá sentido ya que el proceso nunca terminaría, razón por la cual es
necesario mantener los criterios exactos, y que el criterio difuso sea adicional.
152
3.2 EL PROBLEMA DE LA MOCHILA
Una forma de reducir la posibilidad de que se presente el caso (b) es utilizando una
función f(.) cóncava. Como vemos en la Figura 3.2, se cumple f-1(á) < h-1(á) cuando f es
cóncava pero h no lo es. La importancia de esta característica radica en que existe grandes
posibilidades de evitar el caso (b) cuando se utiliza una función cóncava f en la definición
de la pertenencia (3.30), mientras que si se utiliza una función no cóncava como h de la
Figura 3.2 hay pocas posibilidades de evitar que se cumpla el caso (b).
donde n>1. Esta función tienen inversa, ya que es inyectiva en el dominio de definición de
la función de pertenencia (3.30).
(3
153
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
La instrucción que aparece con letras mayúsculas corresponde al criterio de parada difuso.
En el caso del algoritmo MT1 los criterios de parada son explícitos. El procedimiento
se detiene cuando alcanza la cota U 2 o cuando no existe ningún retroceso posible.
En la flexibilización de este algoritmo modificamos la condición: si z=U2 , detener el
proceso, por la condición si se cumple (3.31), detener el proceso, es decir, en el procedimiento
MT del Cuadro 3.5, tanto en el número 4 como en el número 6, la instrucción:
if z = U then return;
154
3.2 EL PROBLEMA DE LA MOCHILA
S En el procedimiento PRODIN:
S En el procedimiento RECUR:
Con ambos procedimientos se obtiene el algoritmo dinámico con estados reducidos y con
criterio de parada difuso.
En el caso del algoritmo HS2, que divide el problema en dos sub-problemas y los
resuelve cada uno usando ADER para finalmente combinar los resultados obtenidos, la
flexibilización, adicionalmente a la heredada de la flexibilización de ADER, tiene que
hacerse en la parte de la combinación de las listas de los resultados de los dos subproblemas
155
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
imponiendo la condición (3.31). Con este último criterio adicional, la combinación de las
listas finales no se hará con todos los resultados sino solo hasta que cumpla con la condición
(3.31).
En cada una de las Tablas de los resultados que corresponden a cada uno de los
algoritmos con criterios de parada difusos vistos en la sección 3.2.4, para cada valor á
indicado, se consignan el error cometido y el tiempo de ejecución. El error se obtiene
mediante la siguiente fórmula:
Debido a que los algoritmos con criterios de parada difusos son algoritmos de
aproximación, para comparar su ventaja con respecto al algoritmo aproximado de Sahni se
muestran también los resultados que proporciona dicho algoritmo tanto para k=2 como para
k=3.
En los criterios de parada difusos de los cuatro algoritmos revisados en la sección
3.2.4, cuyos resultados presentamos en esta sección, se ha utilizado la condición:
z $ L0 +(U0 -L0).á4
es decir, los criterios difusos están definidos mediante la función de pertenencia (3.30) con
f(.) dada por (3.32) con n=4 (un valor no muy grande pero que le da buena concavidad a la
función f); L0 es la solución respectiva obtenida mediante el algoritmo voraz y U0 es la cota
de Dantzig.
156
3.2 EL PROBLEMA DE LA MOCHILA
Las Tablas 3.1, 3.2, 3.3 y 3.4 muestran los resultados de los experimentos
computacionales tras haber utilizado los algoritmos con criterios de parada difusos de la
sección 3.2.4, y en cada una de ellas, para poder compararlas, se consignan los resultados
que proporciona el algoritmo aproximado de Sahni .
1.000 .001928 .042 .00517 .03 .003959 .04 .0032556 .11 .002471 .23
5.000 .000098 1.462 .000464 1.407 .000316 1.446 .000237 2.538 .000168 4.58
10.000 .00002 4.736 .000098 4.624 .000059 4.712 .000298 8.802 .000272 13.97
50.000 .0 114.324 .000022 114.114 .000013 114.312 .000003 212.476 .0 257.764
157
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
caso no difuso y con respecto al algoritmo aproximado de Sahni es muy grande, haciéndose
más significativa cuando n (número de ítems) se incrementa.
Asimismo, el algoritmo de Martello-Toth con criterio de parada difuso (del método de
ramificación y acotación), es más ventajoso en cuanto al tiempo de ejecución respecto al
algoritmo aproximado de Sahni, esta ventaja se hace más significativa cuando n se
incrementa; aunque supone sólo una leve mejoría con respecto a la solución exacta, como
podemos observar en la Tabla 3.2.
Las ventajas que se observan en el tiempo de ejecución de los algoritmos con criterios
de parada difusos alcanzan mayor relevancia si tenemos en cuenta que el algoritmo
aproximado de Sahni se ha aplicado después de reducir (mediante el procedimiento REDUC
Cuadro 3.8.) el problema inicial, reducción que consigue una disminución considerable de
tiempo de ejecución.
Con relación a los resultados de las Tablas 3.3.y 3.4, la escasa diferencia que existe en
los tiempos de ejecución se debe a que se ha utilizado primero el algoritmo de reducción de
Martello-Toth (procedimiento REDUC Cuadro 3.8), y luego, se ha aplicado solamente en el
problema reducido, tanto los algoritmos con criterios de parada difusos como el algoritmo
aproximado de Sahni. Aún así, se observa la ventaja en el tiempo de ejecución de los
algoritmos con criterios de parada difusos con respecto los algoritmos correspondiente sin
los criterios difusos, y con respecto al algoritmo aproximado de Sahni, se aprecia la ventaja
en el error correspondiente.
1.000 .001928 .24 .004367 .19 .00382 .236 .0032556 .11 .002471 .23
5.000 .000098 3.778 .000276 3.076 .000247 3.098 .000237 2.538 .000168 4.58
10.000 .00002 12.198 .000069 10.182 .000029 10.252 .000298 8.802 .000272 13.97
50.000 .0 223.944 .000004 218.350 .000003 218.376 .000003 212.476 .0 257.764
158
3.2 EL PROBLEMA DE LA MOCHILA
1.000 .002576 .67 .006421 .428 .004398 .484 .0032556 .11 .002471 .23
5.000 .000177 12.978 .000672 11.534 .000395 12.918 .000237 2.538 .000168 4.58
10.000 .000024 61.364 .000118 41.688 .000029 41.976 .000298 8.802 .000272 13.97
50.000 .0 488.136 .000016 483.292 .000011 485.070 .000003 212.476 .0 257.764
El TSP, pese a que según Hoffman y Wolfe [83] los orígenes de este problema se
encuentran en los planteamientos tanto de Euler como de Vandermonde (siglo XVIII) sobre
la ruta del caballo en un tablero de ajedrez, en el mundo de las matemáticas recién a
principios de la década 50 alcanzó gran popularidad debido a su relación con prominentes
problemas combinatoriales que dieron origen a nuevas ramas de la programación lineal
como son los problemas de asignación y problemas de transporte.
Actualmente, no existe ninguna discusión sobre la importancia del TSP, por una parte
por sus múltiples aplicaciones como se puede ver en [ 20, 44, 60, 68, 112, 118] entre otros;
y por otra parte porque el TSP, debido a su característica de NP-completo entre otras
razones, constituye un banco de pruebas de diversos algoritmos ya sean exactos,
159
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Puesto que la aspiración del viajante es recorrer la menor distancia posible, la función
objetivo será:
Para garantizar que cada ciudad j sea visitada una única vez, debemos imponer dos
condiciones, la primera
para indicar que a cada ciudad el viajante llega una sola vez y la segunda condición
160
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
para indicar que el viajante sale una sola vez de cada ciudad.
Si utilizamos el lenguaje de grafos para representar el TSP, los nodos como ciudades
y los caminos como arcos, la condición (3.35) indica que para cada ciudad hay un sólo arco
de llegada, mientras que la condición (3.36) indica que hay un sólo arco de salida.
Adicionalmente, debido a que las dos condiciones anteriores no evitan que se generen
sub-rutas aisladas unas de otras, se deben incluir otras restricciones. Un conjunto de
ciudades QdN ( N = { 1,2,...,n} ) forman una sub-ruta si en el recorrido el viajante no puede
salir de dicho grupo de ciudades, esto se puede evitar introduciendo un arco que una la
ciudad i de Q con cualquier ciudad de N-Q; en general se evitará una sub-ruta si imponemos
la condición de que siempre alguna ciudad i de todo subconjunto Q estará unido con alguna
ciudad j de N-Q, esto es:
o equivalentemente
esta última restricción indica que en cada subconjunto QdN el número total de arcos debe
ser menor que el número de ciudades *Q*.
161
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
donde, cuando i=j se asume que dii es suficientemente grande para obligar que en el óptimo
xii=0.
(3.40)
sujeto a:
162
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
El uso de una u otra forma de representación depende del método y tipo de algoritmo que
se utilice para resolver el correspondiente problema.
Para encontrar las primeras aplicaciones del método de ramificación y acotación (RA)
en la solución del TSP tenemos que remontarnos al año 1954, año en que Dantzig, Fulkerson
y Johnson [48] propusieron un método para resolver el TSP. Dicho método tenía las
características de lo que ahora se conoce como el método de ramificación y acotación, aunque
entonces aún no se conocía como un método general para resolver problemas de optimización
de características específicas. Desde entonces hasta la actualidad se han desarrollado
diferentes tipos de algoritmos de RA para resolver el TSP. Una recopilación de los más
importantes podemos encontrarla en [6].
Versión 1:
Paso 1: (Inicialización) Poner el TSP en una lista (de subproblemas activos). Inicialice la
cota superior U=4.
Paso 2: (Selección de un subproblema): Si la lista es vacía, detener el proceso, la ruta
asociada con U es óptima (ó si U=4, el TSP no tiene solución). En otro caso
seleccione un subproblema TSPi de acuerdo a una regla de selección del
subproblema y borrar TSPi de la lista.
Paso 3: (Acotación inferior) Resolver la relajación Ri del TSPi o hallar la cota v(Ri ) de Ri.
Sea Li el valor obtenido:
Si Li$U, regresar al paso 2.
Si Li <U, y la solución define una ruta para TSP, reemplazar la mayor ruta
163
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Versión 2:
Paso 1: (Inicialización) Igual que en la versión 1, pero aquí hay que resolver R antes de
poner el TSP en la lista.
Paso 2. (Selección de un sub-problema): Igual que en la versión 1.
Paso 3: (Acotación superior: opcional) Igual que en el paso 4 de la versión 1.
Paso 4: (Reducción: opcional) Igual que en el paso 5 de la versión 1.
Paso 5: (Ramificación) Usar una regla de ramificación para definir el conjunto de sub-
problemas TSPi1,...,TSPiq, generado del sub-problema actual TSPi,.
Paso 6: (Acotación inferior) Si todos los subproblemas a ser generados de TSPi, de acuerdo
a una regla de ramificación, ya existen, ir al paso 2. En otro caso generar el
siguiente subproblema TSPij, definido mediante una regla de ramificación, resuelve
la relajación Rij deTSPij, o hallar v(Rij) de Rij. Sea Lij el valor obtenido:
Si Lij$U, repetir el paso 6.
Si Lij <U, y la solución define una ruta para TSP, reemplazar la mejor ruta previa
por esta nueva ruta, y hacer U=Lij. luego repetir el paso 6.
Si Lij <U, y la solución no define una ruta para TSP, colocar TSPij en la lista y luego
repetir el paso 6.
164
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
El punto básico en los algoritmos de RA, lo constituyen las relajaciones y las reglas
de ramificación. Existen muchas relajaciones utilizadas, y a su vez dentro de cada
relajación varias reglas de ramificación. Cada una de ellas determinan algoritmos
diferentes. Una revisión de las relajaciones más importantes con sus respectivas reglas de
ramificación se puede encontrar en [6,111], las mismas que revisamos a continuación.
165
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
función objetivo (3.40). Este sub-grafo H se denomina 1-árbol que minimiza (3.40). Para
facilitar la obtención del tal 1-árbol, se combina la función objetivo (3.40) y las restricciones
(3.41) mediante multiplicadores de lagrange, razón por la cual también se denomina
relajación lagrangiana.
166
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
donde:
además dij son los coeficientes de la matriz de distancias reducidas del nodo anterior, es
decir, la matriz que queda después de obtener la asignación óptima en el nodo anterior.
el costo reducido de la solución óptima del sub-problema. Entonces para cada arco (i,j), i0S,
j0T con costo reducido 0, calculamos:
167
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Una vez escogida la variable de ramificación xrs, los dos nuevos nodos se obtienen haciendo
xrs =1 y xrs =0 respectivamente, es decir en el primer nodo nuevo, el conjunto I tiene como
nuevo elemento al arco (r,s), y en el segundo nuevo nodo el conjunto E tiene al arco (r,s),
como un nuevo elemento.
Paso 1: [Inicialización] Hacer U=4 (mejor cota y valor actual) y L={TSP} (lista de sub-
problemas).
Paso 2: [Selección de un sub-problema] Si L=ö detener el proceso, pues la ruta asociada con
U es óptima (si U=4 el TSP no tiene solución).
Si L
ö, elegir el sub-problema TSPi de más reciente creación, y eliminarlo de la
lista L. Ir al paso 3.
Paso 3: [Determinación de una cota superior] Resolver mediante el método Húngaro el
AP(TSPi). Sea Zi el valor obtenido:
Si Zi $U, regresar al paso 2.
Si Zi <U y la correspondiente solución es una ruta para TSP (es decir no existen
subrutas) entonces hacer U=Zi.
Si Zi <U, y la correspondiente solución no define una ruta para TSP (es decir si
existen sub-rutas) ir al paso 4.
Paso 4: [Ramificación] Elegir xrs de acuerdo a (3.47), y generar dos nuevos sub-problemas
TSPi1 y TSPi2, fijando xrs=0 y xrs=1 respectivamente. Hacer L=Lc{ TSPi1,TSPi2 }. Ir
al paso 2.
En general todo algoritmo aproximado o heurística proporciona una cota superior del
168
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
valor óptimo de un TSP. Una revisión de estos tipos de algoritmos podemos encontrarla en
[73, 97, 111, 131, 198].
La cota superior para el valor óptimo del TSP que utilizaremos en este trabajo será
obtenida mediante la heurística denominada Procedimiento de Construcción de una Ruta.
Es una heurística que se inicia con pocas ciudades, pero va adicionando una a una las
ciudades restantes en el recorrido. El orden y la forma en que adiciona cada ciudad se basa
en algún criterio que habrá que fijar, y que le confiere una marcada naturaleza voraz. Por
lo tanto en esta heurística se distinguen tres componentes:
S La elección de una sub-ruta inicial.
S El criterio de selección, y
S El criterio de inserción.
Existen diferentes heurísticas con estas componentes pero que se diferencian entre si
por el procedimiento utilizado en cada una de ellas. Aquí, debido a su eficiencia y
simplicidad, hemos elegido la heurística denominada Procedimiento de la Inserción
Arbitraria, propuesto por Rosenkrantz, Stearns y Lewis [162]
Paso 1: [Inicio] Inicialice la sub-ruta 16i61, con i que minimiza d1i + di1.
Paso 2: [Selección] Seleccione la ciudad k+1 (k+1
i) siendo k la última ciudad insertada.
169
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Paso 3: [Inserción] Encontrar el arco {i,j} en la sub-ruta el cual minimiza dik +dkj-dij . Inserte
k entre i y j.
Una cota inferior para el valor óptimo del TSP es el valor óptimo de su relajación.
Particularmente el valor óptimo de PA(TSP) constituye una cota inferior. Más aún a partir
de la matriz reducida, producida por la asignación óptima, se puede obtener una mejor cota
inferior, si esta asignación no proporciona una ruta de TSP (es decir si no existen sub-rutas).
En este último caso, la función objetivo de TSP se puede escribir en la forma:
Ahora, definamos el grafo G0 que incluye todos los n nodos y sólo los arcos (i,j)
correspondientes a la distancia reducida cero, es decir, . A su vez, en el grafo G0
esta condición.
Sean K1,...,Kr todas las componentes de G0, entonces puede demostrarse que
170
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
Solo hay algoritmos exactos que resuelven el TSP para casos especiales o para un
número reducido de ciudades, como podemos ver en [27, 72]. Para los casos generales se han
desarrollado algoritmos aproximados o heurísticas de tipo clásico, como podemos ver en
[73,97] y heurísticas que utilizan procedimientos basados en las leyes naturales, como son
los algoritmos genéticos, recocido simulado etc. [111, 131, 198].
Cuando incluimos los criterios de parada difusos en los algoritmos exactos, lo que
hacemos es flexibilizar el algoritmo de tal manera que puede ser manipulado fácilmente por
el decisor, es decir, si el tiempo de ejecución para obtener la solución óptima es muy
prolongado, el decisor puede considerar aceptable una solución cercana a la óptima, pero
obtenida en un tiempo razonable.
Para esto, consideramos que el valor de la solución óptima del TSP no solo es una
incógnita, sino también un valor impreciso, debido a que valores cercano a la óptima puede
ser admitidos por el decisor como si lo fueran, es decir, es un conjunto difuso con soporte
determinado por una cota inferior L0 y una cota superior U0, y mediante una función de
pertenencia:
Esta función de pertenencia indica que si el valor z de una ruta TSP es superior a U0,
no es admitido por el decisor. Un valor menor que L0 sería una buena solución, y los valores
entre L0 y U0 son aceptables, pero el grado de aceptación se incrementa, a medida que
171
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
Para que esta condición proporcione los resultados esperados por el decisor, los valores L0,
U0 y la función f en la definición del conjunto difuso deben ser adecuados. Unos valores
inapropiadas de L0 y U0 pueden conducir a soluciones con grandes errores. Así mismo una
función inadecuada puede anular la flexibilización.
Si flexibilizamos los algoritmos de RA del TSP, una buena cota inferior está dada por
el valor óptimo de una relajación. Mientras que una cota superior apropiada puede
obtenerse como en la sección [Link].
172
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
173
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
174
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
Utilizando el algoritmo LMSK con criterio de parada difuso, en el que la función f está
dada por (3.51), con n=2, se obtiene L0=208, U0=308 y las soluciones aceptables para
distintos valores de á se muestran en la Tabla 3.5.
Se observa que para á=0.8, la solución aceptable se obtiene resolviendo sólo las 2/3
partes del total de los sub-problemas que el algoritmo clásico tiene que resolver. Sin
embargo el valor aceptable que se obtiene es muy cercano al óptimo. Por lo tanto es evidente
que la proporción del tiempo que se ahorra es muy superior en comparación con el
diferencial del valor aceptable con valor óptimo. Además para á=0.94 se obtiene una
solución aceptable que es exacta, en menos iteraciones que con el algoritmo original clásico.
Estas ventajas se hacen más evidentes cuanto mayor es el número de ciudades en el TSP.
175
CRITERIOS DE PARADA DIFUSOS EN ALGORITMOS DEL PM Y DEL TSP
176
3.3 EL PROBLEMA DEL VIAJANTE DE COMERCIO
177
COMENTARIOS FINALES
Con la constante variación de las características del mundo empresarial, nunca una
base de modelos de un sistema de soporte de decisión (SSD) es completa, lo que se
evidencia con la incesante aparición de problemas reales para los cuales en el SGBM no
existen modelos con sus correspondientes métodos de solución apropiados o bien los
existentes presentan limitaciones. Ante esta situación se presentarían dos opciones a
seguir (no excluyentes o mejor dicho complementarias): una, la actualización
permanente del SGBM y otra, el diseño de nuevos modelos y métodos de resolución o el
reajuste de los existentes para resolver los nuevos problemas.
En lo que respecta a este trabajo, como se expuso en la introducción, nos ha
preocupado de entre los problemas de la asignación de recursos limitados y del control de
acciones cambiantes con el tiempo, los siguientes aspectos:
177
COMENTARIOS FINALES
CONCLUSIONES
III. Los criterios de parada difusos están asociados con conjuntos difusos y éstos,
definidos a su vez mediante funciones de pertenencia. Estas funciones de
pertenencia deben ser no lineales, convexas o cóncavas, de acuerdo a las
particularidades de los problemas, para obtener los mejores resultados.
IV. El uso de los criterios de parada difusos en los algoritmos exactos permite obtener
nuevos algoritmos de tipo heurístico que proporcionan soluciones aceptables
(cercanas al óptimo) en tiempos de ejecución razonables.
178
CONCLUSIONES
179
COMENTARIOS FINALES
Los algoritmos exactos más importantes del problema de la mochila son los
basados en los métodos de ramificación y acotación, por un lado, y los basados en
la programación dinámica, por otro lado. En algunos de los más eficientes de
estos tipos de algoritmos hemos introducido criterios de parada difusos, en los
que ha quedado verificado la ventaja de utilizar funciones de pertenencia no
lineales cóncavas. De esta manera se han obtenido algoritmos de aproximación
que son más eficientes que el algoritmo aproximado de Sahni, haciéndose más
significativa la ventaja cuando el número de ítems se incrementa.
180
CONCLUSIONES
LÍNEAS FUTURAS:
Por lo tanto, las líneas futuras en este contexto están abiertas en todos los ámbitos,
como el de la programación no lineal por citar alguno.
181
COMENTARIOS FINALES
182
BIBLIOGRAFÍA
183
BIBLIOGRAFÍA
[19] Bit, A.K., M.P. Biswal y S.S. Alam, Fuzzy programming approach to multiobjective
solid transportation problem, Fuzzy Sets and Systems 57 (1993) 183-194.
[20] Bland, R.G. y D.F. Shallcross, Large traveling salesman problems arising
experiments in X-ray crystallography; a preliminary report on computation,
Operations Research Letters 8 (1989) 125-128.
[21] Braasard G. Y P. Bratley, Algoritmica:Concepción y Análisis, Masson (ed.
Española), Barcelona 1990.
[22] Brassard G. Y P. Bratley, Fundamentos de Algorítmia, Prentice Hall, Madrid, 1•
reimpresión 1998 (Primera edición 1997).
[23] Buckley , J. J. Fuzzy programmming and the pareto optimal set, Fuzzy Sets and
Systems 10(1983) 57-63.
[24] Buckley, J.J., Possibilistic linear programming with triangular fuzzy numbers,
Fuzzy Sets and Systems 26 (1988) 135-138.
[25] Buckley, J.J., Solving possibilistic linear programming problems, Fuzzy Sets and
Systems 31 (1989) 329-341.
[26] Buckley, J.J., Multiobjective possibilistic linear programming, Fuzzy Sets and
Systems 35 (1990)23-28.
[27] Burkard, R.E., V.G. Deineko, R. Van Dal, J.A.A. Van Der Veen y G.J. Woeginger,
Well-solvable special cases of the traveling salesman problem: A survey, Siam
Review, vol. 40 No.3 (1998) 496-546.
[28] Cadenas, J.M. y J.L. Verdegay, Using ranking functions in multiobjective fuzzy
linear programming, por aparecer en Fuzzy Sets and Systems.
[29] Cadenas, J.M. y J.L. Verdegay, PROBO: an interactive system in fuzzy linear
programming, Fuzzy Sets and Systems 76 (1995) 319-332.
[30] Carlsson, Ch. y P. Korhonen; A parametric approach to fuzzy linear programming.
Fuzzy Sets and Systems 20(1986) 17-30.
[31] Castro, J.L., F. Herrera y J.L. Verdegay, Solving linear boolean programming
problems with imprecise costs, Proceedings of the IEEE International Conference on
Fuzzy Systems 1992, San Diego(1992) 1025-1032.
[32] Campos, L., Fuzzy linear programming models to solve fuzzy matrix games, Fuzzy
Sets and Systems 32 (1989) 275-289.
[33] Campos, L. y J.L. Verdegay, Linear programming problems and ranking of fuzzy
numbers, Fuzzy Sets and Systems 32 (1989) 1-11.
[34] Chalam, G.A. , Fuzzy goal programming (FGP) approach to a stochastic
transportatión problem under budgetary constraint, Fuzzy Sets and Systems 66
(1994) 293-299.
[35] Chanas S., The use of parametric programming in FLP, Fuzzy Set and Systems 11
(1983) 243-251.
[36] Chanas, S., Fuzzy programming in multiobjetive linear programming - A
parametric aproach, Fuzzy Sets and Systems 29 (1989)303-313.
[37] Chanas, S., M. Delgado, J.L. Verdegay y M.A. Vila, Interval and fuzzy extensions of
classical transportation problems, Transportation Planing and Technology 17
(1993) 203-218.
184
BIBLIOGRAFÍA
185
BIBLIOGRAFÍA
[58] Dutta, D., J.R. Rao y R.N. Tiwari, Fuzzy approaches for multiple criteria linear
fractional optimization: A comment, Fuzzy Sets and Systems 54 (1993) 347-349.
[59] Edmonds, J., Matroids and greedy algorithm, Mathematical Programming, vol 1
(1971) pp. 127-136.
[60] Eiselt, H. A. Y G. Laporte, A combinatorial optimization problem arising in
dartboard design, Journal of the Operational Research Society 42 (1991) 113-118.
[61] Fabian, C., G. Ciobanu y M. Stoica, Interactive polyoptimization for fuzzy
mathematical programming, in J. Kacprzyk y S.A. Orlovski (Eds.) Optimization
Models Using Fuzzy Sets and Possibility Theory (D. Reidel, Dordrecht, 1987)272-
291.
[62] Fabian, C. Y M. Stoica, Fuzzy integer programming, In Fuzzy Sets and Decision
Analysis, H.J. Zimmermann, L.A. Zadeh y B.R. Gaines (Eds.), Amsterdam(1984)
123-132.
[63] Fedrizzi, M., J. Kacprzyk y M. Roubens (Eds), Interactive Fuzzy Optimization,
Lecture Notes in Economics and Mathematical Systems, No. 368, Springer-Verlag.
1991.
[64] Fedrizzi, M. y R. Fullér, Stability in possibilistic linear programming with
continuous fuzzy number parameters, Fuzzy Sets and Systems 47 (1992) 187-191.
[65] Feng Ying-Jun, A method using fuzzy mathematics to solve vectormaximum
problem, Fuzzy Sets and Systems 9 (1983) 129-136.
[66] Fullér, R., On stability in fuzzy linear programming problems, Fuzzy Sets and
Systems 30 (1989) 39-344.
[67] García-Aguado, C. Y J.L. Verdegay, On the sensitivity of membership functions for
fuzzy linear programming problems, Fuzzy Sets and Systems 56 (1993) 47-49.
[68] Garfinkel, R. S., Motivation and modelling, Cap.2 en [113] (1985) 17-36.
[69] Gass, S., Programación Lineal: Métodos y aplicaciones, ed. Continental, Mexico,
1985.
[70] Gay, D.M., A variant of Karmarkars linear programming algorithm for problems in
standard form, Mathematical programming 37 (1987) 81-90.
[71] Gellinck(de), G.T. y J.P. Vial, A polinomial Newton method for linear
programming, Algorithmica (1986) 1:425-453.
[72] Gilmore. P.C., E.L. Lawler y D.B. Shmoys, Well-solved special cases, Cap. 4 de
[113] (1985) 87-143.
[73] Golden, B.L. y W.R. Stewart, Empirical analysis of heuristics, Cap. 7 en [113]
(1985) 207-249.
[74] Goldfarb, D. Y S. Mehrotra, A relaxed version of Karmarkar•s method,
Mathematical Programming 40 (1988) 289-315.
[75] Goldfarb, D. Y S. Mehrotra, Relaxed variants of Karmarka•s algorithm for linear
programs with unknown optimal objective value, Mathematical Programming 40
(1988) 183-195.
[76] Gorry, G.M. y M.S. Scott-Morton, A Framework for management information
systems, Sloan Management Review, Fall-1971.
[77] Hamacher, H., H. Leberling y H.J. Zimmermann, Sensitivity analisis in fuzzy
linear programming , Fuzzy Sets and Systems 1 (1978) 269-281.
186
BIBLIOGRAFÍA
[78] Hannan, E. L., Linear programming with multiple fuzzy goals, Fuzzy Sets and
Systems, 6 (1981) 235-248.
[79] Herrera, F., M. Kovács y J.L. Verdegay, Optimality for fuzzified mathematical
programming problems: A parametric approach, Fuzzy Sets and Systems 54 (1993)
279-285.
[80] Herrera, F. y J.L. Verdegay, Aproaching fuzzy integer linear programming
problems, In Fedrizzi, Kacprzyk and Roubens (Eds.), Interactive Fuzzy
Optimization (Springer-Verlag, Berlin, 1991) 78-91.
[81] Herrera, F. Y J.L. Verdegay. Fuzzy control rules in optimization problems, Scientia
Iranica, Vol 3, Nos.1,2,3. (1996) 89-96.
[82] Herrera, F., J.L. Verdegay y H.J. Zimmermann, Boolean programming problems
with fuzzy constraints, Fuzzy Sets and Systems 55 (3 )(1993) 285-293.
[83] Hoffman, A. J. y P. Wolfe, History, Cap. 1 en [113] (1985) 1-15.
[84] Horowtz, E., S. Sahni y S. Rajasekaran, Computer Algorithms, Computers Sc.
Press,1998.
[85] Hulsurkar, S., M.P. Biswal y S.B. Sinha, Fuzzy programming approach to multi-
objective stochastic linear programming problems, Fuzzy Sets and Systems 88
(1997) 173-181.
[86] Hussein, M.L. Qualitative analysis of basic notions in an iteractive approach to
possibilistic goal programming, Fuzzy Sets and Systems 54 (1993) 39-46.
[87] Ida, K. y M. Gen, Improvemen of the two-phase approach to solving fuzzy multiple
objective linear programing problems, Japanese Journal of Fuzzy and Systems vol
9 (1) (1997) 105-114.
[88] Ignizio, J.P., On the (re)discovery of fuzzy goal programming, Decision Sci. 13
(1982) 331-336.
[89] Ignizio, J.P., Goal programming and extension (Heath Lexington Bookc, London,
1976).
[90] Inuiguchi, M. y H. Ichihashi, Relative modalitoes and their use in possibilistic
linear programming, Fuzzy Sets and Systems 35 (1990) 303-323.
[91] Inuiguchi, M., H. Ichihashi y Y. Kume, A solution algorithm for fuzzy linear
programming with pieciwise linear memnership functions, Fuzzy Sets and Systems
34 (1990) 15-31.
[92] Inuiguchi, M., H. Ichihashi y Y. Kume, Relationships between modality
constrained programming problems and various fuzzy mathematical programming
problems, Fuzzy Sets and Systems 49 (1992) 243-259.
[93] Inuiguchi, M. y M. Sakawa, Possible and necesary optimality tests in possibilistic
linear programming problems, Fuzzy Sets and Systems 67 (1994) 29-46.
[94] Inuiguchi, M. y M. Sakawa, Possible and necesary efficiency in possibilistic
multiobjetive linear programming problems and possible eficiency test, Fuzzy Sets
and Systems 78 (1996) 231-241.
[95] Iri, M. y H. Imai, A multiplicative barrier function method for linear programming,
Algorithmica (1986) 1:455-482.
[96] Jimenez F. y J.L. Verdegay, Uncertain solid transportation problems, Fuzzy Sets
and Systems 100 (1998) 45-57.
187
BIBLIOGRAFÍA
[97] Johnson, D.S. y C.H. Papadimitriou, Performance guarantees for heuristics, Cap. 5
en [113] (1985) 145-180.
[98] Karloff, Howard, Linear Programming, Ed. Birkhäuser, Boston, USA, 1991.
[99] Karmarkar, N., A new polynomial-time algorithm for linear programming,
Combinatórica 4 (1984), 373-395.
[100] Kato, K., M. Sakawa y T. Ikegame, Interactive decision making for multiobjective
block angular 0-1 programming problems with fuzzy parameters trough genetic
algorithms, Japanese Journal of Fuzzy Theory and Systems vol. 9 (1) (1997) 49-59.
[101] Keen, P.G.W. y M.S. Scott-Morton, Decision Support Systems, An Organizational
Perspective, ponencia, MA:Addison-Wesley, 1978.
[102] Khachiyan, L. G., A polynomial algorithm for linear programming, Soviet
Mathematics Doklady 20(1979), 191-194.
[103] Klee, V. y G. J. Minty, How good is the simplex Algorithm?, in Inequalities-III, O.
Shisha, ed., Academic Press, New York, NY, 1972, 159-175.
[104] Kojima, M., Determining basic variables of optimal solutions in Karmarkar•s new
LP algorithm, Algorithmica (1986) 1:499-515.
[105] Lai, Y. J. Y Ch. L. Hwang, Interactive fuzzy linear programming, Fuzzy Sets and
Systems 45 (1992) 169-183.
[106] Lai, Y.J. y Ch.L. Hwang, A new approach to some possibilistic linear programming
problems, Fuzzy Sets and Systems 49 (1992) 121-133.
[107] Lai, Y. J. Y Ch. L. Hwang, Fuzzy Mathematical Programming, methods and
aplications. Lecture notes in economics and mathematical systems 394. Springer-
Verlag, Berlin, 1992.
[108] Lai, Y. J. Y Ch. L. Hwang, IFLP-II: a decision support system, Fuzzy Sets and
Systems 54 (1993) 47-56.
[109] Lai, Y.J. y Ch.L. Hwang, Possibilistic linear programming for managing interest
rate risk, Fuzzy Sets and Systems 54 (1993) 135-146.
[110] Lai, Y.J. y Ch.L. Hwang, A stochastic possibilistic programming model for bank
hedging decision problems, Fuzzy Sets and Systems 57 (1993) 351-363.
[111] Laporte, G. The traveling salesman problem: An overview of exact and aproximate
algoritms European Journal of Operational Research, 59 (1992) 231-247.
[112] Laporte, G. The vehicle routing problem: An overview of exact and aproximate
algorithms, European Journal of Operational Research, 59 (1992) 345-358.
[113] Lawler E.L., J.K. Lenstra, A.H.G. Rinnooy Kan y D.B. Shmoys (editores), The
Traveling Salemsan Problem: A Guided tour of combinatorial optimization, Jhon
Wiley & Sons, Chichester, 1985.
[114] Leberling, H., On finding compromice solutions in multi-criteria problems using
the fuzzy min-operator, Fuzzy Sets and Systems 6 (1981)105-118.
[115] Lee, E.S. y R.J. Li, Fuzzy multiple objective programming and compromise
programming with pareto optimum, Fuzzy Sets and Systems 53 (1993)275-288.
[116] Lee, Y.R., Y. Shi y P.L. Yu, Linear optimal designs and optimal contingency plans,
Management Science 36 (1990) 1106-1119.
[117] Lee, C-S y C-G. Wen, Fuzzy goal programming approach for water quality
management in a river basin, Fuzzy Sets and Systems 89 (1997) 181-192.
188
BIBLIOGRAFÍA
[118] Lenstra, J.K. y A.H.G. Rinnooy Kan, Some simple applications of the traveling
salesman problem, Operational Research Quarterly 26 (1975) 717-783.
[119] Li, H.L. y Ch. S. Yu, Comments on •fuzy programming with nonlinear
membership functions...•, Fuzzy Sets and Systems101 (1999) 109-113.
[120] Little, J.D.C., K.G. Murty, D.W. Sweeney y C. Karel, An algorithm for the traveling
salesman problem, Operations research 11 (1963) 972-989.
[121] Liu, B. y K. Iwamura, Chance constrained programming with fuzzy parameters,
Fuzzy Sets and Systems 94 (1998) 227-237.
[122] Liu, B. y K. Iwamura, A note on chance constrained programming with fuzzy
coefficients, Fuzzy Sets and Systems 100 (1998) 229-233.
[123] Liu, Y.H. y Y. Shi, A fuzzy programming approach for solving a multiple criteria
and multiple constraint level linear programming problem, Fuzzy Sets and Systems
65 (1994) 117-124.
[124] Luhandjula, M. K., Compensatory operators in fuzzy linear programming with
multiple objectives, Fuzzy Sets and Systems 8(1982) 245-252.
[125] Luhandjula, M.K., Linear programming under randomness and fuzzines, Fuzzy
Sets and Systems 10 (1983) 45-55.
[126] Luhandjula, M.K., Fuzzy approaches for multiple objective linear fractional
optimizatión, Fuzzy Sets and Systems 13 (1984)11-23.
[127] Luhandjula, M.K., On possibilistic linear programming, Fuzzy Sets and Systems 18
(1986) 15-30.
[128] Luhandjula, M.K., Multiple objective programming problems with possibilistic
coeficients, Fuzzy Sets and Systems 21 (1987)135-146.
[129] Lusting, I.J., Feasibility issues in a primmal-dual interior-point method for linear
programming, Mathematical Programming 49 (1991) 145-162.
[130] Lusting, I.J., R.E. Marsten y D.F. Shano, Computational experience with a primal-
dual interior point method for linear programming, Linear Algebra and its
Applications, vol. 152 (1991) pp. 191-222.
[131] Malek, M., M. Guruswamy y M. Pandya, Serial and parallel simulated annealing
and tabu search algorithms for the traveling salesman problem, Annals of
Operations Research 21 (1989) 59-84.
[132] Martello, S. y P. Toth, An upper bound for the zero-one knapsack problem and a
branch and bound algorithm, European Journal of Operational Research 1 (1977)
169-175.
[133] Martello, S. y P. Toth, A new algorithm for the 0-1 knapsack problem, Management
Science 34 (1988) 633-644.
[134] Martello, S. y P. Toth, Knapsack Problems, John Wiley and Sons 1990.
[135] Masaaki, I., Optimality on possibilistic linear programming with normal possibility
distribution coefficient, Japanese Journal of Fuzzy Theory and Systems vol 7 (3)
(1995) 349.
[136] Mitten, L.G. Branch-and-bound methods:general formulations and properties,
Operations Research 18(1)(1970) 24-34.
189
BIBLIOGRAFÍA
190
BIBLIOGRAFÍA
191
BIBLIOGRAFÍA
192
BIBLIOGRAFÍA
[192] Tiwari, R.N., S. Dharmar y J.R. Rao, Priority structure in fuzzy goal programming,
Fuzzy Sets and Systems 19 (1986)251-259.
[193] Tiwari, R.N., S. Dharmar y J.R. Rao, Fuzzy goal programming - an additive model,
Fuzzy Sets and Systems 24 (1987)27-34.
[194] Todd, M.J. y B.P. Burrell, An extension of Karmarkar•s algorithm for linear
programing using dual variables, Algorithmica (1986) 1: 409-424.
[195] Todd, M.J. y Y. Ye, A centered proyective algorithm for linear programming,
Mathematics of Operations Research, Vol 15 (1990) pp. 508-529.
[196] Tong S., Interval number and fuzzy number linear programmings, Fuzzy Sets and
Systems 66 (1990) 301-306.
[197] Turban. E., Decision Suport and Expert Systems: Management Support Systems,
Fourth edition, Englewood Cliffs-NJ , Prentice Hall, 1995.
[198] Valenzuela, Ch.L. y A.J. Jones, Evolutionary divide and conquer (I): A novel
genetic approach to the TSP, Evolutionaruy Computation 1 (4) (1994) 313-333.
[199] Vanderbei, R.J., Affine-scaling for linear programs with free variables,
Mathematical Programming 43 (1989) 3-44.
[200] Vanderbei, R.J., M.S. Meketon y B.A. Freedman, A modification of Karmarkar•s
linear programming alghorithm, Algorithmica (1986) 1:395-407.
[201] Verdegay, J.L. Problemas de transporte con parámetro difuso, Rev. Acad. Ciencias
Mat. Fis. Quim. Y Nat. De Garanada, 2 (1983) 47-56.
[202] Verdegay, J. L., A dual approach to solve the fuzzy linear programming problem,
Fuzzy Sets and Systems 14(1984) 131-141.
[203] Verdegay, J.L. Fuzzy mathematical programming, Approximate Reasoning in
Decision Analysis - Gupta, M.M. y E. Sanchez (eds) (North_holland, A,sterdam,
1992).
[204] Verdegay, J. L.; Fuzzy optimization: Models, methods and Perspectives; 6thIFSA-95
World Congress. Sou Paulo - Brazil, 1995, pp. 39-71.
[205] Verma, R., M.P. Biswal y A. Biswas , Fuzzy programming technique to solve multi-
objective transportation problems with some non-linear membership functions,
Fuzzy Sets and Systems 91 (1997) 37-43.
[206] Wang, H.F. y M.L. Wang, A fuzzy multiobjective linear programming, Fuzzy Sets
and Systems 86 (1997) 61-72.
[207] Wang, G-Y. y Q. Zhong, Linear programming with fuzzy random variable
coeficients, Fuzzy Sets and Systems 57 (1993) 295-311.
[208] Werners, B., An interactive fuzzy programming system, Fuzzy Sets and Systems 23
(1987) 131-147.
[209] Werners, B., Interactive multiobjective programming subject to flexible constraints,
European J. Oper. Res. 31 (1987) 342-349.
[210] Wets, R.J.B. , Stochastic Programming, in G.L. Nemhauser, A. H.G. Rinnooy Kan y
M.J. Todd (Eds.), Handbooks in Operations Research and Management Science:
Optimization (North-holland, Amsterdam, 1989) 573-629.
[211] Yamaguchi, T. e Y. Kono, Application of fuzzy multiobjective linear programming
to greenhouse cultivation planning, Japanese Journal of Fuzzy Theory and Systems
vol 4 (6) (1992) 701.
193
BIBLIOGRAFÍA
[212] Yang, T. Y J.P. Ignizio, Fuzzy programming with nonlinear membership functions:
piecewise linear approximation, Fuzzy Sets and Systems 41 (1991)39-53.
[213] Yano, H. Y M. Sakawa, Interactive fuzzy decision making for generalized
multiobjective linear fractional programming problems with fuzzy parameters,
Fuzzy Sets and Systems 32 (1989) 245-261.
[214] Ye, Y. Y M. Kojima, Recovering optimal dual solutions in Karmarkar•s polynomial
algorithm for linear programming, Mathematical Programming 39 (1987) 305-317.
[215] Yokoyama, T., H. Ohta y T. Yamaguchi, Multiobjective probabilistic constrained
programming problems using fuzzy goal, Japanese Journal of Fuzzy Theory and
Systems vol 6 (6) (1994)
[216] Zadeh, L.A.: Fuzy sets, Information and Control 8 (1965) 338-353.
[217] Zadeh, L.A., Fuzzy sets as a basis para una theory of possibility, Fuzzy Sets and
Systems 1 (1978) 3-28.
[218] Zeleny, M., Compromise programming, in: J.L. Cochrane and M. Zeleny, Eds.
Multiple Criteria Decision Making, University of South carolina Pres (1973).
[219] Zhao, R., R. Govind y G. Fan, The complete decision set of the generalized
symetyrical fuzzy linear programming problem, Fuzzy Sets and Systems 51 (1992)
53-65.
[220] Zhong, Q. Y G-Y. Wang, On solutions and distribution problems of the linear
programming with fuzzy random variable coeficients, Fuzzy Sets and Systems 58
(1993) 155-170.
[221] Zhong, Q., Y. Zhang y G-Y. Wang, On fuzzy random linear programming, Fuzzy
Sets and Systems 65 (1994) 31-49.
[222] Zimmermann, H. J., Description and optimization of fuzzy system, International
Journal of general System 2 (1976) 209-216.
[223] Zimmermann, H. J., Fuzzy programming and linear programming with several
objective functions, Fuzzy Sets and Systems 1 (1978) 45-55.
[224] Zimmermann H.J., Fuzzy Sets, Decision Making y Sistemas Expertos (Kluwer
Academic, Boston , 1987).
[225] Zimmermann H.J. y M.A. Pollatschek, Fuzzy 0-1 linear programs, In H.J.
Zimmermann, L.A. Zadeh and [Link] (Eds.), Amsterdam (1984) 133-145.
[226] Zionts, S. Y J. Wallenias, An interactive programming method for solving the
multiple criteria problems, Management Sci. 22 (1976) 652-663.
194