Ma-95-075. Programación de flujos sobre redes.
Datos generales:
Carga
académica: 3-0-8
Requisitos: In95841
Objetivo General: El objetivo de este
curso es dar una introducción a la teoría, el diseño y el análisis de
algoritmos, así como a las aplicaciones de los flujos determinísticos sobre
redes.
Temas
y subtemas:
Descripción
I. Modelación
con redes (6 horas)
Objetivo:
Respresentar situaciones prácticas utilizando el paradigma de flujos en
redes.
El problema lineal puro del flujo de costo
mínimo.
El problema del transporte.
El problema de asignación.
El problema del camino más corto.
El problema del flujo máximo.
El problema generalizado de flujos.
II. Algoritmos para el problema puro de costo
mínimo (7 horas)
Objetivo:
Analizar las opciones para resolver el problema de costo mínimo.
Propiedades de la matriz de restricciones.
Representación de vectores no básicos en
términos de vectores básicos.
El método simplex para el problema de flujos en
redes.
Soluciones iniciales.
III Formas especiales (7 horas)
Objetivos:
Analizar extensiones del método simplex a los problemas de flujos en
redes.
Flujos con cotas superiores e inferiores.
El tablero simplex asociado con un problema de
flujos en redes.
Estructuras para implementar el simplex en
redes.
Degeneración, ciclaje y atoramiento.
IV. Algoritmo Out-of-Kilter (7 horas)
Objetivos:
Presentar los conceptos de algoritmos que no son primales.
Formulación de un flujo en formato out-of-kilter.
Estrategia del algoritmo
Resumen del algoritmo
Procedimientos para implementar el algoritmo.
V Problemas de camino más corto (7 horas)
Objetivos:
Describir y analizar diferentes problemas de casmino más corto y
posibles algoritmos para su solución.
Algunas formulaciones.
Ecuaciones de Bellman.
Redes acíclicas.
Redes con arcos positivos.
Solución mediante aproximaciones sucesivas.
Método de Bellman-Ford.
Interpretación mediante programación lineal.
Caminos más cortos entre todos los pares de nodos.
Multiplicación matricial.
Método de Floyd-Warshall
Detección de ciclos negativos.
VI. Flujos máximos (7 horas)
Objetivos:
Desarrollar algoritmos que permitan encontrar el máximo flujo que puede
ser enviado a través de una red donde sus arcos tienen capacidad finita.
Flujos maximales
Algoritmo de flujo máximo
Eficiencia del algoritmo
El teorema Máx-flujo Min-corte
Implicaciones combinatorias del teorema.
Interpretación de programación lineal del
teorema.
VII. Flujos de múltiples productos (7 horas)
Objetivos:
Extender el problema al caso en el cual existan diferentes flujos en la
red que deban de distiguirse.
Descripción del problema.
Dificultades para resolverlo.
El principio de Descomposición de Dantzig-Wolf
Aplicación del principio de descomposición al
problema.
Textos: Bazaraa, M.S., J.J. Jarvis and H.D. Sherali, Linear Programming and Network Flows, Wiley, 1990
Lawler, E., Combinatorial Optimization, Networks and Matroids, Holt, Rinehart, Winston, 1976