|
|
|
| 1. Introducción a la optimización
|
|
1. 1.1. Problemas
2. 1.2. Optimos locales y globales
3. 1.3. Conjuntos y funciones convexas
4. 1.4. Problemas de programación convexa |
|
|
| 2. Programación Lineal: el Algoritmo Simplex
|
|
1. 2.1. Programación lineal
2. 2.2. Soluciones básicas posibles (sbp)
3. 2.3. Geometría de la programación lineal
4. 2.4. Pivoteo, organización de la tabla, algoritmo simplex |
|
|
| 3. Dualidad
|
|
1. 3.1. Dual de un programa lineal
2. 3.2. Distensión complementaria
3. 3.3. Lema de Farka
4. 3.4. Algoritmo simplex dual |
|
|
| 4. Complejidad del algoritmo simplex
|
|
1. 4.1. Computabilidad, cotas de tiempo, tamaño de la entrada
2. 4.2. Complejidad y análisis de algoritmos
3. 4.3. El algoritmo simplex no es polinomial
4. 4.4. Algoritmos polinomiales para programación lineal |
|
|
| 5. Algoritmos primales-duales
|
|
1. 5.1. Algoritmo primal-dual
2. 5.2. Algoritmo aplicado al problema de caminos cortos en un grafo |
|
|
| 6. Algoritmos para máximo flujo, apareamiento, camino más corto, árboles con cobertura total
|
|
1. 6.1.Algoritmo de Ford-Fulkerson para máximo flujo
2. 6.2. Algoritmo de Dijkstra para caminos cortos
3. 6.3. Algoritmos para apareamiento
4. 6.4. Algoritmos para árboles mínimos con cobertura total |
|
|
| 7. Programación lineal entera
|
|
1. '7.1. Problema. Unimodularidad total.
2. '7.2. Problemas NP difíciles
3. '7.3 Cotas para soluciones. Cortaduras de Gomory. |
|
|
| 8 Otros algoritmos
|
|
1. 8.1. Aproximación
2. 8.2. Acote y ramificación
3. 8.3. Programación dinámica
4. 8.4. Búsqueda local |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
INFORMACIÓN IMPORTANTE