Optimización Lineal

Martes y Jueves 2:00-4:00pm

Salón TM-201

Texto:
  • Introduction to Linear Optimization. D. Bertimas y J.N. Tsitsiklis
Fecha Tema Ejercicios
19/01 Introducción. Ejemplos. 1.6,1.12
21/01 Poliedros y sus "esquinas". Existencia de puntos extremos. 2.5,2.7
26/01 Optimalidad puntos extremos. Proyección de poliedros. Representación de politopos. 2.12,2.14
28/01 Problema dual. Teorema de dualidad debil. 4.3,4.4
09/02 Teorema del hiperplano separador. Lema de Farkas. Dualidad fuerte 4.6,4.26
11/02 Representación de poliedros. 4.10,4.21
16/02 Poliedros en forma estándar. 4.19,2.10
18/02 Método simplex. 3.1,3.3
23/02 Método simplex cont. Simplex dual. 3.6,3.7
08/03 Análisis de sensibilidad local. 5.1, 5.6(a)
10/03 Análisis de sensibilidad global. 5.6 (el resto)
15/03 Análisis de sensibilidad global. Generación de columnas. 5.4, ejercicio dado en clase.*
17/03 Planos de corte. Descomposición de Dantzig-Wolfe. Resuelva el problema de los cortes con W=70, tamaños 10,11,..,19 y demanda 150 para cada tamaño.*
05/04 Descomposición de Dantzig-Wolfe. Programación estocástica. 6.3,6.4
07/04 Programación estocástica. Descomposición de Benders. Grafos y redes. Resolver el problema del ejemplo 6.5 con estos datos. Formule primero el problema completo y luego use el método de descomposición de Benders. Compare el tiempo de cómputo.
12/04 Redes. Simplex para redes. -
14/04 Simplex para redes. Algoritmo de Bellman-Ford para el camino más corto. 7.2,7.9
19/04 Algoritmos de Bellman-Ford y Dijkstra para el camino más corto. Flujo máximo. 7.36,7.38
21/04 No clase 7.20,7.23
* Se entrega la primera semana de abril.
Tareas (50%): Se asignarán uno o dos ejercicios todas las clases y se deben entregar una semana después de haber sido asignados.
Parcial (25%): El parcial es para la casa y cubre los primeros 4 capítulos del texto.
Proyecto (25%): El proyecto consiste en resolver un problema real de gran escala. El problema es escojido por el estudiante y es responsable de obtener los datos necesarios para resolver el problema. Se debe entregar una descripción del proyecto y la forma como piensa obtener los datos junto con el parcial. Para resolver el problema se debe usar el servidor gratuito NEOS.