Antecedentes Generales

Resumen

En esta asignatura se pretende fortalecer las metodologías y técnicas entregadas en Optimización Lineal, potenciando las capacidades de los alumnos para realizar procesos de mejoramiento y optimización en la toma decisiones, para problemas de relevancia en Ingeniería Industrial y de Gestión de Operaciones.

Se pretende analizar y desarrollar técnicas matemáticas y analíticas de Investigación de Operaciones, dando particular énfasis a modelos y aplicaciones que involucran decisiones de flujos y diseño en redes de transporte, en el contexto de problemas logísticos y de producción, entre otros, involucrando particularmente variables de decisiones binarias y enteras.

Se realizará un profundo análisis de aplicaciones específicas de técnicas de la teoría de grafos y de programación entera y optimización combinatorial. Adicionalmente se enseñarán y aplicarán algunas metodologías clásicas para la resolución de los modelos analizados en esta asignatura, enfocándose en optimización de problemas de flujo en redes, métodos de descomposición y relajación de problemas enteros (Ramificación y Acotamiento y Relajación Lagrangeana), así como heurísticas básicas de búsqueda local

Objetivos de Aprendizaje

Al cursar esta asignatura el alumno será capaz de:

• Formular problemas de operación y planificación reales mediante modelos de flujo en redes, con cargo fijo (redes mixtas: discretas y continuas) y de redes discretas y de ruteo vehicular
• Desarrollar e implementar técnicas de resolución de modelos de optimización relevantes, particularmente para problemas en redes y problemas con variables enteras.
• Identificar estructuras estándares existentes para problemas de redes y de naturaleza entera y combinatorial.

Contenidos de Aprendizaje

Unidad 1 : Modelación de Problemas de Flujo en Redes (5 semanas)

En este módulo se revisará los fundamentos de la teoría de flujo en redes, lo cual representa una base para formular deferentes problemas reales de operación. Además de los elementos básicos notacionales y estructurales de estos problemas, se analizaran diversos modelos que resuelven diferentes problemáticas especificas. Adicionalmente se describirán diversos algoritmos para la resolución de los diferentes modelos de optimización analizados, basados principalmente en la aplicación del método Simplex a problemas con estructura de redes. Se destaca la consideración de variables de flujo “continuas”, así como estructuras lineales (función objetivo y restricciones).

Se estudiarán los siguientes tópicos:

• Conceptos y notación en redes (1 a 2 sesiones).
• Transformaciones en redes (1 a 2 sesiones).
• Problemas fundamentales: PFMC, Rutas Mínimas, Problema de Transporte, Flujo Máximo) (2 a 3 sesiones)
• Algoritmos específicos en redes (Simplex de Redes, Dijkstra, etc.). (2 a 3 sesiones)
• Otros problemas específicos (1 a 2 sesiones)

Unidad 2 : Flujo en Redes con Cargo Fijo (5 semanas)

En este módulo se revisan estructuras de problemas en redes, en los cuales existen cargos o costos fijos producto de la utilización y/o construcción de arcos en el sistema, dando pie a modelos con variables binarias. Sobre la base de estas formulaciones generales se desarrollan modelos para problemas de planificación de la producción y de diseño de redes logísticas. Adicionalmente, se revisarán dos enfoques estándares utilizados para este tipo de problemas.

Se estudiarán los siguientes tópicos:

• El problema de flujo en redes con cargo fijo (1 a 2 sesiones)
• Aplicación a problemas producción e inventario (2 a 3 sesiones)
• Diseño de Redes Logísticas y Localización de instalaciones (1 a 2 sesiones)
• Localización con Cobertura y formulaciones multi-objetivo (1 a 2 sesiones)
• Resolución mediante Branch&Bound (Ramificación y Acotamiento) (1 a 2 sesiones)
• Resolución mediante Relajación Lagrangeana (1 a 2 sesiones).

Unidad 3 : Problemas de Ruteo Vehicular (4 semanas)

En este tercer módulo, se analizarán diferentes problemas vinculados al ruteo de vehículos de reparto, problemas de naturaleza combinatorial y alta complejidad. Adicionalmente se revisan métodos heurísticos de construcción de soluciones y de mejoramiento basado en búsqueda local.

Se estudiarán los siguientes tópicos:

• Problema del Vendedor Viajero (1 sesión)
• Problemas de Diseño de Flota (2 sesiones)
• Problemas de Clusterización de Clientes y Zonas de Reparto (2 sesiones)
• Métodos Heurísticos de Búsqueda Local (2 sesiones)
• Problema del Vendedor Viajero Probabilístico (1 sesión)