|
|
Programa IO
|
|
| |
| |
Programa de
la materia |
|
| |
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. |
|
| |
principal |
|
|
|
