El Problema de acoplamiento en gráficas bipartitas.

Abstract

La palabra acoplamiento significa literalmente formar parejas. Si se tiene un conjunto finito de elementos con los que se pueden formar parejas, se representa la situación con una gráfica que tenga un vértice por cada elemento, donde una arista entre dos vértices significa que los elementos representados por tales vértices pueden forman pareja, pero además las parejas no deben tener un vértice en común. En los problemas de acoplamiento en gráficas, la idea más general consiste en encontrar subconjuntos de aristas que cumplen ciertos criterios de optimización, donde los parámetros involucrados pueden ser el número de aristas en la solución, el número de vértices que son extremos del total de aristas o el peso asociado a las aristas. En éste trabajo sólo se estudiarán dos tipos de problemas de acoplamiento los cuales son: Acoplamiento de Cardinalidad Máxima y Acoplamiento con Peso (problema de asignación), ambos en gráficas bipartitas. Los problemas de acoplamiento se estudiaron por mucho tiempo tanto en Análisis Combinatorio como en Investigación de Operaciones, llamando la atención de muchos investigadores interesados por sus múltiples aplicaciones tales como: sistema de representantes distintos, problema de cubrimiento, descomposición en cadenas, cuadrados latinos, problema del matrimonio, calendarización de vuelos, encole de locomotoras, etc. y sus diversas variantes. Sin embargo, en 1957 Claude Berge fue el primero en plantear estos problemas usando el concepto de trayectoria aumentante. El demostró que un acoplamiento es máximo si y sólo sí no hay trayectoria aumentante, éste es un resultado clásico de Optimización Combinatoria él. cuál es la base de los algoritmos más eficientes para resolver los problemas de acoplamiento. El método húngaro para la solución del problema de acoplamiento con peso (problema de asignación) está fundamentado en el trabajo de dos Matemáticos Húngaros, D. Koning y J. Egerváry, y particularmente en el teorema dado por Koning, este teorema fue establecido y demostrado en términos de teoría de gráficas. Una prueba de este teorema usando teoría de gráficas fue dada por Kuhn en 1955 quien desarrolló un algoritmo para obtener n ceros independientes (en distinto renglón y distinta columna) de una matriz obteniendo un acoplamiento de cardinalidad máxima en una gráfica bipartita asociada. Este algoritmo está basado en el trabajo de los matemáticos húngaros Koning y Egerváry. En honor a ellos le llamó a este Método Húngaro o Algoritmo Húngaro. Este trabajo condujo al siguiente afio, al método primal-dual para obtener el acoplamiento de pes6 máximo en gráficas generales. Este trabajo tiene por objeto el análisis y desarrollo de los fundamentos teóricos de los principales métodos de solución de problemas de acoplamientos. Así como su implementación para la solución de problemas de aplicación. Para lograr los objetivos anteriores se proporciona una presentación lo más sencilla posible, cuidando principalmente un enfoque algorítmico que permita una fácil implementación en computadora de los algoritmos más eficientes. Por lo cual los conceptos y resultados teóricos presentados en este trabajo son sólo los necesarios, sin embargo, se incluye un apéndice y una amplia bibliografía. Debido a que al modelar problemas prácticos por lo regular resultan de tamaño considerables, para su solución es imprescindible la implementación de algoritmos eficientes. Los algoritmos fueron implementados en Turbo pascal utilizando estructura de datos para la representación y manipulación de una gráfica. El contenido de este trabajo se desarrolló de la siguiente manera: El capítulo I consta de una visión intuitiva de algunos tipos de problemas de acoplamiento, su aplicación a distintos problemas reales, formulación del problema y análisis comparativo de los principales métodos de solución. En el capítulo II se dan los conceptos básicos de teoría de gráficas y acoplamiento, para enunciar y demostrar los teoremas fundamentales de Berge, Hall y Koning, tales teoremas proporcionan las bases de los algoritmos que se utilizan en este trabajo para resolver el problema de acoplamiento. También se da la implementación del algoritmo y se concluye este capítulo resolviendo un ejemplo. En el capítulo III se desarrolla el método húngaro, así como la justificación de sus pasos y su convergencia. Debido a que el método húngaro es tipo primal-dual se requerirá de resultados de dualidad lineal. Además, se da la transformación de un problema de minimización a uno de maximización y también se da la implementación computacional de este método y se resuelve un ejemplo. Finalmente se dan las conclusiones, bibliografía y apéndice que contiene los teoremas básicos de dualidad lineal y la solución de los problemas planteados en el capítulo I.