SECRETARÍA DE POSGRADO

OPTIMIZACIÓN DEL PROCESO DE TEÑIDO DE TELAS

T

E

S

I

S

QUE PARA OBTENER EL GRADO DE:

DOCTOR EN CIENCIAS BÁSICAS

P

R

E

S

E

N

T

A:

FELIPE MALDONADO ETCHEGARAY

DIRECTOR DE TESIS: DR. LUIS B. MORALES CO-DIRECTOR DE TESIS: DR. ANIBAL ZANINI

QUILMES, ARGENTINA

2005

INDICE TEMÁTICO CAPÍTULO I 1.- INTRODUCCIÓN 1.1.- El estado del arte en lo textil 1.2.- El estado del arte en lo matemático 1.3.- El teñido 1.4.- Objetivos y estructura del trabajo

6 7 8 9 10

CAPÍTULO II 2.- INDUSTRIA TEXTIL E INVESTIGACIÓN DE OPERACIONES 2.1.- Industria Textil 2.2 Optimización 2.3 Aplicaciones 2.3.1 Fabricación de hilos de algodón 2.3.2 Confección 2.3.3 Teñido de telas

13 13 16 16 16 18 21

CAPÍTULO III 3.- COLOR 3.1 La fuente luminosa 3.2 El objeto 3.3 El ojo humano 3.4 El observador estándar 3.5 Espacios de color 3.5.1 El espacio XYZ 3.5.2 Espacio de cromaticidad Yxy 3.6 Elipses de McAdam 3.7 Espacio de color L*a*b* 3.8 Medición del color

22 23 25 25 26 28 29 30 31 32 33

CAPÍTULO IV 4.- OPTIMIZACIÓN 4.1.- Optimización continua 4.1.1 Programación Lineal 4.1.1.1.- El método Simplex 4.1.1.2.- Métodos de punto interior 4.2 Optimización combinatoria 4.2.1.- El problema de la mochila 4.2.2.- Problemas de redes 4.2.3.- Coloración de grafos 4.2.4.- El cartero chino 4.2.5.- Problema del agente viajero 4.2.6.- Métodos de resolución en Optimización Combinatoria 4.2.6.1.- Técnicas enumerativas

35 36 37 38 39 40 41 42 43 43 43 45 45

2

4.2.6.2.- Métodos de relajación Lagrangiana 4.2.6.3.- Planos cortantes

46 47

CAPÍTULO V 5.- TEÑIDO DE TELAS 5.1.-Modelo 5.2 Diferencias de color 5.3 Determinaciones iniciales 5.3.1.- Optimización 5.3.1.1.- Algoritmo basado en permutaciones 5.3.1.2.- Eliminación de ramas 5.4.- Algoritmos de retroceso 5.4.1.- Ramificación y acotamiento

51 53 54 55 56 57 59 63 64

CAPÍTULO VI 6.- APLICACIONES INDUSTRIALES 6.1.- Sucesiones óptimas 6.2.- Restricciones 6.2.1.- Uso previo del equipo de teñido 6.2.2.- Sensibilidad del ojo humano 6.2.3.- Restricciones de tipo comercial 6.2.4.- Series largas de colores 6.2.4.1.- Método de resolución 6.3.- Múltiples equipos de teñido 6.4.- Lavado de los equipos de teñido 6.4.1.- Modelo alternativo 6.4.2.- Políticas de lavado 6.4.2.1.- Solución I 6.4.2.2.- Solución II 6.4.2.3.- Solución III 6.4.3.- Aplicaciones

69 69 70 71 73 74 76 79 80 82 83 86 87 88 89 90

CONCLUSIONES Y RECOMENDACIONES

92

BIBLIOGRAFÍA

94

APÉNDICE I APÉNDICE II APENDICE III

100 102 106

3

ÌNDICE DE TABLAS Y FIGURAS

TABLAS TABLA I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII

Página Coordenadas CIELab de un conjunto de 10 colores 55 Matriz de costos para 10 colores: diferencias entre el color 56 deseado y el obtenido 60 Coordenadas CIELab de un conjunto de 37 colores. El número entre paréntesis indica el orden en que se fueron recibiendo los pedidos Matriz de costos de un conjunto de 37 colores 62 Sucesiones y costos obtenidos por optimización y por opinión 69 de expertos Matriz de costos ampliada con renglón y columna correspondiente al último color de la serie teñida anteriormente Secuencia óptima del conjunto de 36 colores Secuencia óptima del conjunto de 36 colores con el uso previo del equipo para el color C°M Esquema de la matriz de costos ampliada para incorporar los colores que faltaba teñir del secuencia anterior Secuencias de colores con y sin la restricción de evitar diferencias de color “observables” Costo de secuencias ordenadas con distintos métodos Costos relativos de secuencias obtenidas por distintos métodos Esquema de matriz ampliada para incorporar los colores que faltaban teñir en cada equipo Coordenadas de ocho pares de colores referenciacontaminante Diferencias ∆ij para los ocho colores contaminados Diferencias de color causadas por el 1% de colorantes residuales y porcentaje máximo de colorante residual permisible para que la diferencia no sea mayor que K Coordenadas Lab del conjunto P en el espacio CIELab Matriz de costos ∆ij

71 72 72 73 74 77 77 81 84 84 86 87 87

4

FIGURAS Figura 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14-a 14-b 14-c 15 16

Página Productos inicial y final en las distintas ramas de la industria 14 textil Estructura paralela de transformación de la materia prima 15 y de la generación y flujo de información Fabricación de hilo de algodón 17 Proceso de confección de prendas de vestir 18 Distribución espectral de los iluminantes A, D65 y F2 24 Curva espectral de la luz reflejada por una manzana 25 Igualación de un haz de luz monocromática con tres colores 27 básicos Curvas de respuesta del ojo humano en función de la longitud 28 de onda Cono de todos los valores triestímulos posibles 30 Diagrama CIE de cromaticidad 31 Espacio de color L*a*b* 33 Esquema de un fotocolorímetro 34 Proceso de “podado” de ramas 59 Zonas de dispersión de los costos que intervienen en la 78-79 solución óptima Ordenamiento al azar 78 Ordenamiento por el eje L 78 Ordenamiento de acuerdo a los expertos 79 Representación de las diferencias |Cj’ – Cj| contra el 85 porcentaje de contaminante Porcentaje máximo de contaminante permisible para que la 86 diferencia causada, |Cj’ – Cj|, no sea mayor que K contra la diferencia causada por el 1% de colorantes residuales

5

CAPÍTULO I

1

INTRODUCCIÓN

La optimización del teñido de telas, o más concretamente, la determinación de la sucesión óptima de colores en el teñido de telas, constituyen en realidad dos problemas, el color y la optimización, un problema tecnológico y un problema matemático. Esta conjunción es paradigmática. En el ámbito académico se manifiesta asiduamente, la necesidad e importancia de establecer y profundizar la vinculación entre investigación y sector productivo. Sin embargo, y a pesar de los esfuerzos que se realizan en forma continua en tal sentido, esta vinculación está limitada en la práctica, probablemente por razones económicas e ideológicas. Lamentablemente hay descreimiento y escepticismo en el sector industrial sobre la ayuda que podría obtener y, por el otro lado, en el sector académico, encontramos cierto menosprecio por los problemas industriales. Sin embargo, la industria enfrenta problemas cuya resolución mejoraría su productividad y la calidad de sus productos y distintas ramas de las ciencias básicas podrían participar en la resolución de problemas industriales; además de que los problemas industriales pueden motivar y ser fuente de inspiración en trabajos de investigación. Ciertamente, las posibilidades de vinculación entre Ciencias Básicas (Física, Química, Matemáticas, Informática) e Industria son inagotables. Nosotros hemos centrado nuestros esfuerzos en la optimización de procesos en un subsector de la industria manufacturera, el teñido de telas en la industria textil. Aún así restringido, la riqueza del tema es muy amplia, los logros que se han alcanzado revisten particular trascendencia por la importancia que el teñido tiene en toda la cadena del proceso textil, por la incidencia que reviste para la calidad perceptual y factual de los productos y, desde el otro ángulo, porque varios de los problemas que se suscitaron han dado lugar a investigaciones de características inéditas que sustentan y justifican este trabajo de tesis. La confluencia entre ambas disciplinas, la optimización y el teñido de telas, descansa en un modelo que describe el comportamiento del proceso productivo del sector y, en forma mucho más general, de cualquier rama de una industria manufacturera (Maldonado 1996) [1]. En particular, la industria textil, en sus diferentes ramas, ha recibido en las últimas tres o cuatro décadas avances tecnológicos que han alterado la estructura de la producción. Los avances más significativos están relacionados con la robotización de los procesos y con la velocidad de procesamiento de las materias primas. Sin embargo, en las industrias manufactureras como la textil, junto a las sucesivas transformaciones de los materiales, se encuentra un flujo de información que

6

organiza el proceso productivo, incide sobre la calidad perceptual y factual de los artículos fabricados e influye en la estructura de costos. Las etapas donde se genera esta información es donde se pueden detectar y caracterizar problemas cuya resolución contribuiría a optimizar los recursos y mejorar la calidad de los productos diseñados; es decir, constituyen el punto nodal para la optimización de los segmentos subsiguientes del proceso. El modelo desarrollado señala un paralelismo entre el tránsito de la materia prima que va siendo transformada y un flujo de información que establece las acciones sucesivas. En el Capítulo II presentamos este modelo y su utilización en distintas ramas textiles y, en particular, en nuestro caso específico.

1.1

El estado del arte en lo textil

En términos generales, puede decirse que es en los departamentos de Ingeniería del Producto o de Programación de la Producción donde se genera la información sobre la cual es posible incidir para optimizar los procesos (Chávez 1993) [2]. Así sucede en el teñido de telas. La programación del orden en que se teñirán sucesivamente las telas en diferentes colores, es crucial para disminuir el número de lavados de los equipos de teñido y la cantidad de reprocesos de las telas que no han alcanzado el color requerido. Sin embargo, a pesar de los adelantos tecnológicos con que cuenta la industria del acabado de telas, sistemas computarizados para la medición del color, formulación automática de la cantidad de colorantes necesarios, control de temperatura a lo largo del proceso de teñido, se siguen produciendo fallas en la obtención de los colores requeridos. Uno de los motivos, aunque no el único, reside en una selección incorrecta del orden en que se harán los teñidos sucesivos. Y es que la secuencia se establece en la enorme mayoría de las fábricas, en todo el mundo, de manera totalmente empírica. Se utilizan criterios que se mantienen, prácticamente, desde el comienzo de la revolución industrial, pero que tienen un porcentaje significativo de “fracasos”. Aparece como contradictorio que se mantenga un “cuello de botella” tecnológico en el proceso de teñido de una tela mientras que el control del color obtenido se efectúa con equipos de alta precisión. Para muchas industrias el color es un aspecto esencial en los productos que fabrican y los servicios que proveen. Más aun, el color es una parte inseparable de nuestro mundo y un elemento esencial en nuestra cultura. Desde tiempos muy remotos el color estuvo asociado con los dioses, con las fuerzas de la naturaleza y con la jerarquía social. Es decir, estuvo presente y jugó un papel 7

destacado en la vida social y religiosa de Mesoamérica. La manifestación de los colores en nuestra cultura no sólo ha sido importante en el pasado; se ha prolongado hasta nuestros días en los textiles, las cerámicas y los amates. Hoy en día, si el color no es "agradable" al consumidor, los artículos fabricados (las prendas confeccionadas) corren el riesgo de no ser aceptados (AATCC 1991) [3]. Así, la tecnología del color resulta crucial para la industrial textil. En esta industria, el color representa el 70% de todas las causas de rechazo a nivel industrial. En la producción por lotes, tanto en el teñido de telas como en la fabricación de fibras de poliéster, una selección adecuada de la sucesión de colores podría reducir las diferencias indeseadas de color provocadas por la contaminación de los equipos, disminuir los costos causados por el lavado de equipos y por el reprocesado, aumentar la calidad perceptual de los productos y atenuar el impacto ecológico negativo propio de este sector industrial. Hemos desarrollado en el Capítulo III los elementos básicos sobre el color, las componentes que lo caracterizan, los sistemas de medición y la perceptividad; es decir, su vinculación con el ojo humano.

1.2

El estado del arte en lo matemático

La selección de una secuencia óptima de colores corresponde matemáticamente al tipo de problemas de optimización combinatoria (Morales 1996) [4]. Los problemas de optimización combinatoria pueden ser atacados con métodos exactos que garantizan encontrar una solución óptima. Estos métodos derivan muchas veces de Programación Lineal o son técnicas enumerativas como branch and bound y programación dinámica. En principio, podría pensarse que los problemas de optimización discreta son más fáciles de resolver. Es claro que una enumeración completa de todas las soluciones posibles conducirá a la solución óptima. Pero este método está limitado, porque hay una clase de problemas donde el tiempo empleado para encontrar la solución óptima crece exponencialmente con la dimensión del problema. Sucede que aún para los problemas de menor porte, el número de pasos sería tan grande que una computadora tardaría siglos en el proceso de cálculo. Por ejemplo, en un problema donde el número de soluciones posibles es del orden de n!, sí se tarda 10-9 segundos para examinar cada solución, el tiempo empleado sería de 80 años para n=20 y 1,680 años para n=21. La gran variación observada en el tiempo de ejecución, cuando el valor de n aumenta linealmente, es conocida en la literatura como explosión exponencial. Los problemas de este tipo son llamados NPcompletos (Campello 1994) [5]. Un ejemplo clásico del tipo de problemas cuya solución no ha sido alcanzada más que para instancias pequeñas y en algunos casos particulares, es el llamado 8

Problema del Agente Viajero (TSP, por sus siglas en inglés). El TSP es uno de los problemas matemáticos que han demandado mayor atención porque tiene múltiples aplicaciones en problemas científicos y de ingeniería y se enuncia de manera muy simple. Dada una lista de n ciudades {1, 2, ..., n}, y los costos, cij, de viajar entre dos cualesquiera de ellas; el problema del agente viajero consiste en encontrar un camino de mínimo costo que visite cada ciudad una sola vez y que regrese a la ciudad donde empezó el tour. Pero, a pesar de su “sencillez”, hasta ahora han fracasado todos los intentos por encontrar un algoritmo eficiente para resolverlo; diciéndose que es eficiente si el tiempo que tarda para hallar la solución depende en forma polinomial del tamaño del problema, en este caso del número de ciudades. El problema se ha transformado en crucial porque si se encuentra un algoritmo eficiente, en los términos antedichos, se tendrían solucionados todos los problemas de la clase NP-completos (Papadimitriou 1982) [6]. El costo computacional elevado asociado con los intentos de obtener soluciones óptimas, sobre todo en situaciones prácticas que comprenden problemas de dimensiones elevadas, tiene como alternativa la obtención de una buena solución (no necesariamente óptima) con costo computacional más reducido. Esto a llevado al desarrollo de un gran número de Algoritmos Heurísticos (Campello 1994) [5]. En el caso del teñido de telas se trata de establecer las condiciones que minimicen el efecto de la contaminación residual. Efectivamente, un factor que genera diferencias entre el color propuesto y el obtenido en una tela, es la presencia de residuos de los colorantes usados con anterioridad y que contaminan el equipo de teñido. El análisis del proceso de teñido y la elección de la secuencia más adecuada lleva a un problema del tipo del agente viajero, aunque esto no implica que el problema de establecer una secuencia óptima no tenga solución. En realidad, el tamaño del problema; es decir, la cantidad de colores que se procesan como un conjunto en cualquier fábrica textil, son resolubles de manera exacta en una PC. La riqueza del problema no está en la dificultad matemática si no más bien en la conjunción y adaptación de la herramienta de cálculo a las múltiples variantes que surgen de los requerimientos del trabajo industrial.

1.3

El teñido

El teñido del poliéster con colorantes dispersos se efectúa en jet (especie de olla a presión) donde, en cada operación, se coloca la tela, entre 150 y 300 kilogramos, alrededor de 4000 litros de agua, colorantes y los aditivos necesarios, tales como sustancias que aumentan la solubilidad y dispersantes que evitan que las partículas de colorante se aglutinen entre si. El proceso tiene una duración media de cuatro horas, con una temperatura de régimen de 130ºC. En general, después del teñido, la tela se enjuaga dentro del mismo recipiente para eliminar los colorantes que han quedado adheridos a ella pero que no penetraron en la fibra. Finalmente se

9

retira la tela y se expulsa el agua, quedando el equipo “listo” para el siguiente proceso, aunque quedan residuos de los colorantes utilizados. En las empresas que se dedican al acabado se reciben pedidos de sus clientes para teñir telas en un conjunto de distintos colores. Se construye una lista ordenada de los colores que serán usados sucesivamente. Las telas son teñidas en un mismo equipo que es evacuado pero no es lavado después de cada proceso. Después de teñir cada tela, la mayor parte de los colorantes empleados pasa a formar parte integral de ella, pero una fracción permanece en el baño y en el equipo de teñido. La cantidad utilizada en el proceso depende del tipo de fibra, la naturaleza del colorante y de los parámetros de operación tales como tiempo y temperatura. La fracción no usada representa un elemento contaminante que afecta los procesos de teñido subsiguientes; por lo tanto, el color de la tela que es teñida en segunda instancia puede diferir del color deseado debido a la presencia de residuos de los colorantes que se utilizaron previamente. La medida en la que los residuos alteran el color del proceso subsiguiente (bajo idénticas condiciones de operación) depende del color del material residual y del color usado en el nuevo teñido. Así, en cuanto al efecto que tiene para el proceso de teñido, cada par de colores constituye una díada asimétrica. Por eso es que los técnicos, para reducir las consecuencias, tiñen primero los colores “claros” y después los “oscuros”, primero los “limpios” y después los “sucios”. Sin embargo, este tipo de procedimiento hace imposible considerar el conjunto de colores como un todo, dado que, para sólo 10 colores sería necesario considerar 10! = 3,628,800 secuencias diferentes. En consecuencia, se produce una pérdida de calidad por mayores niveles de contaminación y un aumento en los costos por reprocesamiento de telas y lavado más frecuente de los equipos. Se hace evidente la importancia de contar con métodos que permitan obtener la secuencia óptima de colores para que se reduzcan los efectos de la contaminación.

1.4

Objetivos y estructura del trabajo

Llegado a este punto, enfrentamos el siguiente problema: Dado un conjunto de n colores, es necesario encontrar la secuencia de procesamiento que produzca la mínima diferencia entre los colores deseados y los colores que serán obtenidos. Teniendo en cuenta estos elementos se desarrolló un modelo matemático que se basa en las consecuencias que los residuos de colorantes que permanecen en el equipo tienen sobre el teñido subsiguiente (Morales 1996, Maldonado 2000) [4,7]. El modelo obtenido es análogo al Problema del Agente Viajero Asimétrico (ATSP, por sus siglas en inglés), permite aplicar técnicas de optimización y lo presentamos en el Capítulo V. 10

El Capítulo IV lo dedicamos al problema de Optimización en general y Optimización Combinatoria y al ATSP en particular. Para resolver nuestro problema hemos empleado básicamente dos técnicas distintas: una enumeración exhaustiva, para lo cual desarrollamos un programa computacional que puede utilizar computación en paralelo y que calcula las permutaciones de 15 elementos en orden lexicográfico en 10 segundos en una PC a 400 Mz; y un programa basado en el método de branch and bound, con el cual hemos resuelto de manera exacta secuencias de hasta 37 colores (Carpaneto 1995) [8]. En el Capítulo V desarrollamos este método y mostramos detalladamente un ejemplo sencillo. El Capítulo VI lo dedicamos a la resolución del problema de obtener secuencias óptimas de colores para el teñido de telas. En primer lugar resolvemos el caso de un conjunto de 10 colores, sin ningún condicionamiento. Hemos incorporado, entonces, restricciones representativas de las condiciones reales de producción industrial y desarrollamos métodos de resolución utilizables por una empresa fabril. Las restricciones contemplan situaciones relacionadas con el uso previo del equipo de teñido, la sensibilidad del ojo humano y las condiciones de carácter comercial (Maldonado 2000) [7]. En los dos primeros casos hemos resuelto el problema con modificaciones adecuadas en la matriz de costos que conducen a la solución exacta. Para la tercer restricción suele usarse métodos conocidos como ventanas de tiempo. Nosotros hemos desarrollado un método heurístico que conduce a soluciones que difieren a lo máximo en una cota conocida de la sucesión óptima y que se basa en realizar modificaciones adecuadas en la matriz de costos y utiliza también un algoritmo estándar para el ATSP (Maldonado 2001) [9]. Hemos tenido en cuenta otra condición más impuesta por el trabajo industrial: aunque el proceso de encontrar una sucesión óptima para un conjunto de colores de tamaño normal en la industria (n 0 y sk > 0. Los métodos primal-dual pueden considerarse como una variante del método de Newton aplicado al sistema de ecuaciones formado por las primeras tres condiciones de optimalidad. Dada la iteración actual (xk, yk, sk) y el parámetro σk ∈ [0,1], la dirección de búsqueda (wk, zk, tk) se genera resolviendo el sistema lineal Aw = b – Axk, ATz + t = c – Atyk – sk, Skw + Xkt = - SkXke + σkµke, Donde

µk = xTksk/n El nuevo punto se obtiene, entonces, por la relación (xk+1, yk+1, sk+1) = (xk, yk, sk) + (σkwk, σkzk, σktk) Las iteraciones se efectúan simultáneamente en el primal y en el dual, lo que va disminuyendo la “brecha de dualidad” (la función objetivo del primal tiene como límite inferior la función objetivo del dual). En términos generales puede decirse que se utilizan dos criterios de parada. El más directo, aunque más lento, es continuar el proceso hasta la coincidencia de los valores de ambos objetivos, el del primal y el del dual. El otro criterio utilizado consiste en detener el proceso de iteraciones cuando la diferencia entre los valores de ambos objetivos es menor que una precisión establecida y proseguir el proceso con el método simplex, dado que la solución óptima está cercana.

4.2

Optimización combinatoria

Los problemas de optimización combinatoria se refieren a la asignación eficiente de recursos limitados para resolver objetivos deseados cuando los valores de alguna o de todas las variables deben tomar sólo valores enteros. Las limitaciones en recursos básicos, tales como trabajo, materias primas o capital restringen las alternativas factibles. Sin embargo, en la mayoría de estos problemas, hay muchas alternativas posibles a considerar y la meta consiste en determinar cuales son las mejores. La optimización combinatoria abarca problemas de las áreas más disímiles. Su amplitud proviene de que en muchos problemas prácticos, las actividades y los recursos, tales como máquinas, vehículos, personas, son indivisibles. Además, muchos problemas tienen solamente un número finito de opciones alternativas y

40

por lo tanto, se pueden formular como problemas de optimización combinatoria. La palabra combinatoria se refiere al hecho de que existen sólo un número finito de alternativas factibles. Así, la optimización combinatoria es el proceso de encontrar una o más soluciones óptimas en un espacio discreto. Problemas de este tipo aparecen en casi todos los campos administrativos (finanzas, comercialización, producción, control de inventarios, localización), y en innumerables ramas de la ingeniería (el diseño óptimo de canales y puentes, diseño de circuitos, determinación de los estados mínimos de energía en la fabricación de aleaciones, logística de la generación y del transporte de corriente eléctrica, programación de líneas de producción en fabricas, problemas de cristalografía). En esta sección trataremos el caso en que, tanto el objetivo como los vínculos son funciones lineales. El modelo general de un problema lineal entero de optimización combinatoria tiene la forma n

min {cTx: Ax = b, x ≥ 0, x ∈ Z } donde Z es el conjunto de los números enteros. Cuando alguna de las variables x pueden tomar valores reales, el problema se llama problema de programación entera mixto. Cuando las variables x están restringidas a los valores 0 y 1, el problema se llama problema de programación entera 0-1. A continuación, presentamos algunos problemas clásicos de optimización combinatoria.

4.2.1 El problema de la mochila Se dispone de un conjunto de n elementos para llenar una mochila de capacidad V. Cada objeto i tiene asociado un valor ci y ocupa un volumen vi. Se trata de determinar el subconjunto de objetos I ⊆ {1, 2, …, n} que se puedan introducir en la mochila y que maximice la función objetivo. El problema tiene un único vínculo lineal, que la suma del peso de todos los artículos no exceda el peso total permitido y una función objetivo lineal, la suma del valor de los artículos colocados en la mochila [40]. max

∑ ci i ∈I

sujeto a

∑ vi ≤ V i ∈I

41

El problema de la mochila tiene múltiples aplicaciones en criptografía, en la protección de archivos de computadora, correo electrónico y transferencia electrónica de fondos. La “llave” de seguridad consiste en la combinación lineal de un conjunto de datos que deben igualarse a un determinado valor. La generalización del problema, con varios vínculos de mochila, tiene también aplicaciones importantes. Un ejemplo es el problema de presupuesto. El problema consiste en determinar un subconjunto de centenares de proyectos bajo consideración que aseguren el mayor retorno de la inversión, satisfaciendo los requerimientos financieros y regulatorios [41].

4.2.2 Problemas de redes Muchos problemas de optimización pueden ser representados por una red o grafo, definida por nodos y arcos que los conectan. Algunos surgen de redes físicas tales como las calles de una ciudad, red de carreteras, sistema ferroviario, redes de comunicación y circuitos integrados. Además, hay otros problemas que se pueden modelar como redes aunque no haya una red física subyacente. Por ejemplo, el problema de asignación donde se desea asignar un conjunto de personas a un conjunto de tareas a mínimo costo. Un sistema de nodos representan a las personas que se asignarán y otro sistema de nodos representan a los trabajos y habrá un arco que conecta a cada persona con cada trabajo que sea capaz de realizar [42] [43]. El problema puede ser establecido como min ∑ cij xij I,j

sujeto a xij = 1, si el recurso I es asignado a la actividad j xij = 0, de otra manera

∑xij=1

j =1,..., n

∑xij = 1

I =1,..., m

i=1

j=1

donde cij es el costo de aplicar el recurso i a la actividad j. El problema de asignación es un caso especial del problema del transporte, el cual, a su vez, es una caso especial del problema de flujo máximo. Todos estos problemas pueden ser resueltos usando el algoritmo del simplex, pero cada

42

problema cuenta con algoritmos más eficientes diseñados para tomar ventaja de su estructura particular.

4.2.3 Coloración de grafos Hay muchos problemas de teoría de grafos que examinan las características del grafo o de la red subyacente. Tales problemas incluyen el problema de colorear los vértices, conocido como problema de coloración de grafos y que consiste en la asignación de colores a un conjunto de n vértices, en un grafo no dirigido, con la única condición que para todo par de vértices adyacentes estos no sean coloreados del mismo color. Formalmente, sea un grafo G=(V,E) con el conjunto de vértices V y conjunto de aristas E. Una k-coloración de G es una partición de V en K subconjuntos V1,....,Vk tal que no haya dos vértices en el mismo conjunto que sean adyacentes. Los conjuntos V1,....,Vk se refieren a clases de colores o a colores. El problema de coloración puede definirse así: Dado un grafo G, encontrar X(G), el mínimo valor de k para el cual G es coloreable [44]. Hay numerosas aplicaciones prácticas de coloración de grafos, tales como la calendarización de exámenes [44], el diseño y operación de sistemas de manufactura flexible [45] y el problema de los cuatro colores [46] entre otras.

4.2.4 El cartero chino El problema fue estudiado inicialmente por el matemático chino Kwan MeiKo [47]. Consiste en cubrir todas las calles asignadas y regresar al punto de partida habiendo recorrido la menor distancia posible. Si se construye un grafo G=(V,E) en el que cada arista representa una calle donde hay que entregar correspondencia y cada vértice representa una intersección, este problema es equivalente a hallar un ciclo en G que atraviese cada arista al menos una vez y que la distancia total recorrida sea mínima. Hay distintas variantes del problema del cartero chino. El grafo asociado puede ser o no dirigido y, por otro lado, puede ser cerrado o abierto, es decir, puede existir la condición de que el cartero regrese al punto de partida o que no sea necesario. Este problema tiene varias aplicaciones: en la planeación del mantenimiento de calles, el manejo de robots de exploración, la búsqueda en páginas web vinculadas y en sistemas de información geográfica (GIS)[48]. Los métodos de resolución se basan en el análisis de los arcos que deben ser duplicados para convertir el grafo asociado al problema en un grafo de Euler. Un grafo es euleriano cuando existe un camino que regrese al punto de partida recorriendo todas las aristas solamente una vez. Si se agrega la restricción de que cada nodo debe ser visitado exactamente una vez y elimina la condición de que se debe recorrer cada arista, el problema se transforma en problema del agente viajero.

43

4.2.5 Problema del agente viajero El problema del agente viajero, TSP por sus siglas en inglés, es uno de los problemas que ha atraído más la atención dentro del campo de la Investigación de Operaciones. Es muy sencillo de enunciar, pero muy difícil de resolver. Dado un conjunto de n ciudades y el costo de viajar entre dos cualquiera de ellas, se trata de encontrar el camino que pasa por todas las n ciudades y que regresa a la de origen con un costo mínimo [49]. En términos de la teoría de grafos la formulación del problema es la siguiente: Dado un grafo completo con pesos, se trata de encontrar el ciclo hamiltoniano de peso mínimo. Aquí, los nodos representan a las ciudades, las aristas representan a los caminos entre ellas y los pesos de cada arista es el costo del camino que representa. Dependiendo de si el costo de una arista depende o no de la dirección en que se la recorra, el problema del agente viajero será asimétrico o simétrico. Formalmente, para el caso del agente viajero asimétrico, min ∑ cij xij I,j

sujeto a xij = 1, si se recorre la arista que va del vértice i al vértice j xij = 0, de otra manera

∑xij=1

j =1,..., n

∑xij = 1

I =1,..., n

i=1 j=1

∑ xij ≥ 1

i∈S, j∈S*

para todas las particiones (S,S*) de los n puntos

donde cij es el peso del arco (I,j). El último vínculo evita que se produzcan subtours. Existen múltiples aplicaciones del problema del agente viajero en problemas reales [49]. Por ejemplo en la distribución o recolección de artículos como puede ser el reparto de correspondencia, el recorrido de máquinas quita nieve, rutas de autobuses escolares, etc., la programación de servicios de llamadas, optimización de las trayectorias de la herramienta en un equipo de fabricación de piezas, por ejemplo, el brazo de la soldadora asignado para soldar todas las conexiones en un tablero de circuito impreso, un trazador de gráficos para dibujar una figura dada, la programación de la máquina perforadora para agujerear plaquetas para circuitos.

44

En particular, encontrar el orden en que deben teñirse un conjunto de telas en la industria textil será formulado como un TSP.

4.2.6 Métodos de resolución en Optimización Combinatoria La solución de problemas de optimización combinatoria es una tarea difícil. La dificultad se debe a que, distinto de lo que sucede en programación lineal donde la región factible es convexa y, en consecuencia una solución local es un óptimo global, en los problemas combinatorios se debe buscar en una red de puntos factibles y se tienen múltiples mínimos locales. Básicamente, hay cuatro métodos generales para resolver problemas de optimización combinatoria, aunque en la práctica se combinan en procedimientos híbridos: • • •

Técnicas enumerativas Técnicas de relajación Planos cortantes

Ahora presentaremos estas técnicas de manera breve. En el siguiente capítulo ampliaremos las utilizadas en la resolución de los problemas encarados en este trabajo.

4.2.6.1 Técnicas enumerativas El método más simple para resolver un problema de optimización combinatoria es enumerar todas las soluciones factibles determinar cual es la óptima. El número de soluciones factibles es finito, sin embargo, debido a que el número de soluciones crece exponencialmente con el tamaño del “problema”, la llamada "explosión combinatoria", solamente se podrían solucionar con este método los casos más pequeños. A veces se pueden eliminar muchas posibilidades por argumentos de viabilidad. Además de la enumeración implícita o de “fuerza bruta”, el método enumerativo más usado se denomina branch and bound, donde la ramificación se refiere a la enumeración y el acotamiento se refiere a la eliminación de soluciones posibles por comparación con un límite superior (o inferior) [50]. Para obtener una cota, el problema se relaja de modo que el problema relajado sea fácil de resolver. El método de branch and bound requiere dos herramientas. La primera es contar con una forma de cubrir toda la región factible con varias sub-regiones factibles más pequeñas, esto es lo que se conoce como ramificación porque el

45

procedimiento, repetido recursivamente a cada sub-región, forma una estructura de árbol. La otra herramienta es el acotamiento, que es una forma rápida de encontrar límites superiores e inferiores para la solución óptima en cada subregión. La parte medular del método se basa en que, si en un problema de minimización, el límite inferior de una sub-región P es mayor que el límite superior para cualquier otra sub-región Q examinada previamente, entonces, la sub-región P puede eliminarse del proceso de búsqueda. Este tipo de acción se conoce como podar y, en general, se implementa guardando en una variable global el mínimo límite superior de todas las sub-regiones examinadas. Puede suceder que el límite superior en una sub-región coincida con su límite inferior. Este valor es el, entonces, el mínimo de la función dentro de la correspondiente sub-región. Se dice que la rama ha sido resuelta. El procedimiento concluye cuando todas las ramas han sido podadas o resueltas, aunque es posible establecer un límite al número de iteraciones, en cuyo caso queda definido un rango de valores que contiene al mínimo global. La eficiencia del método depende en forma crítica de los algoritmos usados para la ramificación y el acotamiento. Si el procedimiento no es el correcto, por ejemplo, ramificando sin podar, las sub-regiones se irán haciendo cada vez más pequeñas y el procedimiento se reduce a una enumeración exhaustiva. No hay algoritmos universales para todos los problemas, los algoritmos de ramificación y acotamiento se diseñan especialmente para cada aplicación. Otra forma de ataque consiste en eliminar la condición de integralidad y resolver el problema de programación lineal continuo resultante. Si la solución al problema de programación linear relajado satisface las restricciones de integralidad, la solución obtenida es óptima. Si el problema relajado no es factible, entonces tampoco lo es el problema entero. Si, en cambio, alguna de las variables en la solución del problema de programación lineal es fraccionaria, se eligen esas variables fraccionarias y se “ramifica” creando subproblemas que excluyen las soluciones anteriores pero no elimina ninguna solución factible entera. Estos nuevos problemas constituyen “nodos” en el árbol de ramificación y se resuelven nuevamente como problemas de programación lineal [51]. Este proceso continua hasta que la solución óptima encontrada es un valor entero.

4.2.6.2 Métodos de relajación Lagrangiana El método de relajación Lagrangiana consiste en eliminar del conjunto de restricciones aquellas que sean más problemáticas y agregarlas en el objetivo en el forma clásica de Lagrange, con multiplicadores que son modificados

46

iterativamente. El sub-problema resultante es más sencillo de resolver. Esto es imprescindible porque el sub-problema tiene que ser resuelto repetidamente hasta alcanzar valores óptimos para los multiplicadores. Este método proporciona una cota de la solución entera y puede incorporarse en un algoritmo branch and bound; es decir, es alternativo al de programación lineal relajada. El de relajación Lagrangiana es un método de propósitos especial. Aprovecha la estructura especial del conjunto de vínculos y, por lo tanto requiere un conocimiento profundo de las características del problema [52].

4.2.6.3 Planos cortantes La resolución de problemas de programación lineal entera utilizando planos cortantes se debe inicialmente a Gomory [53]. La idea básica del método es quitar inicialmente el requerimiento de integralidad y resolver el problema de programación lineal correspondiente, por ejemplo por el método simplex. Esto proporciona un vector óptimo x*. Si, casualmente, todas las componentes de x* resultan enteras, entonces sería también la solución óptima para el problema de programación entera. En el caso de que no tenga todas las componentes enteras se agrega una nueva desigualdad, un plano, que abarque todas las soluciones enteras pero que deje fuera la solución x*. La repetición del procedimiento converge a una solución óptima entera. Para explicar el proceso detalladamente, conviene rescribir el problema de Programación Lineal. Sea P un problema de programación lineal entero maximizar z = cx sujeto a Ax = b x≥0 x entero donde c ∈ ℜn, b ∈ ℜm y A ∈ ℜmxn son dados y x ∈ ℜn es el vector de las variables de decisión. Si eliminamos el último vínculo (x entero), tenemos un problema de programación lineal relajado, digamos P*. Sea B una submatriz de A, de orden mxm, tal que det(B) ≠ 0, entonces, podemos escribir A = (B N), y análogamente x = (xB xN) y c = (cB cN).

47

El problema de programación lineal P*, puede escribirse sujeto a

maximizar z = cBxB + cNxN bxB + NxN = b xB ≥ 0, xN ≥ 0

Si despejamos a xB en términos de xN xB = B-1b – B-1NxN el problema P* queda maximizar z = cB B-1b – (cB B-1N + Cn)xN sujeto a

xB = B-1b – B-1NxN xB ≥ 0, xN ≥ 0

Entonces, designando por aj a cada columna de A, las columnas del tableau del simplex, en el proceso de resolución, son yj = B-1aj. Los valores de la solución final viene dados por xºB = B-1b. Finalmente, el problema de programación entera relajado, se puede escribir maximizar z = zº - ∑(zj – cj)xj j∈IN sujeto a xB = xºB - ∑yjxj j∈IN xB ≥ 0, xj ≥ 0, j∈IN donde IN es el conjunto de índices de las columnas en N. El vínculo del problema P* puede también escribirse xB(i) = xºB(i) - ∑yjixj j∈IN Una vez resuelto el problema P*, B es una base óptima, tal que xºB = B-1b ≥ 0 y zj – cj ≥ 0. Al menos una de las variables de la solución, digamos xºB(k), será no entera, entonces,

48

xB(k) = xºB(k) - ∑ykjxj j∈IN o, lo que es lo mismo xºB(k) = xB(k) +

∑ykjxj

j∈IN Como todas las x son mayores o iguales que cero, e indicando con el símbolo ⎣ ⎦, la parte entera de, se ve que xºB(k) ≥ xB(k) +

∑⎣ykj⎦ xj j∈IN

dado que los valores originales de las variables en el problema P son enteros, podemos escribir ⎣xºB(k)⎦ ≥ xB(k) + ∑⎣ykj⎦ xj j∈IN o, introduciendo una variable de holgura s ≥ 0 ⎣xºB(k)⎦ = s + xB(k) +

∑⎣ykj⎦ xj j∈IN

remplazando xB(k) , se tiene ⎣xºB(k)⎦ = s + xºB(k) - ∑ykjxj + ∑⎣ykj⎦ xj, ó j∈IN j∈IN s = ⎣xºB(k)⎦ - xºB(k) + ∑(ykj - ⎣ykj⎦ )xj j∈IN Si ahora definimos a fkj = ykj - ⎣ykj⎦ y a fk0 = xºB(k) - ⎣xºB(k)⎦ , se tiene que s = - fk0 +∑ fkj xj j∈IN Evidentemente fkj y fk0 están en el intervalo 0-1, y dado que s ≥ 0, se tiene que

∑fkj xj ≥ fk0 j∈IN Estas desigualdades son conocidas como cortes de Gomory. Estos planos

49

no son únicos y se debe definir una estrategia para su incorporación sucesiva. Aunque el algoritmo de Gomory converge a una solución óptima entera en un número finito de pasos, su convergencia es muy lenta. Se han logrado avances significativos tanto en el tamaño como en la complejidad de los problemas resueltos por medio de la teoría poliédrica. La idea rectora de la combinatoria poliédrica es reemplazar el conjunto de vínculos del problema de programación entera por una convexificación de los puntos factibles. Desde 1935, H. Weyl mostró que un poliedro convexo puede definirse alternativamente como la intersección de un número finito de semi-espacios o como la cubierta convexa de un número finito de vectores. El teorema de Weyl implica que existen un sistema finito de desigualdades cuyo conjunto de solución coincide con la cubierta convexa de los puntos enteros del problema. Esta recibe el nombre de conv(S). Las caras de del poliedro conv(S) son los mejores cortes posibles para continuar la búsqueda de las soluciones enteras, pero son más difíciles de determinar y dependen de cada problema particular [54] [55].

50

CAPÍTULO V 5

TEÑIDO DE TELAS

Para muchas industrias el color es un aspecto esencial en los productos que fabrican y los servicios que proveen. Más aun, el color es una parte inseparable de nuestro mundo y un elemento esencial en nuestra cultura. Desde tiempos muy remotos el color estuvo asociado con los dioses, con las fuerzas de la naturaleza y con la jerarquía social. Es decir, estuvo presente y jugó un papel destacado en la vida social y religiosa de Mesoamérica. La manifestación de los colores en nuestra cultura no sólo ha sido importante en el pasado; se ha prolongado hasta nuestros días en los textiles, las cerámicas y los amates. Hoy en día, si el color no es "agradable" al consumidor, los artículos fabricados corren el riesgo de no ser aceptados (Morales 1996) [4]. En particular, el color desempeña un papel fundamental en la fabricación y comercialización de los productos textiles; es decir, la tecnología del color resulta crucial para la industrial textil. Tanto es así, que en esta industria, el color representa el 70% de todas las causas de rechazo a nivel industrial. El segmento del proceso productivo relacionado íntimamente con el color es en el teñido de telas. La programación del orden en que se teñirán sucesivamente las telas en diferentes colores, es crucial para la calidad de los artículos, para disminuir el número de lavados de los equipos de teñido y la cantidad de reprocesos de las telas que no han alcanzado el color requerido. En la producción por lotes, tanto en el teñido de telas como en la fabricación de fibras de poliéster, una selección adecuada de la sucesión de colores podría reducir las diferencias indeseadas de color provocadas por la contaminación de los equipos, disminuir los costos causados por el lavado de equipos y por el reprocesado, aumentar la calidad perceptual de los productos y atenuar el impacto ecológico negativo propio de este sector industrial. El sector industrial del teñido de telas utiliza grandes volúmenes de agua que deben ser reprocesadas porque incluyen colorantes, ácido acético, sosa cáustica y alteraciones importantes en el PH. En particular, el teñido del poliéster con colorantes dispersos se efectúa en jet (especie de olla a presión) donde, en cada operación, se coloca la tela, entre 150 y 300 kilogramos, alrededor de 4000 litros de agua, colorantes y los aditivos necesarios, tales como sustancias que aumentan la solubilidad y dispersantes que evitan que las partículas de colorante se aglutinen entre si. El proceso tiene una duración media de cuatro horas, con una temperatura de régimen de 130ºC. En general, después del teñido, la tela se enjuaga dentro del mismo recipiente para eliminar los colorantes que han quedado adheridos a ella pero que no penetraron en

51

la fibra. Finalmente se retira la tela y se expulsa el agua, quedando el equipo “listo” para el siguiente proceso, aunque quedan residuos de los colorantes utilizados. En las empresas que se dedican al acabado se reciben pedidos de sus clientes para teñir telas en un conjunto de distintos colores. Se construye una lista ordenada de los colores que serán usados sucesivamente. Las telas son teñidas en un mismo equipo que es evacuado pero no es lavado después de cada proceso. Después de teñir cada tela, la mayor parte de los colorantes empleados pasa a formar parte integral de ella, pero una fracción permanece en el baño y en el equipo de teñido. La cantidad utilizada en el proceso depende del tipo de fibra, la naturaleza del colorante y de los parámetros de operación tales como tiempo y temperatura. La fracción no usada, que permanece en el equipo, representa un elemento contaminante que afecta los procesos de teñido subsiguientes; por lo tanto, el color de la tela que es teñida en segunda instancia puede diferir del color deseado debido a la presencia de residuos de los colorantes que se utilizaron previamente. La medida en la que los residuos alteran el color del proceso subsiguiente (bajo idénticas condiciones de operación) depende del color del material residual y del color usado en el nuevo teñido. Así, en cuanto al efecto que tiene para el proceso de teñido, cada par de colores constituye una díada asimétrica. Por eso es que los técnicos, para reducir las consecuencias, tiñen primero los colores “claros” y después los “oscuros”, primero los “limpios” y después los “sucios”. Los técnicos en teñido consideran “limpios” a los colores más puros, esto es, a los que están en la parte exterior del espacio de color y “sucios” a los que provienen de mezclas de colores, es decir, los que están hacia el centro del especio de color, que tienen tonalidades de gris. Sin embargo, este tipo de procedimiento hace imposible considerar el conjunto de colores como un todo, dado que, para sólo 10 colores sería necesario considerar 10! = 3,628,800 secuencias diferentes. En consecuencia, se produce una pérdida de calidad por mayores niveles de contaminación y un aumento en los costos por reprocesamiento de telas y lavado más frecuente de los equipos. Se hace evidente la importancia de contar con métodos que permitan obtener la secuencia óptima de colores para que se reduzcan los efectos de la contaminación. Se enfrenta entonces el siguiente problema: Dado un conjunto de n colores, es necesario encontrar la secuencia de procesamiento que produzca la mínima diferencia entre los colores deseados y los colores que serán obtenidos. Teniendo en cuenta estos elementos se desarrolló un modelo matemático que se basa en las consecuencias que los residuos de colorantes que permanecen en el equipo tienen sobre el teñido subsiguiente (Morales 1996)(Maldonado 2000) [4][7]. Para resolver este problema hemos empleado básicamente dos técnicas distintas: una enumeración exhaustiva, para lo cual desarrollamos un programa

52

computacional que podría utilizar computación en paralelo y que calcula las permutaciones de 13 elementos en orden lexicográfico en 10 segundos en una PC a 400 Mz; y un programa basado en el método de retroceso (backtracking en inglés), con el cual hemos resuelto de manera exacta secuencias de hasta 37 colores (Carpaneto 1995) [8]. Los resultados obtenidos los presentamos en el siguiente capítulo. Hemos incorporado, además, restricciones representativas de las condiciones reales de producción industrial y desarrollamos métodos de resolución utilizables por una empresa fabril. El modelo desarrollado es representativo del comportamiento del proceso de teñido bajo múltiples restricciones industriales y comerciales (Maldonado 2000) [7], inclusive ante el uso simultáneo de varios equipos de teñido.

5.1

Modelo

Hemos señalado más arriba que al teñir una tela una parte de los colorantes no se introduce en las fibras de poliéster, queda en la superficie de la tela, en el baño y en el equipo. La porción de colorantes adheridos a la tela se elimina mediante un enjuague y se va en el agua evacuada, pero una parte queda contaminando el equipo de teñido. Esta fracción afecta el siguiente proceso de teñido de modo que, aunque se controlen exhaustivamente todos los parámetros y reactivos involucrados, el color que se obtiene es distinto del color que se necesita. La diferencia de color que se produce, debido a la presencia de colorantes residuales en el equipo de teñido depende, bajo idénticas condiciones de operación, de cuales son los dos colores involucrados, el color que se va a teñir y cual se tiñó con anterioridad. Vamos a presentar ahora una descripción formal del proceso de teñido de telas. Dado un conjunto de N colores C1, C2, ..., CN; cuando se tiñe una tela con un color Cj después de haber teñido otra tela con un color Ci, se obtiene un color C’j. Indicaremos con ∆ij a la distancia euclideana entre las coordenadas L'j, a'j, b'j del color C'j obtenido y las coordenadas Lj, aj, bj del color Cj que se deseaba obtener. Lj, aj, bj son las coordenadas CIELab del color Cj.

∆ij = ((L'j, - Lj)2 + (a'j - aj)2 + (b'j - bj)2)1/2 A los valores ∆ij le daremos el significado de un costo. Denominamos matriz de las diferencias o matriz de costos al arreglo (∆ij). Cada sucesión de los N colores a ser teñidos corresponden a una permutación π del conjunto {1,2,..., N}(Bose 1984) [58]. Entonces, una permutación π = (π(1), π(2),..., π(N)) define una

53

sucesión de los colores que serán teñidos; esto es, π(1) es el color que será teñido en primer lugar, π(2) será el segundo color que se teñirá y así sucesivamente hasta π(N), el último color a ser teñido. Si π-1 es la inversa de la permutación π, entonces π-1(i) es la posición del color Cj en la sucesión de colores a ser teñidos. Entonces, el problema de encontrar la sucesión de colores que produce la mínima diferencia entre los colores deseados y los colores obtenidos puede formularse como el problema de optimización combinatoria de encontrar una permutación π que minimice el costo de la función N-1 z(π) = Σ ∆π(i)π(i +1) i=1

(5.1)

El problema descrito previamente es un caso específico del bien conocido problema del agente viajero asimétrico (ATSP, por sus siglas en inglés) (Papadimitriou 1982) [6].

5.2

Diferencias de color

De acuerdo al modelo desarrollado, al teñir, cada color Cj se ve afectado por los residuos de los colorantes usados previamente para teñir el color Ci. La cantidad de residuos que permanecen en el equipo de teñido después de cada proceso, depende del equipo en si mismo y de los materiales involucrados, pero, en cada caso puede ser determinada experimentalmente. Las experiencias realizadas a tal efecto muestran una contaminación de aproximadamente 1% para el equipo utilizado. A continuación exponemos cual fue el procedimiento seguido para determinarla. 1. Teñimos tela de punto circular de poliéster texturizado con colorantes dispersos en el color Cj, con el equipo limpio. 2. Teñimos el mismo tipo de tela en el color Cj después de haber teñido otra tela del mismo tipo en el color Ci, obteniéndose el color C’j. En todos los casos se utilizó un equipo Jet Dyeing Machine de alta temperatura (403 ºK). 3. Se midió la diferencia entre los colores C’j y Cj. El equipo utilizado para realizar las mediciones de color fue un espectrofotómetro HunterLab ULTRASCAN XE. Las condiciones empleadas en las mediciones fueron: geometría del instrumento 0/45, iluminante D65, observador estándar 10º. 4. Se efectuaron 8 determinaciones con cada color medido y la contaminación tuvo un valor de 0, 985%, en promedio. En base a lo anterior, determinamos las diferencias entre cada color Cj, que sería obtenido al teñir con el equipo limpio y el color C’j, que se obtendría usando el equipo contaminado con el 1% de los colorantes necesarios para obtener el color Ci. El proceso se efectuó, por simulación, en un espectrocolorímetro de las características ya citadas. El procedimiento seguido fue el siguiente

54

1) 1.1) 1.2) 1.3) 2) 2.1)

2.2) 3) 3.1) 3.2)

5.3

Lectura de las formulaciones Se determinaron y almacenaron en memoria las coordenadas Lab del conjunto de colores C1, C2,..., CN. Se determinó la formula (cantidad de colorantes necesarios para producirlo) para cada uno de los colores de la muestra. Se calculó el 1% de cada una de las formulas para utilizarlño como contaminante. Síntesis Se recuperó de la memoria la formula de cada uno de los colores C1, C2,..., CN y se les agregó el 1% correspondiente a cada color como contaminante. Se determinaron las coordenadas Lab de cada uno de los colores resultantes. Deferencias de color. Se registraron en el equipo las coordenadas de cada color original en calidad de estándar. Se determinaron las diferencias de color ∆E entre las coordenadas de los colores originales (estándares) y las coordenadas de los colores contaminados.

Determinaciones iniciales

En la Tabla I damos las cordenadas CIELab de un conjunto de los 10 colores utlizados en el primer grupo de determinaciones. Los colores están puestos en el orden indicado por los expertos Tabla I. Coordenadas CIELab de un conjunto de 10 colores No. 1 2 3 4 5 6 7 8 9 10

Colores utilizados L a 96.56 -23.07 81.70 4.90 57.61 35.27 54.21 46.20 38.69 52.73 20.67 20.24 41.17 1.25 48.98 -36.38 20.26 -9.64 39.47 -3.61

b 68.93 84.71 63.59 38.64 26.16 -25.63 -40.97 10.19 -1.32 -2.49

55

Los valores de las diferencias, ∆ij, entre los colores deseados (equipo limpio) y los colores obtenidos (equipo contaminado), determinados por el proceso de simulación antes descrito, están consignados en la Tabla II. Tabla II. Matriz de costos: diferencias entre el color deseado y el obtenido 0.00 5.91 15.03 20.12 42.84 46.33 21.38 14.69 39.28 16.86

.21 0.00 1.98 3.95 16.71 28.01 14.36 11.49 32.15 8.28

.07 .18 0.00 .31 1.89 11.66 7.41 6.59 19.94 3.80

.12 .42 .62 0.00 .82 11.69 8.33 7.72 21.00 4.38

.07 .38 .34 .08 0.00 5.78 4.63 4.95 13.19 2.24

.20 1.31 1.15 .47 .60 0.00 .17 .48 1.13 .22

1.28 7.22 6.50 2.34 3.32 2.64 0.00 1.31 4.77 1.00

.22 1.18 .99 1.25 7.42 8.04 .89 0.00 3.10 .82

.05 .23 .16 .08 .55 .65 .06 .12 0.00 .05

.22 1.39 1.22 .38 2.07 3.26 .46 .44 1.29 0.00

5.3.1 Optimización Una vez determinada la matriz de costos, (∆ij), se presenta el problema de optimizar la expresión (5.1). Nosotros utilizamos, en instancias con N pequeño (hasta 12 colores), un algoritmo basado en la generación de permutaciones en orden lexicográfico y una forma simple del método de ramificación y acotamiento (branch and bound, en inglés) (Papadimitriou 1982) [6], y para instancias con mayor N (hasta 40 colores) un algoritmo más elaborado, basado en un algoritmo de retroceso (backtacking, en inglés). En esta sección (Maldonado 1999) [59] y en la siguiente presentamos los algoritmos desarrollados. La generación de permutaciones ha sido, desde hace varias décadas, un problema importante en computación; tanto intrínsecamente, por la búsqueda de métodos que tratan de disminuir el tiempo de máquina, la memoria utilizada, etc., como por la gran cantidad de aplicaciones que tienen en ciencias e ingeniería. El primer algoritmo computacional data de 1956 y es debido a Tomkins [60]; y a partir de allí se han desarrollado una variedad de algoritmos secuenciales que generan permutaciones con cambio mínimo(Tomkims 1956)(Ord-Smith 1970) [61],[62], en orden lexicográfico (Ord-Smith 1070)(Phillips 1967)(Shen 1963) [61],[63],[64] e inclusive sin un orden especial (Ord-Smith 1970)[61]. Más recientemente se han publicado varios algoritmos en paralelo (Akl 1987)(Lee 1994) [65]-[71], en arquitecturas SIMD (Gupta) [67], en diseños sistólicos (Gupta 1967) [67] o con procesadores vectoriales (Lin 1990) [68].

56

En un problema típico de optimización combinatoria, tal como el (5.1) donde el objetivo z se debe optimizar sobre un conjunto de permutaciones π, se puede desarrollar un algoritmo que genere las permutaciones ordenadamente y que permita eliminar subconjuntos de permutaciones donde, por algún criterio K, se tiene la certidumbre de que el objetivo no alcanzará su óptimo. Nosotros hemos desarrollado un algoritmo que genera las permutaciones en orden lexicográfico utilizando solamente como información la permutación precedente y cuando es usado para resolver problemas del tipo (5.1) permite eliminar todas las permutaciones de una rama. El algoritmo desarrollado genera todas las permutaciones de N elementos en orden lexicográfico y es comparado con éxito con los algoritmos publicados más eficientes. Realizamos también un análisis cuantitativo del desempeño de nuestro algoritmo al ser usado en una búsqueda exhaustiva.

5.3.1.1 Algoritmo basado en permutaciones La mayoría de los algoritmos que generan las permutaciones de N elementos en orden lexicográfico utilizan un vector auxiliar, denominado “firma”, en forma explícita o implícitamente (Tomkings 1963) [60]. Aunque la cantidad de memoria utilizada por el vector es despreciable, la generación de la “firma” y su lectura para la determinación de cada permutación conllevan el uso de un tiempo considerable. Sin embargo, cuando los elementos a permutar son alfanuméricos el vector auxiliar no es necesario. El algoritmo desarrollado utiliza las siguientes características de las permutaciones ordenadas en forma lexicográfica: a) Si asignamos el número 1 a la primer permutación, {1,2,...,n}; todas las permutaciones pares se obtienen de la anterior intercambiando los dos primeros elementos. Así, si la permutación k-ésima (k, impar) de n elementos es a1, a2, a3, ...., an; entonces, la permutación k+1-ésima se obtiene intercambiando a2 con a1; es decir, a2, a1, a3 ..., an. b) Las permutaciones impares se obtienen intercambiando el primer elemento aj, desde a3 a an, por el primero de su izquierda que sea menor a él; y ordenando de menor a mayor a los elementos de a1 a aj-1. Cuando se llega a an sin haber encontrado un elemento menor a su izquierda el proceso de generación de las permutaciones a concluido. Nótese, que cuando se ve afectado el elemento aj, los elementos del conjunto {a1, a2, ..., aj-1} están ordenados en forma lexicográfica inversa. Por lo tanto, el ordenamiento de menor a mayor de estos elementos no implica un proceso de búsqueda sino solamente de r intercambios; donde r es el entero que resulta de dividir (j-1) entre 2. Si tomamos, por ejemplo, la permutación 42135

57

(número 12 de los cinco elementos 1,2,3,4,5), la siguiente permutación se obtiene: a) intercambiando el elemento a4, porque es el primero, de izquierda a derecha, que tiene a su izquierda uno menor a él -el a2-, para obtener el arreglo intermedio 43125; y b) ordenando de menor a mayor los primeros 3 elementos (4-1). Para ello se intercambia el elemento a1 por a3 -los primeros parte entera de j/2 elementos. La permutación número 13 es entonces 13425. Formalmente, un pseudo código del algoritmo tiene la estructura presentada a continuación: Comenzar Escoger un valor de N Generar la primer permutación Repetir Intercambiar los dos primeros elementos Buscar ak, entre a3 y an, con algún elemento menor a su izquierda. Si existe, intercambiarlos. En caso contrario p es falso Ordenar de menor a mayor el subconjunto {a1, a2, …, ak-1} Mientras el criterio p de parada sea verdadero Fin El número total de intercambios necesarios para generar, con nuestro algoritmo, las permutaciones de n elementos es 1.543n!. Este número se puede obtener con el siguiente análisis: i) Para obtener las permutaciones pares se efectúa un intercambio por cada una. O sea un total de .5n! intercambios. ii) Para obtener las permutaciones impares se efectúan dos procesos. Un intercambio del elemento aj por el primero que sea menor a su izquierda y un ordenamiento. O sea, nuevamente, un total de .5n! intercambios; más los intercambios necesarios para el reordenamiento de menor a mayor de j-1 elementos. Designando con Pj-1 a la cantidad de intercambios realizados por reordenamientos cuando se permutan j-1 elementos; entonces, al permutar j elementos se efectuarán j*Pj-1 + (j-1)*|(j-1)/2| intercambios. El último sumando se debe a que al permutar j elementos, el j-ésimo elemento es intercambiando una vez con cada uno de los j-1 elementos que le anteceden; y en cada uno de esos casos, al reordenar se producen |(j-1)/2| intercambios. Se obtiene así la relación de recurrencia

58

Pj = j*Pj-1 + (j-1)*|(j-1)/2|

(4.2)

con P3 = 2. Al sumar la serie para j = 10, se obtiene el valor .54308n!, y puede mostrarse que la serie converge a ese valor. Los términos posteriores al décimo, (j=10), son menores que 1/2(j+1). Si se suma la serie 1/210*∑1/2j (desde j=1 hasta ∞) se obtiene como cota el valor .0001.

5.3.1.2 Eliminación de ramas El procedimiento que utilizamos consiste en sumar, para cada permutación generada, el costo de los caminos parciales, en el orden de menor a mayor velocidad de cambio, e ir controlando si se supera el menor valor, Q, obtenido hasta ese momento. Si al sumar k caminos parciales se supera la cota, entonces se genera la última permutación de esa rama ordenado de mayor a menor los n-k elementos restantes. Dado que, como explicamos anteriormente, el algoritmo utiliza cada permutación para generar la siguiente, el proceso de búsqueda continúa desde la permutación subsiguiente a la generada por ordenamiento. En la Figura 13 se presenta un esquema del proceso de búsqueda y de eliminación de una rama cuando se supera una cota mínima, la mejor encontrada hasta ese momento.

Figura 13. Proceso de “podado” de ramas

59

En el Apéndice I mostramos el programa fuente en Turbo Pascal del programa generador de permutaciones en orden lexicográfico y en el Apéndice II el programa fuente del programa de optimización basado en la generación de permutaciones. En el siguiente capítulo presentamos los resultados obtenidos al aplicar este algoritmo a un conjunto de 10 colores. Los valores comparan favorablemente con los que resultarían de teñir en el orden sugerido por expertos. A continuación mostramos en las Tablas III y IV los valores, coordenadas en el espacio CIELab y la matriz de costos, correspondientes a un conjunto de 37 colores. Este valor de N es acorde con la cantidad de telas que se programan para teñir en una empresa de acabados. Tabla III. Coordenadas CIELab, 37 colores. El número entre paréntesis indica el orden en que se fueron recibiendo los pedidos.

N° 1 (4) 2 (7) 3 (9) 4 (29) 5 (31) 6 (23) 7 (10) 8 (33) 9 (22) 10 (14) 11 (3) 12 (20) 13 (13) 14 (18) 15 (30) 16 (2) 17 (15) 18 (25) 19 (1) 20 (17) 21 (24) 22 (8) 23 (28) 24 (27) 25 (6)

L 96.56 91.86 87.02 84.02 81.70 72.69 60.03 38.69 42.01 47.16 58.02 52.11 52.68 46.79 46.60 39.47 41.05 40.20 54.21 43.03 20.45 48.98 20.03 35.02 46.03

A -23.07 13.70 -15.10 -5.10 4.90 5.10 26.03 52.73 40.13 44.07 26.12 39.69 34.66 22.11 -25.36 -3.61 -4.76 36.31 46.70 -9.76 12.61 -36.38 -8.04 17.31 -23.61

b 68.93 32.20 78.02 70.02 84.71 31.05 -7.85 26.16 15.55 -12.46 60.80 54.06 28.00 16.32 6.51 -2.49 2.78 30.65 38.64 10.04 -16.86 10.19 12.47 -34.74 7.08

60

26 (26) 27 (9) 28 (11) 29 (12) 30 (21) 31 (36) 32 (35) 33 (32) 34 (34) 35 (19) 36 (16) 37 (37)

27.16 30.38 20.33 43.14 20.67 25.36 41.17 32.31 25.18 40.24 20.26 57.51

13.89 -6.84 -3.04 -1.44 20.24 10.18 1.25 -9.10 -8.04 -3.40 -9.64 35.27

-30.04 -1.03 2.47 -24.32 -25.63 -18.02 -40.97 -1.07 -1.32 -14.12 -1.32 63.59

61

TABLA IV. Matriz de costos de un conjunto de 37 colores * 177 341 509 590 880 1169 2012 1922 1502 1769 1429 1636 2637 1686 3246 1468 1554 1723 2437 713 2137 3823 2557 4284 2051 4359 2914 3363 4436 3969 2763 4524 3430 4633 3431 3927

6 * 231 339 437 697 877 1468 1439 1101 1313 1097 1320 2012 1458 2754 1385 1449 1614 2131 44 1944 3070 2264 3685 1975 3724 2604 2985 3770 3547 2680 4048 3222 4175 3285 3689

11 105 * 220 293 473 537 960 946 710 1000 723 991 1394 1194 2016 1284 1369 1525 1720 38 1768 2416 2004 3088 1912 3186 2250 2648 3041 3169 2581 3379 2906 3608 3179 3519

16

20

17

62 48 * 131 200 232 480 553 353 597 454 644 893 988 1324 1187 1270 1394 1443 1527 1542 1892 1703 2370 1837 2593 1943 2308 2418 2655 2499 2852 2633 3176 3045 3282

15 10 4 * 66 131 395 350 198 304 178 247 727 827 1037 1148 1225 1293 1159 1370 1435 1310 1645 1670 1763 1923 1831 2050 2157 2382 2434 2471 2494 2801 2963 3215

14 11 7 5 * 99 279 270 154 226 132 181 590 682 825 1028 1061 1114 1004 31 1214 982 1389 1313 1571 1473 1645 1820 1781 2016 2157 2073 2236 2383 2535 2855

13

11 12 21 11 27 11 35 11 41 35 47 * 51 196 * 169 10 108 62 167 25 92 58 126 45 441 21 572 438 516 42 901 771 940 780 989 800 888 614 37 817 1033 832 631 64 1136 897 1001 81 1380 1140 1021 318 1446 1157 1518 980 1386 570 1669 1085 1870 1454 1743 894 1993 1589 1920 1168 2183 1832 2536 2100

10 19 24 31 35 41 49 4 * 42 23 46 36 26 434 53 757 767 771 623 1148 813 93 893 93 1127 346 1161 977 603 1082 1433 902 1594 1168 1787 2077

7 9 12 16 18 12 6 31 22 * 15 2 7 68 379 122 659 677 694 685 47 740 156 881 188 988 476 1179 970 749 1063 1316 1058 1613 1165 1619 1994

9 9 16 10 20 12 26 14 29 16 32 18 37 39 13 115 16 62 29 48 * 90 34 * 25 44 41 271 415 458 78 220 727 763 738 819 744 838 641 748 243 1917 789 814 115 370 889 877 120 532 1082 1137 380 658 1167 1271 975 1265 645 944 1075 1296 1390 1579 957 1412 1600 1785 1167 1507 1716 1776 2052 2129

8 12 16 22 24 23 21 22 19 14 18 17 * 56 398 99 692 706 72 1 663 28 766 135 886 156 1036 429 1174 972 693 1070 1358 1011 1608 1166 1665 2027

10 20 27 35 40 43 47 1 10 54 23 53 39 * 383 32 709 705 709 554 773 728 49 799 60 1044 277 1060 841 487 931 1326 747 1404 1031 1640 1846

21 56 84 113 138 135 131 37 51 122 74 126 99 91 * 127 43 44 44 23 45 46 166 96 206 65 234 51 159 273 252 88 299 94 325 107 128

9 19 27 34 40 40 43 4 11 48 21 46 34 13 332 * 644 640 623 505 15 638 35 686 36 919 240 949 703 409 778 1199 618 1218 838 1490 1680

21 33 58 19 94 127 51 73 165 46 245 325 72 152 284 76 371 477 99 231 387 90 518 641 117 201 400 111 567 721 113 158 341 115 539 704 108 194 359 121 537 689 125 138 173 36 207 233 123 159 221 45 287 331 99 224 365 112 509 650 115 179 260 58 372 448 102 278 398 104 519 671 106 199 314 89 414 540 284 281 277 80 272 266 81 84 90 9 95 100 420 412 378 113 336 295 * 15 60 34 103 130 18 * 60 39 83 113 39 44 * 41 65 77 110 114 128 * 144 159 65 64 0 989 * 1653 88 70 41 37 22 * 612 575 498 138 416 322 168 157 118 83 84 41 742 719 585 187 461 331 97 127 161 56 198 230 758 684 554 205 417 317 170 188 218 45 258 287 348 317 254 129 176 117 775 754 606 220 453 296 584 552 429 231 304 202 169 221 259 75 298 338 790 731 575 269 437 278 238 262 306 77 341 378 803 673 539 258 416 264 273 288 335 74 376 417 309 352 401 111 440 476

8 118 17 260 26 385 34 482 38 644 37 558 38 613 6 170 12 277 41 536 19 395 38 531 29 427 8 218 265 90 11 231 573 117 555 101 555 70 454 133 613 42 541 4 * 297 574 * 19 285 788 197 199 257 816 253 561 100 319 245 613 158 1078 296 485 219 1026 335 691 218 1355 359 1471 353

7 16 26 34 37 36 35 7 12 34 19 34 25 6 224 4 494 490 480 425 94 463 2 491 * 705 154 744 519 301 550 971 432 983 578 1194 1318

17 10 14 84 14 51 13 18 8 20 8 5 42 25 34 186 37 128 33 47 22 57 22 9 56 40 55 284 57 201 41 79 36 93 23 14 82 55 67 352 79 233 56 100 43 116 37 19 97 61 75 500 85 331 68 106 50 130 48 23 92 58 85 434 81 278 64 108 56 127 42 20 79 56 90 425 83 275 58 108 56 123 37 18 88 19 26 128 32 87 56 42 17 46 23 7 96 21 36 206 30 126 64 40 22 53 39 9 80 52 79 397 71 250 53 92 50 114 31 15 87 36 43 273 51 168 60 65 28 72 26 12 78 58 79 380 77 253 54 95 51 118 29 17 83 44 60 297 61 200 63 82 38 92 33 14 216 16 60 165 31 99 157 41 42 50 76 20 63 166 2 65 106 39 44 61 3 21 27 5 329 18 85 159 32 108 239 47 64 54 142 35 3 383 26 95 233 67 7 123 19 47 10 11 16 366 28 80 273 59 15 138 20 45 12 11 28 387 32 56 257 47 20 129 20 36 11 9 85 339 13 107 210 70 59 122 8 42 28 4 1785 57 801 35 7 353 729 838 19 26 741 518 64 340 24 8 245 13 36 130 15 17 18 5 464 18 112 214 36 141 291 48 79 57 166 48 129 338 62 26 215 19 87 113 36 12 56 18 560 15 135 227 34 151 342 49 87 60 148 55 * 541 40 157 381 113 56 218 25 63 37 9 541 * 146 190 91 121 369 56 94 41 217 57 121 547 * 194 362 122 76 177 17 66 21 2 252 403 88 * 253 30 152 105 62 7 75 35 568 227 162 175 * 103 372 72 107 22 158 59 461 399 171 108 239 * 315 93 115 4 202 48 129 760 56 227 505 155 * 238 31 82 36 6 605 302 194 157 163 69 393 * 140 5 227 62 186 701 54 265 423 167 117 188 * 85 66 1 561 382 203 144 188 68 372 2 141 * 139 64 192 929 50 292 620 194 106 310 25 102 * 3 212 910 73 275 511 195 114 222 43 112 42 *

62

5.4

Algoritmo de retroceso

El algoritmo desarrollado en las dos secciones anteriores es muy simple y cómodo porque permite imponer condiciones de forma muy directa. Sin embargo, resulta poco eficiente cuando la instancia a resolver es de N>15. Para superar esta limitación desarrollamos otro algoritmo en el que la búsqueda exhaustiva es atacada con una técnica que recibe el nombre algoritmo de retroceso. El método consiste en tratar de extender una solución parcial. Cuando no es posible extender la solución parcial, se regresa a una solución parcial más corta y se trata nuevamente de extenderla. La idea esencial del retroceso se entiende fácilmente si se piensa en como se hace para atravesar un laberinto: se comienza en un punto y se trata de avanzar limitado por la existencia de barreras que impiden ciertos movimientos. Uno puede tratar de atravesar un laberinto siguiendo solamente dos reglas: a) Desde el punto actual, tomar cualquier camino no explorado previamente. b) Si en el punto actual no existe ningún camino no explorado, regresar hasta el punto anterior donde haya estado antes del punto actual. La primer regla permite extender, cuando es posible, el camino actual; la segunda hace regresar cuando se está bloqueado para buscar otra alternativa. Supondremos que la solución a un problema es un vector (a1, a2, …) de longitud finita pero indeterminada, que satisface ciertos vínculos. Cada ai es miembro de un conjunto finito, linealmente ordenado Ai. Se empieza con un vector nulo ( ) como solución parcial, y los vínculos dirán cual de los miembros de de A1 son candidatos para a1; sea S1 este subconjunto. Elegimos un elemento de S1 como a1. Tenemos entonces la solución parcial (a1). En general, las soluciones posibles del subconjunto Sk de Ak dirán cuales son candidatos para extender la solución parcial (a1, a2, …, ak-1) a (a1, a2, …, ak-1, ak). Si la solución parcial (a1, a2, …, ak-1) no tiene posibilidades para ak, entonces Sk = ∅, y se debe regresar y hacer una nueva elección para ak-1. Un algoritmo para atravesar un laberinto sería el siguiente: S1 k

A1

ak

1

Sk while Sk ≠ ∅ do

elemento de Sk Sk – {ak}

if (a1, a2, …, ak) es solución then registrar k = k -1

while k >0 ó An = ∅ do backtrack k k -1

63

Si, al finalizar, el valor de k = 0, implica que no hay ningún camino para atravesar el laberinto. Si, en cambio se llega a un cierto An vacío, implica que se ha llegado a la puerta de salida del laberinto.

5.4.1 Ramificación y acotamiento La aplicación del algoritmo de retroceso puede mejorarse utilizando distintos métodos que excluyen soluciones que no resultan adecuadas. Una variante de exclusión muy utilizada recibe el nombre de ramificación y acotamiento. En el método de ramificación y acotamiento la exclusión se basa en la suposición de que cada solución tiene asociado un costo y que el objetivo es encontrar la solución de mínimo costo. Para que el método de ramificación y acotamiento sea aplicable, el costo de cada solución parcial debe estar bien definido; esto es costo(a1, a2, ..., ak-1) ≤ costo(a1, a2, ..., ak-1, ak) Cuando el costo tiene esta propiedad, se puede desechar una solución parcial (a1, a2, ..., ak) si su costo es mayor o igual que el costo de una solución calculada previamente. Esta condición se puede aplicar fácilmente al anterior algoritmo de retroceso, obteniéndose costomin ∞ costo 0 S1 A1 k 1

ak Sk

elemento de Sk Sk – {ak}

while Sk ≠ ∅ and cost < costomin do if (a1, a2, …, ak) es solución and costo < costomin then

registrar (a1, a2,..., ak) costomin

costo

k=k+1 calcular Sk

while k >0 do

k

k -1

costo costo(a1, a2,..., ak) Un caso típico que se puede resolver con el método de ramificación y acotamiento es el problema del agente viajero. En este problema el agente debe

64

visitar n ciudades y retornar al punto de partida minimizando el costo del viaje. En nuestro problema de secuenciar n colores el camino es abierto; es decir, no se debe retornar al punto inicial (en Investigación de Operaciones se le conoce como problema del vagabundo viajero). Este efecto se logra agregando un renglón y una columna de ceros en la matriz de costos. La forma más eficiente de aplicar el anterior algoritmo de ramificación y acotamiento consiste en partir, en cada etapa, todas las soluciones en dos grupos, el grupo de las soluciones que incluyen el camino entre dos ciudades i y j, y el grupo de las soluciones que la excluyen. Esto genera un árbol binario donde cada nodo tendrá asociada una cota inferior del costo de todas las soluciones que descienden de él. El método utiliza el hecho de que si se sustrae una constante a cualquier fila o columna de la matriz de costos, la solución óptima no se altera. Desde luego, cambia el costo de la solución pero no el camino en sí. El costo de la solución óptima disminuye exactamente en la cantidad que es sustraída de cualquier fila o columna. La sustracción se realiza de manera que todo renglón y columna tenga un cero y tal que los demás elementos sean no negativos. Entonces, la cantidad total sustraída será una cota inferior para el costo de la solución óptima. Aplicaremos el algoritmo a un ejemplo tomando un subconjunto de la matriz de costos de la Tabla II. Sea n = 6 y la matriz de costos

1 2 3 4 5 6 7

1 ∞ 591 1503 2012 4284 4633 0

2 21 ∞ 198 395 1671 2801 0

3 7 18 ∞ 31 189 1166 0

4 12 42 62 ∞ 82 1169 0

5 7 38 34 8 ∞ 578 0

6 20 131 115 47 60 ∞ 0

7 0 0 0 0 0 0 ∞

En este primer paso no es necesario realizar sustracciones en ningún renglón ni columna dado que todos tienen un cero debido al renglón y columna nulos que se agregaron para que el camino resulte abierto. En consecuencia, para cualquier arco que elijamos, la cota mínima será 0. El arco más conveniente es el 6-7. Esta elección elimina automáticamente todo el árbol que excluye este arco. Si tomáramos el camino que excluye al arco 6-7, pondríamos un valor infinito en el lugar de ese elemento y deberíamos restar el valor 578 al sexto renglón para obtener un cero. Entonces, el camino que excluye al arco 6-7 tiene una cota inferior de 578. En general, el procedimiento consiste en elegir el renglón que contiene el valor más alto del elemento más pequeño.

65

Al seleccionar el arco 6-7 se elimina el renglón 6 y la columna 7 y se coloca un valor infinito en el elemento 7,6. La matriz queda entonces,

1 2 3 4 5 7

1 ∞ 591 1503 2012 4284 0

2 21 ∞ 198 395 1671 0

3 7 18 ∞ 31 189 0

4 12 42 62 ∞ 82 0

5 7 38 34 8 ∞ 0

6 20 131 115 47 60 ∞

Ahora hay que transformar la matriz para obtener un cero en cada renglón. Para ello, como dijimos anteriormente, restamos a cada renglón el menor de sus elementos, 7 al primer renglón, 18 al segundo renglón y así sucesivamente. La matriz queda,

1 2 3 4 5 7

1 ∞ 573 1469 2004 4224 0

2 14 ∞ 164 387 1611 0

3 0 0 ∞ 23 129 0

4 5 24 28 ∞ 22 0

5 0 20 0 0 ∞ 0

6 13 113 81 39 0 ∞

En total se restó 7 + 18 + 34 + 8 + 60 = 127. Este valor, 127 es una cota mínima para la sucesión óptima. En el segundo paso resulta conveniente elegir el arco 3-5. Se elimina entonces el renglón 3 y la columna 5, y el elemento 5,3 se hace infinito. Entonces, la matriz queda, 1 2 3 4 6 1 14 0 5 13 ∞ 2 573 0 24 113 ∞ 4 2004 387 23 39 ∞ 5 4224 1611 22 0 ∞ 7 0 0 0 0 ∞ Para obtener nuevamente un cero en cada renglón, es necesario restar 23 al segundo renglón y 22 al segundo, lo que eleva la cota mínima a 127 +23 + 22 = 172. En cambio, si se elige el camino que excluye al arco 3-5, habría que reemplazar al valor de este elemento por infinito y restar el valor 28 al tercer renglón para volver a obtener un cero en él. En ese caso, la cota inferior pasaría a

66

tener un valor de 127 + 28 = 155. En consecuencia, resulta beneficioso hacer un backtracking y explorar esta opción. Entonces la matriz toma la forma 1 ∞ 573 1469 2004 4224 0

1 2 3 4 5 7

2 14 ∞ 164 387 1611 0

3 0 0 ∞ 23 129 0

4 5 24 0 ∞ 22 0

5 0 20 ∞ 0 ∞ 0

6 13 113 81 39 0 ∞

y el arco seleccionado es el 3-4. Al eliminar el renglón 3 y la columna 5 se obtiene la siguiente matriz, que no debe ser transformada porque tiene un cero en cada renglón y columna. 1 ∞ 573 2004 4224 0

1 2 4 5 7

2 14 ∞ 387 1611 0

3

5

0 0 ∞ 129 0

0 20 0 ∞ 0

6 13 113 39 0 ∞

En el tercer paso se debe elegir el arco 5-6 porque el renglón 5 contiene el elemento de mayor valor, 129. Eliminando el renglón 5 y la columna 6 se tiene la siguiente matriz, que contiene, sin modificar, un cero en cada renglón y columna. 1 ∞ 573 2004 0

1 2 4 7

2 14 ∞ 387 0

3

5 0 0 ∞ 0

0 20 0 0

En el cuarto paso se debe elegir el arco 4-5 porque el renglón 4 contiene el elemento de mayor valor, 387. Eliminando el renglón 4 y la columna 5 se tiene la siguiente matriz, que contiene, sin modificar, un cero en cada renglón y columna.

1 2 7

1 ∞ 573 0

2 14 ∞ 0

3 0 0 0

67

En el quinto paso se debe elegir el arco 2-3 porque el renglón 2 contiene el elemento de mayor valor, 573. Eliminando el renglón 2 y la columna 3 se tiene la siguiente matriz. Para generar un cero en el primer renglón se resto 14. Ello eleva la cota inferior a 155 +14 = 169. 1 7

1 ∞ 0

2 0 0

Los paso 6 y 7 son triviales y llevan a elegir los arcos 1-2 y 7-1, respectivamente. La secuencia óptima resulta la 1-2-3-4-5-6-7-1, donde 7 es el color ficticio agregado para “abrir” la secuencia, y con un costo de 169. Ambos resultados coinciden con los presentados en la Tabla V del Capítulo VI.

68

CAPÍTULO VI 6

APLICACIONES INDUSTRIALES

En este capítulo presentamos los resultados obtenidos en la determinación de sucesiones óptimas, tanto para conjuntos pequeños (hasta 10 colores), como de un tamaño semejante al que puede llegar a encontrarse en una empresa textil dedicada a acabado y tintorería. En los primeros ejemplos resueltos, que corresponden a conjuntos de 10 colores se usó el algoritmo descrito en 5.3.1.1 y 5.3.1.2. Para resolver instancias con un mayor número de colores se utilizó el algoritmo presentado en la sección 5.4.1. Con este algoritmo se resolvieron instancias con 37 colores y se utilizó para comparar la calidad de las sucesiones obtenidas por métodos heurísticos en la búsqueda iterativa de sucesiones óptimas parciales. Este mismo algoritmo se utilizó para resolver el problema de encontrar la secuencia óptima de colores sujeto a un conjunto de restricciones de carácter industrial, su comportamiento ante la presencia de diferencias de color detectables a simple vista y cuando el equipo se ha utilizado previamente en el teñido de otro conjunto de telas, y comercial, atendiendo a la necesidad de teñir una tela en posiciones anteriores a la establecida en la secuencia óptima (Maldonado 2000) [7]. También con las instancias más grandes se resolvió el problema del lavado de equipos de teñido y el establecimiento de políticas acordes al mercado atendido por cada empresa, y a la resolución del problema del teñido de conjuntos de telas utilizando varios equipos de teñido simultáneamente.

6.1

Sucesiones óptimas

Aplicamos, el algoritmo generador de permutaciones, en particular, para el conjunto de colores de la Tabla I. Las sucesiones y los costos obtenidos en el proceso de optimización los presentamos en la Tabla V. En esta tabla se muestran las secuencias óptimas y los costos z obtenidos por el proceso de optimización, así como las secuencias y los costos de las que propusieron los expertos. Tabla V. Sucesiones y costos obtenidos por optimización y por opinión de expertos Colores 4 5 6 7 8 9 10

Secuencia óptima 1243 12345 123456 1235476 12543876 125438769 12354(10)8769

Costos Z .94 1.09 1.69 4.06 4.19 4.84 4.88

Secuencia propuesta 1234 12345 123456 1234567 12345678 123456789 123456789(10)

Costos Z 1.01 1.09 1.69 4.33 5.22 5.34 6,63

69

Los resultados obtenidos por el proceso de optimización fueron comparados con las sucesiones propuestas por los expertos. En todos los casos los costos de las sucesiones obtenidas por optimización fueron menores o iguales a los de las sucesiones propuestas por los expertos. Además, las sucesiones obtenidas por optimización fueron aceptadas, a posteriori, por los expertos como más convenientes a las propuestas por ellos mismos.

6.2

Restricciones

Explicamos anteriormente que determinando los niveles de contaminación provocados por los residuos de los colorantes que permanecen en los equipos de teñido y analizando las consecuencias cuantitativas, obtuvimos un modelo análogo al ATSP y, como tal, fue posible aplicar técnicas de optimización y obtener secuencias de teñido que minimizan el efecto de la contaminación. Sin embargo, los requerimientos de la industria imponen nuevas condiciones de tal modo que una secuencia de colores que es matemáticamente óptima puede resultar no adecuada desde un punto de vista industrial. Puede suceder que una sucesión sea óptima, lógicamente porque la suma de las diferencias espectrométricas entre los colores obtenidos y los solicitados tenga un valor mínimo, pero que contenga un sumando grande correspondiente a una diferencia de color detectable por el ojo humano. También, cuando se aplica un proceso de optimización para determinar una sucesión óptima de colores, debemos tener en cuenta que, en general, el equipo ha sido usado con anterioridad para teñir otro conjunto de telas. Como resultado, el primer color a ser teñido en la nueva serie no puede ser elegido libremente porque se verá afectado por el último color teñido en la serie anterior. En muchas oportunidades, por motivos de tipo comercial, tal como necesidad o exigencia del cliente, no es posible esperar a teñir una determinada tela en el momento matemáticamente adecuado. Cabe aclarar que en cada teñido se emplean unas cinco horas, por lo que un conjunto de 40 telas implica casi diez días entre la primera y la última tela teñida. En la sección anterior resolvimos el problema de encontrar una secuencia óptima para un conjunto de diez colores, pero en la industria textil, normalmente se trabaja con conjuntos de 30, 40 o más colores. Entonces, hay que considerar un factor adicional: para generar cada matriz de costos, se deberían determinar centenares de diferencias de color en un espectrocolorímetro, pero el empleo de personal técnico calificado durante un largo período de tiempo puede resultar inviable. A continuación analizamos cada una de las restricciones descritas. El proceso de optimización se efectuó en instancias de hasta 36 colores. En la Tabla

70

III del Capítulo V se dieron las coordenadas de un conjunto 37 colores, ordenados de acuerdo al orden en que deberían ser teñidos, en opinión de los expertos, y en la Tabla IV, del mismo capítulo anterior se dio la matriz de costos.

6.2.1 Uso previo del equipo de teñido Cuando en una fábrica se recibe un pedido de N telas para teñir, la empresa, en general, no tiene un equipo limpio para trabajar. El equipo está tiñendo una serie de M telas que fueron solicitas previamente y para las cuales se estableció una cierta secuencia, Co1, Co2,..., CoM. La nueva serie a teñir se verá afectada por los colorantes residuales del último de la serie previa, CoM, exactamente como si fuera el primer color de una serie de N+1 colores. El problema puede plantearse como sigue: Dada una serie de N colores, se debe encontrar la sucesión óptima para un a serie de N+1 colores donde el primero está predeterminado. El método de resolución es bastante sencillo. Consiste en realizar una modificación adecuada de la matriz de costos. A la matriz de costos se le agrega un renglón y una columna, correspondientes al color CoM, con las siguientes características: los elementos de la columna, que indican el costo de teñir el color CoM, después de cualquiera de los N colores, son penalizados, asignándoles un costo suficientemente alto. A los elementos del renglón que corresponde a CoM, que representan el costo de teñir cualquiera de los N colores después de haber teñido el color CoM, se le asignan los costos reales determinados en el espectrocolorímetro. El esquema se presenta en la Tabla VI.

Tabla VI. Matriz de costos ampliada con renglón y columna correspondiente al último color de la serie teñida anteriormente

0

c12

c21

0

C13

...

c1,n

∞

...

∞

cn1 cn+1,1

∞

cn+1,2

...

...

0

∞

cn+1,n

0

Para el proceso de optimización utilizamos el conjunto de 36 colores mencionados en la Tabla IV y suponemos que el último color teñido de la secuencia previa, CoM, fue el color con coordenadas CIELab 57.51, 35.27, 63.59.

71

La secuencia óptima del conjunto de 36 colores se presenta en la Tabla VII, mientras que en la Tabla VIII presentamos la secuencia óptima encontrada con la condición de que el color CoM ocupe el primer lugar. Se observa al inicio de la secuencia un retorno de colores oscuros hacia colores más claros. Tabla VII. Secuencia óptima del conjunto de 36 colores Ordenamiento óptimo

Costo

1,2,3,4,5,6,7,11,12,10,9,8,13,15,22,24,26,29,34,32, 30,28,23,21,20,18,17,16,25,31,35,27,14,19,33,36

11.38

Tabla VIII. Secuencia óptima del conjunto de 36 colores con el uso previo del equipo para el color C°M. Ordenamiento óptimo

Costo

C°M,7,4,2,1,3,5,6,11,12,10,9,8,13,1522,24,26,29,34, 32,30,28,23,21,20,18,17,16,25,31,35,27,14,19,33,36

17.97

Es claro que, la condición de procesar un nuevo conjunto no se produce exactamente cuando se está terminando con el último elemento del conjunto anterior. En general, se tiene identificado un nuevo conjunto de n elementos cuando todavía faltan procesar q elementos del conjunto anterior. Determinando la sucesión óptima de todo el conjunto de q + n elementos se obtienen sucesiones de un costo menor. La condición que debe cumplirse es que los q elementos del conjunto anterior deben procesarse antes que ninguno de los elementos del nuevo conjunto. Si no se impusiera esta restricción se correría el riesgo de que se fuera postergando repetidas veces el procesamiento de un elemento determinado. Desde luego, además, se debe tener en cuenta, como en el caso anterior, cual fue el último color teñido. El aspecto más importante a destacar es que se puede optimizar el conjunto de q + n elementos, que cumplan la condición de que los q elementos que faltaban se procesen antes que los n elementos del nuevo conjunto, utilizando un algoritmo estándar para el ATSP, modificando de manera adecuada la matriz de costos. Para lograrlo se arma una matriz de costos orden q+n+1 con las siguientes sub-matrices: a) Una sub-matriz Q, de orden q, donde los elementos son los costos originales de los colores que faltaba procesar; b) Una sub-matriz N, de orden n, donde sus elementos son los costos de los colores del nuevo

72

conjunto; c) Una sub-matriz QN, de q renglones y n columnas, donde los elementos son los costos reales de pasar de un color del conjunto primitivo a un color del nuevo conjunto; d) Una sub-matriz NQ, de n renglones y q columnas, con los costos penalizados (M grande), para inhibir el paso de un color del nuevo conjunto a un color del conjunto anterior. Este artificio asegura que todos los colores del conjunto anterior se procesarán antes que cualquiera de los colores del nuevo conjunto; y, una columna con elementos suficientemente grandes (M grande) y un renglón con los costos reales entre el último color teñido y los q que faltan teñir. El costo entre el último color teñido y los n nuevos colores también debe estar penalizado (M grande). El esquema se muestra en la Tabla IX.

Tabla IX. Esquema de la matriz de costos ampliada para incorporar los colores que faltaba teñir del secuencia anterior

Sub-matriz Q, de orden q

Sub-matriz QN, de orden q X n ∞

Sub-matriz NQ, de orden n X q

Sub-matriz N, de orden n

∞

Cij

∞

0

6.2.2 Sensibilidad del ojo humano Desde un punto de vista industrial, el aspecto más importante no es encontrar una ruta óptima; es decir, una secuencia de colores con el costo matemático mínimo, si no teñir las telas en una secuencia de colores tal que la diferencia entre los colores obtenidos y los solicitados sea imperceptible al ojo humano. Es evidente que puede existir un a ruta de costo mínimo con una mayoría de costos pequeños y un costo grande. Si este costo (diferencia entre colores) es mayor que unas cierta cota (observable), entonces, la ruta óptima no es la adecuada en términos industriales. Para asegurar que ninguno de los colores obtenidos difiera del color solicitado en un grado observable, se debe buscar un camino donde los costos no excedan una cierta cota, K (el valor de la cota K depende de la posición que el color ocupa en el espacio CIELab). En la instancia resuelta de 36 colores, hay un costo que podríamos tomar como ejemplo de una diferencia observable. Suponiendo que este es el caso para

73

la diferencia causado en el color C28 cuando es teñido después del color C30 (C28,30 = 1.08). Para evitar esta diferencia observable, se debe “penalizar” la secuencia que la contendría; es decir, remplazar en la matriz de costos el valor que corresponde a C28,30 por un valor varios órdenes de magnitud mayor. En este ejemplo, es posible encontrar una secuencia que evite teñir el color C28 después del color C30. Aunque el costo total se ve incrementado (no es la secuencia óptima matemática), la ventaja es que un observador no detectaría una diferencia de color. En la Tabla X se muestran la secuencia original, que incluye el teñido del color C28 a continuación del teñido de C30, con un costo total de 11.38 y la secuencia obtenida al impedirlo mediante penalización. El costo de la nueva sucesión es 11.86. Tabla X. Secuencias de colores con y sin la restricción de evitar diferencias de color “observables” Sin restricción

1,2,3,4,5,6,7,11,12,10,9,8,13,15,22,24,26,29,34,32,30, 28,23,21,20,18,17,16,25,31,35,27,14,19,33,36

Costo = 11.38

Con restricción

1,2,3,4,5,6,7,11,12,10,9,8,13,15,22,24,26,29,34,32,30, 36,35, 33, 27,19,14,28,23,21,20,18,17,16,25,31

Costo = 11.86

Desde luego, no siempre es posible encontrar una secuencia que elimine todas las diferencias consideradas observables. En este caso, el equipo de teñido debe ser lavado. El tema del lavado de los equipos será tratado con amplitud más adelante.

6.2.3 Restricciones de tipo comercial En el parágrafo 4.2, al hablar sobre restricciones, explicamos que, en muchas oportunidades, por motivos de tipo comercial, no era posible respetar el orden establecido en la secuencia óptima y también, que en cada proceso de teñido se emplean alrededor de cinco horas. Para tener en cuenta el tiempo, incluiremos una restricción al problema de optimización (4.1). Si designamos por τ al tiempo que se emplea en el proceso de teñir una tela, el modelo de optimización tendrá la forma N-1 z(π) = Σ ∆π(i)π(i +1) i=1

(4.1)

74

sujeto a

π -1(j) ≤ tj/τ

(4.2)

donde πj-1 indica la posición del color Cj en la sucesión y t es el tiempo máximo permisible para realizar el teñido de la tela en ese color Cj. Las restricciones de tiempo son resueltas, generalmente, a través de “ventanas de tiempo” o penalizando el objetivo, pero se puede alcanzar el óptimo o soluciones cercanas al óptimo usando un algoritmo estándar para el ATSP iterativamente y alterando la matriz de costos (Maldonado 2001) [9]. Supongamos que necesitamos colocar un color C* en la posición k y que, cuando determinamos la sucesión óptima el color C* ocupa una posición posterior. Entonces, el método que hemos desarrollado consiste en resolver sucesivamente el problema para n-1 colores (eliminando C*) y reemplazando el costo ∆k-1,k, correspondiente a los colores que ocupan las posiciones k-1 y k en la sucesión óptima determinada, por el costo que correspondería a colocar al color C* entre esos dos colores; es decir, en la posición k. Esto es, resolvemos el problema para n-1 colores (sin el color C*); entonces, incrementamos en la matriz de costos el costo, ∆k-1,k, entre los colores que ocupan las posiciones k-1, k, a ∆’k-1,k . ∆’k-1,k = ∆k-1,j + ∆k,k = ∆k-1,k + δ donde, por la propiedad triangular (∆k-1,j + ∆j,k > ∆k-1,k ), δ > 0, y resolvemos el problema nuevamente. Si se obtiene la misma sucesión con ambos costos (con el costo original ∆k-1,k y el aumentado ∆’k-1,k), esto implica que la sucesión obtenida es óptima con el color C* en la posición k. Si la sucesión es distinta se repite el proceso, incrementando el costo entre los colores que queden en las posiciones k-1 y k, hasta que la sucesión obtenida permanezca invariable. Se puede demostrar que el proceso no es cíclico y converge a una solución acotada en un número de iteraciones proporcional a n2. Para demostrarlo, veamos en primer lugar que en la nueva sucesión se rompe el orden de precedencia Ck-1, Ck. Sea C1, C2, …, Ck-1, Ck, …, Cn-1, la sucesión óptima para n-1 colores, con costo Q Cambiamos el costo ∆k-1,k a ∆’k-1,k = ∆k-1,j + ∆k,k = ∆k-1,k + δ; entonces, el costo con el color C* en la posición k sería Q + δ

75

Si la sucesión, con C* en la posición k, no es óptima, entonces, el costo de la nueva sucesión óptima será Q’, con Q’ < Q + δ. Evidentemente, no puede mantenerse el orden de precedencia de los colores que estaban en las posiciones k-1 y k porque si se regresa su costo al valor original daría para la sucesión un costo menor que Q. Para repetir el proceso, incrementamos el costo entre los nuevos colores que queden en las posiciones k-1 y k. El costo de la sucesión con el color C* en la posición k, será Q’ + δ’. El costo de la nueva sucesión óptima será Q’’, con Q’’ < Q’ + δ’. En caso contrario, la sucesión anterior con C* en la posición k será la de menor costo. También, si Q’ + δ’ < Q + δ, el valor Q’ + δ’ se transforma en una nueva cota superior. Entonces, al encontrar la sucesión óptima se rompe el orden de precedencia de los colores que ocupaban las posiciones k-1 y k y el par anterior no puede rearmarlo. Por lo tanto, al incrementar el costo entre dos colores que ocupan posiciones contiguas k-1 y k, las sucesiones que se obtienen no contienen ninguno de los pares de colores que ocuparon esas posiciones. Así, el número máximo de iteraciones viene dado (n-1)(n-2) y existe una cota de valor conocido Q + δ para el máximo valor que puede tomar el costo de la sucesión con el color C* en la posición k. Repetimos el procedimiento de incrementar el costo de la manera expuesta hasta que se obtiene la misma sucesión o que el costo supera la cota Q + δ. Entonces, en esa sucesión podemos incorporar al color C* en la posición k. a) En todas las pruebass realizadas, obtuvimos la mejor solución en n/3 iteraciones en promedio. b) Se alcanzó el óptimo en el 60% de los casos. c) La mejor solución no estuvo nunca más alejada del óptimo que un 10%.

6.2.4 Series largas de colores Como es sabido, no existe aún un algoritmo capaz de resolver el problema del ATSP de manera eficiente. La dificultad básica de todos los métodos exactos es que el tiempo que se tarda para encontrar la solución óptima crece exponencialmente con el tamaño del problema –en nuestro caso, el número de colores. Sin embargo, el proceso de encontrar una secuencia óptima para un conjunto de colores del tamaño que es usual en la industria textil (N