1. Programación lineal: Ejemplos de problemas de programación lineal. Forma standard. Soluciones básicas y soluciones factibles. Teorema fundamental de la programación lineal. Dualidad: lema de Farkas, teorema de dualidad, teorema de holgura complementaria. Transformaciones pivote. Algoritmo simplex. Algoritmo dual. Algoritmo simplex revisado.
2. Grafos y algoritmos: Grafos dirigidos y no dirigidos. Caminos y ciclos. Matriz de incidencia vértice-rama. Grafos bipartitos. Arboles y forestas. Grafos planares. Tabla de adyacencia. Algoritmo search. Spanning tree mínimo: algoritmo de Kruskal y algoritmo de Prim. Caminos dirigidos de mínimo costo: método de programación dinámica, algoritmo de Dijkstra y algoritmo de Ford – Bellman. Aplicación del algoritmo de Ford – Bellman en la búsqueda de ciclos dirigidos de costo negativo.
3. Máximo flujo y mínimo corte: Conceptos de flujo y valor del flujo. El problema de máximo flujo. El problema de mínimo corte. Algoritmo de Ford – Fulkerson. Aplicaciones: máximo matching y mínimo cover en un grafo bipartito, cierre óptimo en un grafo dirigido, elección de localidades, asignación de tareas, el problema del transshipment, el problema del torneo, el problema de circulación, el problema del transporte.
4. Flujo de mínimo costo: Descripción del problema de flujo de mínimo costo. Optimalidad de una solución factible. Algoritmo para resolver el problema de flujo de mínimo costo. Eliminación de las restricciones de capacidad. El método “simplex” para un grafo conexo y su aplicación para resolver el problema del transporte.
5. Programación lineal entera: Ejemplos de problemas que se pueden plantear por programación lineal entera: el problema de la mochila, el problema de la carga fija, condiciones “either ... or”, funciones objetivo no lineales, variables discretas, el problema de recortar el stock, scheduling, el problema de los cuatro colores, el problema del viajante, cuadrados latinos ortogonales, el problema SAT. El método de branch and bound. Aplicación de branch and bound para la resolución del problema de programación lineal entera. Aplicación de branch and bound para la resolución del problema del viajante.
BIBLIOGRAFIA
Notas de clase (1er. Cuatrimestre 1999).
Linear Programming (Bazara et al, 1997).
Optimization Algorithms (Evans & Minieka, 1992).
Neetwork flows (Ahuja et al, 1993).
Linear Programming (Chavatal, 1983).
Cook et al, "Combinatorial Optimization" 1998.
Nemhauer & Wolsey, "Integer and Combinatorial Optimization" 1988.
CORRELATIVAS: Probabilidades y Estadística - Introducción a la Computación