Intensidad: 4 horas semanales y 8 horas semanales de
trabajo autónomo del estudiante
Objetivos:
Capacitar al estudiante en las habilidades de: formular modelos de
programación matemática (lineal, lineal entera, de metas, grafos y
dinámica) dada la definición de un problema de la ingeniería, la economía,
etc.; hallar su solución por medio de los métodos principales apropiados y
hacer su análisis, como etapas del proceso de la aplicación de la
investigación de operaciones (10} real en la toma de decisiones. Entender
la teoría matemática básica de la programación matemática y los métodos de
optimización de los modelos matemáticos típicos de la 10. Incentivar la
iniciativa del trabajo personal del estudiante.
Metodología: El
profesor usará la cátedra magistral para explicar los temas y
proporcionará los ejemplos apropiados para el mejor entendimiento de cada
tema.
Estrategia de aprendizaje: Trabajo autónomo del estudiante de 8 horas
semanales para la preparación de exámenes y la realización de las tareas.
El estudiante participará en respuestas a preguntas, trabajos individuales
y presentaciones cortas, la programación de algún algoritmo o en el
conocimiento de algún software.
Evaluación: El
método de asignación de calificación que se usará será el estadístico
(calificación por curva} para estimular la participación de los
estudiantes. En cada uno de tres (3} períodos se harán trabajos,
presentaciones, exámenes cortos (quices) y un examen intermedio para un
25% de la calificación final. El examen final valdrá 25%.
Contenidos:
1.
LA INVESTIGACIÓN DE OPERACIONES
Modelado
matemático. El arte del modelado.
2.
LA PROGRAMACIÓN LINEAL
El
problema de la programación lineal (PL). Formas del modelo. Construcción
del modelo por el método de análisis de actividades (Dantzig, Cap. 3).
Ejemplos
de transporte, producción, etc. Solución gráfica de problemas de PL.
3.
DUALIDAD EN LA PROGRAMACIÓN LINEAL
El
problema dual en la PL. Interpretación económica de las variables duales y
restricciones duales. Formas duales equivalentes. Sistemas canónico y
estándar de dualidad. Soluciones de sistemas de ecuaciones y/o
desigualdades lineales.
Teorema
de Farkas.
La
teoría de dualidad: dualidad en forma débil, optimidad de soluciones de
las parejas de problemas duales, dualidad en forma fuerte, condiciones de
holgura complementaria (teoremas de equilibrio en la interpretación
económica; Gale, Cap. 1). Ejemplos de transporte, producción para
satisfacer la demanda dada a costos mínimos, producción para maximizar los
ingresos con recursos dados, etc.
4.
SOLUCIÓN DE PROBLEMAS LINEALES.
Interpretaciones geométricas de un problema de PL. El espacio solución Rn
y el espacio de los recursos o requerimientos Rm. Elementos de análisis
convexo y de conjuntos poliédricos.
El
método simplex. Forma estándar del problema de PL. Forma canónica.
Determinación de soluciones básicas. El algoritmo simplex para la PL.
Convergencia. El método de las dos fases. Solución inicial artificial.
Casos especiales ( degeneración, soluciones alternativas, no acotadas, y
problemas no factibles).
El
método simplex dual.
Análisis
de sensibilidad: cambios que afectan la factibilidad y cambios que afectan
la optimalidad.
5.
PROGRAMACIÓN LINEAL AVANZADA
Pruebas
de validez del método simplex. Conjunto convexo. Poliedros y politopos
convexos. Puntos extremos. Puntos extremos y soluciones básicas. Optimidad
del algoritmo simplex.
El
método simplex revisado. Forma de producto de la inversa Algoritmo para
problemas de PL con variables acotadas. Algoritmo de descomposición de
Dantzig-Wolfe
Programación lineal paramétrica. Cambios paramétricos en c y en b.
Algoritmo de punto interior de Karmarkar.
6.
LOS PROBLEMAS DE TRANSPORTE Y DE ASIGNACIÓN
Definición del problema de transporte. Modelos de transporte no
tradicionales. El método simplex para el problema de transporte. El modelo
de asignación. El método húngaro. El problema de transporte con
transbordos.
7.
PROBLEMAS DE GRAFOS (O REDES)
Definición de grato. Problema del árbol de expansión mínima y algoritmo.
Problema de la ruta más corta. Ejemplo; de aplicación. Algoritmo. Problema
del flujo máximo. Enumeración de cortes. Algoritmo de flujo máximo. El
problema de flujo de costo mínimo. El método simplex de redes.
CPM y
PERT. Representación de la red. Cálculo de la ruta crítica. Programación
en el tiempo.
8.
PROGRAMACIÓN DE METAS
Objetivo
individual y objetivos múltiples. Formulación de programación de metas.
Algoritmos de programación de metas.
9.
PROGRAMACIÓN LINEAL ENTERA
Construcción de modelos o problemas de programación lineal entera (PLE).
Solución de problemas de PLE: algoritmo del plano cortante; algoritmo de
ramificación y acotamiento.
10. PROGRAMACIÓN DINÁMICA DETERMINÍSTICA
Principio de optimidad de Bellman. Terminología. Definición de la función
de valor óptimo y de sus argumentos, la función de política óptima, la
relación de recurrencia y las condiciones de frontera. Etapa y estado.
Programación dinámica (PD) hacia adelante y PD hacia atrás. Ejemplos de la
ruta más corta, reemplazo de equipos, asignación de recursos, etc.
Bibliografía:
Texto
guía: Taha, H. A., 1998. Investigación de Operaciones, una introducción.
Sexta edición. Prentice Hall Hispanoamericana, México.
Alevras,
D., Padberg, M. W., 2001. Linear Optimization and Extensions, Problems and
Solutions. Springer-Verlag, New York.
