Problema de embotellamiento y aplicaciones

Abstract

La presente monografía está dedicada a problemas clásicos de la Investigación Operativa bajo un enfoque distinto: la optimización en el mayor de los coeficientes del problema. La dificultad de abordar bajo este objetivo problemas que ya de por sí son irresolubles en un tiempo computacional razonable, hace que en la actualidad esté casi sin explorar. Se han seleccionado por su envergarudra los problemas de transporte, asignación cuadrática y de rutas para ampliar su estudio y ofrecer soluciones alternativas a un objetivo clásico, como es la optimización en la suma de las componentes de los coeficientes del problema. Se considera en la presente monografía el problema de embotellamiento tal y como viene definido por Burkard en 1973 con la formulación alternativa de Punnen, así como para el problema cuadrático. Se presentan algoritmos de resolución, tanto generales como aproximados, así como su planteamiento mediante la Teoría de Grafos. Se presentan diferentes teoremas clásicos en la literatura que permiten caracterizar las soluciones óptimas, bajo un enfoque común establecido en la monografía, de una Teoría General del Embotellamiento. Se analizan los diferentes casos particulares: transporte, asignación, localización, viajante, lexicográfico, petición, árbol soporte biconexo, capacidad, camino mínimo, emparejamiento, árboles de Steiner y sus variantes, ancho de banda, entre otros. Por último se presentan las aplicaciones más notables existentes en la literatura.