• Modelar y resolver diferentes problemas de programación lineal en su forma general y en sus formas particulares.
• Conocer las bases teóricas y las aplicaciones de los diferentes métodos para resolver problemas de programación lineal y optimización combinatoria.
• El alumno deberá ser capaz de resolver los problemas asignados dentro de algún ambiente computacional. Cuando la complejidad computacional sea mayor, el alumno deberá ser capaz de programar la solución del problema en algún lenguaje de alto nivel.

Contenido sintético

1. Introducción

1. Problemas de optimización lineal.
2. Programación lineal en el plano.

2. El Método Simplex

1. Soluciones básicas factibles.
2. Pivoteo.
3. Criterios de optimalidad.
4. Soluciones degeneradas y ciclado.
5. Métodos de dos fases.
6. Método simplex revisado.

3. Dualidad

1. Problemas duales.
2. Teorema de dualidad.
3. Dualidad y análisis de sensibilidad.
4. El método simplex dual.
5. El método primal-dual.

4. Optimización Combinatoria

1. Elementos de teoría de gráficas.
2. Árboles generadores con peso mínimo.
3. Trayectorias más cortas.
4. Acoplamientos máximos en gráficas bipartitas.
5. Flujos en redes.

Modalidades de conducción del proceso de enseñanza-aprendizaje

• Los temas serán expuestos por el profesor.

Modalidades de evaluación

• Al menos dos evaluaciones periódicas y/o una evaluación terminal: 60%.
• Tareas y ejercicios: 20%.
• Elaboración de un reporte escrito sobre algún tema de aplicación: 20%.

Bibliografía

1. Bazaraa, M.S., Jarvis, J.J. & Sherali, H.D., Linear Programming and Network Flows. Second edition, John Wiley & Sons Inc., New York, 1990.
2. Bondy J.A. & Murty U.S.R., Graph Theory with Applications. North Holland, 1990.
3. Chvátal, V., Linear programming. A series of Books in the Mathematical Sciences. W.H. Freeman and Co., New York, 1983.
4. Cook, W., Cunningham, J., Pulleyblank, W.H. & Schrijver, A., Combinatorial Optimization. Wiley-Intersciences Ser. in Discrete Mathematics and Optimization. A Wiley-Interscience Pub. John Wiley & Sons, Inc., New York, 1998.
5. Ford, L.R. Jr. & Fulkerson, D.R., Flows in Networks. Princeton University Press, 1962.
6. Hillier, F.S., Lieberman, G.J. & Liberman, G.J. Introduction to Operations Research. MacGraw Hill, Science/Engeneering/Math. 7th. Ed., 2002.
7. Korte, B. & Vygen, J., Combinatorial optimization. Theory and algorithms. Algorithms and Combinatorics, 21. Springer-Verlag, Berlin, 2000.
8. Luenberger, D.G., Introduction to Linear and Nonlinear Programming, Second Edition. Addison Wesley, 2003.
9. Papadimitriu, C.H. & Steiglitz, K., Combinatorial Optimization Algorithms and Complexity [unabridged]. Dover Pubs. , 1998.