FLUJOS EN REDES
Objetivos
Se pretende que el alumno conozca los conceptos y algoritmos más importantes de Flujos en Redes, así como sus aplicaciones más inmediatas. En este sentido, se insiste en la modelización de problemas reales y se enfatizan los aspectos algorítmicos, i.e. de resolución, de los problemas estudiados.
Programa Teoría
1.- Definiciones y conceptos previos.
Grado, caminos, conectividad, cortaduras, árboles, etc. Representaciones de redes. Problemas de flujos. Flujo de coste mínimo, flujo máximo, asignación, etc. Aplicaciones. Complejidad algorítmica.
2.- Flujo máximo.
Definición y aplicaciones. Flujos y cortaduras. Método de los caminos aumentados. Etiquetado. Teorema del flujo máximo - cortadura mínima y sus consecuencias. Algoritmos avanzados. Casos especiales. El problema de la cortadura mínima.
3.- Flujo de coste mínimo.
Introducción y aplicaciones. Condiciones de optimalidad. Algoritmo Simplex en redes. Soluciones árbol. Arboles fuertemente posibles. Análisis de sensibilidad. Aplicaciones: Problema de Transporte, Problema de Asignación. Problema del Cartero Chino Dirigido.
4.- Problemas de flujos más generales.
Problemas de flujos con costes convexos. Flujos generalizados. Flujos multiterminales. Aplicaciones.
Programa Prácticas
Las prácticas de la asignatura incluirán la resolución de problemas y cuestiones relacionadas con cada tema teórico, la modelización de problemas de flujos en redes y el uso de distintos códigos para su resolución por ordenador.
Bibliografía
- Ahuja, R., Magnanti, T. & Orlin, J. (1993) "Network Flows". Ed. Prentice Hall.
- Christofides, N. (1975) "Graph Theory. An algorithmic approach". Ed. Academic Press.
- Hu, T.C. (1982) "Combinatorial Algorithms" . Ed. Addison-Wesley.
- Kennington, J.L. & Helgason, R.V. (1980) "Algorithms for network programming". Ed. John Wiley & Sons.
- Lawler, E.L. (1976) "Combinatorial Optimization: Networks & Matroids" Ed. Holt, Rinehart and Winston.
- Bondy, J.A. & Murty, U.S. (1976) "Graph Theory with applications". Ed. MacMillan Press.
- Even, S. (1979) "Graph Algorithms" Ed. Computer Science Press Inc.
- Swamy, M.N. & Thulasiraman, K. (1981) "Graphs, networks and algorithms" Ed. John Wiley & Sons Inc.
- Bondy, J.A. & Murty, U.S. (1976): "Graph Theory with Applications". Ed. MacMillan Press.
- Christofides, N. (1975): "Graph Theory: An Algorithmic Approach" Ed. Academic Press.
- Even, S. (1979): "Graph Algorithms" Ed. Computer Science Press Inc.
- Swamy, M.N. & Thulasiraman, K. (1981) "Graphs, networks and algorithms" Ed. John Wiley & Sons Inc.
|
|
|
|