Actuaría (plan 2006) 2021-1

Optativas, Programación Entera

En el curso de programación entera estaremos trabajando juntos para que logres conocer los antecedentes históricos de la Programación Lineal Entera, tener una visión general de los modelos de optimización lineal discreta, conocer los elementos necesarios para analizar, formular y resolver problemas enteros, así como conocer algoritmos exactos, algoritmos especializados en casos particulares y la teoría de complejidad.

Compromisos del estudiante

Asistencia a las sesiones en Google Meet en un horario de 10 : 00−11 : 00am.

Cada subtema estará integrado por:

• Apuntes en formato PDF.
• Sesiones con el grupo por semana en Google Meet para analizar los apuntes, realizar las demostraciones necesarias, plantear modelos matemáticos,analizar los diferentes algoritmos y realizar los ejercicios necesarios para que el tema quede completado.
• Una tarea que se entregará en forma individual o por equipo (depende del número de alumnos en el curso)
• Al menos 1 actividad en un periodo de 7 a 15 días, puede ser desde leer un artículo y exponer al final del periodo de entrega o contestar un cuestionario en MOODLE

En cada parcial habrá un proyecto para suplir el examen, éste puede ser desde realizar un cartel científico, hasta un trabajo de investigación que involucre la creatividad y el conocimiento adquirido en el parcial. (en el ciclo escolar habrá 3 parciales, por lo que habrán 3 proyectos en todo el semestre)

Todas las entregas estarán calendarizadas. Los trabajos deberán cumplir con sus respectivos requisitos y con las fechas establecidas, no habrá tolerancia en el tiempo de entrega.

A pesar de que el curso es a distancia, espero contar con todo su apoyo para que lo tomen con toda la seriedad necesaria y se lleve a cabo de la mejor manera posible.

Compromisos de mi parte

Ofrecerte un curso completo, con recursos de aprendizaje diversos, que promueva los conocimientos, habilidades, actitudes y valores mencionados, en un entorno de respeto y seguridad,

Aportar retroalimentación sobre tu desempeño, tanto a través de tus entregas de actividades y proyectos, como a partir de sesiones de asesoría en grupo o individuales.

Mostrar empatía por la situación por la que estamos atravesando.

Forma de evaluar

• 30% actividades de clase
• 50% proyecto
• 20% tareas

En cuanto al puntaje

La calificación mínima para aprobar el curso de programación entera es 6

Del 0.7 en adelante, sube al siguiente entero, siempre y cuando la calificación sea aprobatoria. En el caso de que la calificación final sea menor a 6 no sube

a pesar de que sea 5.9

No habrá reposiciones, solo habrá un final que constará de un examen en la plataforma MOODLE y un proyecto. (sin excepción)

La primer sesión en Meet es el día 21 de septiembre a las 10:00am, ingresarás con la siguiente liga http://meet.google.com/xpx-otoo-xcr

¡Espero que tengamos una experiencia de aprendizaje muy valiosa en tu formación!

Mat. Ana Lilia Anaya Muñoz

Septiembre de 2020

Temario

1. Introducción

1.1 Panorama general de la programación entera.

1.2 Problemas de optimización combinatoria.

1.3 Problemas enteros

• Problemas enteros puros
• Problemas enteros binarios
• Problems enteros mixtos

1.4 Planteamiento de problemas enteros.

• Problema de la mochila.
• Problemas de presupuesto de capital.
• Problema de cobertura.
• Problema de cargo fijo.
• Restricciones condicionales.
• Función lineal por pedazos.
• Otros más.

2. Programación lineal y su relación con los problemas de programación entera.

2.1 Optimalidad y relajación PL.

2.2 Cotas superiores e inferiores para problemas de maximización y minimización respectivamente.

2.3 Dualidad.

2.4 Análisis de sensibilidad.

3. Planos de corte

3.1 Concepto de corte y su profundidad.

3.2 Cortadura fraccional de Gomory.

• Algoritmo entero puro.
• Algoritmo entero mixto.

4. Ramificación y acotamiento.

4.1 Metodología de la ramificación y acotamiento

4.2 Ramificación y acotamiento para problemas de programación lineal entera.

4.3 Enumeración implícita.

5. Teoría de la complejidad.

5.1 Introducción

5.2 Problemas de decisión y problemas de optimización.

5.3 Clases P, NP, NP-Completo y NP-Duro.

5.4 Reducciones polinomiales.

6. Problemas Específicos.

6.1 Problema de Acoplamiento.

• Acoplamiento en gráficas bipartitas.
• Acoplamiento en gráficas no bipartitas.

6.2 Problema de la mochila.

• Problema de la mochila general.
• Problema de la mochila binario.
• Problema de la mochila acotado.

6.3 Problema de asignación.

• Algoritmo húngaro.
• Algoritmo de subastas.

6.4 Problema del agente viajero.

• Problema relajado.
• Ramificación y acotamiento.

7. Algoritmos heurísticos y metaheurísticos

7.1 Algoritmos constructivos.

7.2 Algoritmos de búsqueda.

7.3 Búsqueda Tabú.

7.4 Recocido Silulado

7.5 Algoritmo genético

8. Aplicaciones.

Bibliografía

• de los Cobos, S., Goddard, J.,Gutiérrez, M., Martínez, A., (2010), Búsqueda y Exploración Estocástica, Primera Edición, México D.F., México, UAM. Gendreau, M., Potvin, J.,(2010), Handbook of Metaheuristics, Segunda Edición, Springer.

• Papadimitriou Christos H., Sterglitz Kenneth. Combinatorial Optimization, Algorithms and Complexity. Ed. Dover Publications, INC, USA, 1998.

• Salkin Harvey M. Integer Programming. Ed. Addison-Wesley, USA, 1975.

• Taha, Hamdy A. Integer Programming Theory, Applications and Computations. Ed. Academic Press, USA, 1995.

• Winston, Wayne L. Investigación de Operaciones. Grupo Editorial Iberoamericana, México, 1994.