Contenidos mínimos
Ejemplos de problemas de programación lineal. Forma standard. Soluciones básicas y soluciones factibles. Teorema fundamental de la programación lineal. Dualidad, teorema de la dualidad. Teorema de la holgura complementaria. Algoritmo simplex. Algoritmo dual. Algoritmo simplex revisado. Grafos dirigidos y no dirigidos. Caminos y ciclos. Matriz de incidencia vértice-rama- Grafos bipartitos. Árboles y forestas. Grafos planares. Tabla de Adyacencia. Algoritmo search. Caminos dirigidos de mínimo costo., método de programación dinámica. Conceptos de flujo y valor de flujo. El problema de máximo flujo. El problema de mínimo corte. 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 de transhipment, el problema del torneo, el problema de circulación, el problema del transporte. Programación lineal entera. Ejemplos: el problema de la mochila el problema de la carga fija, variables discretas, el problema de recortar el stock, scheduling, el problema de los cuatro colores, el problema del viajante. El método 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.