PROGRAMA DE CURSO
Código Nombre
MA3701 Optimización
Nombre en Inglés
Optimization
Unidades Horas de Horas Docencia Horas de Trabajo
SCT
Docentes Cátedra Auxiliar Personal
6 10 3 2 5
Requisitos Carácter del Curso
MA2002 Cálculo Avanzado y Aplicaciones CFB, curso de Licenciatura
obligatorio para Ingeniería Civil
Matemática
Resultados de Aprendizaje
El alumno sabrá resolver problemáticas que aparecen en el modelamiento de
problemas de ingeniería con herramientas de optimización lineal y no-lineal tanto
continua como entera, con o sin restricciones, y utilizar algunos algoritmos adecuados.
El alumno sabrá utilizar paquetes computacionales útiles en la resolución de
problemas de optimización.
Metodología Docente Evaluación General
Clases teóricas, demostrando solamente lo Tres controles y un examen¹.
esencial y ejercicios para trabajo personal.
Nota de tarea: 20%, se aprueba por separado.
Una tarea consistente en modelar
completamente un problema complejo y
resolverlo usando software libre de la Web.
Resumen de Unidades Temáticas
Número Nombre de la Unidad Duración en
Semanas
1 Principales clases de problemas en programación matemática. 1.0
2 Programación Lineal 6.0
3 Introducción a los problemas lienales de gran tamaño 1.0
4 Optimización sin restricciones 3.0
5 Optimización con restricciones 3.0
6 Programación dinámica 1.0
TOTAL 15.0
1 Según el artículo 35 del reglamento de estudios FCFM, el profesor tiene la facultad de realizar un examen oral a un estudiante. Esta instancia
podrá darse, por ejemplo, cuando el alumno presente inasistencias reiteradas a los controles. De ser examinado en ambas formas (escrita y oral),
recibirá calificaciones parciales separadas, las que se promediarán aritméticamente para dar la calificación del examen.
Unidades Temáticas
Número Nombre de la Unidad Duración en Semanas
1 Principales clases de problemas en programación 1.0
matemática.
Resultados de Aprendizajes de la Referencias a
Contenidos
Unidad la Bibliografía
1.1 Resolución de problemas El alumno deberá comprender y Wagner
simples de programación clasificar los distintos tipos de Hillier-
lineal, programación entera y problemas de optimización Liebermann
programación no-lineal con o (lienales, enteros, no lineales,
sin restricciones. estructuras de grafos, etc).
1.2 Ejemplos de problemas
reales.
Número Nombre de la Unidad Duración en Semanas
2 Programación Lineal 6.0
Resultados de Aprendizajes de la Referencias a
Contenidos
Unidad la Bibliografía
2.1 El método Simplex: desarrollo El alumno comprende el algoritmo Chvatal
analítico e interpretación Simplex y su aplicación a diferentes
gráfica. tipos de problemas, incluyendo
problemas de flujos en redes y
2.2 Problema dual: para problemas de programación
planteamiento y propiedades entera.
con respecto al primal.
Interpretación Económica. Sabe distinguir comprender e
interpretar la noción de dualidad.
2.3 Nociones de análisis post- El alumno puede hacer análisis de
optimal (variación del lado sensibilidad en casos simples, a
derecho, variación de los través del cual comprende el
costos, agregar columna, concepto de estabilidad.
agregar fila).
2.4 Aplicaciones a la producción y
el transporte.
2.5 Noción de grafo y problemas
lineales representables en
grafos (enunciar problema
flujo de costo mínimo y los
casos particulares: transporte,
asignación, camino más corto,
flujo máximo).
2.6 Algoritmos de flujos en redes:
transporte, flujo máximo,
camino más corto.
2.7 Motivos de no-linealidad en
grafos.
2.8 Programación lineal entera:
método de ramificación y
acotamiento. Verlo a través
de un ejemplo ilustrativo.
Número Nombre de la Unidad Duración en Semanas
3 Introducción a los problemas lienales de gran 1.0
tamaño
Resultados de Aprendizajes de la Referencias a
Contenidos
Unidad la Bibliografía
3.1 Introducción. El alumno sabe identificar casos de
optimización lineal en la que se
3.2 Noción de descomposición. pueden aplicar métodos de
Entre ellos Dantzig-Wolfe. descomposición.
3.3 Ejemplos
Número Nombre de la Unidad Duración en Semanas
4 Optimización sin restricciones 3.0
Resultados de Aprendizajes de la Referencias a
Contenidos
Unidad la Bibliografía
3.1 Condiciones de Optimalidad El alumno conoce y aplica la noción
de 1er. y 2do. orden. fundamental de algoritmos de
descenso,
3.2 Nociones de búsqueda basado en la búsqueda sobre una
unidimensional: Golstein-Armijo, dirección dada.
dicotomía, Fibonacci y otras.
Conoce y aplica las condiciones de
3.3 Método del gradiente y su optimalidad de primer y segundo
tasa de convergencia (lineal). orden en el caso diferenciable y se
introduce la idea en el caso no
3.4 Familia de algoritmos de tipo diferenciable.
gradiente conjugado. Ejemplo:
algoritmo de Fletcher y Reeves y El alumno comprende
otros. los distintos conceptos de los tipos
de convergencia: lineal,
3.5 Algoritmo de Newton, cuasi- superlioneal, cuadrática a través de
Newton (DFP y BFGS) y tasas de la revisión de
convergencia (convergencia métodos específicos.
cuadrática en caso particular de
Newton).
Número Nombre de la Unidad Duración en Semanas
5 Optimización con restricciones 3.0
Resultados de Aprendizajes de la Referencias a
Contenidos
Unidad la Bibliografía
4.1 Nociones de convexidad y El alumno comprende cabalmente
separación de convexos. Teorema las condiciones necesarias y
de Farkas. suficientes de optimalidad con
restricciones.
4.2 Condiciones de Optimalidad
de 1er orden. Definiciones: Conoce los conceptos de dirección
admisible, dirección de descenso y
dirección admisible, dirección de
en general como se construye el
descenso. Teorema de Karush- Teorema de Kuhn-Tucker como
Kuhn-Tucker. una idea de separación de
convexos.
4.3 Nociones de sensibilidad e
interpretación económica. Sabe las limitaciones del Teorema
de Kuhn-Tucker y conoce algunas
4.4 Método de direcciones de sus aplicaciones en economía.
admisibles (caso restricciones
lineales). Conoce y aplica correctamente
métodos de direcciones clásicos,
4.5 Método de penalidad, de direccions admisibles y de
barrera. penalización de barrera.
4.6 Introducción del concepto de
sub-gradiente y optimización no-
diferenciable.
Número Nombre de la Unidad Duración en Semanas
6 Programación dinámica 1.0
Contenidos Resultados de Aprendizajes de la Referencias a
Unidad la Bibliografía
5.1 Fundamentos teóricos de la El alumno conoce las nociones
programación dinámica: básicas de la programación
optimalidad, noción de estado, dinámica y el Principio de Bellman.
ecuación funcional (principio de
Bellman).
5.2 Aplicaciones: problema de la
mochila, problema de
producción, portafolio de
inversiones, etc.
Bibliografía
• Bazaraa, M. y Sheltly, C., Nonlinear Programming, Wiley, (1979).
• Chvatal, V., Linear Programming, Freeman & Co. (1983).
• Dakin, R., A Tree Search Algorithm for Mixed Integer Programming Problems. The
Computer Journal 8 (1965), 250-255.
• Hillier, F., Lieberman, G., Introducción a la Investigación de Operaciones, Mcgraw Hill-
Interamericana, 6 ed, 1997.
• Luenberger, D., Introduction to Linear and Nonlinear Programming, Addison-Wesley,
(1973).
• Marsten, R. & Morin, T., A Hybrid Approach to Discrete Mathematical Programming.
Mathematical Programming 14(:1)(1978), 21-40.
• McCormick, G., Nonlinear Programming, John Wiley (1983). New York, Mac Graw-Hill,
1970.
• Minoux, M., Programmation Mathematique, Tomo I y II. Dunod (1983).
• Murthy, K., Linear and Combinatorial Programming, Wiley, (1976).
• Ortega, J.M., Rheinbolt, W.C., Iterative solution of nonlinear equations of Several
Variables. New York, Academic Press, (1970).
• Polak, E., Computational Methods in optimization. New York, Academic Press, (1971).
• Rockafellar, R.T., Convex Analysis. New Jersey, Princeton University Press, (1970).
• Shapiro, J.F., Mathematical Programming: Structures and algorithms, John Wiley &
Sons, (1979).
• Wagner, H., Principles of Operations Research, Prentice Hall, (1975).
Vigencia desde: Primavera 2009
Elaborado por: Jorga Amaya
Revisado por: Axel Osses (Jefe Docente)
