Antecedentes Generales

Clave Nombre de la asignatura
EII -400 Optimización Lineal
Horas semanales de cátedra Horas semanales prácticas Créditos PUCV
Taller Ayudantía
4 2 2 4
Pre-requisitos
  MAT -186 Algebra Lineal
  EII-210 Arquitectura de Sistemas de Software

Resumen

Este curso provee una introducción a los conceptos, metodología, técnicas y aplicaciones de la Investigación de Operaciones enfatizando su comprensión como un enfoque racional para la toma de decisiones y la optimización de sistemas.

El contenido de la asignatura se focaliza en la Programación Matemática como herramienta para el modelamiento y solución de problemas de optimización, y más específicamente, en la técnicas de Programación Lineal y Programación Lineal Entera Mixta.

La asignatura busca arraigar en el alumno la convicción que la optimización de sistemas, en sus distintas formas, es un elemento clave tanto en la formación como el desarrollo profesional del Ingeniero Civil Industrial.

Objetivos de Aprendizajes

Al cursar esta asignatura el alumno será capaz de:

  • Comprender el lenguaje de la Investigación de Operaciones y particularmente de la Programación matemática.
  • Entender el rol de la Programación Matemática en la solución de un problema de toma de decisiones.
  • Modelar clases e instancias de problemas de Programación Lineal (PL) y de Programación Lineal Entera Mixta (PLEM).
  • Identificar y comprender aplicaciones de PL y PLEM en el ámbito de la Gestión de Operaciones y la Ingeniería Industrial.
  • Entender los fundamentos matemáticos de la PL y del Método Simplex.
  • Entender los conceptos básicos de la teoría de la dualidad en el contexto de la PL.
  • Entender los fundamentos del Método de Ramificación y Acotamiento y su aplicación a la PLEM.
  • Usar planillas electrónicas para resolver problemas pequeños de PL y PLEM.
  • Usar un lenguaje de programación matemática para modelar clases de problemas de PL y PLEM, y resolver instancias de tamaño moderado.

Contenidos de Asignatura

PARTE 1: Introducción

Unidad 1 : Introducción a la Investigación de Operaciones (3 sesiones)

Se reseña la brevemente la historia de la Investigación de Operaciones y su Rol en el desarrollo de la Ingeniería Industrial. Se describe el rol del curso en el contexto del programa de estudios de la carrera. Se describe la metodología de la Investigación de Operaciones y se introduce la Programación Matemática como una de sus herramientas fundamentales. Se formaliza el concepto de problema como una situación en que debe decidirse respecto de la asignación de recursos limitados a objetivos en conflicto, y se discute el rol de los modelos y algoritmos de programación matemática en la solución de un problema de decisiones. Se clasifican los modelos según el tipo de información que proveen al tomador de decisiones y según características matemático-estructurales.

  • Definición e historia de la investigación de operaciones.
  • Metodología de la investigación de operaciones
  • Ejemplos introductorios
  • Problemas, modelos y algoritmos de solución
  • Clases de problemas e instancias de problemas
  • Clasificación de los modelos


PARTE 2 : Programación Matemática: Modelamiento

Unidad 2:  Programación Lineal (5 sesiones)

Se introduce la técnica de la Programación Lineal. Se discute brevemente los aspectos metodológicos que deben ser considerados en la construcción de modelos lineales. Se presenta una amplia cantidad de modelos estándares en la literatura, que describen una extensa variedad de situaciones. Estas situaciones corresponden, en general, a versiones simplificadas de problemas decisionales en el ámbito de la Gestión de Operaciones y la Ingeniería Industrial. La discusión de focaliza en los aspectos estructurales del modelo y cómo distintas situaciones prácticas pueden representarse a través de estructuras matemáticas comunes. En la ejercitación se enfatiza, por un lado, el reconocimiento de estas estructuras en problemas originados en ámbitos de aplicación distintos a los estudiados, y por otro lado, la combinación de estructuras en la construcción de modelos integrados para dos o más de las problemáticas discutidas (Ejemplo: planificación de producción más transporte). Paralelamente se ejercita la capacidad de representación simbólico-matemática de los problemas, el uso correcto de la notación, y en general la lecto-escritura matemática.

  • Forma general y componentes del modelo de Programación Lineal Pura
  • Supuestos de un modelo de Programación Lineal
  • El problema de planificación de la producción de un periodo
  • Problemas de mezcla
  • Problemas de transporte y transbordo
  • El problema de flujo en redes de costo mínimo
  • El problema de planificación de producción multi-periodo
  • Resolución vía planillas electrónicas

Unidad 3:  Programación Lineal  Entera Mixta (7 sesiones)

Se introduce la técnica de la Programación Lineal Entera Mixta. Se discute las condiciones es que es recomendable y/o necesario usar variables enteras generales, y cuándo un modelo lineal puro puede representar una aproximación razonable. Se introduce el uso de variables binarias para representar relaciones lógico-matemáticas.  En forma similar al  Capítulo 3, se presenta una amplia variedad de modelos estándares en la literatura, correspondientes a versiones simplificadas de problemas decisionales en el ámbito de la Gestión de Operaciones y la Ingeniería Industrial. La discusión nuevamente se focaliza en los

aspectos estructurales del modelo. En la ejercitación se enfatiza, por un lado, el reconocimiento de estas estructuras en problemas originados en ámbitos de aplicación distintos a los estudiados, y por otro lado, la combinación de estructuras para resolver problemas integrados (Ejemplo: selección de proyectos con planificación de personal, planificación de la producción con problemas de corte, etc.). Se profundiza en aspectos generales de lecto-escritura matemática.

  • Forma general del modelo de Programación Lineal Entera Mixta y sus variantes
  • Modelamiento con variables entera generales
  • Problemas de corte (cutting stock problem)
  • Problemas de planificación de personal
  • Modelamiento con variables binarias
  • El problema de la mochila
  • El problema de asignación
  • El problema de selección de proyectos
  • El problema de cobertura, particionamiento y agrupamiento de conjuntos
  • Modelos mixtos y funciones de costo con cargo fijo
  • El problema de planificación de la producción multi-periodo con set-ups
  • El problema de localización de instalaciones
  • El problema de flujo en redes con cargo fijo
  • Introducción a un lenguaje de programación matemática (Ej. OPL)

Unidad 4:  Programación No-Lineal (1 sesión*)

* Si existe disponibilidad de tiempo se realiza una breve introducción al modelamiento no-lineal.

  • Problemas en gestión de inventarios
  • Ejemplos misceláneos

PARTE 3 : Programación Matemática: Teoría y Métodos

Unidad 5: Programación Lineal y el método SIMPLEX (7 sesiones)

Se presenta la teoría de la programación lineal a un nivel de profundidad medio, se presenta los fundamentos matemáticos y el algoritmo del Método Simplex, y se describe una implementación tabular. Se introduce el concepto de dualidad y las múltiples propiedades asociadas, se discute su interpretación económica y su  importancia para el análisis post-optimal. Se detalla varios tipos de análisis post-optimal  y se discute el tipo de información que este provee al modelador. Se ejercitan inicialmente los aspectos mecánicos del Método Simplex  y del método Dual Simplex, usando la forma tabular, para luego enfatizar la comprensión del álgebra correspondiente, utilizando el enfoque matricial. Se utiliza problemas de planteo para ejercitar el análisis post-optimal y la interpretación de resultados.

  • Geometría del problema de Programación Lineal
  • Álgebra del problema de Programación Lineal
  • Método SIMPLEX.
  • Dualidad y el método Dual-Simplex,
  • Análisis post-optimal y análisis de sensibilidad local.

Unidad 6: Programación Lineal Entera Mixta (3 sesiones)

Se discute elementos básicos relacionados a la calidad de un modelo de PLEM. Se enfatiza la mayor importancia de estos aspectos en PLEM en relación a PL. Se introduce el concepto de relajación lineal, y la noción de “formulación ideal”, y se discute cuando la solución lineal relajada entrega la solución exacta de un

modelo de PLEM. Se introduce le método de Ramificación y Acotamiento como un enfoque general para el desarrollo de algoritmos para problemas complejos, y se discute su aplicación al caso de PLEM. En la ejercitación se enfatiza la comprensión global del enfoque por sobre sus aspectos mecánicos.

  • Geometría del modelo de PLEM
  • Formulaciones correctas y formulaciones buenas
  • Cotas de optimalidad
  • Resolución por ramificación y acotamiento

Unidad 7: Optimización Clásica (2 sesiones*)

* Si existe disponibilidad de tiempo se realiza un breve recordatorio de optimización no lineal, incluyendo elementos tales como condiciones de optimalidad, multiplicadores de Lagrange, Método de Newton, etc.

  • Conceptos Básicos
  • Optimización no-lineal no-restringida
  • Optimización no-lineal restringida: Multiplicadores de Lagrange.