(Unidades:3-0-8 Requisito: In95-841, Ma95-075,
Ma95-076, Ma95-078)
Semestre y carrera:
Equivalencia:No tiene
Objetivo general de la materia: Introducir a los alumnos al estudio
de la programación entera, así como a sus diferentes técnicas
de
solución con el fin de desarrollar en ellos las habilidades de resolver
problemas con variables discretas, además de interpretar
los
resultados obtenidos mediante la experimentación. Estudio de la técnica de
Ramificación y Acotamiento. Estudio del poliedro de
restricciones mediante la obtención de desigualdades válidas y
facetas.
Temas y subtemas del curso:
Unidad I Modelación con variables binarias.
1.1 Problema de la mochila.
1.2 Problema de múltiples mochilas.
1.3 Problema de asignación.
1.4 Problema de cobertura de
conjuntos
1.5 Problema de locación de plantas
1.6 Problema del agente viajero
1.7 Problemas enteros mixtos
1.8 Otros problemas
1.9 Restricciones disjuntas
1.10 Ejemplos
Unidad II Ramificación y acotamiento.
2.1 Ramificación y acotamiento.
2.2 Estrategias de ramificación y
acotamiento.
Unidad III Teoría de poliedros.
3.1 Definiciones y elementos de
álgebra lineal.
3.2 Definiciones que caracterizan a
un poliedro
3.3 Facetas de un poliedro
Unidad IV Teoría de desigualdades válidas.
4.1 Desigualdades fuertes y
desigualdades válidas.
4.2 Generación de desigualdades
válidas para diversos casos.
4.3 Método de Gomory
4.4 Procedimiento de Chvatal -
Gomory
4.5 Desigualdades para problemas
enteros mixtos
Unidad V Desigualdades válidas y facetas para problemas binarios.
5.1 Introducción.
5.2 Desigualdades de cobertura y
extensión
5.3 Desigualdades válidas fuertes
5.4 Desigualdades válidas para el
poliedro del problema de la mochila.
5.5 Desigualdades válidas para el
poliedro del problema múltiple de la mochila.
5.6 Desigualdades válidas para el
poliedro del problema de asignación.
5.7 Desigualdades válidas para el
poliedro del problema del agente viajero.
5.8 Desigualdades válidas para el
poliedro del problema de flujo con cota superior para las variables.
5.9 Desigualdades válidas para otros
poliedros.
Unidad VI Tópicos especiales.
6.1 Levantamiento.
6.2 Algoritmo de separación.
Objetivos específicos de aprendizaje:
Unidad I
Aprender a reconocer y plantear el modelo
matemático de problemas enteros binarios.
Unidad II
Resolver problemas de programación entera
haciendo uso de la técnica de ramificación y acotamiento.
Unidad III
Definir los conceptos y herramientas
matemáticas necesarias para caracterizar un poliedro.
Unidad IV
Determinar desigualdades válidas y aplicar
métodos de obtención de desigualdades válidas para el poliedro de
restricciones.
Unidad V
Definir coberturas, facetas y obtener
desigualdades válidas fuertes para los poliedros de problemas específicos.
Metodología de enseñanza
Tiempo estimado de cada tema:
Unidad I 9 horas
Unidad II 4 horas
Unidad III 4 horas
Unidad IV 7 horas
Unidad V 13 horas
Unidad VI 5 horas
Políticas de evaluacion sugeridas:
Tres exámenes parciales (80%)
Examen final (20%)
Cada examen consta de dos partes, una para
realizar en el salón de clases y otra extra clase que será discutida con el
profesor
Bibliografía:
Perfil del Profesor:Profesor con doctorado en
el área de optimización y graduado de una carrera de matemáticas o ingeniería.