Actuaría (plan 2006) 2024-1

Optativas, Programación Entera

Programación entera

En el curso se estudiarán las propiedades de problemas de optimización lineal discreta. El objetivo principal es proporcionar elementos necesarios para la formulación, análisis y solución del modelo general de programación entera así como especializaciones para algunos de los problemas clásicos.

Se analizará la complejidad de este tipo de modelos y se dará una visión general de las heurísticas.

En el temario se contemplan los siguientes puntos.

Temario

1. Introducción
2. Formulación de problemas enteros y algunas aplicaciones
3. Planos de corte
4. Ramificación y acotamiento
5. Teoría de complejidad
6. Problemas específicos (Acoplamientos, Mochila, Asignación, Agente viajero)
7. Visión general de algoritmos aproximativos (Glotón, Mejoras sucesivas, Recocido simulado)
8. Otros problemas

Requisitos para el curso

Es indispensable haber cursado Investigación de Operaciones o Programación Lineal y recomendable cursar del quinto semestre en adelante.

Bibliografía básica:

• Chen, D.S., Batson, R.G. and Dang, Y. (2010). Applied Integer Programming: Modeling and Solution. John Wiley & Sons.

• Hillier, F.S. and Lieberman, G.J. (2009). Introduction to Operations Research (9a edición). Mc Graw Hill.

• Nemhauser, G.L., and Wolsey, L.A. (1999). Integer and Combinatorial Optimization. John Wiley & Sons.

• Papadimitriou, C.H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.

• Taha, H.A. (2010). Operations Research: an Introduction (9a edición). Prentice Hall/Pearson Education.

• Winston, W.L. (2003). Operations Research: Applications and Algorithms (4a edición). Prentice Hall-Kent.

• Wolsey, L.A. (1998). Integer Programming. John Wiley & Sons.

Evaluación

Los alumnos deberán realizar obligatoriamente:

1. Tareas en equipo (30% de la calificación final si el promedio de los parciales es aprobatorio)
2. Exámenes parciales (3) individuales (50% de la calificación final)
3. Presentación escrita y oral de un proyecto relacionado con los temas vistos. (20%de la calificación final)
4. Tareas pequeñas individuales (servirán para afianzar algunos conceptos)
5. Exposiciones de algunos de los problemas resueltos en tareas o exámenes

En caso de que el promedio de exámenes no sea aprobatorio, se tendrá la opción de presentar examen final que contará 70% de la calificación final o de reponer uno de los parciales.

También podrán programar de manera opcional, algunos de los algoritmos vistos en clase y con ello subir el promedio de las tareas.