MATERIA: Programación Entera

CLAVE: COMP-470

SEMESTRE DE UBICACION: Cuarto

AREA: Matemáticas

OBJETIVOS: Proporcionar al alumno los conocimientos que le permitan comprender la dificultad del paso de la Programacion Lineal a la Programacion Entera, conocer las aplicaciones tipicas, entender la interrelacion con problemas de optimizacion asi como aplicar los diferentes algoritmos adecuadamente

TEMARIO:

  1. Introducción

    • Origen de la Programación Entera

    • Problemas típicos de Programación Entera

    • Formulaciones equivalentes

  2. Metodo de cortaduras

    • Algoritmo ciclico

    • Algoritmo discreto de Gomory

    • Algoritmo mixto

    • Algoritmos primales

    • Convergencia

  3. Metodos de Enumeracion

    • Concepto general de separación y evaluación progresiva

    • Algoritmos de Branch and Bound

    • Problemas de programación entera pura y mixta

    • Algoritmos de enumeración implícita

    • Ejemplos

  4. Metodos de Teoria de Grupos

    • Cortadura fraccional de Gonory y el grupo formado por las cortaduras

    • Ejemplos de solución al problema del grupo de programación dinámica

BIBLIOGRAFIA:

  • Garfinkel, R.S.; Nemhauser, G. L., Integer Programming, Viley Intersience, 1972

  • Hu, T. C., Integer Programming And Network Flows, Addison Wesley, l969

  • Murty, K., Linear and Combinatorial Programmiong, John Wiley & Sons, 1976

BIBLIOGRAFIA COMPLEMENTARIA:

  • Foulds. L.R., Optimization Techniques: An Introduction, Springer-Verlag, l981

  • Kauffman, A., Methodes el modeles de la Recherche Operationnelle, Vol, III., Ed. Dunod

  • Minoux, M., Mathematical Programming: Theory and Algorithms, Wiley-Intersciences, 1986

  • Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization, Prentice-Hall, !982

  • Parker, G.; Rondin, R. L., Discrete Optimization, Acadecic Press, 1986

  • Schrage, L., Linear, Integer and Quadratic Programming with LINDO, The Scientific Press, 1986

  • Schrijmer, A., Linear ant Integer Programming, Wiley- Interscience, John Wiley And Sons, 1986

  • Taha, H., Integer Programming: Theory, Applications, Computations, Academic Press, l975