Programa del Curso

La disciplina que en la actualidad se conoce como Investigación Operativa (Operations Research o Management Science en la literatura en inglés) surgió y adquirió su nombre durante la segunda guerra mundial, y se consolidó durante la década de los 50. Si bien sus primeras aplicaciones fueron en el campo militar, desde entonces y hasta la actualidad el campo de aplicación fue creciendo e incluye numerosos problemas de la economía, la producción, la logística, empresas de servicios, organizaciones en general, otras ciencias, etc. Entre estos podemos mencionar: problemas de transporte, de ruteo de vehículos, problemas de diseño y ruteo en redes de comunicaciones, VLSI, planificación de la producción, diseño de códigos, flujo en redes, análisis financiero, asignación de tareas a procesadores, problema de doblado de proteínas y otros problemas de la genómica, problemas de asignación de horarios en instituciones educativas, problemas de asignación de tripulaciones en líneas aéreas o ferrocarriles, optimización de desperdicio en el corte de distintos materiales, etc. Y día a día continúan surgiendo nuevas aplicaciones derivadas de la necesidad de tomar decisiones en muchos ámbitos que requieren de la formulación de nuevos modelos y el desarrollo de algoritmos para resolverlos.

En todos estos problemas se requiere tomar decisiones óptimas o casi óptimas que involucran variables sujetas a requerimientos. Hay tres componentes básicas en el proceso de decisión que deben ser determinadas para formular un modelo matemático: cuáles son las variables de decisión, cuáles son las restricciones del problema y cuál es el objetivo a optimizar. Después debemos elegir un método existente o desarrollar un nuevo algoritmo que encuentre la solución óptima o aproximada.

Los problemas de Investigación Operativa y Optimización ofrecen entonces interés para su estudio tanto desde el punto de vista teórico como desde el punto de vista de las importantes aplicaciones a problemas reales.

OBJETIVO

El objetivo de este curso es brindar las primeras ideas de como formular modelos y de los métodos básicos para resolver la gran variedad de problemas de optimización que pueden ser de programación lineal y lineal-entera con restricciones lineales y función objetivo lineal, (en algunos casos con algunas o todas las variables enteras). En particular la mayoría de los problemas de Optimización Combinatoria pueden ser modelados como problemas de programación lineal entera.

El curso contará de clases teóricas, se dejarán ejercicios para hacer y se prevé hacer prácticos en el laboratorio de computación modelando y resolviendo problemas sencillos.

PREREQUISITOS

Nociones básicas de: algebra lineal, métodos numéricos y algoritmos.

DURACIÓN

15 horas

PROFESOR

Dra. Irene Louseau

CONTENIDO

  • Historia. Diseño y elementos de un modelo de decisión.
  • Programación Lineal. Modelos de programación lineal: planificación de la producción determinación del stock, procesos de producción, inversión de capitales, planificación financiera, programación de tareas, problemas de mezcla, etc.
  • Programación Lineal: Método Simplex. Interpretación geométrica. Convergencia. Complejidad. Problema dual. Interpretación económica y geométrica. Teorema de dualidad. Teorema de Holgura Complementaria. Método Simplex Revisado. Analisis de sensibilidad y paramétrico. Interpretación económica. Software para problemas de programación lineal.
  • Problemas de programación lineal entera: cubrimiento, empaquetamiento, problema del viajante de comercio, matching, asignación de tareas, diseño de redes de comunicaciones, problema de la mochila, problemas de minimización de desperdicio en el corte de materiales, etc. Formulación de modelos de programación entera. Complejidad. Buenas y malas formulaciones. Problemas fáciles: flujo en redes, problema de transporte.
  • Ideas básicas de los algoritmos de resolución de un problema lineal entero. Métodos de planos de corte. Metodos Branch and Bound. Estrategias de recorrido del árbol. Métodos Branch an Cut. Métodos de generación de columnas. Software para problemas de programación lineal entera.

BIBLIOGRAFÍA

  1. Bazaraa, M., Jarvis, J., Linear Programming and Network Flows, John Willey &.Sons, 1990
  2. Chvatal, V., Linear Programming, Freeman, 1983
  3. Cook, W., Cunningham, Pulleyblank, Schrijver, A., Combinatorial Optimization, John Willey &.Sons, 1998.
  4. Williams, H.P., Model Building in Mathematical Programming, John Willey &.Sons, 1999.
  5. Winston,W., Operations Research, Applications and Algorithms, Duxbury Press, 1994.
  6. Wolsey,L., Integer Programming, John Willey &.Sons, 1998.