(2022-2) maria.hernandez: Parece súper intimidante al principio por el uso de programas, pero el profesor cada clase explicaba paso por paso cómo modelar objetos relacionados a los encargos y cómo los archivos se deben configurar para ser llevados a la manufactura. Además de que siempre se nos proporcionaron tutoriales en video para poder trabajar desde casa. La mayor dificultad es la organización, ya que las máquinas de la U se pueden usar sólo con horas agendadas previamente!

CURSO: FLUJO EN REDES
TRADUCCION: NETWORK FLOWS
SIGLA: ICT2233
CREDITOS: 06 SCT-Chile / 10 UC
MODULOS: 03
TIPO DE ASIGNATURA: CATEDRA
CALIFICACION: ESTANDAR
DISCIPLINA: INGENIERIA


I. DESCRIPCION

El curso desarrolla los conocimientos necesarios para utilizar a nivel operativo los metodos y algoritmos de solucion de flujo en redes, a modo de aplicarlos a redes de transporte.


II. OBJETIVOS

1. Identificar matrices unimodulares y comprender su relevancia.

2. Distinguir la importancia de representar un problema a traves de un modelo multicommodity.

3. Detectar la estructura de grafo inherente en un problema de optimizacion.

4. Formular matematicamente problemas de optimizacion que ocurren sobre un grafo o red.

5. Manejar distintas estructuras y representaciones matriciales de grafos.

6. Determinar la complejidad de los algoritmos relacionados a los problemas ense?ados en este curso.

7. Resolver problemas clasicos de investigacion operativa en redes.

8. Abordar, a traves de metodos heuristicos y exactos, problemas complejos de transporte sobre una red como el problema del vendedor viajero, el problema de ruteo vehicular y sus extensiones.

9. Implementar computacionalmente algoritmos de solucion a problemas en redes.

10. Desarrollar la intuicion para el analisis y desarrollo de nuevos algoritmos.


III. CONTENIDOS

1. Introduccion a estructura de grafos: elementos y definiciones.

2. Estructuras de datos para representar redes y grafos.

3. Formulacion matematica de problemas de optimizacion en grafos o redes.

4. Orden de complejidad de algoritmos de solucion.

5. Clasificacion de problemas en redes segun complejidad.

6. Matrices unimodulares y su relevancia.

7. Problemas de flujo en redes a minimo costo (PFMC).

8. Casos particulares del PFMC: asignacion, clasico de transporte (Hitchcock), rutas minimas, ruta critica en proyectos, problema de flujo maximo, y aplicaciones. Extensiones a problemas con multiples flujos.

9. lgoritmos de rutas minimas: label correcting y label setting.

10. Algoritmo de Ford-Fulkerson para problemas de flujo maximo.

11. Teorema de flujo maximo y corte minimo.

12. Problemas de ruteo en arcos: grafo euleriano y problema del cartero chino.

13. Problemas de ruteo en nodos: circuito hamiltoniano y problema del vendedor viajero.

14. Problemas de ruteo vehicular.

15. Metodos de solucion para problemas de ruteo: metodos heuristicos y exactos.

16. Localizacion optima de instalaciones en redes.


IV. METODOLOGIA

- Clases expositivas.
- Ayudantias.
- Resolucion de problemas.


V. EVALUACION

- Trabajo de programacion.
- Pruebas.
- Proyectos y/o tareas.


VI. BIBLIOGRAFIA

Minima:

Ahuja, R., T. Magnanti y J. Orlin. Network Flows: theory, algorithms and applications. Prentice-Hall, 1993.

Papadimitriou, C. y K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. 2? Ed. Mineola, NY.: Dover Publications, Inc., 1998.

Coplementaria:

Ball, M. O., T. L. Magnanti, C. L. Monma y G. L. Nemhauser, eds. Network Routing. Handbooks in Operations Research and Management Science. Vol. 8. Amsterdam, North Holland: Elsevier Science, 1995.

Evans, J. y E. Minieka. Optimization Algorithms for Networks and Graphs. 2? Ed. Monticello, NY.: Marcel Dekker, Inc., 1992.



PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
ESCUELA DE INGENIERIA / AGOSTO 2015