Ma-95-076. Programación Entera

 

(3-0-8) Requisitos:  In95-841, Ma95-075)

 

Equivalencia:  NT.

 

Objetivo General: 

Introducir a los alumnos al estudio de los modelos de programación entera y en sus diferentes técnicas de solución con el fin de desarrollar en ellos las habilidades de modelar y resolver problemas aplicados con variables enteras, así como interpretar los resultados obtenidos.

 

Temas y subtemas:

 

 

Unidad I 

Introducción a la Programación Entera.

 

1.1

Necesidad de programas con variables enteras.

1

1.2

Formulación de los modelos de la Programación Entera.

1

1.3

Modelación de los problemas clásicos de la Programación Entera.

6

1.4

Formulaciones alternativas.

2

 

subtotal

10

 

Unidad II

Complejidad de los problemas de la Programación Entera.

 

2.1

Introducción a la complejidad computacional.

1

2.2

Problemas fáciles.

2

2.3

Problemas difíciles.

2

 

subtotal

5

 

Unidad III 

 Generalidades de los métodos de solución.

 

3.1

Optimalidad y relajación.

1

3.2

Acotamiento de la solución optima.

1

3.3

Relajación por aproximación a un problema de Programación Lineal.

1

3.4

Relajación lagrangiana.

1

3.5

Dualidad.

1

 

subtotal

5

 

Unidad IV 

Algoritmo de ramificación y acotamiento.

 

4.1

Descomposición de conjuntos.

1

4.2

Desarrollo del algoritmo de ramificación y acotamiento.

4

4.3

Preprocesamiento.

2

 

subtotal

5

 

Unidad V 

 Algoritmo de los planos cortantes.

 

5.1

Desigualdades válidas.

2

5.2

Adición a priori de restricciones.

1

5.3

Algoritmo general de los planos cortantes.

2

5.4

Cortes enteros mixtos.

2

5.5

Algoritmo de ramificación y corte.

4

 

Subtotal

11

 

Unidad VI

Dualidad lagrangiana.

 

6.1

Relajación lagrangiana.

2

6.2

Consistencia del dual lagrangiano.

2

6.3

Solución del dual lagrangiano.

2

6.4

Elección del dual lagrangiano.

2

 

subtotal

8

 

 

Objetivos específicos de aprendizaje por tema.

 

Unidad I

Introducción a la Programación Entera.

1.1     Mostrar mediante ejemplos la necesidad de programas lineales con variables enteras.

1.2     Formular los diferentes modelos de la Programación Entera.

·       Modelo entero puro.

·       Modelo entero mixto.

·       Modelo binario (entero 0-1).

1.3     Obtener los modelos de los problemas clásicos de la Programación Entera.

·       Problema de asignación.

·       Problema de la mochila.

·       Problema de cubrimiento de un conjunto.

·       Problema del agente viajero.

·       Modelos de costo fijo.

1.4     Ejemplificar algunas formulaciones alternativas utilizando las variables binarias.

 

Unidad II

Complejidad de los problemas de la Programación Entera.

 

2.1     Introducir el concepto de complejidad computacional.

2.2     Resaltar la importancia de la clasificación de los problemas de programación entera en fáciles o difíciles, según su complejidad computacional.

 

Unidad III

Generalidades de los métodos de solución.

 

3.1       Explicar la relación entre optimalidad de la solución y los métodos de relajación.

3.2       Acotamiento de la solución optima.

3.3       Relajación por aproximación a un problema de Programación Lineal.

3.4       Relajación lagrangiana.

3.5       Dualidad.

 

Unidad IV

Algoritmo de ramificación y acotamiento.

4.1       Descomposición de conjuntos.

4.2       Desarrollar el algoritmo de ramificación y acotamiento.

4.3       Introducir las técnicas de preprocesamiento.

 

Unidad V

Algoritmo de los planos cortantes.

5.1       Introducir los conceptos de desigualdades válidas.

5.2       Técnicas de adición a priori de restricciones.

5.3       Desarrollar el algoritmo general de los planos cortantes.

5.4       Cortes enteros mixtos.

5.5       Desarrollar el algoritmo de ramificación y corte.

 

Unidad VI

Dualidad lagrangiana.

6.1       Introducir la relajación lagrangiana.

6.2       Mostrar la consistencia del dual lagrangiano.

6.3       Resolver el dual lagrangiano.

6.4       Método para la elección del dual lagrangiano.

 

Metodología sugerida y actividades de aprendizaje.

Utilizar el método de elaboración conjunta, donde los estudiantes mediante la discusión dirigida por el profesor, forman los conceptos, modelos y métodos de solución. El profesor resume, generaliza y formaliza los resultados obtenidos. Fomentar el trabajo de los estudiantes en pequeños grupos en la realización de tareas extraclases.

 

Políticas de Evaluación sugeridas

Tres exámenes parciales (70%)

 Examen final (30%)

Cada examen consta de dos partes, una para realizar en el salón de clases y otra extraclase que será discutida con el profesor

 

Libro de Texto:

L. A. Wolsey, “Integer Programming”. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1998.

 

Bibliografía:

1.        K. Murty, “Operations Research: Deterministic optimization models”. Prentice Hall, 1995

2.        R. Rardin,  “Optimization in Operations Research”. Prentice Hall, 1998.

3.        H. Taha, “Investigación de Operaciones, una introducción”. 6ta Edición, Prentice Hall, México, 1998.

4.        F. Hillier, G. Lieberman, “Introducción a la Investigación de Operaciones”. 4ta Edición, McGraw Hill, México, 1997.

 

Perfil del Maestro:

Profesor con maestría o doctorado en el área de optimización y graduado de una carrera de matemáticas o ingeniería.