Embed Size (px)
Citation preview
CONFIGURACION DE PLANTA CON ENFRIAMIENTO SIMULADO
ROLANDO JOSE ACOSTA AMADO
M.Sc. Ingeniería Industrial
UNIVERSIDAD DE LOS ANDES
FACULTAD DE INGENIERÌA
Dpto. Ing. Industrial
Bogotá
1
TABLA DE CONTENIDO
1 INTRODUCCIÓN ____________________________________________________ 3
1.1 PLANTEAMIENTO DEL PROBLEMA A SOLUCIONAR _____________________ 5
1.2 JUSTIFICACIÓN DEL PROYECTO _______________________________________ 5
1.3 OBJETIVOS ___________________________________________________________ 6 1.3.1 Objetivo General ___________________________________________________________ 6 1.3.2 Objetivos Específicos________________________________________________________ 6
1.4 METODOLOGÍA _______________________________________________________ 6
2 MARCO TEORICO ___________________________________________________ 8
2.1 INTRODUCCIÓN_______________________________________________________ 8
2.2 FORMULACIÓN DEL PROBLEMA DE CONFIGURACIÓN DE PLANTA ______ 8
2.3 SIMULATED ANNEALING _____________________________________________ 13 2.3.1 El Método Básico de Optimización Local _______________________________________ 14 2.3.2 El algoritmo de Templado ___________________________________________________ 16 2.3.3 Decisiones Genéricas _______________________________________________________ 18 2.3.4 Decisiones específicas del problema ___________________________________________ 20
2.4 ALGORITMOS PARA CONFIGURACIÓN DE PLANTA ____________________ 21
3 CREACIÓN DEL ALGORITMO DE ENFRIAMIENTO SIMULADO (SIMULATED ANNEALING) PARA CONFIGURACIÓN DE PLANTA___________ 23
3.1 ESTRUCTURA DE CODIFICACIÓN DE UNA SOLUCIÓN FACTIBLE________ 23
3.2 DECISIONES GENÉRICAS _____________________________________________ 23 3.2.1 Temperatura inicial y temperatura final _________________________________________ 24 3.2.2 Criterio de Parada _________________________________________________________ 25 3.2.3 Número de repeticiones por temperatura ________________________________________ 25
3.3 DECISIONES ESPECÍFICAS DEL PROBLEMA ___________________________ 26 3.3.1 Espacio de soluciones factibles _______________________________________________ 26 3.3.2 Forma de la función de costo _________________________________________________ 27 3.3.3 Estructura de vecinaje empleada ______________________________________________ 27
3.4 IMPLEMENTACIÓN COMPUTACIONAL ________________________________ 28
4 EXPERIMENTOS ___________________________________________________ 30
4.1 METODOLOGÍA ______________________________________________________ 30
4.2 SIMULATED ANNEALING PARA UNA CONFIGURACIÒN DE PLANTA DE 7 DEPARTAMENTOS________________________________________________________ 31
4.3 SIMULATED ANNEALING PARA UNA CONFIGURACIÓN DE PLANTA DE 12 DEPARTAMENTOS________________________________________________________ 33
4.4 SIMULATED ANNEALING PARA UNA CONFIGURACIÓN DE PLANTA DE 32 DEPARTAMENTOS________________________________________________________ 38
5 CONCLUSIONES ___________________________________________________ 52
2
6 ANEXOS___________________________________________________________ 54
6.1 Anexo 1: Ejemplo de cromosoma y configuración de planta resultante, utilizando el procedimiento X-Y Oscilatorio ________________________________________________ 55
6.2 Anexo 2: Subrutina para matrices de flujo, costo y areas para el problema de 12 departamentos _____________________________________________________________ 56
6.3 Anexo 3: Subrutina para Matrices de flujo, costo y áreas para el problema de 32 departamentos _____________________________________________________________ 57
6.4 Anexo 4: Gráficos ______________________________________________________ 64
7 BIBLIOGRAFÍA ____________________________________________________ 73
3
1 INTRODUCCIÓN
El problema de configuración de planta involucra la selección del arreglo más
efectivo de los departamentos o estaciones de trabajo, para lograr la mayor
eficiencia en la combinación de recursos para producir un producto o servicio,
cumpliendo las condiciones del entorno y satisfaciendo objetivos múltiples
previamente establecidos. Estas condiciones del entorno, son susceptibles de
expresarse matemáticamente en términos de las variables que empleamos en una
función objetivo a optimizar, cuyo(s) criterio(s) de optimización depende(n) del
interés del investigador, como veremos más adelante.
La investigación se basa en la formulación de un modelo de múltiples criterios de
optimización y se fundamenta en la creación y desarrollo de un modelo Simulated
Annealing para generar soluciones efectivas de configuración de planta para
problemas de diferentes grados de complejidad con una eficiencia computacional
razonable.
El modelo de múltiples criterios de Islier, a partir del cual se construye esta
investigación, busca minimizar la carga de transporte, maximizar el grado de
compactación de las áreas y minimizar la diferencia entre las áreas demandadas y
las disponibles. Así pues, son tres (3) los criterios de optimización que debemos
tener en cuenta a la hora de proponer una configuración de planta.
El informe está dividido en 5 partes así: la primera parte explica los objetivos de la
investigación, específicos y general además de presentar la metodología de
investigación empleada. En la segunda parte del informe, encontramos un marco
teórico del problema de configuración de planta, de la técnica heurística Simulated
Annealing (Enfriamiento Simulado), incluyendo una descripción genérica y
4
específica del algoritmo así como el tipo de decisiones que se involucran en el
diseño de un algoritmo de enfriamiento simulado. También se presentan algunos
comentarios acerca de algoritmos para configuración de planta. En la tercera
parte se presenta todo lo relacionado con la creación del algoritmo de enfriamiento
simulado para solucionar el problema. También se presenta en esta sección, la
implementación computacional del mismo. Ya en la cuarta sección, encontramos
los resultados de la parte experimental de la investigación y la última parte está
destinada para las conclusiones y recomendaciones.
5
1.1 PLANTEAMIENTO DEL PROBLEMA A SOLUCIONAR Se quieren hallar mejores configuraciones de planta, para problemas de la
literatura por medio de la creación de un modelo de enfriamiento simulado
(Simulated Annealing) programado con el lenguaje Visual Basic.
1.2 JUSTIFICACIÓN DEL PROYECTO La importancia de encontrar mejores configuraciones de planta radica de acuerdo
a Tompkins and White, en que se estima que los costos de manufactura atribuidos
al transporte representan entre el 20 y el 50% de los costos operacionales totales.
De esta manera, configuraciones de planta efectivas pueden reducir estos costos
entre un 10 y un 30% aumentando la productividad de la planta.
Los algoritmos de inteligencia artificial, como Simulated Anneling, son una nueva
corriente que tiene ventajas competitivas sobre los métodos de optimización
tradicionales generando soluciones más eficientes y son apropiados para
determinar configuraciones de planta.
Este modelo es una herramienta atractiva para la toma de decisiones en la
configuración de planta.
6
1.3 OBJETIVOS
1.3.1 Objetivo General
Crear un algoritmo heurístico con Simulated Annealing para solucionar el
problema de configuración de planta con múltiples criterios de optimización a fin
de encontrar mejores configuraciones de planta y evaluar su eficiencia y utilidad
con un benchmarking en la literatura.
1.3.2 Objetivos Específicos
• Establecer un marco teórico acerca de la técnica metaheurística Simulated
Annealing
• Realizar una investigación sobre modelos de solución del problema de
configuración de planta basados Simulated Annealing
• Establecer los parámetros y operadores que permitan mapear la información
del problema de configuración de planta en términos de los parámetros de
Simulated Annealing
• Desarrollar un Software en Visual Basic del nuevo algoritmo creado de forma
que pueda ser fácilmente utilizado por el investigador
• Evaluar el algoritmo creado por medio de experimentos encontrados en la
literatura
• Establecer conclusiones y recomendaciones
1.4 METODOLOGÍA • Establecer los marcos teóricos de interés: Simulated Annealing, y del modelo
de configuración de planta de Islier
• Determinar los parámetros de interés de Simulated Annealing y mapear estos
parámetros en el problema de configuración de planta, modelo Islier
7
• Diseñar el algoritmo para solucionar el problema de configuración de planta
con Simulated Annealing
• Codificar el algoritmo con Visual Basic en un macro de excel
• Probar el algoritmo con diferentes problemas de la literatura para medir su
desempeño
• Graficar el comportamiento de la función objetivo, así como de los diferentes
criterios de optimización, a lo largo del desarrollo del algoritmo para cada uno
de los diferentes problemas.
• Establecer Conclusiones y Recomendaciones
8
2 MARCO TEORICO
2.1 INTRODUCCIÓN
Establecer la mejor configuración de una planta de producción implica la ubicación
física eficiente de los elementos de producción y/o manufactura e incluye tanto los
espacios necesarios para el movimiento de material, almacenamiento,
trabajadores indirectos y todas las otras actividades o servicios, como el equipo de
trabajo y el personal de la planta. En síntesis, es tomar una decisión concerniente
con la ubicación eficiente de los recursos de producción
En los últimos años, se han venido realizando numerosas investigaciones acerca
del tema con el fin de determinar nuevas formas de solucionar el problema de
configuración de planta utilizando técnicas de inteligencia artificial, entre las que se
encuentra Simulated Annealing, cuyo uso para solucionar este problema es muy
cuestionado debido a la cantidad de tiempo que le toma al algoritmo converger en
una solución heurística.
2.2 FORMULACIÓN DEL PROBLEMA DE CONFIGURACIÓN DE PLANTA El problema de configuración de planta es un problema de optimización muy
complejo y ampliamente estudiado. Como resultado de esto, se han desarrollado
muchos modelos y técnicas. Básicamente, el problema de configuración de planta
consiste en el arreglo de departamentos dentro de una planta teniendo en cuenta
una función objetivo a optimizar. Mecklenburgh (1985) y Francis (1992) definen
los siguientes objetivos que pueden ser considerados para optimizar en el
momento de diseñar la configuración de la planta:
9
• Minimizar el costo del manejo de materiales, el tiempo y la frecuencia del
manejo de los materiales
• Minimizar el capital y el costo de operación de planta y equipo
• Minimizar el tiempo global de entrega
• Incrementar el uso efectivo y económico del espacio
• Facilitar el proceso de manufactura y el flujo de las operaciones
• Proveer para la conveniencia de los empleados, seguridad y confort
• Mantener flexibilidad del arreglo y de operación
• Minimizar la variación en tipos de equipo para el manejo de materiales
• Facilitar la estructura organizacional y la gestión de toma de decisiones
• Minimizar ruido al público
• Proveer una construcción segura y eficiente
• Proveer una configuración acorde con consideraciones legales: salud, asuntos
concernientes con planes de emergencia y medio ambiente.
Malakooti (1989) comenta que cualquier problema de configuración de planta tiene
múltiples criterios para seleccionar la mejor configuración que son muy específicos
al problema. Las partes se mueven de un departamento a otro para ser
procesadas en un ambiente de manufactura causando costos de transporte. Los
conceptos de unidad de carga y centroides simplifican en gran medida el cálculo
del costo total de transporte de cualquier alternativa de configuración. Por unidad
de carga podemos entender ya sea una carga física que consiste de un pallet,
algún contenedor de tamaño estándar etc. O algún equivalente conceptual de
carga determinado mediante algunas presunciones y conversiones. El número de
unidades de carga transportados entre dos departamentos dentro de un período
(un mes o un año) es el flujo entre estos.
El cálculo de las distancias entre los centroides está generalmente basado en los
centroides (centros de área) de esos departamentos. Para un problema de
10
configuración de planta bidimensional, el cálculo de la distancia se realiza
mediante la siguiente expresión:
2211 jijiij xxxxd −+−= (1)
El producto d estas distancias con los flujos y los costos unitarios lleva al costo de
transporte total en un período. Los costos unitarios son los costos de mover una
unidad de carga de un departamento a otro por unidad de longitud. Los datos
colectados son organizados en matrices de distancia, flujo y costo unitario. Estas
matrices no necesariamente son simétricas. Sin embargo, en todos los
experimentos de este trabajo, se asumen las matrices de flujo, costo y distancias
como simétricas, a menos que se especifique lo contrario. Uno de los objetivos
del método propuesto es optimizar el radio de la carga ideal (costo cero) con la
carga real. El incremento de este radio muestra una reducción del costo de
transporte y así mejores soluciones.
Otro problema común de las técnicas de distribución de planta es terminar en
formas no razonables para los departamentos. Se puede tener una solución
resultante que contenga algunos departamentos divididos en dos o más partes.
Necesitamos entonces un indicador para detectar esas formas no deseadas. Un
concepto bien conocido de mecánica, momento de las áreas, es el más adecuado.
A medida que el área se vuelve más compacta este valor se reduce. Para obtener
una escala manejable, los momentos calculados son divididos por las áreas para
obtener los factores de forma. El segundo objetivo del modelo propuesto es
optimizar este factor proveyendo así áreas departamentales no separadas.
La técnica de planeación sistemática de configuración de Muther busca un
balance entre las áreas disponibles y las requeridas. De acuerdo a esto, las áreas
requeridas para los departamentos deberían establecerse dentro de cierta
tolerancia, en lugar de insistir en valores exactos. De esta manera el tercero y
11
último objetivo del modelo diseñado es minimizar la desviación total de las áreas
más deseadas mientras son mantenidas entre límites superiores e inferiores.
Los factores usados para construir la función objetivo del modelo pueden ser
definidos más formalmente como sigue:
Factor de Carga:
∑ ∑−
= =
= 1
1 2..
n
i
n
j ijijij dfc
Vt (2)
donde:
V: carga ideal (obtenida mediante la multiplicación de los vectores de distancia y
de flujo
n: número de departamentos
cij: costo de llevar una unidad de carga por una unidad de longitud entre los
departamentos i y j
fij: número de unidades de carga a ser transportadas entre los departamentos i y j
en un período
dij: distancia entre el departamento i y j (rectilínea)
Factor de Forma
∑ ∑ ∑∑
= = =
== b
i
e
j
n
k ijk
n
k k
a
rs
1 1 1
1 (3)
donde:
Sk: el conjunto de celdas del departamento k
Upk: distancia rectilínea desde el centroide del departamento k al centroide de la
celda p
Aijk: Indicador que es igual a 1 si la celta en la i-ésima fila y la j-ésima columna en
el plano está asignada al k-esimo departamento. (de otra forma vale cero)
b: número de filas en el plano
e: número de columnas en el plano
12
rk: momento del área del k-ésimo departamento así:
∑∈
=kSp
pkk ur 2 (4)
Factor de Desviación:
∑ ∑ ∑∑ ∑ ∑
= = =
= = =−
−= b
i
e
j
n
k ijk
n
k
b
i
e
j ijkk
a
aAh
1 1 1
1 1 11 (5)
donde Ak es el área más deseada para el departamento k. Entonces el modelo
final tiene la siguiente forma:
∑∑∑
∑ ∑
∑
= = =
= =
=
≤
∀≤≤
∀≤
b
i
e
j
n
kijk
kb
i
e
j ijkk
n
kijk
bea
kAaA
jyiats
hst
Max
1 1 1
1 1
1
.
,
,1..
.
(7)
La primera restricción prohibe el compartir alguna celda por más de un
departamento. Así, el traslape de los departamentos es evitado. La segunda
restricción mantiene el número total de celdas de cualquier departamento dentro
de los límites predeterminados. Aquí, kk AA , son los límites inferior y superior
para el número de celdas del k-ésimo departamento. La última restricción revista
que el número total de celdas de todos los departamentos no exceda el área
disponible. Representar las áreas como elementos finitos (celdas) es significativo
desde el punto de vista práctico.
13
2.3 SIMULATED ANNEALING El uso de Simulated Annealing como una técnica para optimización discreta se
remonta al principio de la década de los 80, demostrando ser sencillo de
implementar y aplicable a muchos problemas.
Las ideas que forman las bases de Simulated Annealing fueron publicadas primero
por Metropolis en 1953 como un algoritmo para simular el enfriamiento de un
material en un baño de calor, -proceso conocido como templado (Annealing). Si
un material sólido es calentado hasta su punto de fusión y después enfriado hasta
su estado sólido, las propiedades estructurales del sólido enfriado dependen de la
tasa de enfriamiento. Esencialmente, el algoritmo de Metropolis simula el cambio
en la energía del sistema cuando está sujeto a un proceso de enfriamiento hasta
que converge en un estado estable congelado. 30 años más tarde, Kirkpatrick
sugirió que este tipo de simulación podría ser usada para buscar las soluciones
factibles en un problema de optimización con el objetivo de converger a una
solución óptima.
En la heurística de Simulated se permiten movimientos de ascenso en la función
objetivo. La frecuencia de estos movimientos ascendentes es gobernada por una
función de probabilidad que cambia a medida que el algoritmo progresa.
La inspiración para esta forma de control fue el trabajo de Metropolis en
termodinámica estadística. Las leyes de la termodinámica establecen que a una
temperatura t, la probabilidad de un incremento en energía de magnitud δE está
dada por:
( ) ktE
eEpδ
δ−
= (8)
donde k es una constante física conocida como la constante de Boltzmann.
14
La simulación de Metrópolis genera una perturbación y calcula el cambio de
energía resultante. Si la energía ha disminuido el sistema se mueve a este nuevo
estado. Si la energía se ha incrementado, el nuevo estado es aceptado de
acuerdo a la probabilidad dada en la ecuación 8. El proceso es repetido para un
número predeterminado de iteraciones para cada temperatura, después del cual la
temperatura decrece hasta que el sistema se “congele” en un estado estable.
Kirkpatrick y Cerny, independientemente, mostraron que el algoritmo de Metrópolis
podría ser aplicado a problemas de optimización mapeando los elementos del
proceso de enfriamiento físico sobre los elementos de un problema de
optimización combinatorio como es mostrado en la siguiente tabla:
Simulación Termodinámica Optimización Combinatoria
Estados del sistema Soluciones factibles
Energía Costo
Cambio de estado Vecinaje de Soluciones
Temperatura Parámetros de control
Estado congelado Solución heurística
Así, cualquier algoritmo de optimización local, puede ser convertido en un
algoritmo templado mediante el muestreo aleatorio de las vecindades de la
solución actual y permitiendo la aceptación de una solución inferior de acuerdo a
la probabilidad dada en la ecuación 1. El nivel de aceptación de movimientos
ascendentes entonces depende de la magnitud del incremento en la función de
costo y del tiempo de búsqueda hasta el momento.
2.3.1 El Método Básico de Optimización Local
Supongamos que tenemos un problema de minimización sobre una región factible
S y una función de costo f:S=>R, la cual puede ser calculada para todo s∈S. En
15
teoría, la solución óptima podría ser obtenida mediante una búsqueda exhaustiva
calculando f(s) para cada s∈S y seleccionando el mínimo. Sin embargo, en la
mayoría de los problemas de la vida real, el conjunto S será demasiado grande, lo
cual hace este procedimiento impráctico. La optimización local aborda este
problema buscando solo en un pequeño subconjunto del espacio solución. Esto
es alcanzado mediante la definición de una estructura de vecindad sobre este y
buscando en la vecindad de la solución actual una mejora. Si no hay vecino que
represente una mejora a la función de costo, la solución actual es tomada como
una aproximación al óptimo. Si una mejora es encontrada, la solución actual es
reemplazada por la que representa la mejora y se repite el proceso nuevamente.
En comparación con los métodos de descenso empinado, estos buscan toda la
vecindad y seleccionan aquel vecino del cual resulta la mejora más grande en la
función de costo. El descenso aleatorio selecciona las soluciones vecinas
aleatoriamente y acepta la primera solución que mejore la función de costo.
La optimización local es un enfoque particularmente atractivo para muchos
problemas de optimización combinatorios ya que tienen una estructura de
vecindad natural. Si el número de elementos en la solución óptima es fijado y
conocido, un vecino puede estar definido como el conjunto de soluciones
obtenidas cambiando aleatoriamente un número fijo de elementos en la solución
actual para el mismo número de elementos no solución.
Formalmente podemos establecer el proceso de optimización local como sigue:
Optimización local para un problema con espacio solución S, función de costo f y
estructura de vecindad N
Seleccione una solución inicial s0∈S
Repita
Selección s tal que f(s)<f(s0) con un método conveniente;
Reemplace s0 por s
Hasta que f(s)>f(s0) para todo s∈N(s0)
16
s0 es la aproximación a la solución óptima.
(Las formas usuales de seleccionar s son descenso empinado o descenso
aleatorio)
2.3.2 El algoritmo de Templado
Como se ha venido sugiriendo, la principal desventaja de la búsqueda local es su
alto riesgo de encontrar un óptimo local en vez de un óptimo global, Simulated
Annealing ofrece una manera de abordar este problema, permitiendo algunos
movimientos de ascenso en forma controlada. El algoritmo de templado es similar
a los métodos aleatorios de descenso en los cuales la vecindad es muestreada
aleatoriamente. Difiere en que un vecino que da origen a un aumento o
incremento en la función de costo, puede ser aceptado y esta aceptación
dependerá del parámetro de control (temperatura), y de la magnitud del
incremento. El algoritmo puede ser establecido como sigue:
Simulated Annealing para un problema de minimización con espacio solución S,
función objetivo f y estructura de vecindad N
Seleccione una solución inicial s0
Seleccione una temperatura inicial t0
Seleccione una función de reducción de temperatura α
Repita
Repita
Aleatoriamente seleccione s∈N(s0)
δ=f(s)-f(s0)
si δ<0 entonces
s0=s
si no entonces
genera un x aleatoriamente en el rango (0-1)
si x<exp(-δ/t) entonces s0=s
17
hasta que el contador de iteraciones =nrep
haga t=α(t)
hasta que el criterio de parada=true
s0 es la aproximación a la solución óptima
En el caso de maximización, el algoritmo se establece de la siguiente forma:
Seleccione una solución inicial s0
Seleccione una temperatura inicial t0
Seleccione una función de reducción de temperatura α
Repita
Repita
Aleatoriamente seleccione s∈N(s0)
δ=f(s)-f(s0)
si δ>0 entonces
s0=s
si no entonces
genera un x aleatoriamente en el rango (0-1)
si x<exp(δ/t) entonces s0=s
hasta que el contador de iteraciones =nrep
haga t=α(t)
hasta que el criterio de parada=true
s0 es la aproximación a la solución óptima
Note que t es ahora simplemente un parámetro de control y que no tiene analogía
física; que la constante de Boltzman ha sido obviada de la función de probabilidad
de aceptación. Sin embargo, todavía es usual referirse a t como la temperatura y
la tasa a la cual t es reducida como la tasa de enfriamiento.
18
El algoritmo dado arriba es muy general. Con el fin de implementarlo en un
problema particular podemos tomar 2 clases de decisiones. Primeramente, hay
decisiones de tipo genéricas que tienen que ver con los parámetros del algoritmo
de templado como tal. Estas incluyen factores tales como:
• la temperatura inicial
• la tasa de enfriamiento (gobernada por el parámetro nrep y la selección de la
función de reducción de temperatura)
• el criterio de parada.
La segunda clase de decisiones son específicas al problema e involucran:
la selección del espacio de soluciones factibles
la forma de la función de costo
la estructura de vecinaje empleada.
Ha habido una cantidad sustancial de investigación sobre el comportamiento
estadístico del algoritmo Simulated Annealing. Algunos de los resultados de estas
investigaciones han probado ser de gran ayuda en la determinación de los
parámetros para la tasa de enfriamiento y de funciones de costo adecuadas, así
como de estructuras de vecinaje.
En Simulated Annealing la temperatura no es constante, pero es reducida después
de un número de iteraciones.
2.3.3 Decisiones Genéricas
Las decisiones genéricas básicamente envuelven la tasa de enfriamiento
incluyendo los límites superiores e inferiores para los parámetros de la
temperatura y la tasa a la cual esta debe ser reducida.
La tasa a la cual el parámetro de la temperatura debe reducirse es vital para el
éxito de cualquier proceso de templado simulado. Esta está gobernada por el
19
número de repeticiones a cada temperatura y la tasa a la cual la temperatura es
reducida. La teoría sugiere que la temperatura debería converger gradualmente a
un valor de cero. Como esto tiende a implicar tiempos infactibles de computación
se debe hacer alguna clase de reducción en el número de iteraciones. Esto se
puede alcanzar ya sea mediante el uso de un número grande de iteraciones y
pocas temperaturas o con un número pequeño de iteraciones y muchas
temperaturas.
Las dos tasas de enfriamiento que más ampliamente se utilizan en la práctica
ilustran los extremos opuestos. La primera involucra una función de reducción
geométrica ( ) att =α donde a<1. La experiencia ha mostrado que valores
relativamente altos de a se desempeñan mejor y la mayoría de los éxitos
reportados en la literatura usan valores entre 0.8 y 0.99. Esto corresponde a un
enfriamiento bastante lento. El número de iteraciones a cada temperatura es
usualmente relacionado con el tamaño de las vecindades o a veces con el del
espacio solución y puede variar de una temperatura a otra temperatura. Por
ejemplo es importante gastar mucho tiempo a temperaturas más bajas para
asegurar que un óptimo local ha sido totalmente explorado. Así puede ser
benéfico el incremento del valor de nrep, ya sea geométricamente (mediante la
multiplicación con un factor mayor que uno) o aritméticamente (adicionando un
factor constante) a cada nueva temperatura.
Otra forma de determinar nrep es usando retroalimentación del proceso de
templado. Por ejemplo, puede ser deseable aceptar cierto número de
movimientos antes de decrecer la temperatura. Esto implicará un tiempo más
corto gastado en altas temperaturas cuando la tasa de aceptaciones es alta.
La segunda tasa de enfriamiento más comúnmente usada fue primero sugerida
por Lundy & Mees. Esta ejecuta solo una iteración a cada temperatura pero
reduce la temperatura muy lentamente de acuerdo a la fórmula
20
( ) ( )tt
βα
+=
11
(9)
donde β es un pequeño valor conveniente que, se sugiere, se puede hallar por
experimentación.
En teoría la temperatura debería disminuir hasta cero antes de que se alcance el
criterio de parada. Sin embargo, no hay necesidad de disminuir la temperatura
hasta ese punto. Dada la precisión limitada de cualquier implementación
computacional, mientras t se aproxima a cero positivo, la probabilidad de aceptar
cualquier movimiento de ascenso será indistinguible de cero. Incluso antes de que
este punto sea alcanzado, es probable que el chance de un escape completo del
óptimo local actual será despreciable. Así, el criterio de parada puede ser
expresado ya sea en términos de un valor mínimo del parámetro de la temperatura
o en términos del congelamiento del sistema en la solución actual. Algunos
criterios de parada consisten en congelar el sistema especificando que un número
de iteraciones o temperaturas han pasado sin ninguna aceptación. La regla más
simple de todas es pre-especificar un número total de iteraciones y detenerse
cuando se haya completado este número. Esta regla debe estar cuidadosamente
sintonizada con los otros parámetros con el fin de asegurar que corresponde con
una temperatura suficientemente baja para asegurar convergencia.
2.3.4 Decisiones específicas del problema
Esta clase de decisiones están relacionadas con el espacio solución, la estructura
de vecinaje y la función de costo. El resultado de Hajek, soporta las
observaciones empíricas de que esos factores tienen un efecto significante en el
éxito de un algoritmo de templado. Como en las decisiones genéricas no es
posible establecer una serie de reglas que definan siempre las mejores
escogencias para un problema dado. Sin embargo, lo que sí se puede, es
destacar algunas propiedades que son deseables. Algunas son de sentido
21
común, otras son el resultado de la experimentación, mientras que otras vienen de
observaciones acerca de los resultados sobre teoría de convergencia.
En algunos casos puede no ser posible satisfacer todos estos requerimientos de
una sola vez –de hecho algunos de ellos pueden ser contradictorios para algunos
tipos de problemas. En la toma de estas decisiones hay tres objetivos
importantes: mantener la validez del algoritmo, usar efectivamente el tiempo de
computación para tantas iteraciones como sea posible, y conseguir que la solución
debe estar cerca al óptimo global.
2.4 ALGORITMOS PARA CONFIGURACIÓN DE PLANTA De acuerdo a Kusiak y Hergu los algoritmos para configuración de planta pueden
ser clasificados en dos principales categorías:
Algoritmos de solución óptima, tales como Branch and Bound (ramificación y
acotamiento) y algoritmos de plano de corte (Cutting Plane). Debido a que el
problema es NP completo, los métodos óptimos pueden solamente utilizarse para
resolver problemas pequeños que contengan hasta 15 recursos.
Algoritmos de solución heurística: Han sido desarrollados para asistir a los
diseñadores en el proceso de configuración de planta y tener una mayor cobertura
en los problemas. Este grupo se puede subdividir en:
• Métodos de construcción: el proceso de construcción consta de dos fases. La
primera en determinar el orden de selección, es decir, decidir la secuencia de
colocar las máquinas o estaciones de trabajo dentro del área establecida y la
segunda, instalarlas de acuerdo a ciertos objetivos.
• Métodos de mejoramiento: buscan intercambiar la localización de las máquinas
o estaciones de trabajo para aumentar la calidad de la solución. Para un gran
número de departamentos, estos métodos resultan ser mejores como
heurísticos que los layout óptimos y han sido utilizados ampliamente en la
22
literatura. Se fundamentan en la búsqueda por valles o procesos estocásticos
para el intercambio de los departamentos hasta que ya no hay más
mejoramiento.
• Métodos híbridos: combinan los dos métodos anteriormente mencionados.
• Método de grafos teóricos: en este caso la configuración es presentada como
un grafo cuyos vértices son los departamentos y las interconexiones son los
costos. Se busca encontrar el dual del subgrafo máximo planar.
23
3 CREACIÓN DEL ALGORITMO DE ENFRIAMIENTO SIMULADO
(SIMULATED ANNEALING) PARA CONFIGURACIÓN DE PLANTA
3.1 ESTRUCTURA DE CODIFICACIÓN DE UNA SOLUCIÓN FACTIBLE Es necesario tener una estructura mediante la cual se codifique determinada
solución factible de configuración de planta. De acuerdo a Islier, la estructura para
definir una configuración de n departamentos, es un vector de dimensión 2xn+4.
En las primeras n casillas del vector vamos a encontrar la secuencia que rige la
disposición de los departamentos en el área disponible. De la casilla n+1 a 2xn
encontramos las áreas de los correspondientes departamentos. De la casilla
2xn+1 a 2xn+4 encontramos los anchos de las 4 bandas en las cuales dividimos el
largo del área disponible. A partir de los datos contenidos en este vector,
construimos la configuración en el área disponible mediante el procedimiento X-Y
oscilartorio. Este procedimiento divide el área disponible en cuatro partes y luego
aplica una oscilación en una sola dimensión para cada una, al ubicar las áreas de
los departamentos. Los anchos se generan de manera aleatoria y la suma debe
ser igual al largo o al ancho (según se escoja) del área disponible de la planta.
Para un ejemplo ilustrativo, ver anexo 1: ejemplo de cromosoma y configuración
de planta resultante, utilizando el procedimiento XY Oscilatorio. Una vez
construida la solución, se llama a la subrutina que se encarga de calcular la
función objetivo con el fin de evaluar la solución encontrada y así, tener un criterio
mediante el cual se pueda dirigir la búsqueda de acuerdo a la metodología de
Simulated Annealing.
3.2 DECISIONES GENÉRICAS Acá se involucra la tasa de enfriamiento, incluyendo, los límites superior e inferior
para el parámetro de temperatura y la tasa a la cual esta debe reducirse. La tasa
de enfriamiento está gobernada por el número de repeticiones en cada
temperatura y la tasa a la cual se reduce cada temperatura.
24
La función de enfriamiento escogida involucra una reducción geométrica de la
temperatura dada por t=at, a<1. Según la literatura, con valores relativamente
altos de a se obtienen mejores resultados.
En los experimentos que se corrieron para los diferentes tamaños de problema (7,
12 y 32 departamentos) se hicieron corridas para a=0.98, 0.96, 0.94, ..., 0.88.
Efectivamente, como era de esperarse, con tasas de enfriamiento más lentas, el
resultado es mejor. Los resultados de los experimentos que se presentan
corresponden todos a una tasa de enfriamiento con el parámetro a=0.98.
3.2.1 Temperatura inicial y temperatura final
Para la temperatura inicial y final se tienen en cuenta los valores que se puedan
tener de tt eoeδδ−
(según el caso: minimización, maximización) de acuerdo a los
valores que tomen las funciones objetivo que son las que determinan el tamaño de
Delta. A temperaturas altas, la tasa de aceptación es más alta que a temperaturas
bajas. Además, en temperaturas altas, no se gasta mucho tiempo. En
temperaturas bajas se debe gastar más tiempo Hay que tener en cuenta lo
siguiente:
Cuando, . Cuando tδ es mayor que 3 la probabilidad de aceptar una mala
configuración empieza a ser cada vez más insignificante. Así pues, dependiendo
de los valores de δ se escogen rangos de temperatura que permitan obtener
valores de teδ−
acordes con los objetivos, teniendo en cuenta el valor que puede
tomar la diferencia entre las funciones objetivos de la solución actual y de la
solución que se está evaluando. Los valores de δ dependen de los valores de las
funciones objetivo empleadas para hallarlos como se mencionó anteriormente. De
esta forma, la temperatura inicial y final, dependen de los datos del problema que
estemos tratando y de los criterios de optimización.
25
3.2.2 Criterio de Parada
En esta investigación el criterio de parada del algoritmo es independiente del
tamaño del problema y sus datos. Se escoge una temperatura mayor y una
menor. La escogencia de la mayor, se hace teniendo en cuenta que esta
proporcione una permisividad alta de aceptación de configuraciones que
desmejoren la función objetivo. La temperatura inferior, se escoge teniendo en
cuenta que la permisividad de aceptación de una mala solución sea casi nula, de
manera pues que solamente se acepten soluciones que mejoren la función
objetivo. Con una tasa de enfriamiento ( ) att =α , la temperatura Superior y la
temparatura inferior tienen la siguiente relación:
nerior
erior aT
T infsup = (10)
donde n es el número de temperaturas que se quiere recorra el algoritmo. Es
decir, si tenemos una temperatura inferior de 300 que se escogió
convenientemente, teniendo en cuenta los valores de la variable delta, y se quiere
que se recorran 80 temperaturas, la temperatura superior está dada por la
siguiente expresión:
151098.0
30080sup ≈=eriorT (11)
El número de temperaturas a recorrer por el algoritmo se escoge de acuerdo al
tamaño del problema. Se sugiere hacer varios experimentos para encontrar hasta
donde es práctico y fructuoso aumentar el valor de n para determinado tamaño de
problema.
3.2.3 Número de repeticiones por temperatura
Según la bibliografía consultada, el tiempo invertido en búsqueda cuando estamos
en las temperaturas superiores debe ser muy poco y el tiempo gastado a bajas
temperaturas debe ser mayor. Inicialmente, de manera arbitraria se toma un
26
número de iteraciones dado por n
n
4 para los problemas de n=7 y n=12
departamentos. Este número de iteraciones es constante en todas las
temperaturas. Se experimenta con diferentes rangos de temperaturas.
Posteriormente se aumenta el número de iteraciones a medida que se va
disminuyendo la temperatura. El aumento es geométrico. Cada vez se aumenta
el número de iteraciones en un cinco porciento aproximadamente, ya que
aumentos mayores van en detrimento de la eficiencia computacional. En este
proceso, se tiene en cuenta que al aumentar la tasa en la cual se incrementa el
número de iteraciones por temperatura, el tiempo computacional requerido para
que el algoritmo alcance el criterio de parada, que es la temperatura inferior,
aumenta en mayor proporción. Finalmente, para el caso de 7 y 12 departamentos,
se establece que el número de iteraciones por temperatura debe ser de 20 en la
temperatura superior, aumentándose cada vez en un cinco porciento
aproximadamente, hasta alcanzar la temperatura inferior. En el caso del problema
de 32 departamentos, el número de iteraciones en la temperatura inicial es de 30 y
se aumenta también un cinco porciento aproximadamente cada vez que se reduce
la temperatura. Además de esto, el número de temperaturas que se recorre desde
la inicial hasta la final en este último problema es un 40% mayor a este mismo
número correspondiente al caso de 7 y 12 departamentos en donde se toman 80
temperaturas, es decir n=80 en la ecuación 10.
3.3 DECISIONES ESPECÍFICAS DEL PROBLEMA
3.3.1 Espacio de soluciones factibles
El algoritmo genera soluciones de manera aleatoria que son de antemano
factibles. Esta factibilidad está dada en términos del cumplimiento de las
restricciones del modelo planteado por Islier.
27
La programación del macro diseñado, garantiza que ningún área sea ocupada por
más de un departamento, que el área de cada departamento se mantenga entre
los límites establecidos y que el área total asignada, no exceda el área total
disponible, lo cual es acorde con el cumplimiento de las restricciones matemáticas
del modelo de islier.
3.3.2 Forma de la función de costo
El planteamiento del problema establece una función objetivo multicriterios. Sin
embargo, para realizar el benchmark del problema se utiliza una función objetivo
modificada cuyo único criterio de optimización es el flujo de cargas.
Cuando tenemos una función objetivo multicriterios (flujo de cargas, compactación
de las áreas y área asignada Vs. Área más deseada) buscamos maximizar esa
función, lo cual redunda en una pequeña modificación del algoritmo annealing que
se enunció anteriormente, representada en las siguientes instrucciones:
( ) ( )
( )...
10
0
0
0
entoncesexsi
talyentrexgenerarnosi
ssentoncesSi
sfsf
tδ
δδ
<
=>
−=
(12)
3.3.3 Estructura de vecinaje empleada
Inicialmente, se empleó una estructura de vecinaje muy conservadora que
consistía, únicamente en intercambiar 2 departamentos en el vector. El resultado
que se obtenía con esta estructura no era muy prometedor en términos de las
mejoras obtenidas en el desarrollo del algoritmo a largo plazo. Por este motivo, se
decide utilizar una estructura de vecinaje un poco más compleja, que
intercambiaba 2 departamentos y cambiaba el ancho de las bandas. Con esto se
28
obtuvieron mejores resultados que los que se lograron con la estructura de
vecinaje anterior. Posteriormente, con fines experimentales, se decide utilizar una
estructura de vecinaje más agresiva, cambiando 2 pares de departamentos, el
área asignada a cada departamento y los anchos de banda. Los resultados son
mucho mejores que en las anteriores. Todos los experimentos que se muestran
en esta investigación emplearon esta última estructura de vecinaje.
3.4 IMPLEMENTACIÓN COMPUTACIONAL La metodología y estructura expuesta para desarrollar el algoritmo de enfriamiento
simulado fue programada en Visual Basic en un macro de Excel. El programa
desarrollado tiene los datos correspondientes a la matriz de flujo, la matriz de
costo, y la matriz de áreas, dentro de sus instrucciones, de tal suerte que al
cambiar el problema que se está tratando, se modifica la subrutina que establece
los valores de estas matrices, así como el número de departamentos. Se declaran
el ancho y el largo como dos constantes del módulo de tal forma que al cambiar de
un caso a otro (de siete departamentos a doce departamentos por ejemplo) se
asigne a esas constantes el valor que corresponda según sea el caso. Esto nos
permite aplicar el programa a diferentes problemas –diferentes en datos y tamaño-
para la realización de los experimentos.
A continuación se presenta la subrutinas para el problema de 7 departamentos.
Sub flujo_costo()
f(1, 1) = 0: f(1, 2) = 5: f(1, 3) = 2: f(1, 4) = 4: f(1, 5) = 1: f(1, 6) = 0: f(1, 7) = 0
f(2, 1) = 0: f(2, 2) = 0: f(2, 3) = 3: f(2, 4) = 0: f(2, 5) = 2: f(2, 6) = 2: f(2, 7) = 2
f(3, 1) = 0: f(3, 2) = 0: f(3, 3) = 0: f(3, 4) = 1: f(3, 5) = 0: f(3, 6) = 2: f(3, 7) = 5
f(4, 1) = 0: f(4, 2) = 0: f(4, 3) = 0: f(4, 4) = 0: f(4, 5) = 5: f(4, 6) = 2: f(4, 7) = 2
f(5, 1) = 0: f(5, 2) = 0: f(5, 3) = 0: f(5, 4) = 0: f(5, 5) = 0: f(5, 6) = 10: f(5, 7) = 0
f(6, 1) = 0: f(6, 2) = 0: f(6, 3) = 0: f(6, 4) = 0: f(6, 5) = 0: f(6, 6) = 0: f(6, 7) = 5
f(7, 1) = 0: f(7, 2) = 0: f(7, 3) = 0: f(7, 4) = 0: f(7, 5) = 0: f(7, 6) = 0: f(7, 7) = 0
co(1, 1) = 0: co(1, 2) = 1: co(1, 3) = 1: co(1, 4) = 1: co(1, 5) = 1: co(1, 6) = 1: co(1, 7) = 1
co(2, 1) = 1: co(2, 2) = 0: co(2, 3) = 1: co(2, 4) = 1: co(2, 5) = 1: co(2, 6) = 1: co(2, 7) = 1
29
co(3, 1) = 1: co(3, 2) = 1: co(3, 3) = 0: co(3, 4) = 1: co(3, 5) = 1: co(3, 6) = 1: co(3, 7) = 1
co(4, 1) = 1: co(4, 2) = 1: co(4, 3) = 1: co(4, 4) = 0: co(4, 5) = 1: co(4, 6) = 1: co(4, 7) = 1
co(5, 1) = 1: co(5, 2) = 1: co(5, 3) = 1: co(5, 4) = 1: co(5, 5) = 0: co(5, 6) = 1: co(5, 7) = 1
co(6, 1) = 1: co(6, 2) = 1: co(6, 3) = 1: co(6, 4) = 1: co(6, 5) = 1: co(6, 6) = 0: co(6, 7) = 1
co(7, 1) = 1: co(7, 2) = 1: co(7, 3) = 1: co(7, 4) = 1: co(7, 5) = 1: co(7, 6) = 1: co(7, 7) = 0
End Sub
Sub are()
area(1, 1) = 1: area(1, 2) = 1: area(1, 3) = 1: area(1, 4) = 1: area(1, 5) = 1: area(1, 6) = 1: area(1, 7) = 1
area(2, 1) = 1: area(2, 2) = 1: area(2, 3) = 1: area(2, 4) = 1: area(2, 5) = 1: area(2, 6) = 1: area(2, 7) = 1
area(3, 1) = 1: area(3, 2) = 1: area(3, 3) = 1: area(3, 4) = 1: area(3, 5) = 1: area(3, 6) = 1: area(3, 7) = 1
End Sub
Estas subrutinas correspondientes a los problemas de 12 y 32 departamentos se
encuentran en el anexo 2 y 3 respectivamente.
30
4 EXPERIMENTOS
4.1 METODOLOGÍA Como en la literatura no se encuentran problemas resueltos para una función
multicriterios [8], el benchmarking se hace únicamente para la función objetivo de
un solo criterio de optimización, siendo este la minimización del flujo de cargas,
dada por:
∑ ∑−
= =
1
1 2..
n
i
n
j ijijij dfcMin (13)
Sin embargo, también se presentan los resultados obtenidos para la función
objetivo multicriterios de los diferentes problemas estudiados.
El programa diseñado se corre 3 veces para cada problema y se presenta en el
informe la mejor solución obtenida de las tres corridas. Los puntos de partida para
cada corrida, es decir, la solución inicial, es seleccionada aleatoriamente. Sin
embargo, esto no tiene mucho de importante ya que Simulated Annealing ha
demostrado ser muy independiente de la solución inicial[8] por el hecho de permitir
admisibilidad de soluciones que desmejoran la función objetivo con cierta
probabilidad, lo cual le permite escapar de los óptimos locales.
En el caso de 7 departamentos solo se evaluó la función objetivo modificada dada
por 13 ya que no tiene sentido evaluar factor de forma ni factor de desviación por
la naturaleza misma del problema.
Las medidas de desempeño que nos interesan en el caso de los problemas con
función objetivo modificada son el valor de carga y el tiempo de convergencia para
la temperatura superior e inferior dadas, así como para el aumento en el número
de iteraciones en cada temperatura empleado.
El valor de la carga se registra para todas las soluciones que son aceptadas, tanto
las que mejoran la solución, así como las que la desmejoran y se va asociando
con la temperatura a la cual es encontrada la correspondiente solución.
31
El tiempo de convergencia se mide desde el momento en que se inicia el algoritmo
hasta el momento en que termina de imprimir los resultados.
Para la solución final se registran la matriz de distancias, la matriz de coordenadas
de los distintos departamentos y la matriz de flujo de cargas, siendo esta última
dato del problema y la primera variable de decisión determinada a partir de la
segunda.
4.2 SIMULATED ANNEALING PARA UNA CONFIGURACIÒN DE PLANTA DE 7 DEPARTAMENTOS
Largo: 4 unidades de longitud
Ancho: 2 unidades de longitud
Area total disponible:8 unidades cuadradas de longitud
Areas Departamentos Dpto. 1 2 3 4 5 6 7 Amin 1 1 1 1 1 1 1 Amax 1 1 1 1 1 1 1 Ades 1 1 1 1 1 1 1
Matriz de Flujos 1 2 3 4 5 6 7 1 0 5 2 4 1 0 0 2 0 0 3 0 2 2 2 3 0 0 0 1 0 2 5 4 0 0 0 0 5 2 2 5 0 0 0 0 0 10 0 6 0 0 0 0 0 0 5 7 0 0 0 0 0 0 0
Matriz de Costos 1 2 3 4 5 6 7 1 0 1 1 1 1 1 1 2 1 0 1 1 1 1 1 3 1 1 0 1 1 1 1 4 1 1 1 0 1 1 1 5 1 1 1 1 0 1 1 6 1 1 1 1 1 0 1 7 1 1 1 1 1 1 0
32
En la gráfica 1 del anexo 4 se encuentra la evolución del factor de carga para este
problema.
La mejor configuración de planta de acuerdo al algoritmo de enfriamiento simulado
es la siguiente, junto con las respectivas coordenadas para cada departamento,
matriz de distancias entre departamentos y tiempo de computación:
6 7 3 5 4 2 1
El código correspondiente a la anterior configuración de planta es el siguiente:
6 7 5 4 2 1 3 1 1 1 1 1 1 1 2 2
matriz de coordenadas
Dpto 1 (4 2) Dpto 2 (3 2) Dpto 3 (3 1) Dpto 4 (2 2) Dpto 5 (1 2) Dpto 6 (1 1) Dpto 7 (2 1)
matriz de distancias 1 2 2 3 4 3 1 1 2 3 2 2 3 2 1 1 2 1 1 2 1
matriz de flujo 0 5 2 4 1 0 0 0 0 3 0 2 2 2 0 0 0 1 0 2 5 0 0 0 0 5 2 2 0 0 0 0 0 10 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0
74 0:04:46
33
En el modelo desarrollado para solucionar este mismo modelo de configuración de
planta con algoritmos genéticos [8] se obtiene un valor de 74 para la función
objetivo de este problema, lo cual nos dice que para problemas de tamaño
pequeño el algoritmo de enfriamiento simulado genera buenos resultados. El
tiempo de convergencia sí es mayor pero debemos tener en cuenta que todos los
experimentos que se presentan en este trabajo se realizaron en un computador
pentium 166 Mhz. MMX con 48 megas de memoria RAM. En otras palabras, los
recursos informáticos en términos de hardware, que se emplearon son bastante
limitados y por consiguiente no se puede hacer una comparación con el tiempo
reportado para ese problema con algoritmos genéticos [8] ya que allí se empleó un
computador más avanzado.
4.3 SIMULATED ANNEALING PARA UNA CONFIGURACIÓN DE PLANTA DE 12 DEPARTAMENTOS
En los datos presentados en la tesis de Diana García [8], se hace un cambio en
las escalas de medición del problema original con fines de practicidad
computacional, haciéndose necesario multiplicar por 10 el resultado final para
hacer válidos los resultados obtenidos. A continuación se presentan los datos
correspondientes al problema en cuestión:
Area Departamentos 1 2 3 4 5 6 7 8 9 10 11 12
Amin 18 12 20 36 33 10 36 20 21 25 20 15 Amáx 23 16 25 49 44 12 46 25 30 30 25 16 Ades 21 14 23 43 39 11 41 23 26 28 23 16
34
Matriz de Flujos
1 2 3 4 5 6 7 8 9 10 11 12 1 0 30 0 0 0 0 0 0 0 0 0 30 2 0 0 40 10 0 0 10 0 0 0 0 0 3 0 0 0 35 5 0 0 0 0 0 0 20 4 0 0 0 0 20 20 45 0 0 0 0 30 5 0 0 0 0 0 0 5 20 10 0 0 0 6 0 0 0 0 0 0 5 20 15 10 0 0 7 0 0 0 0 0 0 0 45 10 20 0 0 8 0 0 0 0 0 0 0 0 25 0 60 0 9 0 0 0 0 0 0 0 0 0 50 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0
Matriz de Costos 1 2 3 4 5 6 7 8 9 10 11 12 1 0 1 1 1 1 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 1 1 1 3 1 1 0 1 1 1 1 1 1 1 1 1 4 1 1 1 0 1 1 1 1 1 1 1 1 5 1 1 1 1 0 1 1 1 1 1 1 1 6 1 1 1 1 1 0 1 1 1 1 1 1 7 1 1 1 1 1 1 0 1 1 1 1 1 8 1 1 1 1 1 1 1 0 1 1 1 1 9 1 1 1 1 1 1 1 1 0 1 1 1 10 1 1 1 1 1 1 1 1 1 0 1 1 11 1 1 1 1 1 1 1 1 1 1 0 1 12 1 1 1 1 1 1 1 1 1 1 1 0
En la Gráfica 2 del Anexo 4 se encuentra la evolución del factor de Carga para
este problema en el caso de la función objetivo modificada (Carga de transporte
únicamente). En las gráficas 3, 4 y 5 ilustran la evolución del factor de forma, el
factor de desviación y la función objetivo multicriterios. La mejor configuración de
planta teniendo en cuenta un solo criterio, -la carga de transporte-, de acuerdo al
algoritmo de enfriamiento simulado es la siguiente, junto con las respectivas
coordenadas para cada departamento, matriz de distancias entre departamentos y
tiempo de computación:
El código de la mejor configuración de planta encontrada es el siguiente:
35
9 10 11 2 8 5 12 6 3 4 7 1 27 25 24 13 20 42 15 10 20 39 38 21 18 1 1 1
Mejor Configuración de Planta para 12 departamentos 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 1 5 5 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 5 5 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 5 5 8 8 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 5 5 5 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 3 3 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 5 5 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 5 5 7 7 7 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 10 10 10 10 10 10 5 5 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 5 5 10 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 5 5 9 9 9 9 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5
Matriz de coordenadas
Dpto 1 9.95 1.05 Dpto 2 9.50 5.00 Dpto 3 9.22 6.04 Dpto 4 9.20 9.93 Dpto 5 19.68 8.46 Dpto 6 10.00 14.00 Dpto 7 9.50 7.67 Dpto 8 8.70 4.10 Dpto 9 8.57 13.19 Dpto 10 10.60 11.80 Dpto 11 8.70 2.90 Dpto 12 10.00 2.00
matriz de flujo
0 30 0 0 0 0 0 0 0 0 0 30 0 0 40 10 0 0 10 0 0 0 0 0 0 0 0 35 5 0 0 0 0 0 0 20 0 0 0 0 20 20 45 0 0 0 0 30 0 0 0 0 0 0 5 20 10 0 0 0 0 0 0 0 0 0 5 20 15 10 0 0 0 0 0 0 0 0 0 45 10 20 0 0 0 0 0 0 0 0 0 0 25 0 60 0
36
0 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Función Objetivo: 29845.47 2:20:46
matriz de distancias 4.39 5.72 9.63 17.15 13.00 7.06 4.29 13.51 11.40 3.09 1.00 1.33 5.23 13.65 9.50 2.67 1.70 9.12 7.90 2.90 3.50 3.91 12.89 8.74 1.91 2.46 7.79 7.14 3.66 4.83 11.95 4.87 2.57 6.33 3.89 3.27 7.53 8.73 15.22 10.98 15.35 15.84 12.42 16.55 16.15 6.83 11.20 2.24 2.80 12.40 12.00 4.37 6.45 5.23 5.57 6.17 9.22 9.60 1.20 3.40 3.42 10.42 12.62 10.80 10.40 2.20
En el experimento realizado con el modelo de algoritmos genéticos [8] para este
mismo problema, se reporta un valor para esta función objetivo de 30252 obtenido
durante una operación del algoritmo que duró 8 minutos 40 segundos. Con
enfriamiento simulado, se obtiene un valor de la función objetivo con una mejora
incremental pero con un tiempo computacional bastante grande. Debemos
recordar que estos tiempos computacionales corresponden a los empleados por
un computador con hardware desactualizado. El valor de la función objetivo
obtenido, como se ilustra arriba, es de 29845.47 obtenido en 2:20:46. (Según reloj
del sistema). Es interesante observar como el tiempo de computación del
algoritmo aumenta de manera dramática al aumentar el tamaño del problema.
Recordemos que para el caso de 7 departamentos el tiempo que le tomó al
computador correr el algoritmo fue de 0:04:46 pasando a ser ahora de 2:20:46.
Para el Caso de Múltiples Criterios, infortunadamente no contamos con un punto
de referencia para comparar, pero vale la pena presentar el resultado obtenido ya
que puede servir como punto de comparación para futuras investigaciones acerca
37
del tema. La mejor configuración de planta obtenida por el algoritmo se muestra a
continuación: Mejor Configuración de Planta
12 12 12 12 12 12 12 5 5 5 5 5 5 5 5 9 9 9 9 9 9
12 12 12 12 12 12 12 5 5 5 5 5 5 5 5 9 9 9 9 9 9
12 4 4 4 4 4 4 5 5 5 5 5 5 5 5 9 9 9 9 9 9
4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 3 3 3 9 9 9
4 4 4 4 4 4 4 5 5 5 5 5 6 6 6 3 3 3 3 3 3
4 4 4 4 4 4 4 5 5 5 5 5 6 6 6 3 3 3 3 3 3
4 4 4 4 4 4 4 11 11 11 11 11 6 6 6 3 3 3 3 3 3
4 4 4 4 4 4 4 11 11 11 11 11 10 6 6 1 1 1 1 1 3
4 4 4 4 4 7 7 11 11 11 11 11 10 10 10 1 1 1 1 1 1
7 7 7 7 7 7 7 11 11 11 11 11 10 10 10 1 1 1 1 1 1
7 7 7 7 7 7 7 8 8 8 8 8 10 10 10 1 1 1 1 2 2
7 7 7 7 7 7 7 8 8 8 8 8 10 10 10 2 2 2 2 2 2
7 7 7 7 7 7 7 8 8 8 8 8 10 10 10 2 2 2 2 2 2
7 7 7 7 7 7 7 8 8 8 8 8 10 10 10 10 10 10 10 10 10
La mejor configuración de planta está dada por:
12 4 7 8 11 5 6 10 2 1 3 9 15 46 37 20 20 42 11 25 14 21 22 21 7 5 3 6
matriz de coordenadas Dpto. 1 18.19 9.43 Dpto. 2 18.79 12.29 Dpto. 3 18.41 5.82 Dpto. 4 3.96 5.93 Dpto. 5 11.14 3.21 Dpto. 6 14.09 6.36 Dpto. 7 4.14 11.84 Dpto. 8 10.00 12.50 Dpto. 9 18.71 2.29 Dpto. 10 15.04 11.96 Dpto. 11 10.00 8.50 Dpto. 12 3.80 1.60
matriz de distancias
3.45 3.83 17.73 13.26 7.16 16.46 11.26 7.67 5.68 9.12 22.22 6.84 21.18 16.71 10.62 15.10 9.00 10.07 4.07 12.57 25.67 14.57 9.87 4.86 20.29 15.09 3.84 9.51 11.09 18.83 9.91 10.56 6.08 12.61 18.41 17.11 8.61 4.49 6.10 15.63 10.43 8.50 12.64 6.43 8.96 15.43 10.23 8.70 6.55 6.23 15.05 6.53 24.13 11.03 9.20 10.57 18.93 5.58 4.00 17.10 13.35 14.93 15.60 8.50 21.60 13.10
38
matriz de flujo 0 30 0 0 0 0 0 0 0 0 0 30 0 0 40 10 0 0 10 0 0 0 0 0 0 0 0 35 5 0 0 0 0 0 0 20 0 0 0 0 20 20 45 0 0 0 0 30 0 0 0 0 0 0 5 20 10 0 0 0 0 0 0 0 0 0 5 20 15 10 0 0 0 0 0 0 0 0 0 45 10 20 0 0 0 0 0 0 0 0 0 0 25 0 60 0 0 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
t 1.0000 s 5.5864 h 0.0680 fobj 2.6314 1:49:02
El tiempo empleado por el computador es menor en el caso de múltiples criterios
ya que la temperatura inicial y la temperatura final son diferentes debido a la
naturaleza de la función objetivo como se mencionó en el numeral 3.2.1.
4.4 SIMULATED ANNEALING PARA UNA CONFIGURACIÓN DE PLANTA DE 32 DEPARTAMENTOS
Las modificaciones de los datos originales son iguales a las presentadas en el
experimento anterior para 12 departamentos. Sin embargo, sí vale la pena hacer
una observación. En el anexo 2 de [8] se presentan los datos originales del
problema y las dimensiones de largo y ancho no son coincidentes con las que se
trabaja en el experimento realizado con algoritmos genéticos en [8]. Los datos
originales del problema correspondiente al enunciado de Banerjee P. Y Montereuil
B [20] de la compañía Har Bal (Mariotti) 1977 de 32 departamentos presentan un
largo de 485 y un ancho de 300, mientras que en [8] se trabaja con un largo de 42
y un ancho de 22. Sin embargo, en este trabajo, con fines comparativos, se
39
realiza el experimento con las dimensiones tomadas en [20] para que no se
alteren los valores de la función objetivo. A continuación se presentan los datos
para el problema de 32 departamentos extraídos de [8]
40
Area de Departamentos
Amin 53 28 81 30 20 30 3 42 2 9 8 16 8 8 11 11 8 28 28 46 33 33 25 23 23 12 30 42 30 9 28 42
Amax 60 33 90 36 23 36 39 49 6 53 11 20 11 11 14 14 11 33 33 53 39 39 30 28 28 16 36 49 36 12 33 49
Ades 57 31 86 33 22 33 36 46 4 31 10 18 10 10 13 13 10 31 31 50 36 36 28 26 26 14 33 46 33 11 31 46
Matriz de Flujos
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 0 0 0 0 0 0 0 0 0
2 0 0 56 56 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 20 20 45 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 46 5 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 52 52 26 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 68 0 0 0 0 68 0 0 0 211 0 0 0 0 0 0 65 68 74 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 56 56 0 0 0 0 0 0 0 0 40 0
17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0
18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 0 0 0 0 0 0 0 0 0 0
19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 83 0 0
21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 94 0 0 0 0 0 0 0
24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 0
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50
26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
41
30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20
31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Matriz de Costos
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
8 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
11 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
12 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
13 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
14 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
17 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
21 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
22 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
23 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
24 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
26 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
27 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
28 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
42
29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
30 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
31 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
32 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
43
Los resultados obtenidos para este caso no son muy buenos que digamos. El
tiempo de computación aumentó dramáticamente empezando a evidenciar
impracticidad a medida que aumenta el tamaño del problema Además la solución
que se encontró no logró llegar a la encontrada en [8]. A continuación se
presentan los resultados obtenidos para el modelo de la función objetivo
modificada:
44
3 3 3 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 14 14 14 14 14 14 14 14 27
3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 21 21 21 21 21 21 21 21 21 21 21 27 27 18
3 3 3 5 5 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 27 27 18 18 18 18
3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 8 8 8 8 8 8 8 8 8 8 8 8 8 8 27 27 18 18 18 18
3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 12 12 12 27 27 18 18 18 18
3 3 3 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 12 12 12 12 12 27 27 18 18 18 18
3 3 3 19 19 19 30 30 30 30 30 30 30 30 30 30 26 26 26 26 26 26 26 26 26 26 26 26 22 22 22 22 22 22 27 27 18 18 18 18
3 3 3 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 27 27 18 18 18 18
3 3 3 22 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 27 27 18 18 18 18
3 3 3 28 28 28 28 28 28 28 28 28 28 13 13 13 13 13 13 13 13 15 15 15 15 15 15 15 15 15 15 15 15 15 27 27 1 1 1 1
3 3 3 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 27 27 1 1 1 1
3 3 3 32 32 32 32 32 32 32 32 32 32 17 17 17 17 17 17 17 17 17 7 7 7 7 7 28 28 28 28 28 28 28 27 27 1 1 1 1
3 3 3 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 27 27 1 1 1 1
3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 16 16 16 16 16 16 16 16 16 16 16 16 32 32 32 32 32 27 27 1 1 1 1
3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 11 11 11 11 11 11 11 11 20 20 20 20 20 20 20 27 27 1 1 1 1
3 3 3 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 27 27 1 1 1 1
3 3 3 20 20 20 20 20 20 20 20 20 20 20 20 20 10 10 10 10 10 10 10 10 10 10 10 10 10 10 24 24 24 24 27 27 1 1 1 1
3 3 3 29 29 29 29 29 29 29 29 29 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 9 27 1 1 1 1
3 3 3 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 25 25 25 25 25 25 25 25 25 25 9 9 1 1 1 1
3 3 3 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 1 9 1 1 1 1
3 3 3 31 31 31 31 31 31 31 31 31 31 31 31 31 31 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 1 1 1 1 1 1
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 23 23 23 23 23 23 23 23 23 23 1 1 1 1 1 1
La mejor configuración de planta está dada por:
3 23 31 25 29 24 10 20 11 2 16 32 17 7 28 13 15 4 22 26 30 19 12 6 8 5 21 14 27 9 1 18 87 27 29 26 30 26 14 51 8 30 12 46 9 5 48 8 13 30 38 12 10 29 19 34 43 22 35 8 34 4 57 29 3 31 2 4 1 1
45
matriz de coordenadas Dpto. 1 38.000 16.000 Dpto. 17 18.000 12.000 Dpto. 2 11.000 15.000 Dpto. 18 38.000 6.000 Dpto. 3 5.000 14.000 Dpto. 19 15.000 6.000 Dpto. 4 20.000 9.000 Dpto. 20 18.000 16.000 Dpto. 5 13.000 2.000 Dpto. 21 20.000 1.000 Dpto. 6 12.000 5.000 Dpto. 22 21.000 8.000 Dpto. 7 25.000 12.000 Dpto. 23 27.000 21.000 Dpto. 8 22.000 3.000 Dpto. 24 25.000 18.000 Dpto. 9 36.000 19.000 Dpto. 25 28.000 20.000 Dpto. 10 24.000 17.000 Dpto. 26 23.000 7.000 Dpto. 11 24.000 15.000 Dpto. 27 36.000 10.000 Dpto. 12 29.000 5.000 Dpto. 28 19.000 11.000 Dpto. 13 18.000 10.000 Dpto. 29 12.000 19.000 Dpto. 14 32.000 1.000 Dpto. 30 12.000 7.000 Dpto. 15 28.000 10.000 Dpto. 31 11.000 20.000 Dpto. 16 24.000 14.000 Dpto. 32 18.000 13.000
El valor de la función objetivo es 205405. El valor de la función objetivo obtenido
en el trabajo realizado con Algoritmos Genéticos [8] es sustancialmente más bajo
161170. Por otro lado, el tiempo de computación fue de 5:01:30, tiempo bastante
grande en comparación con el empleado por algoritmos genéticos [8]:0:28:08.
46
matriz de distancias 29 36 26 40 38 18 29 5 15 16 21 27 22 17 17 25 11 33 20 34 26 16 15 14 25 10 25 28 36 31 24 7 14 14 11 17 23 29 15 13 27 11 34 22 13 10 36 13 9 22 16 23 17 22 19 30 11 5 8 6 9 20 20 17 22 28 36 22 20 33 17 40 27 19 15 42 18 16 28 22 30 24 28 25 35 17 12 14 12 14 14 12 9 9 26 12 10 13 3 20 10 9 5 22 7 8 8 2 20 14 19 5 17 3 17 10 20 5 3 22 11 40 26 24 19 13 20 23 23 15 30 7 20 8 14 34 28 32 15 30 15 17 6 20 16 21 12 38 24 22 17 11 23 22 21 14 28 5 18 11 12 32 26 31 13 29 13 14 3 17 15 11 18 7 5 10 10 18 5 4 7 20 16 11 16 9 12 6 10 8 13 8 20 19 23 8 29 15 13 8 12 11 12 12 13 19 10 17 5 6 23 17 22 4 19 11 26 15 29 14 14 16 21 27 22 17 17 25 16 33 20 33 26 11 12 8 25 10 25 24 36 26 23 2 17 13 24 12 3 11 26 19 6 19 12 8 2 7 11 20 11 13 22 16 9 15 11 22 10 1 9 24 17 6 17 10 10 4 9 9 18 9 15 20 18 7 16 7 5 14 17 10 14 21 13 11 17 16 15 8 11 16 30 19 33 18 23 11 10 3 25 6 7 11 5 21 15 20 8 19 2 14 9 17 4 13 21 25 12 21 28 12 18 25 23 22 15 13 23 37 26 40 25 9 12 15 17 16 17 10 12 11 10 9 8 10 25 20 28 13 8 23 16 7 16 9 11 5 10 8 17 8 16 19 19 6 27 9 4 12 7 19 13 17 10 20 2 13 12 16 1 23 30 23 20 27 26 25 17 7 25 39 28 42 27 13 9 7 27 21 26 8 24 8 16 5 19 10 16 10 14 8 13 13 24 5 9 16 12 3 7 28 22 26 8 24 11 25 14 28 13 20 14 19 3 17 5 19 10 22 7 6 2 19 20 19 18 30 17 18 5 13 19 13 14 24 17 12 18 18 18 16 29 18 16 16 8 22 11 25 10 18 33 27 36 21 14 11 17 2 12 3 12 14 13 15
47
La evolución del factor de carga para este caso se encuentra en el gráfico 6 del
anexo 4. En cuanto al modelo de múltiples criterios para 32 departamentos la
evolución del factor de forma se muestra en el gráfico 7, la evolución del factor de
desviación se encuentra en el gráfico 8 y la evolución de la función objetivo
multicriterios se encuentra en el gráfico 9 del mismo anexo.
A continuación se muestra el resultado arrojado para el problema de 32
departamentos con múltiples criterios de optimización:
48
1 1 1 1 1 1 1 1 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 11 11 11 11 11 11 11 1 1 1 1 1 1 1 1 16 16 16 16 31 31 31 31 31 31 31 31 31 27 27 27 27 27 27 27 27 27 27 11 24 24 24 24 24 24 1 1 1 1 1 1 1 1 16 16 16 16 16 16 16 16 16 32 32 32 32 27 27 27 27 27 27 27 27 27 27 22 24 24 24 24 24 24 1 1 1 1 1 1 1 1 32 32 32 32 32 32 32 32 32 32 32 32 32 27 27 27 27 27 27 27 27 27 27 22 24 24 24 24 24 24 1 1 1 1 1 1 1 1 32 32 32 32 32 32 32 32 32 32 32 32 32 27 27 27 27 15 15 15 15 15 15 22 24 24 24 24 24 24 1 1 1 1 1 1 1 1 32 32 32 32 32 32 32 32 32 32 32 32 32 12 12 12 15 15 15 15 15 15 15 22 26 26 26 24 24 24 1 1 1 1 1 20 20 20 32 32 32 32 10 10 10 10 10 10 10 10 10 12 12 12 12 12 12 12 12 12 12 22 26 26 26 26 26 26 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 10 8 8 8 8 8 8 8 12 12 12 22 28 26 26 26 26 26 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 19 8 8 8 8 8 8 8 8 8 8 22 28 28 28 28 28 28 20 20 20 20 20 20 20 20 18 18 18 18 18 18 18 18 19 19 19 19 19 8 8 8 8 8 8 8 8 8 8 22 28 28 28 28 28 28 20 20 20 20 20 20 20 20 18 18 18 18 18 18 18 18 18 18 18 18 18 8 8 8 8 8 8 8 8 8 8 22 28 28 28 28 28 28 20 20 20 20 20 20 20 20 17 17 17 18 18 18 18 18 18 18 18 18 18 3 3 3 8 8 8 8 8 8 8 22 28 28 28 28 28 28 20 20 20 20 20 20 20 14 17 17 17 17 17 17 17 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 22 28 28 28 28 28 28 13 13 13 14 14 14 14 14 14 14 14 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 22 28 28 28 28 28 28 13 13 13 13 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 29 29 3 3 3 3 3 3 3 3 3 3 22 28 28 28 28 28 28 13 13 13 5 4 4 4 4 4 4 4 4 29 29 29 29 29 29 29 29 29 29 29 29 29 3 3 3 3 3 3 3 3 3 3 22 21 21 21 21 21 21 5 5 5 5 4 4 4 4 4 4 4 4 29 29 29 29 29 29 29 29 29 29 29 29 29 3 3 3 3 3 3 3 3 3 3 22 21 21 21 21 21 21 5 5 5 5 4 4 4 4 4 4 4 4 6 6 6 9 9 9 9 9 29 29 29 29 29 3 3 3 3 3 3 3 3 3 3 22 21 21 21 21 21 21 5 5 5 5 4 4 23 23 23 23 23 23 6 6 6 6 6 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3 3 3 22 21 21 21 21 21 21 5 5 5 5 23 23 23 23 23 23 23 23 6 6 6 6 6 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 3 3 3 22 21 21 21 21 21 21 7 5 5 5 23 23 23 23 23 23 23 23 6 6 6 6 6 25 25 25 25 25 25 25 25 3 3 3 3 22 22 22 22 22 22 22 21 21 21 21 21 21 7 7 7 7 23 23 23 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 22 22 22 22 22 22 22 22 22 22 22 21 30 30 30 30 30 30 30 30 30
Mejor configuración de planta obtenida:
1 20 14 4 23 25 6 9 29 2 17 18 19 10 32 16 31 27 15 12 8 3 22 11 24 26 28 21 30 7 5 13 53 50 9 34 25 26 34 5 33 30 10 31 30 10 47 13 32 34 13 16 44 87 36 8 27 14 43 37 9 5 20 10 8 13 10 1 6 4
49
matriz de coordenadas Dpto. 1 4.358 3.830 Dpto. 17 11.400 12.700 Dpto. 2 15.333 14.167 Dpto. 18 14.839 11.065 Dpto. 3 26.241 16.552 Dpto. 19 15.467 8.767 Dpto. 4 4.324 16.647 Dpto. 20 4.580 10.240 Dpto. 5 40.650 17.750 Dpto. 21 35.432 18.595 Dpto. 6 13.971 19.588 Dpto. 22 29.889 16.556 Dpto. 7 40.200 20.800 Dpto. 23 4.440 20.320 Dpto. 8 26.500 10.000 Dpto. 24 35.667 3.778 Dpto. 9 14.000 18.000 Dpto. 25 14.038 21.692 Dpto. 10 17.400 7.100 Dpto. 26 35.357 7.143 Dpto. 11 34.625 1.125 Dpto. 27 26.147 3.235 Dpto. 12 26.500 7.000 Dpto. 28 35.442 11.907 Dpto. 13 40.500 14.000 Dpto. 29 15.939 16.636 Dpto. 14 4.889 13.889 Dpto. 30 38.000 22.000 Dpto. 15 28.231 5.538 Dpto. 31 19.156 1.281 Dpto. 16 12.231 2.692 Dpto. 32 15.000 5.000
El valor de la función objetivo es de 2.5201. Infortunadamente, al igual que en el
caso de 12 departamentos no se cuenta con un punto de referencia con el cual
hacer una comparación pero se presenta el resultado para futuras investigaciones
como se dijo anteriormente. Algo interesante, es el incremento dramático del
tiempo de computación: 7:54:44 A medida que el problema va creciendo en
tamaño, el tiempo de computación crece de manera exponencial.
A continuación se muestra la matriz de distancias obtenida. Esta matriz, al igual
que la anterior, tiene las distancias aproximadas al entero más cercano. En el
archivo adjunto de Excel correspondiente a 32 departamentos multicriterios se
muestran los valores exactos de estas matrices.
50
matriz de distancias 21 35 13 50 25 53 28 24 16 33 25 46 11 26 9 16 18 16 7 46 38 17 31 28 34 22 39 24 52 17 12 13 13 29 7 32 15 5 9 32 18 25 11 22 15 5 4 6 15 25 17 17 31 9 27 22 22 3 31 17 10 22 16 15 18 7 14 18 24 10 17 24 13 28 19 17 19 28 11 4 26 22 17 19 13 14 10 17 22 23 37 13 40 29 11 23 46 32 39 3 35 22 11 16 19 7 33 26 4 44 15 41 35 36 12 39 30 22 29 4 22 27 34 23 25 4 40 25 43 34 32 34 44 6 12 39 19 31 16 29 11 26 7 38 38 27 22 2 16 39 25 32 15 28 19 9 9 12 19 22 19 10 38 2 34 29 29 5 26 23 16 25 29 37 25 28 7 42 27 46 37 35 37 46 7 15 36 22 27 19 32 14 28 3 41 41 21 12 17 3 18 26 6 22 18 13 12 22 18 10 32 15 24 12 7 11 17 24 16 17 14 38 24 31 13 27 17 8 8 11 17 22 17 12 36 4 32 27 28 3 28 22 14 23 9 30 19 12 10 12 7 4 16 30 22 26 22 18 18 13 23 11 36 8 4 14 19 43 11 24 35 30 27 39 18 20 49 4 41 7 11 12 34 24 16 24 21 29 3 19 21 16 13 25 21 13 35 12 27 9 4 14 20 27 13 14 36 21 40 30 29 30 40 10 13 42 15 34 12 25 7 27 11 34 35 32 19 8 13 16 4 35 28 7 41 17 37 32 33 14 41 27 19 19 24 19 16 28 20 13 39 9 30 9 4 14 23 26 13 14 11 11 9 15 39 32 25 25 21 28 14 32 18 45 8 5 5 8 9 30 22 15 33 12 30 24 25 8 36 19 11 3 11 28 21 20 28 11 24 19 21 7 34 14 6 12 30 22 23 25 14 22 16 23 8 36 11 4 39 32 10 38 21 34 29 33 18 45 24 16 8 33 15 24 12 25 7 21 6 34 34 29 19 21 15 17 10 14 14 26 26 48 11 44 39 39 15 35 34 26 40 4 10 8 33 21 19 22 36 31 31 7 24 26 18 13 5 29 18 22 23 18 24 31 9 13 24 13 27 27 27 19 13 40 40 8
51
matriz de flujo
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 136 0 0 0 0 0 0 0 0 0
0 0 56 56 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 20 20 45 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 46 5 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 52 52 26 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 68 0 0 0 0 68 0 0 0 211 0 0 0 0 0 0 65 68 74 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 56 56 0 0 0 0 0 0 0 0 40 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 40 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 46 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 83 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 94 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
52
5 CONCLUSIONES
• El rango de temperaturas se debe escoger teniendo en cuenta que se
garantice que cuando el algoritmo encuentra una solución lo suficientemente
buena, las probabilidades de cambiarla en altas temperaturas sean bastante
bajas y que cuando encuentre una solución mala en bajas temperaturas, las
probabilidades de cambiarla sean considerablemente altas.
• Con diferentes puntos de arranque, la aleatoriedad del algoritmo permite llegar
al óptimo global sin quedar atrapado en óptimos locales. La probabilidad de
aceptar malas soluciones le permite al algoritmo tener independencia de la
solución inicial.
• Con recursos informáticos más avanzados, en términos de hardware, la
eficiencia en el uso del tiempo computacional permite realizar más iteraciones
en el mismo tiempo al algoritmo lo cual aumenta la posibilidad de encontrar
mejores soluciones. Las capacidades de Hardware son importantes en el éxito
del algoritmo.
• A medida que el tamaño del problema aumenta, es decir, el número de
departamentos crece, la técnica de vecinaje se debe hacer más agresiva. El
número de anchos de banda pasa, por conveniencia, de 4 a 6 en el problema
de 32 departamentos y además se deben cambiar las áreas asignadas y 2
pares de departamentos. Esto con el fin de obtener mejores resultados
mediante la ampliación de las posibilidades de vecinaje. Por otro lado, el rango
entre la temperatura inicial y la temperatura final debe ser mayor con el fin de
darle al algoritmo más tiempo para muestrear la región factible en busca de
mejores soluciones Por estas razones, a medida que aumenta el tamaño del
problema, el tiempo computacional se va haciendo menos práctico.
• En cuanto a la tasa de enfriamiento, la que dio mejores resultados es T=0.98T.
Esta, junto con un aumento geométrico en el número de iteraciones dado por
p=Int(1.05p), donde p es el número de iteraciones, permite que a temperaturas
altas, se emplee mucho menos tiempo que en las temperaturas finales. El p
inicial en el caso de 7 y 12 departamentos fue de 20. Para el caso de 32
53
departamentos fue de 30 y el resultado no fue muy satisfactorio presentando
además un tiempo de computación excesivo sugiriendo la inconveniencia de
aumentar el valor inicial de p
• El algoritmo de enfriamiento simulado es muy bueno para problemas pequeños
y medianos. En el caso de problemas grandes, el tiempo computacional
aumenta de manera exponencial con el problema (como se menciona en la
literatura). Se recomiendan técnicas heurísticas más sistemáticas como Tabu
Search o Algoritmos Genéticos, para tratar problemas grandes.
• La estructura de vecinaje se debe hacer más agresiva a medida que el tamaño
del problema aumenta, ya que con este, también aumenta el tamaño de la
región factible, por razones obvias. Con disponibilidad de hardware más
avanzado y más tiempo computacional, se sugiere con base en los
experimentos realizados que el algoritmo puede dar mejores resultados. Se
entiende que un problema es grande cuando n>16 (n es el número de
departamentos).
• Se debe tener especial cuidado en la selección de las temperaturas inferiores
ya que se corre el riesgo de que al ser estas demasiado bajas el algoritmo
llegue a un óptimo local y la probabilidad de que este escape de esa región a
otra más promisoria, aceptando una solución que desmejore la función
objetivo, sea indistinguible de cero.
• La escogencia del mejor rango de temperaturas se hace basándose en el
comportamiento observado del algoritmo a lo largo de varios experimentos.
54
6 ANEXOS
55
6.1 Anexo 1: Ejemplo de cromosoma y configuración de planta resultante, utilizando el procedimiento X-Y Oscilatorio
12 6 9 4 8 7 11 1 10 3 2 5 15 11 21 39 20 45 22 22 25 21 14 39 5 10 4 2
12 12 12 12 12 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 5 12 12 12 12 12 1 1 1 1 1 10 10 10 10 10 10 10 10 10 5 5 12 12 12 12 12 1 1 1 1 1 1 1 1 1 1 10 10 3 3 5 5 6 6 6 6 6 11 11 11 1 1 1 1 1 1 1 3 3 3 3 5 5 6 6 6 6 6 11 11 11 11 11 11 11 11 11 11 3 3 3 3 5 5 9 9 9 9 6 7 11 11 11 11 11 11 11 11 11 3 3 3 3 5 5 9 9 9 9 9 7 7 7 7 7 7 7 7 7 7 3 3 3 3 5 5 9 9 9 9 9 7 7 7 7 7 7 7 7 7 7 2 3 3 3 5 5 9 9 9 9 9 7 7 7 7 7 7 7 7 7 7 2 2 2 2 5 5 4 4 4 9 9 7 7 7 7 7 7 7 7 7 7 2 2 2 2 5 5 4 4 4 4 4 7 7 7 7 8 8 8 8 8 8 2 2 2 2 5 5 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 5 5 5 2 5 5 4 4 4 4 4 8 8 8 8 4 4 4 4 4 4 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5
56
6.2 Anexo 2: Subrutina para matrices de flujo, costo y áreas para el problema de 12 departamentos Sub flujo_costo()
f(1, 1) = 0: f(1, 2) = 30: f(1, 3) = 0: f(1, 4) = 0: f(1, 5) = 0: f(1, 6) = 0: f(1, 7) = 0: f(1, 8) = 0: f(1, 9) = 0: f(1, 10) = 0: f(1, 11) = 0: f(1, 12) = 30
f(2, 1) = 0: f(2, 2) = 0: f(2, 3) = 40: f(2, 4) = 10: f(2, 5) = 0: f(2, 6) = 0: f(2, 7) = 10: f(2, 8) = 0: f(2, 9) = 0: f(2, 10) = 0: f(2, 11) = 0: f(2, 12) = 0
f(3, 1) = 0: f(3, 2) = 0: f(3, 3) = 0: f(3, 4) = 35: f(3, 5) = 5: f(3, 6) = 0: f(3, 7) = 0: f(3, 8) = 0: f(3, 9) = 0: f(3, 10) = 0: f(3, 11) = 0: f(3, 12) = 20
f(4, 1) = 0: f(4, 2) = 0: f(4, 3) = 0: f(4, 4) = 0: f(4, 5) = 20: f(4, 6) = 20: f(4, 7) = 45: f(4, 8) = 0: f(4, 9) = 0: f(4, 10) = 0: f(4, 11) = 0: f(4, 12) = 30
f(5, 1) = 0: f(5, 2) = 0: f(5, 3) = 0: f(5, 4) = 0: f(5, 5) = 0: f(5, 6) = 0: f(5, 7) = 5: f(5, 8) = 20: f(5, 9) = 10: f(5, 10) = 0: f(5, 11) = 0: f(5, 12) = 0
f(6, 1) = 0: f(6, 2) = 0: f(6, 3) = 0: f(6, 4) = 0: f(6, 5) = 0: f(6, 6) = 0: f(6, 7) = 5: f(6, 8) = 20: f(6, 9) = 15: f(6, 10) = 10: f(6, 11) = 0: f(6, 12) = 0
f(7, 1) = 0: f(7, 2) = 0: f(7, 3) = 0: f(7, 4) = 0: f(7, 5) = 0: f(7, 6) = 0: f(7, 7) = 0: f(7, 8) = 45: f(7, 9) = 10: f(7, 10) = 20: f(7, 11) = 0: f(7, 12) = 0
f(8, 1) = 0: f(8, 2) = 0: f(8, 3) = 0: f(8, 4) = 0: f(8, 5) = 0: f(8, 6) = 0: f(8, 7) = 0: f(8, 8) = 0: f(8, 9) = 25: f(8, 10) = 0: f(8, 11) = 60: f(8, 12) = 0
f(9, 1) = 0: f(9, 2) = 0: f(9, 3) = 0: f(9, 4) = 0: f(9, 5) = 0: f(9, 6) = 0: f(9, 7) = 0: f(9, 8) = 0: f(9, 9) = 0: f(9, 10) = 50: f(9, 11) = 0: f(9, 12) = 0
f(10, 1) = 0: f(10, 2) = 0: f(10, 3) = 0: f(10, 4) = 0: f(10, 5) = 0: f(10, 6) = 0: f(10, 7) = 0: f(10, 8) = 0: f(10, 9) = 0: f(10, 10) = 0: f(10, 11) = 0: f(10, 12) = 0
f(11, 1) = 0: f(11, 2) = 0: f(11, 3) = 0: f(11, 4) = 0: f(11, 5) = 0: f(11, 6) = 0: f(11, 7) = 0: f(11, 8) = 0: f(11, 9) = 0: f(11, 10) = 0: f(11, 11) = 0: f(11, 12) = 0
f(12, 1) = 0: f(12, 2) = 0: f(12, 3) = 0: f(12, 4) = 0: f(12, 5) = 0: f(12, 6) = 0: f(12, 7) = 0: f(12, 8) = 0: f(12, 9) = 0: f(12, 10) = 0: f(12, 11) = 0: f(12, 12) = 0
co(1, 1) = 0: co(1, 2) = 1: co(1, 3) = 1: co(1, 4) = 1: co(1, 5) = 1: co(1, 6) = 1: co(1, 7) = 1: co(1, 8) = 1: co(1, 9) = 1: co(1, 10) = 1: co(1, 11) = 1: co(1, 12) = 1
co(2, 1) = 1: co(2, 2) = 0: co(2, 3) = 1: co(2, 4) = 1: co(2, 5) = 1: co(2, 6) = 1: co(2, 7) = 1: co(2, 8) = 1: co(2, 9) = 1: co(2, 10) = 1: co(2, 11) = 1: co(2, 12) = 1
co(3, 1) = 1: co(3, 2) = 1: co(3, 3) = 0: co(3, 4) = 1: co(3, 5) = 1: co(3, 6) = 1: co(3, 7) = 1: co(3, 8) = 1: co(3, 9) = 1: co(3, 10) = 1: co(3, 11) = 1: co(3, 12) = 1
co(4, 1) = 1: co(4, 2) = 1: co(4, 3) = 1: co(4, 4) = 0: co(4, 5) = 1: co(4, 6) = 1: co(4, 7) = 1: co(4, 8) = 1: co(4, 9) = 1: co(4, 10) = 1: co(4, 11) = 1: co(4, 12) = 1
co(5, 1) = 1: co(5, 2) = 1: co(5, 3) = 1: co(5, 4) = 1: co(5, 5) = 0: co(5, 6) = 1: co(5, 7) = 1: co(5, 8) = 1: co(5, 9) = 1: co(5, 10) = 1: co(5, 11) = 1: co(5, 12) = 1
co(6, 1) = 1: co(6, 2) = 1: co(6, 3) = 1: co(6, 4) = 1: co(6, 5) = 1: co(6, 6) = 0: co(6, 7) = 1: co(6, 8) = 1: co(6, 9) = 1: co(6, 10) = 1: co(6, 11) = 1: co(6, 12) = 1
co(7, 1) = 1: co(7, 2) = 1: co(7, 3) = 1: co(7, 4) = 1: co(7, 5) = 1: co(7, 6) = 1: co(7, 7) = 0: co(7, 8) = 1: co(7, 9) = 1: co(7, 10) = 1: co(7, 11) = 1: co(7, 12) = 1
co(8, 1) = 1: co(8, 2) = 1: co(8, 3) = 1: co(8, 4) = 1: co(8, 5) = 1: co(8, 6) = 1: co(8, 7) = 1: co(8, 8) = 0: co(8, 9) = 1: co(8, 10) = 1: co(8, 11) = 1: co(8, 12) = 1
co(9, 1) = 1: co(9, 2) = 1: co(9, 3) = 1: co(9, 4) = 1: co(9, 5) = 1: co(9, 6) = 1: co(9, 7) = 1: co(9, 8) = 1: co(9, 9) = 0: co(9, 10) = 1: co(9, 11) = 1: co(9, 12) = 1
co(10, 1) = 1: co(10, 2) = 1: co(10, 3) = 1: co(10, 4) = 1: co(10, 5) = 1: co(10, 6) = 1: co(10, 7) = 1: co(10, 8) = 1: co(10, 9) = 1: co(10, 10) = 0: co(10, 11) = 1: co(10, 12) = 1
co(11, 1) = 1: co(11, 2) = 1: co(11, 3) = 1: co(11, 4) = 1: co(11, 5) = 1: co(11, 6) = 1: co(11, 7) = 1: co(11, 8) = 1: co(11, 9) = 1: co(11, 10) = 1: co(11, 11) = 0: co(11, 12) = 1
co(12, 1) = 1: co(12, 2) = 1: co(12, 3) = 1: co(12, 4) = 1: co(12, 5) = 1: co(12, 6) = 1: co(12, 7) = 1: co(12, 8) = 1: co(12, 9) = 1: co(12, 10) = 1: co(12, 11) = 1: co(12, 12) = 0
End Sub
Sub are()
area(1, 1) = 18: area(1, 2) = 12: area(1, 3) = 20: area(1, 4) = 36: area(1, 5) = 33: area(1, 6) = 10: area(1, 7) = 36: area(1, 8) = 20: area(1, 9) = 21: area(1, 10) = 25: area(1, 11) =
20: area(1, 12) = 15
57
area(2, 1) = 23: area(2, 2) = 16: area(2, 3) = 25: area(2, 4) = 49: area(2, 5) = 44: area(2, 6) = 12: area(2, 7) = 46: area(2, 8) = 25: area(2, 9) = 30: area(2, 10) = 30: area(2, 11) =
25: area(2, 12) = 16
area(3, 1) = 21: area(3, 2) = 14: area(3, 3) = 23: area(3, 4) = 43: area(3, 5) = 39: area(3, 6) = 11: area(3, 7) = 41: area(3, 8) = 23: area(3, 9) = 26: area(3, 10) = 28: area(3, 11) =
23: area(3, 12) = 16
End Sub
6.3 Anexo 3: Subrutina para Matrices de flujo, costo y áreas para el problema de 32 departamentos Sub flujo_costo()
f(1, 1) = 0: f(1, 2) = 0: f(1, 3) = 0: f(1, 4) = 0: f(1, 5) = 0: f(1, 6) = 0: f(1, 7) = 0: f(1, 8) = 0: f(1, 9) = 0: f(1, 10) = 0: f(1, 11) = 0: f(1, 12) = 0: f(1, 13) = 0: f(1, 14) = 0: f(1, 15) = 0: f(1,
16) = 0: f(1, 17) = 0: f(1, 18) = 0: f(1, 19) = 0: f(1, 20) = 0: f(1, 21) = 0: f(1, 22) = 0: f(1, 23) = 136: f(1, 24) = 0: f(1, 25) = 0: f(1, 26) = 0: f(1, 27) = 0: f(1, 28) = 0: f(1, 29) = 0: f(1,
30) = 0: f(1, 31) = 0: f(1, 32) = 0
f(2, 1) = 0: f(2, 2) = 0: f(2, 3) = 56: f(2, 4) = 56: f(2, 5) = 0: f(2, 6) = 0: f(2, 7) = 0: f(2, 8) = 0: f(2, 9) = 0: f(2, 10) = 0: f(2, 11) = 0: f(2, 12) = 0: f(2, 13) = 0: f(2, 14) = 0: f(2, 15) = 0:
f(2, 16) = 0: f(2, 17) = 0: f(2, 18) = 0: f(2, 19) = 0: f(2, 20) = 0: f(2, 21) = 0: f(2, 22) = 0: f(2, 23) = 0: f(2, 24) = 0: f(2, 25) = 0: f(2, 26) = 0: f(2, 27) = 0: f(2, 28) = 0: f(2, 29) = 0: f(2,
30) = 0: f(2, 31) = 0: f(2, 32) = 0
f(3, 1) = 0: f(3, 2) = 0: f(3, 3) = 0: f(3, 4) = 0: f(3, 5) = 0: f(3, 6) = 0: f(3, 7) = 0: f(3, 8) = 0: f(3, 9) = 0: f(3, 10) = 0: f(3, 11) = 0: f(3, 12) = 0: f(3, 13) = 0: f(3, 14) = 0: f(3, 15) = 0: f(3,
16) = 0: f(3, 17) = 0: f(3, 18) = 0: f(3, 19) = 0: f(3, 20) = 0: f(3, 21) = 0: f(3, 22) = 0: f(3, 23) = 0: f(3, 24) = 0: f(3, 25) = 0: f(3, 26) = 0: f(3, 27) = 0: f(3, 28) = 0: f(3, 29) = 0: f(3, 30)
= 0: f(3, 31) = 0: f(3, 32) = 0
f(4, 1) = 0: f(4, 2) = 0: f(4, 3) = 0: f(4, 4) = 0: f(4, 5) = 20: f(4, 6) = 20: f(4, 7) = 45: f(4, 8) = 0: f(4, 9) = 0: f(4, 10) = 50: f(4, 11) = 0: f(4, 12) = 0: f(4, 13) = 0: f(4, 14) = 0: f(4, 15) =
0: f(4, 16) = 0: f(4, 17) = 0: f(4, 18) = 0: f(4, 19) = 0: f(4, 20) = 0: f(4, 21) = 0: f(4, 22) = 0: f(4, 23) = 0: f(4, 24) = 0: f(4, 25) = 0: f(4, 26) = 0: f(4, 27) = 0: f(4, 28) = 0: f(4, 29) = 0:
f(4, 30) = 0: f(4, 31) = 0: f(4, 32) = 0
f(5, 1) = 0: f(5, 2) = 0: f(5, 3) = 0: f(5, 4) = 0: f(5, 5) = 0: f(5, 6) = 46: f(5, 7) = 5: f(5, 8) = 0: f(5, 9) = 0: f(5, 10) = 0: f(5, 11) = 0: f(5, 12) = 0: f(5, 13) = 0: f(5, 14) = 0: f(5, 15) = 0:
f(5, 16) = 0: f(5, 17) = 0: f(5, 18) = 0: f(5, 19) = 0: f(5, 20) = 0: f(5, 21) = 46: f(5, 22) = 0: f(5, 23) = 0: f(5, 24) = 0: f(5, 25) = 0: f(5, 26) = 0: f(5, 27) = 0: f(5, 28) = 0: f(5, 29) = 0:
f(5, 30) = 0: f(5, 31) = 0: f(5, 32) = 0
f(6, 1) = 0: f(6, 2) = 0: f(6, 3) = 0: f(6, 4) = 0: f(6, 5) = 0: f(6, 6) = 0: f(6, 7) = 0: f(6, 8) = 0: f(6, 9) = 0: f(6, 10) = 0: f(6, 11) = 0: f(6, 12) = 0: f(6, 13) = 0: f(6, 14) = 0: f(6, 15) = 0: f(6,
16) = 0: f(6, 17) = 0: f(6, 18) = 0: f(6, 19) = 0: f(6, 20) = 0: f(6, 21) = 0: f(6, 22) = 0: f(6, 23) = 0: f(6, 24) = 0: f(6, 25) = 0: f(6, 26) = 46: f(6, 27) = 0: f(6, 28) = 0: f(6, 29) = 0: f(6,
30) = 0: f(6, 31) = 0: f(6, 32) = 0
f(7, 1) = 0: f(7, 2) = 0: f(7, 3) = 0: f(7, 4) = 0: f(7, 5) = 0: f(7, 6) = 0: f(7, 7) = 0: f(7, 8) = 0: f(7, 9) = 0: f(7, 10) = 0: f(7, 11) = 52: f(7, 12) = 52: f(7, 13) = 26: f(7, 14) = 26: f(7, 15) =
0: f(7, 16) = 0: f(7, 17) = 0: f(7, 18) = 0: f(7, 19) = 0: f(7, 20) = 0: f(7, 21) = 0: f(7, 22) = 0: f(7, 23) = 0: f(7, 24) = 0: f(7, 25) = 0: f(7, 26) = 0: f(7, 27) = 0: f(7, 28) = 0: f(7, 29) = 0:
f(7, 30) = 0: f(7, 31) = 0: f(7, 32) = 0
58
f(8, 1) = 0: f(8, 2) = 0: f(8, 3) = 0: f(8, 4) = 0: f(8, 5) = 0: f(8, 6) = 0: f(8, 7) = 0: f(8, 8) = 0: f(8, 9) = 0: f(8, 10) = 0: f(8, 11) = 0: f(8, 12) = 0: f(8, 13) = 0: f(8, 14) = 0: f(8, 15) = 0: f(8,
16) = 0: f(8, 17) = 0: f(8, 18) = 0: f(8, 19) = 0: f(8, 20) = 0: f(8, 21) = 0: f(8, 22) = 0: f(8, 23) = 0: f(8, 24) = 0: f(8, 25) = 0: f(8, 26) = 46: f(8, 27) = 0: f(8, 28) = 0: f(8, 29) = 0: f(8,
30) = 0: f(8, 31) = 0: f(8, 32) = 0
f(9, 1) = 0: f(9, 2) = 0: f(9, 3) = 0: f(9, 4) = 0: f(9, 5) = 0: f(9, 6) = 0: f(9, 7) = 0: f(9, 8) = 0: f(9, 9) = 0: f(9, 10) = 0: f(9, 11) = 0: f(9, 12) = 0: f(9, 13) = 0: f(9, 14) = 0: f(9, 15) = 0: f(9,
16) = 0: f(9, 17) = 0: f(9, 18) = 0: f(9, 19) = 0: f(9, 20) = 0: f(9, 21) = 0: f(9, 22) = 0: f(9, 23) = 46: f(9, 24) = 0: f(9, 25) = 0: f(9, 26) = 0: f(9, 27) = 0: f(9, 28) = 0: f(9, 29) = 0: f(9,
30) = 0: f(9, 31) = 0: f(9, 32) = 0
f(10, 1) = 0: f(10, 2) = 0: f(10, 3) = 0: f(10, 4) = 0: f(10, 5) = 0: f(10, 6) = 0: f(10, 7) = 0: f(10, 8) = 0: f(10, 9) = 0: f(10, 10) = 0: f(10, 11) = 68: f(10, 12) = 0: f(10, 13) = 0: f(10, 14)
= 0: f(10, 15) = 0: f(10, 16) = 68: f(10, 17) = 0: f(10, 18) = 0: f(10, 19) = 0: f(10, 20) = 211: f(10, 21) = 0: f(10, 22) = 0: f(10, 23) = 0: f(10, 24) = 0: f(10, 25) = 0: f(10, 26) = 0: f(10,
27) = 65: f(10, 28) = 68: f(10, 29) = 74: f(10, 30) = 0: f(10, 31) = 0: f(10, 32) = 0
f(11, 1) = 0: f(11, 2) = 0: f(11, 3) = 0: f(11, 4) = 0: f(11, 5) = 0: f(11, 6) = 0: f(11, 7) = 0: f(11, 8) = 0: f(11, 9) = 0: f(11, 10) = 0: f(11, 11) = 0: f(11, 12) = 0: f(11, 13) = 0: f(11, 14) =
0: f(11, 15) = 0: f(11, 16) = 0: f(11, 17) = 0: f(11, 18) = 0: f(11, 19) = 0: f(11, 20) = 0: f(11, 21) = 0: f(11, 22) = 0: f(11, 23) = 0: f(11, 24) = 0: f(11, 25) = 0: f(11, 26) = 0: f(11, 27) =
0: f(11, 28) = 0: f(11, 29) = 0: f(11, 30) = 0: f(11, 31) = 0: f(11, 32) = 0
f(12, 1) = 0: f(12, 2) = 0: f(12, 3) = 0: f(12, 4) = 0: f(12, 5) = 0: f(12, 6) = 0: f(12, 7) = 0: f(12, 8) = 0: f(12, 9) = 0: f(12, 10) = 0: f(12, 11) = 0: f(12, 12) = 0: f(12, 13) = 0: f(12, 14) =
0: f(12, 15) = 0: f(12, 16) = 0: f(12, 17) = 0: f(12, 18) = 0: f(12, 19) = 0: f(12, 20) = 0: f(12, 21) = 0: f(12, 22) = 0: f(12, 23) = 0: f(12, 24) = 0: f(12, 25) = 0: f(12, 26) = 0: f(12, 27) =
0: f(12, 28) = 0: f(12, 29) = 0: f(12, 30) = 0: f(12, 31) = 0: f(12, 32) = 0
f(13, 1) = 0: f(13, 2) = 0: f(13, 3) = 0: f(13, 4) = 0: f(13, 5) = 0: f(13, 6) = 0: f(13, 7) = 0: f(13, 8) = 0: f(13, 9) = 0: f(13, 10) = 0: f(13, 11) = 0: f(13, 12) = 0: f(13, 13) = 0: f(13, 14) =
0: f(13, 15) = 0: f(13, 16) = 0: f(13, 17) = 0: f(13, 18) = 0: f(13, 19) = 0: f(13, 20) = 0: f(13, 21) = 0: f(13, 22) = 0: f(13, 23) = 0: f(13, 24) = 0: f(13, 25) = 0: f(13, 26) = 0: f(13, 27) =
0: f(13, 28) = 0: f(13, 29) = 0: f(13, 30) = 0: f(13, 31) = 0: f(13, 32) = 0
f(14, 1) = 0: f(14, 2) = 0: f(14, 3) = 0: f(14, 4) = 0: f(14, 5) = 0: f(14, 6) = 0: f(14, 7) = 0: f(14, 8) = 0: f(14, 9) = 0: f(14, 10) = 0: f(14, 11) = 0: f(14, 12) = 0: f(14, 13) = 0: f(14, 14) =
0: f(14, 15) = 0: f(14, 16) = 0: f(14, 17) = 0: f(14, 18) = 0: f(14, 19) = 0: f(14, 20) = 0: f(14, 21) = 0: f(14, 22) = 0: f(14, 23) = 0: f(14, 24) = 0: f(14, 25) = 0: f(14, 26) = 0: f(14, 27) =
0: f(14, 28) = 0: f(14, 29) = 0: f(14, 30) = 0: f(14, 31) = 0: f(14, 32) = 0
f(15, 1) = 0: f(15, 2) = 0: f(15, 3) = 0: f(15, 4) = 0: f(15, 5) = 0: f(15, 6) = 0: f(15, 7) = 0: f(15, 8) = 0: f(15, 9) = 0: f(15, 10) = 0: f(15, 11) = 0: f(15, 12) = 0: f(15, 13) = 0: f(15, 14) =
0: f(15, 15) = 0: f(15, 16) = 65: f(15, 17) = 0: f(15, 18) = 0: f(15, 19) = 0: f(15, 20) = 0: f(15, 21) = 0: f(15, 22) = 0: f(15, 23) = 0: f(15, 24) = 0: f(15, 25) = 0: f(15, 26) = 0: f(15, 27)
= 0: f(15, 28) = 0: f(15, 29) = 0: f(15, 30) = 0: f(15, 31) = 0: f(15, 32) = 0
f(16, 1) = 0: f(16, 2) = 0: f(16, 3) = 0: f(16, 4) = 0: f(16, 5) = 0: f(16, 6) = 0: f(16, 7) = 0: f(16, 8) = 0: f(16, 9) = 0: f(16, 10) = 0: f(16, 11) = 0: f(16, 12) = 0: f(16, 13) = 0: f(16, 14) =
0: f(16, 15) = 0: f(16, 16) = 0: f(16, 17) = 0: f(16, 18) = 0: f(16, 19) = 0: f(16, 20) = 0: f(16, 21) = 56: f(16, 22) = 56: f(16, 23) = 0: f(16, 24) = 0: f(16, 25) = 0: f(16, 26) = 0: f(16, 27)
= 0: f(16, 28) = 0: f(16, 29) = 0: f(16, 30) = 0: f(16, 31) = 40: f(16, 32) = 0
f(17, 1) = 0: f(17, 2) = 0: f(17, 3) = 0: f(17, 4) = 0: f(17, 5) = 0: f(17, 6) = 0: f(17, 7) = 0: f(17, 8) = 0: f(17, 9) = 0: f(17, 10) = 0: f(17, 11) = 0: f(17, 12) = 0: f(17, 13) = 0: f(17, 14) =
0: f(17, 15) = 0: f(17, 16) = 0: f(17, 17) = 0: f(17, 18) = 0: f(17, 19) = 0: f(17, 20) = 0: f(17, 21) = 52: f(17, 22) = 0: f(17, 23) = 0: f(17, 24) = 0: f(17, 25) = 0: f(17, 26) = 0: f(17, 27)
= 0: f(17, 28) = 0: f(17, 29) = 0: f(17, 30) = 0: f(17, 31) = 0: f(17, 32) = 0
59
f(18, 1) = 0: f(18, 2) = 0: f(18, 3) = 0: f(18, 4) = 0: f(18, 5) = 0: f(18, 6) = 0: f(18, 7) = 0: f(18, 8) = 0: f(18, 9) = 0: f(18, 10) = 0: f(18, 11) = 0: f(18, 12) = 0: f(18, 13) = 0: f(18, 14) =
0: f(18, 15) = 0: f(18, 16) = 0: f(18, 17) = 0: f(18, 18) = 0: f(18, 19) = 0: f(18, 20) = 0: f(18, 21) = 40: f(18, 22) = 0: f(18, 23) = 0: f(18, 24) = 0: f(18, 25) = 0: f(18, 26) = 0: f(18, 27)
= 0: f(18, 28) = 0: f(18, 29) = 0: f(18, 30) = 0: f(18, 31) = 0: f(18, 32) = 0
f(19, 1) = 0: f(19, 2) = 0: f(19, 3) = 0: f(19, 4) = 0: f(19, 5) = 0: f(19, 6) = 0: f(19, 7) = 0: f(19, 8) = 0: f(19, 9) = 0: f(19, 10) = 0: f(19, 11) = 0: f(19, 12) = 0: f(19, 13) = 0: f(19, 14) =
0: f(19, 15) = 0: f(19, 16) = 0: f(19, 17) = 0: f(19, 18) = 0: f(19, 19) = 0: f(19, 20) = 0: f(19, 21) = 0: f(19, 22) = 46: f(19, 23) = 0: f(19, 24) = 0: f(19, 25) = 0: f(19, 26) = 0: f(19, 27)
= 0: f(19, 28) = 0: f(19, 29) = 0: f(19, 30) = 0: f(19, 31) = 0: f(19, 32) = 0
f(20, 1) = 0: f(20, 2) = 0: f(20, 3) = 0: f(20, 4) = 0: f(20, 5) = 0: f(20, 6) = 0: f(20, 7) = 0: f(20, 8) = 0: f(20, 9) = 0: f(20, 10) = 0: f(20, 11) = 0: f(20, 12) = 0: f(20, 13) = 0: f(20, 14) =
0: f(20, 15) = 0: f(20, 16) = 0: f(20, 17) = 0: f(20, 18) = 0: f(20, 19) = 0: f(20, 20) = 0: f(20, 21) = 0: f(20, 22) = 0: f(20, 23) = 0: f(20, 24) = 0: f(20, 25) = 0: f(20, 26) = 0: f(20, 27) =
0: f(20, 28) = 0: f(20, 29) = 0: f(20, 30) = 83: f(20, 31) = 0: f(20, 32) = 0
f(21, 1) = 0: f(21, 2) = 0: f(21, 3) = 0: f(21, 4) = 0: f(21, 5) = 0: f(21, 6) = 0: f(21, 7) = 0: f(21, 8) = 0: f(21, 9) = 0: f(21, 10) = 0: f(21, 11) = 0: f(21, 12) = 0: f(21, 13) = 0: f(21, 14) =
0: f(21, 15) = 0: f(21, 16) = 0: f(21, 17) = 0: f(21, 18) = 0: f(21, 19) = 0: f(21, 20) = 0: f(21, 21) = 0: f(21, 22) = 0: f(21, 23) = 0: f(21, 24) = 0: f(21, 25) = 0: f(21, 26) = 0: f(21, 27) =
0: f(21, 28) = 0: f(21, 29) = 0: f(21, 30) = 0: f(21, 31) = 0: f(21, 32) = 0
f(22, 1) = 0: f(22, 2) = 0: f(22, 3) = 0: f(22, 4) = 0: f(22, 5) = 0: f(22, 6) = 0: f(22, 7) = 0: f(22, 8) = 0: f(22, 9) = 0: f(22, 10) = 0: f(22, 11) = 0: f(22, 12) = 0: f(22, 13) = 0: f(22, 14) =
0: f(22, 15) = 0: f(22, 16) = 0: f(22, 17) = 0: f(22, 18) = 0: f(22, 19) = 0: f(22, 20) = 0: f(22, 21) = 0: f(22, 22) = 0: f(22, 23) = 0: f(22, 24) = 0: f(22, 25) = 0: f(22, 26) = 0: f(22, 27) =
0: f(22, 28) = 0: f(22, 29) = 0: f(22, 30) = 0: f(22, 31) = 0: f(22, 32) = 0
f(23, 1) = 0: f(23, 2) = 0: f(23, 3) = 0: f(23, 4) = 0: f(23, 5) = 0: f(23, 6) = 0: f(23, 7) = 0: f(23, 8) = 0: f(23, 9) = 0: f(23, 10) = 0: f(23, 11) = 0: f(23, 12) = 0: f(23, 13) = 0: f(23, 14) =
0: f(23, 15) = 0: f(23, 16) = 0: f(23, 17) = 0: f(23, 18) = 0: f(23, 19) = 0: f(23, 20) = 0: f(23, 21) = 0: f(23, 22) = 0: f(23, 23) = 0: f(23, 24) = 0: f(23, 25) = 94: f(23, 26) = 0: f(23, 27)
= 0: f(23, 28) = 0: f(23, 29) = 0: f(23, 30) = 0: f(23, 31) = 0: f(23, 32) = 0
f(24, 1) = 0: f(24, 2) = 0: f(24, 3) = 0: f(24, 4) = 0: f(24, 5) = 0: f(24, 6) = 0: f(24, 7) = 0: f(24, 8) = 0: f(24, 9) = 0: f(24, 10) = 0: f(24, 11) = 0: f(24, 12) = 0: f(24, 13) = 0: f(24, 14) =
0: f(24, 15) = 0: f(24, 16) = 0: f(24, 17) = 0: f(24, 18) = 0: f(24, 19) = 0: f(24, 20) = 0: f(24, 21) = 0: f(24, 22) = 0: f(24, 23) = 0: f(24, 24) = 0: f(24, 25) = 0: f(24, 26) = 0: f(24, 27) =
0: f(24, 28) = 0: f(24, 29) = 0: f(24, 30) = 23: f(24, 31) = 0: f(24, 32) = 0
f(25, 1) = 0: f(25, 2) = 0: f(25, 3) = 0: f(25, 4) = 0: f(25, 5) = 0: f(25, 6) = 0: f(25, 7) = 0: f(25, 8) = 0: f(25, 9) = 0: f(25, 10) = 0: f(25, 11) = 0: f(25, 12) = 0: f(25, 13) = 0: f(25, 14) =
0: f(25, 15) = 0: f(25, 16) = 0: f(25, 17) = 0: f(25, 18) = 0: f(25, 19) = 0: f(25, 20) = 0: f(25, 21) = 0: f(25, 22) = 0: f(25, 23) = 0: f(25, 24) = 0: f(25, 25) = 0: f(25, 26) = 0: f(25, 27) =
0: f(25, 28) = 0: f(25, 29) = 0: f(25, 30) = 0: f(25, 31) = 0: f(25, 32) = 50
f(26, 1) = 0: f(26, 2) = 0: f(26, 3) = 0: f(26, 4) = 0: f(26, 5) = 0: f(26, 6) = 0: f(26, 7) = 0: f(26, 8) = 0: f(26, 9) = 0: f(26, 10) = 0: f(26, 11) = 0: f(26, 12) = 0: f(26, 13) = 0: f(26, 14) =
0: f(26, 15) = 0: f(26, 16) = 0: f(26, 17) = 0: f(26, 18) = 0: f(26, 19) = 0: f(26, 20) = 0: f(26, 21) = 0: f(26, 22) = 0: f(26, 23) = 0: f(26, 24) = 0: f(26, 25) = 0: f(26, 26) = 0: f(26, 27) =
0: f(26, 28) = 0: f(26, 29) = 0: f(26, 30) = 0: f(26, 31) = 0: f(26, 32) = 0
f(27, 1) = 0: f(27, 2) = 0: f(27, 3) = 0: f(27, 4) = 0: f(27, 5) = 0: f(27, 6) = 0: f(27, 7) = 0: f(27, 8) = 0: f(27, 9) = 0: f(27, 10) = 0: f(27, 11) = 0: f(27, 12) = 0: f(27, 13) = 0: f(27, 14) =
0: f(27, 15) = 0: f(27, 16) = 0: f(27, 17) = 0: f(27, 18) = 0: f(27, 19) = 0: f(27, 20) = 0: f(27, 21) = 0: f(27, 22) = 0: f(27, 23) = 0: f(27, 24) = 0: f(27, 25) = 0: f(27, 26) = 0: f(27, 27) =
0: f(27, 28) = 0: f(27, 29) = 0: f(27, 30) = 0: f(27, 31) = 0: f(27, 32) = 0
60
f(28, 1) = 0: f(28, 2) = 0: f(28, 3) = 0: f(28, 4) = 0: f(28, 5) = 0: f(28, 6) = 0: f(28, 7) = 0: f(28, 8) = 0: f(28, 9) = 0: f(28, 10) = 0: f(28, 11) = 0: f(28, 12) = 0: f(28, 13) = 0: f(28, 14) =
0: f(28, 15) = 0: f(28, 16) = 0: f(28, 17) = 0: f(28, 18) = 0: f(28, 19) = 0: f(28, 20) = 0: f(28, 21) = 0: f(28, 22) = 0: f(28, 23) = 0: f(28, 24) = 0: f(28, 25) = 0: f(28, 26) = 0: f(28, 27) =
0: f(28, 28) = 0: f(28, 29) = 0: f(28, 30) = 0: f(28, 31) = 0: f(28, 32) = 0
f(29, 1) = 0: f(29, 2) = 0: f(29, 3) = 0: f(29, 4) = 0: f(29, 5) = 0: f(29, 6) = 0: f(29, 7) = 0: f(29, 8) = 0: f(29, 9) = 0: f(29, 10) = 0: f(29, 11) = 0: f(29, 12) = 0: f(29, 13) = 0: f(29, 14) =
0: f(29, 15) = 0: f(29, 16) = 0: f(29, 17) = 0: f(29, 18) = 0: f(29, 19) = 0: f(29, 20) = 0: f(29, 21) = 0: f(29, 22) = 0: f(29, 23) = 0: f(29, 24) = 0: f(29, 25) = 0: f(29, 26) = 0: f(29, 27) =
0: f(29, 28) = 0: f(29, 29) = 0: f(29, 30) = 0: f(29, 31) = 0: f(29, 32) = 0
f(30, 1) = 0: f(30, 2) = 0: f(30, 3) = 0: f(30, 4) = 0: f(30, 5) = 0: f(30, 6) = 0: f(30, 7) = 0: f(30, 8) = 0: f(30, 9) = 0: f(30, 10) = 0: f(30, 11) = 0: f(30, 12) = 0: f(30, 13) = 0: f(30, 14) =
0: f(30, 15) = 0: f(30, 16) = 0: f(30, 17) = 0: f(30, 18) = 0: f(30, 19) = 0: f(30, 20) = 0: f(30, 21) = 0: f(30, 22) = 0: f(30, 23) = 0: f(30, 24) = 0: f(30, 25) = 0: f(30, 26) = 0: f(30, 27) =
0: f(30, 28) = 0: f(30, 29) = 0: f(30, 30) = 0: f(30, 31) = 0: f(30, 32) = 20
f(31, 1) = 0: f(31, 2) = 0: f(31, 3) = 0: f(31, 4) = 0: f(31, 5) = 0: f(31, 6) = 0: f(31, 7) = 0: f(31, 8) = 0: f(31, 9) = 0: f(31, 10) = 0: f(31, 11) = 0: f(31, 12) = 0: f(31, 13) = 0: f(31, 14) =
0: f(31, 15) = 0: f(31, 16) = 0: f(31, 17) = 0: f(31, 18) = 0: f(31, 19) = 0: f(31, 20) = 0: f(31, 21) = 0: f(31, 22) = 0: f(31, 23) = 0: f(31, 24) = 0: f(31, 25) = 0: f(31, 26) = 0: f(31, 27) =
0: f(31, 28) = 0: f(31, 29) = 0: f(31, 30) = 0: f(31, 31) = 0: f(31, 32) = 0
f(32, 1) = 0: f(32, 2) = 0: f(32, 3) = 0: f(32, 4) = 0: f(32, 5) = 0: f(32, 6) = 0: f(32, 7) = 0: f(32, 8) = 0: f(32, 9) = 0: f(32, 10) = 0: f(32, 11) = 0: f(32, 12) = 0: f(32, 13) = 0: f(32, 14) =
0: f(32, 15) = 0: f(32, 16) = 0: f(32, 17) = 0: f(32, 18) = 0: f(32, 19) = 0: f(32, 20) = 0: f(32, 21) = 0: f(32, 22) = 0: f(32, 23) = 0: f(32, 24) = 0: f(32, 25) = 0: f(32, 26) = 0: f(32, 27) =
0: f(32, 28) = 0: f(32, 29) = 0: f(32, 30) = 0: f(32, 31) = 0: f(32, 32) = 0
co(1, 1) = 0: co(1, 2) = 1: co(1, 3) = 1: co(1, 4) = 1: co(1, 5) = 1: co(1, 6) = 1: co(1, 7) = 1: co(1, 8) = 1: co(1, 9) = 1: co(1, 10) = 1: co(1, 11) = 1: co(1, 12) = 1: co(1, 13) = 1:
co(1, 14) = 1: co(1, 15) = 1: co(1, 16) = 1: co(1, 17) = 1: co(1, 18) = 1: co(1, 19) = 1: co(1, 20) = 1: co(1, 21) = 1: co(1, 22) = 1: co(1, 23) = 1: co(1, 24) = 1: co(1, 25) = 1: co(1,
26) = 1: co(1, 27) = 1: co(1, 28) = 1: co(1, 29) = 1: co(1, 30) = 1: co(1, 31) = 1: co(1, 32) = 1
co(2, 1) = 1: co(2, 2) = 0: co(2, 3) = 1: co(2, 4) = 1: co(2, 5) = 1: co(2, 6) = 1: co(2, 7) = 1: co(2, 8) = 1: co(2, 9) = 1: co(2, 10) = 1: co(2, 11) = 1: co(2, 12) = 1: co(2, 13) = 1:
co(2, 14) = 1: co(2, 15) = 1: co(2, 16) = 1: co(2, 17) = 1: co(2, 18) = 1: co(2, 19) = 1: co(2, 20) = 1: co(2, 21) = 1: co(2, 22) = 1: co(2, 23) = 1: co(2, 24) = 1: co(2, 25) = 1: co(2,
26) = 1: co(2, 27) = 1: co(2, 28) = 1: co(2, 29) = 1: co(2, 30) = 1: co(2, 31) = 1: co(2, 32) = 1
co(3, 1) = 1: co(3, 2) = 1: co(3, 3) = 0: co(3, 4) = 1: co(3, 5) = 1: co(3, 6) = 1: co(3, 7) = 1: co(3, 8) = 1: co(3, 9) = 1: co(3, 10) = 1: co(3, 11) = 1: co(3, 12) = 1: co(3, 13) = 1:
co(3, 14) = 1: co(3, 15) = 1: co(3, 16) = 1: co(3, 17) = 1: co(3, 18) = 1: co(3, 19) = 1: co(3, 20) = 1: co(3, 21) = 1: co(3, 22) = 1: co(3, 23) = 1: co(3, 24) = 1: co(3, 25) = 1: co(3,
26) = 1: co(3, 27) = 1: co(3, 28) = 1: co(3, 29) = 1: co(3, 30) = 1: co(3, 31) = 1: co(3, 32) = 1
co(4, 1) = 1: co(4, 2) = 1: co(4, 3) = 1: co(4, 4) = 0: co(4, 5) = 1: co(4, 6) = 1: co(4, 7) = 1: co(4, 8) = 1: co(4, 9) = 1: co(4, 10) = 1: co(4, 11) = 1: co(4, 12) = 1: co(4, 13) = 1:
co(4, 14) = 1: co(4, 15) = 1: co(4, 16) = 1: co(4, 17) = 1: co(4, 18) = 1: co(4, 19) = 1: co(4, 20) = 1: co(4, 21) = 1: co(4, 22) = 1: co(4, 23) = 1: co(4, 24) = 1: co(4, 25) = 1: co(4,
26) = 1: co(4, 27) = 1: co(4, 28) = 1: co(4, 29) = 1: co(4, 30) = 1: co(4, 31) = 1: co(4, 32) = 1
co(5, 1) = 1: co(5, 2) = 1: co(5, 3) = 1: co(5, 4) = 1: co(5, 5) = 0: co(5, 6) = 1: co(5, 7) = 1: co(5, 8) = 1: co(5, 9) = 1: co(5, 10) = 1: co(5, 11) = 1: co(5, 12) = 1: co(5, 13) = 1:
co(5, 14) = 1: co(5, 15) = 1: co(5, 16) = 1: co(5, 17) = 1: co(5, 18) = 1: co(5, 19) = 1: co(5, 20) = 1: co(5, 21) = 1: co(5, 22) = 1: co(5, 23) = 1: co(5, 24) = 1: co(5, 25) = 1: co(5,
26) = 1: co(5, 27) = 1: co(5, 28) = 1: co(5, 29) = 1: co(5, 30) = 1: co(5, 31) = 1: co(5, 32) = 1
61
co(6, 1) = 1: co(6, 2) = 1: co(6, 3) = 1: co(6, 4) = 1: co(6, 5) = 1: co(6, 6) = 0: co(6, 7) = 1: co(6, 8) = 1: co(6, 9) = 1: co(6, 10) = 1: co(6, 11) = 1: co(6, 12) = 1: co(6, 13) = 1:
co(6, 14) = 1: co(6, 15) = 1: co(6, 16) = 1: co(6, 17) = 1: co(6, 18) = 1: co(6, 19) = 1: co(6, 20) = 1: co(6, 21) = 1: co(6, 22) = 1: co(6, 23) = 1: co(6, 24) = 1: co(6, 25) = 1: co(6,
26) = 1: co(6, 27) = 1: co(6, 28) = 1: co(6, 29) = 1: co(6, 30) = 1: co(6, 31) = 1: co(6, 32) = 1
co(7, 1) = 1: co(7, 2) = 1: co(7, 3) = 1: co(7, 4) = 1: co(7, 5) = 1: co(7, 6) = 1: co(7, 7) = 0: co(7, 8) = 1: co(7, 9) = 1: co(7, 10) = 1: co(7, 11) = 1: co(7, 12) = 1: co(7, 13) = 1:
co(7, 14) = 1: co(7, 15) = 1: co(7, 16) = 1: co(7, 17) = 1: co(7, 18) = 1: co(7, 19) = 1: co(7, 20) = 1: co(7, 21) = 1: co(7, 22) = 1: co(7, 23) = 1: co(7, 24) = 1: co(7, 25) = 1: co(7,
26) = 1: co(7, 27) = 1: co(7, 28) = 1: co(7, 29) = 1: co(7, 30) = 1: co(7, 31) = 1: co(7, 32) = 1
co(8, 1) = 1: co(8, 2) = 1: co(8, 3) = 1: co(8, 4) = 1: co(8, 5) = 1: co(8, 6) = 1: co(8, 7) = 1: co(8, 8) = 0: co(8, 9) = 1: co(8, 10) = 1: co(8, 11) = 1: co(8, 12) = 1: co(8, 13) = 1:
co(8, 14) = 1: co(8, 15) = 1: co(8, 16) = 1: co(8, 17) = 1: co(8, 18) = 1: co(8, 19) = 1: co(8, 20) = 1: co(8, 21) = 1: co(8, 22) = 1: co(8, 23) = 1: co(8, 24) = 1: co(8, 25) = 1: co(8,
26) = 1: co(8, 27) = 1: co(8, 28) = 1: co(8, 29) = 1: co(8, 30) = 1: co(8, 31) = 1: co(8, 32) = 1
co(9, 1) = 1: co(9, 2) = 1: co(9, 3) = 1: co(9, 4) = 1: co(9, 5) = 1: co(9, 6) = 1: co(9, 7) = 1: co(9, 8) = 1: co(9, 9) = 0: co(9, 10) = 1: co(9, 11) = 1: co(9, 12) = 1: co(9, 13) = 1:
co(9, 14) = 1: co(9, 15) = 1: co(9, 16) = 1: co(9, 17) = 1: co(9, 18) = 1: co(9, 19) = 1: co(9, 20) = 1: co(9, 21) = 1: co(9, 22) = 1: co(9, 23) = 1: co(9, 24) = 1: co(9, 25) = 1: co(9,
26) = 1: co(9, 27) = 1: co(9, 28) = 1: co(9, 29) = 1: co(9, 30) = 1: co(9, 31) = 1: co(9, 32) = 1
co(10, 1) = 1: co(10, 2) = 1: co(10, 3) = 1: co(10, 4) = 1: co(10, 5) = 1: co(10, 6) = 1: co(10, 7) = 1: co(10, 8) = 1: co(10, 9) = 1: co(10, 10) = 0: co(10, 11) = 1: co(10, 12) = 1:
co(10, 13) = 1: co(10, 14) = 1: co(10, 15) = 1: co(10, 16) = 1: co(10, 17) = 1: co(10, 18) = 1: co(10, 19) = 1: co(10, 20) = 1: co(10, 21) = 1: co(10, 22) = 1: co(10, 23) = 1: co(10,
24) = 1: co(10, 25) = 1: co(10, 26) = 1: co(10, 27) = 1: co(10, 28) = 1: co(10, 29) = 1: co(10, 30) = 1: co(10, 31) = 1: co(10, 32) = 1
co(11, 1) = 1: co(11, 2) = 1: co(11, 3) = 1: co(11, 4) = 1: co(11, 5) = 1: co(11, 6) = 1: co(11, 7) = 1: co(11, 8) = 1: co(11, 9) = 1: co(11, 10) = 1: co(11, 11) = 0: co(11, 12) = 1:
co(11, 13) = 1: co(11, 14) = 1: co(11, 15) = 1: co(11, 16) = 1: co(11, 17) = 1: co(11, 18) = 1: co(11, 19) = 1: co(11, 20) = 1: co(11, 21) = 1: co(11, 22) = 1: co(11, 23) = 1: co(11,
24) = 1: co(11, 25) = 1: co(11, 26) = 1: co(11, 27) = 1: co(11, 28) = 1: co(11, 29) = 1: co(11, 30) = 1: co(11, 31) = 1: co(11, 32) = 1
co(12, 1) = 1: co(12, 2) = 1: co(12, 3) = 1: co(12, 4) = 1: co(12, 5) = 1: co(12, 6) = 1: co(12, 7) = 1: co(12, 8) = 1: co(12, 9) = 1: co(12, 10) = 1: co(12, 11) = 1: co(12, 12) = 0:
co(12, 13) = 1: co(12, 14) = 1: co(12, 15) = 1: co(12, 16) = 1: co(12, 17) = 1: co(12, 18) = 1: co(12, 19) = 1: co(12, 20) = 1: co(12, 21) = 1: co(12, 22) = 1: co(12, 23) = 1: co(12,
24) = 1: co(12, 25) = 1: co(12, 26) = 1: co(12, 27) = 1: co(12, 28) = 1: co(12, 29) = 1: co(12, 30) = 1: co(12, 31) = 1: co(12, 32) = 1
co(13, 1) = 1: co(13, 2) = 1: co(13, 3) = 1: co(13, 4) = 1: co(13, 5) = 1: co(13, 6) = 1: co(13, 7) = 1: co(13, 8) = 1: co(13, 9) = 1: co(13, 10) = 1: co(13, 11) = 1: co(13, 12) = 1:
co(13, 13) = 0: co(13, 14) = 1: co(13, 15) = 1: co(13, 16) = 1: co(13, 17) = 1: co(13, 18) = 1: co(13, 19) = 1: co(13, 20) = 1: co(13, 21) = 1: co(13, 22) = 1: co(13, 23) = 1: co(13,
24) = 1: co(13, 25) = 1: co(13, 26) = 1: co(13, 27) = 1: co(13, 28) = 1: co(13, 29) = 1: co(13, 30) = 1: co(13, 31) = 1: co(13, 32) = 1
co(14, 1) = 1: co(14, 2) = 1: co(14, 3) = 1: co(14, 4) = 1: co(14, 5) = 1: co(14, 6) = 1: co(14, 7) = 1: co(14, 8) = 1: co(14, 9) = 1: co(14, 10) = 1: co(14, 11) = 1: co(14, 12) = 1:
co(14, 13) = 1: co(14, 14) = 0: co(14, 15) = 1: co(14, 16) = 1: co(14, 17) = 1: co(14, 18) = 1: co(14, 19) = 1: co(14, 20) = 1: co(14, 21) = 1: co(14, 22) = 1: co(14, 23) = 1: co(14,
24) = 1: co(14, 25) = 1: co(14, 26) = 1: co(14, 27) = 1: co(14, 28) = 1: co(14, 29) = 1: co(14, 30) = 1: co(14, 31) = 1: co(14, 32) = 1
co(15, 1) = 1: co(15, 2) = 1: co(15, 3) = 1: co(15, 4) = 1: co(15, 5) = 1: co(15, 6) = 1: co(15, 7) = 1: co(15, 8) = 1: co(15, 9) = 1: co(15, 10) = 1: co(15, 11) = 1: co(15, 12) = 1:
co(15, 13) = 1: co(15, 14) = 1: co(15, 15) = 0: co(15, 16) = 1: co(15, 17) = 1: co(15, 18) = 1: co(15, 19) = 1: co(15, 20) = 1: co(15, 21) = 1: co(15, 22) = 1: co(15, 23) = 1: co(15,
24) = 1: co(15, 25) = 1: co(15, 26) = 1: co(15, 27) = 1: co(15, 28) = 1: co(15, 29) = 1: co(15, 30) = 1: co(15, 31) = 1: co(15, 32) = 1
62
co(16, 1) = 1: co(16, 2) = 1: co(16, 3) = 1: co(16, 4) = 1: co(16, 5) = 1: co(16, 6) = 1: co(16, 7) = 1: co(16, 8) = 1: co(16, 9) = 1: co(16, 10) = 1: co(16, 11) = 1: co(16, 12) = 1:
co(16, 13) = 1: co(16, 14) = 1: co(16, 15) = 1: co(16, 16) = 0: co(16, 17) = 1: co(16, 18) = 1: co(16, 19) = 1: co(16, 20) = 1: co(16, 21) = 1: co(16, 22) = 1: co(16, 23) = 1: co(16,
24) = 1: co(16, 25) = 1: co(16, 26) = 1: co(16, 27) = 1: co(16, 28) = 1: co(16, 29) = 1: co(16, 30) = 1: co(16, 31) = 1: co(16, 32) = 1
co(17, 1) = 1: co(17, 2) = 1: co(17, 3) = 1: co(17, 4) = 1: co(17, 5) = 1: co(17, 6) = 1: co(17, 7) = 1: co(17, 8) = 1: co(17, 9) = 1: co(17, 10) = 1: co(17, 11) = 1: co(17, 12) = 1:
co(17, 13) = 1: co(17, 14) = 1: co(17, 15) = 1: co(17, 16) = 1: co(17, 17) = 0: co(17, 18) = 1: co(17, 19) = 1: co(17, 20) = 1: co(17, 21) = 1: co(17, 22) = 1: co(17, 23) = 1: co(17,
24) = 1: co(17, 25) = 1: co(17, 26) = 1: co(17, 27) = 1: co(17, 28) = 1: co(17, 29) = 1: co(17, 30) = 1: co(17, 31) = 1: co(17, 32) = 1
co(18, 1) = 1: co(18, 2) = 1: co(18, 3) = 1: co(18, 4) = 1: co(18, 5) = 1: co(18, 6) = 1: co(18, 7) = 1: co(18, 8) = 1: co(18, 9) = 1: co(18, 10) = 1: co(18, 11) = 1: co(18, 12) = 1:
co(18, 13) = 1: co(18, 14) = 1: co(18, 15) = 1: co(18, 16) = 1: co(18, 17) = 1: co(18, 18) = 0: co(18, 19) = 1: co(18, 20) = 1: co(18, 21) = 1: co(18, 22) = 1: co(18, 23) = 1: co(18,
24) = 1: co(18, 25) = 1: co(18, 26) = 1: co(18, 27) = 1: co(18, 28) = 1: co(18, 29) = 1: co(18, 30) = 1: co(18, 31) = 1: co(18, 32) = 1
co(19, 1) = 1: co(19, 2) = 1: co(19, 3) = 1: co(19, 4) = 1: co(19, 5) = 1: co(19, 6) = 1: co(19, 7) = 1: co(19, 8) = 1: co(19, 9) = 1: co(19, 10) = 1: co(19, 11) = 1: co(19, 12) = 1:
co(19, 13) = 1: co(19, 14) = 1: co(19, 15) = 1: co(19, 16) = 1: co(19, 17) = 1: co(19, 18) = 1: co(19, 19) = 0: co(19, 20) = 1: co(19, 21) = 1: co(19, 22) = 1: co(19, 23) = 1: co(19,
24) = 1: co(19, 25) = 1: co(19, 26) = 1: co(19, 27) = 1: co(19, 28) = 1: co(19, 29) = 1: co(19, 30) = 1: co(19, 31) = 1: co(19, 32) = 1
co(20, 1) = 1: co(20, 2) = 1: co(20, 3) = 1: co(20, 4) = 1: co(20, 5) = 1: co(20, 6) = 1: co(20, 7) = 1: co(20, 8) = 1: co(20, 9) = 1: co(20, 10) = 1: co(20, 11) = 1: co(20, 12) = 1:
co(20, 13) = 1: co(20, 14) = 1: co(20, 15) = 1: co(20, 16) = 1: co(20, 17) = 1: co(20, 18) = 1: co(20, 19) = 1: co(20, 20) = 0: co(20, 21) = 1: co(20, 22) = 1: co(20, 23) = 1: co(20,
24) = 1: co(20, 25) = 1: co(20, 26) = 1: co(20, 27) = 1: co(20, 28) = 1: co(20, 29) = 1: co(20, 30) = 1: co(20, 31) = 1: co(20, 32) = 1
co(21, 1) = 1: co(21, 2) = 1: co(21, 3) = 1: co(21, 4) = 1: co(21, 5) = 1: co(21, 6) = 1: co(21, 7) = 1: co(21, 8) = 1: co(21, 9) = 1: co(21, 10) = 1: co(21, 11) = 1: co(21, 12) = 1:
co(21, 13) = 1: co(21, 14) = 1: co(21, 15) = 1: co(21, 16) = 1: co(21, 17) = 1: co(21, 18) = 1: co(21, 19) = 1: co(21, 20) = 1: co(21, 21) = 0: co(21, 22) = 1: co(21, 23) = 1: co(21,
24) = 1: co(21, 25) = 1: co(21, 26) = 1: co(21, 27) = 1: co(21, 28) = 1: co(21, 29) = 1: co(21, 30) = 1: co(21, 31) = 1: co(21, 32) = 1
co(22, 1) = 1: co(22, 2) = 1: co(22, 3) = 1: co(22, 4) = 1: co(22, 5) = 1: co(22, 6) = 1: co(22, 7) = 1: co(22, 8) = 1: co(22, 9) = 1: co(22, 10) = 1: co(22, 11) = 1: co(22, 12) = 1:
co(22, 13) = 1: co(22, 14) = 1: co(22, 15) = 1: co(22, 16) = 1: co(22, 17) = 1: co(22, 18) = 1: co(22, 19) = 1: co(22, 20) = 1: co(22, 21) = 1: co(22, 22) = 0: co(22, 23) = 1: co(22,
24) = 1: co(22, 25) = 1: co(22, 26) = 1: co(22, 27) = 1: co(22, 28) = 1: co(22, 29) = 1: co(22, 30) = 1: co(22, 31) = 1: co(22, 32) = 1
co(23, 1) = 1: co(23, 2) = 1: co(23, 3) = 1: co(23, 4) = 1: co(23, 5) = 1: co(23, 6) = 1: co(23, 7) = 1: co(23, 8) = 1: co(23, 9) = 1: co(23, 10) = 1: co(23, 11) = 1: co(23, 12) = 1:
co(23, 13) = 1: co(23, 14) = 1: co(23, 15) = 1: co(23, 16) = 1: co(23, 17) = 1: co(23, 18) = 1: co(23, 19) = 1: co(23, 20) = 1: co(23, 21) = 1: co(23, 22) = 1: co(23, 23) = 0: co(23,
24) = 1: co(23, 25) = 1: co(23, 26) = 1: co(23, 27) = 1: co(23, 28) = 1: co(23, 29) = 1: co(23, 30) = 1: co(23, 31) = 1: co(23, 32) = 1
co(24, 1) = 1: co(24, 2) = 1: co(24, 3) = 1: co(24, 4) = 1: co(24, 5) = 1: co(24, 6) = 1: co(24, 7) = 1: co(24, 8) = 1: co(24, 9) = 1: co(24, 10) = 1: co(24, 11) = 1: co(24, 12) = 1:
co(24, 13) = 1: co(24, 14) = 1: co(24, 15) = 1: co(24, 16) = 1: co(24, 17) = 1: co(24, 18) = 1: co(24, 19) = 1: co(24, 20) = 1: co(24, 21) = 1: co(24, 22) = 1: co(24, 23) = 1: co(24,
24) = 0: co(24, 25) = 1: co(24, 26) = 1: co(24, 27) = 1: co(24, 28) = 1: co(24, 29) = 1: co(24, 30) = 1: co(24, 31) = 1: co(24, 32) = 1
co(25, 1) = 1: co(25, 2) = 1: co(25, 3) = 1: co(25, 4) = 1: co(25, 5) = 1: co(25, 6) = 1: co(25, 7) = 1: co(25, 8) = 1: co(25, 9) = 1: co(25, 10) = 1: co(25, 11) = 1: co(25, 12) = 1:
co(25, 13) = 1: co(25, 14) = 1: co(25, 15) = 1: co(25, 16) = 1: co(25, 17) = 1: co(25, 18) = 1: co(25, 19) = 1: co(25, 20) = 1: co(25, 21) = 1: co(25, 22) = 1: co(25, 23) = 1: co(25,
24) = 1: co(25, 25) = 0: co(25, 26) = 1: co(25, 27) = 1: co(25, 28) = 1: co(25, 29) = 1: co(25, 30) = 1: co(25, 31) = 1: co(25, 32) = 1
63
co(26, 1) = 1: co(26, 2) = 1: co(26, 3) = 1: co(26, 4) = 1: co(26, 5) = 1: co(26, 6) = 1: co(26, 7) = 1: co(26, 8) = 1: co(26, 9) = 1: co(26, 10) = 1: co(26, 11) = 1: co(26, 12) = 1:
co(26, 13) = 1: co(26, 14) = 1: co(26, 15) = 1: co(26, 16) = 1: co(26, 17) = 1: co(26, 18) = 1: co(26, 19) = 1: co(26, 20) = 1: co(26, 21) = 1: co(26, 22) = 1: co(26, 23) = 1: co(26,
24) = 1: co(26, 25) = 1: co(26, 26) = 0: co(26, 27) = 1: co(26, 28) = 1: co(26, 29) = 1: co(26, 30) = 1: co(26, 31) = 1: co(26, 32) = 1
co(27, 1) = 1: co(27, 2) = 1: co(27, 3) = 1: co(27, 4) = 1: co(27, 5) = 1: co(27, 6) = 1: co(27, 7) = 1: co(27, 8) = 1: co(27, 9) = 1: co(27, 10) = 1: co(27, 11) = 1: co(27, 12) = 1:
co(27, 13) = 1: co(27, 14) = 1: co(27, 15) = 1: co(27, 16) = 1: co(27, 17) = 1: co(27, 18) = 1: co(27, 19) = 1: co(27, 20) = 1: co(27, 21) = 1: co(27, 22) = 1: co(27, 23) = 1: co(27,
24) = 1: co(27, 25) = 1: co(27, 26) = 1: co(27, 27) = 0: co(27, 28) = 1: co(27, 29) = 1: co(27, 30) = 1: co(27, 31) = 1: co(27, 32) = 1
co(28, 1) = 1: co(28, 2) = 1: co(28, 3) = 1: co(28, 4) = 1: co(28, 5) = 1: co(28, 6) = 1: co(28, 7) = 1: co(28, 8) = 1: co(28, 9) = 1: co(28, 10) = 1: co(28, 11) = 1: co(28, 12) = 1:
co(28, 13) = 1: co(28, 14) = 1: co(28, 15) = 1: co(28, 16) = 1: co(28, 17) = 1: co(28, 18) = 1: co(28, 19) = 1: co(28, 20) = 1: co(28, 21) = 1: co(28, 22) = 1: co(28, 23) = 1: co(28,
24) = 1: co(28, 25) = 1: co(28, 26) = 1: co(28, 27) = 1: co(28, 28) = 0: co(28, 29) = 1: co(28, 30) = 1: co(28, 31) = 1: co(28, 32) = 1
co(29, 1) = 1: co(29, 2) = 1: co(29, 3) = 1: co(29, 4) = 1: co(29, 5) = 1: co(29, 6) = 1: co(29, 7) = 1: co(29, 8) = 1: co(29, 9) = 1: co(29, 10) = 1: co(29, 11) = 1: co(29, 12) = 1:
co(29, 13) = 1: co(29, 14) = 1: co(29, 15) = 1: co(29, 16) = 1: co(29, 17) = 1: co(29, 18) = 1: co(29, 19) = 1: co(29, 20) = 1: co(29, 21) = 1: co(29, 22) = 1: co(29, 23) = 1: co(29,
24) = 1: co(29, 25) = 1: co(29, 26) = 1: co(29, 27) = 1: co(29, 28) = 1: co(29, 29) = 0: co(29, 30) = 1: co(29, 31) = 1: co(29, 32) = 1
co(30, 1) = 1: co(30, 2) = 1: co(30, 3) = 1: co(30, 4) = 1: co(30, 5) = 1: co(30, 6) = 1: co(30, 7) = 1: co(30, 8) = 1: co(30, 9) = 1: co(30, 10) = 1: co(30, 11) = 1: co(30, 12) = 1:
co(30, 13) = 1: co(30, 14) = 1: co(30, 15) = 1: co(30, 16) = 1: co(30, 17) = 1: co(30, 18) = 1: co(30, 19) = 1: co(30, 20) = 1: co(30, 21) = 1: co(30, 22) = 1: co(30, 23) = 1: co(30,
24) = 1: co(30, 25) = 1: co(30, 26) = 1: co(30, 27) = 1: co(30, 28) = 1: co(30, 29) = 1: co(30, 30) = 0: co(30, 31) = 1: co(30, 32) = 1
co(31, 1) = 1: co(31, 2) = 1: co(31, 3) = 1: co(31, 4) = 1: co(31, 5) = 1: co(31, 6) = 1: co(31, 7) = 1: co(31, 8) = 1: co(31, 9) = 1: co(31, 10) = 1: co(31, 11) = 1: co(31, 12) = 1:
co(31, 13) = 1: co(31, 14) = 1: co(31, 15) = 1: co(31, 16) = 1: co(31, 17) = 1: co(31, 18) = 1: co(31, 19) = 1: co(31, 20) = 1: co(31, 21) = 1: co(31, 22) = 1: co(31, 23) = 1: co(31,
24) = 1: co(31, 25) = 1: co(31, 26) = 1: co(31, 27) = 1: co(31, 28) = 1: co(31, 29) = 1: co(31, 30) = 1: co(31, 31) = 0: co(31, 32) = 1
co(32, 1) = 1: co(32, 2) = 1: co(32, 3) = 1: co(32, 4) = 1: co(32, 5) = 1: co(32, 6) = 1: co(32, 7) = 1: co(32, 8) = 1: co(32, 9) = 1: co(32, 10) = 1: co(32, 11) = 1: co(32, 12) = 1:
co(32, 13) = 1: co(32, 14) = 1: co(32, 15) = 1: co(32, 16) = 1: co(32, 17) = 1: co(32, 18) = 1: co(32, 19) = 1: co(32, 20) = 1: co(32, 21) = 1: co(32, 22) = 1: co(32, 23) = 1: co(32,
24) = 1: co(32, 25) = 1: co(32, 26) = 1: co(32, 27) = 1: co(32, 28) = 1: co(32, 29) = 1: co(32, 30) = 1: co(32, 31) = 1: co(32, 32) = 0
64
6.4 Anexo 4: Gráficos
Gràfico 1: Evolución del factor de Carga para 7 departamentos
0.000
20.000
40.000
60.000
80.000
100.000
120.000
2.000
2.000
2.000
1.960
1.882
1.845
1.845
1.808
1.667
1.601
1.477
1.419
1.362
1.362
1.335
1.309
1.309
1.282
1.282
1.232
1.232
1.159
1.113
1.113
1.048
1.048
1.006
1.006
1.006
1.006
Temperatura
Val
or
de
Car
ga
Carga
65
Gráfico 2: Evolución de la carga Vs. Temperatura
0.00
10000.00
20000.00
30000.00
40000.00
50000.00
60000.00
70000.00
80000.00
600.
000
576.
240
553.
421
520.
875
500.
249
461.
413
443.
141
425.
593
417.
081
400.
565
377.
008
369.
468
354.
837
340.
786
327.
291
320.
745
314.
330
308.
043
308.
043
301.
882
295.
845
278.
447
272.
878
251.
694
241.
727
241.
727
232.
154
227.
511
222.
961
214.
132
174.
961
168.
033
158.
151
148.
851
137.
295
134.
549
Temperatura
Car
ga
Carga
66
Gráfico 3: Evolución del Factor de forma
0.000
5.000
10.000
15.000
20.000
25.000
30.000
0.250
00.2
4500.2
353
0.230
60.2
3060.2
306
0.226
00.2
2600.2
215
0.221
50.2
1700.2
127
0.212
70.2
127
0.208
40.2
043
0.196
20.1
846
0.180
90.1
809
0.177
30.1
773
0.173
80.1
703
0.170
30.1
669
0.157
10.0
507
Temperatura
fact
or
de
form
a
Factor de Forma
67
Gráfico 4: Evolución del Factor de desviación
0.000
0.020
0.040
0.060
0.080
0.100
0.120
0.250
00.2
450
0.235
30.2
3060.2
306
0.230
60.2
2600.2
260
0.221
50.2
215
0.217
00.2
127
0.212
70.2
1270.2
084
0.204
30.1
9620.1
846
0.180
90.1
809
0.177
30.1
773
0.173
80.1
7030.1
703
0.166
90.1
5710.0
507
Temperatura
fact
or
de
des
viac
ión
Factor de desviación
68
Gráfico 5: Evolución de la Función objetivo multicriterio
0.0000
0.5000
1.0000
1.5000
2.0000
2.5000
3.0000
3.5000
4.0000
0.250
00.2
4500.2
3530.2
3060.2
3060.2
3060.2
2600.2
2600.2
2150.2
2150.2
1700.2
1270.2
1270.2
1270.2
0840.2
0430.1
9620.1
8460.1
8090.1
8090.1
7730.1
7730.1
7380.1
7030.1
7030.1
6690.1
5710.0
507
Temperatura
Fu
nci
ón
Ob
jeti
vo m
ult
icri
teri
o
Función objetivo multicriterio
69
Gráfico 6: Evolución del factor de Carga
0.00
50000.00
100000.00
150000.00
200000.00
250000.00
300000.00
350000.00
400000.00
450000.00
1600
.00
1568
.00
1568
.00
1536
.64
1505
.91
1475
.79
1334
.00
1281
.17
1255
.55
1255
.55
1205
.83
1205
.83
1158
.08
1089
.97
1068
.17
1025
.8798
5.2596
5.5494
6.2383
8.2182
1.4580
5.0272
7.6768
4.8867
1.1867
1.1864
4.6063
1.7155
9.6052
6.6949
5.7247
6.0946
6.5643
9.13
Temperatura
Car
ga
Carga
70
Gráfico 7: Evolución del Factor de Forma
0.000
5.000
10.000
15.000
20.000
25.000
30.000
35.000
0.050 0.050 0.050 0.050 0.050 0.050 0.049 0.049 0.049 0.048 0.046 0.044 0.040 0.035 0.025 0.019 0.016 0.010
Temperatura
Fac
tor
de
Fo
rma
Forma
71
Gráfico 8: Evolución del factor de Desviación
0.000
0.050
0.100
0.150
0.200
0.250
0.300
0.350
0.400
0.450
0.500
0.050 0.050 0.050 0.050 0.050 0.050 0.049 0.049 0.049 0.048 0.046 0.044 0.040 0.035 0.025 0.019 0.016 0.010
Temperatura
Fac
tor
de
Des
viac
ión
Desviación
72
Gráfico 9: Evolución de la Función Objetivo Multicriterios
0.00000
0.50000
1.00000
1.50000
2.00000
2.50000
3.00000
0.050
0.050
0.050
0.050
0.050
0.050
0.049
0.049
0.049
0.048
0.046
0.044
0.040
0.035
0.025
0.019
0.016
0.010
Temperatura
Fu
nci
ón
Ob
jeti
vo M
ult
icri
teri
os
Función Objetivo Multicriterios
73
7 BIBLIOGRAFÍA
1. APPLE James M. “Plant layout and material handling” Editorial John Wiley & Sons, tercera edición 1977
2. ARMOUR G. Y BUFA E. “A heuristic algorithm and simulation approach to relative location facilities” Management Science, Vol. 9, 1963, 294-309
3. ASKIN & STANDRIGE “Modelying and Analysis of manufacturing systems” 1994
4. BANERJEE P., MONTREUIL B., MOODIE C.L. Y KASHYAP R.L. “A modelling of interactive facilities layout designer reasoning using qualitative patterns”, International Journal of Production Research, Vol. 30, No.3, 1992, 433-453
5. BANERJEE P. Y ZHOU Y. “Facilities layout design optimization with single loop material flow path configuration” International Journal of Production Research, Vol. 33, No. 1, 1995, 183-203
6. BOCTOR D. “Microsoft Office 97 Visual Basic paso a paso “ Mc. Graw Hill, España 1997
7. DUNCAN T: “Experiments in the use of neighbourhood search techniques for vehicle routing” Artificial Intelligence Applications Institute, University of Edinburgh, Edinburgh EH1 1HN, AIAA-TR-176 June 1995
8. GARCÍA P. Diana. “Configuración de planta por medio de algoritmos genéticos”, asesor Fidel Torres, 2001
9. GOLDBERG D.E., “Genetic Algorithms in search, optimization and machine learning” Addison Weslye Publishing Company, 1989
10. GOLANY B. y ROSENBLATT M.J. “A heuristic algorithm for the quadratic assignment formulation to plant layout problem”, International Journal of Production Research, Vol. 27, No. 2, 1989, 293-308
11. GRANT William. “Factory planning and plant layout”, Prentice-Hall, 1963. 12. ISLIER A.A “A genetic algorithm approach for multiple criteria facility layout
design” International Journal of Production Research, Vol. 36, No. 6, 1998, 1549-1569
13. MUTHER Richard “Distribución en planta” Editorial hispano europea cuarta edición 1981
14. PICONE CJ y WILHEM W.E. “A perturbation scheme to improve Hillier’s solution to the facilities layout problem” Management Science, Vol. 30, No. 10, Octubre 1984, 1238-1249
15. RAOOT AD y RAKSHIT A. “A linguistic pattern approach for multiple criteria facility layout problems” International Journal of Production Research, Vol. 31, No. 1, 1993 203-222
16. ROSEMBLATT M.J. “The dynamics of plant layout” Management Science, Vol. 32, No. 1, Enero 1986, 76-86
17. TAM K.Y. y LIS H. “A hierarchical approach to the facility layout problem” International Journal of Production Research, Vol. 29, No. 1, 1991, 165-184
18. VALHONRAT J.M. y COROMINAS A. “Localización, configuración en planta y manutención”
74
19. WELGAMA P.S. y GIBSON P.R. “A construction algorithm for the machine layout problem with fixed pick up and drop off pints”, International Journal of Production Research, Vol. 31, No. 11, 1993, 2575-2590
![8aker [1] definió en forma sencilla el scheduling como el ... · 4.1.3 Reglas de dominación. 28 . 4.2 ENFRIAMIENTO SIMULADO (SA) 30 . 4.2.1 Criterio para la generación de cada](https://img.pdfslide.es/doc/110x75/5bc7d54609d3f22f268bb904/8aker-1-definio-en-forma-sencilla-el-scheduling-como-el-413-reglas.jpg)
![simulado 4 [1468082]](https://img.pdfslide.es/doc/110x75/577c82e31a28abe054b2aaa6/simulado-4-1468082.jpg)
