Problema de embotellamiento y aplicaciones
- SIMON DE BLAS, CLARA
- Francisco José Cano Sevilla Director
- José Simón Martín Co-director
Universidade de defensa: Universidad Complutense de Madrid
Fecha de defensa: 03 de setembro de 2004
- Francisco Javier Yáñez Gestoso Presidente
- María Teresa Ortuño Sánchez Secretaria
- Laureano Fernando Escudero Bueno Vogal
- Martin Francisco Javier Quintana Vogal
- Antonio Pérez Prados Vogal
Tipo: Tese
Resumo
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.