Accesos directos a las distintas zonas del curso
Ir a los contenidos
Ir a menú navegación principal
Ir a menú pie de página
Subject's code : 31104021
La asignatura comienza con la identificación de problemas sencillos de programación matemática y su representación utilizando lenguajes de modelado para este tipo de problemas (OPL, OML, AMPL, GAMS, LINGO, etc.). Después se introducen los principales métodos de resolución de problemas lineales continuos y enteros, métodos que operan en el interior de los lenguajes de modelado. Finalmente se analizan y resuelven problemas de optimización reales que aparecen en los entornos industriales. Los contenidos anteriores se organizan en tres partes con tres temas cada parte:
Parte I: Modelado de problemas de optimización lineal.
Tema 1: Modelos lineales de optimización con variables continuas.
Tema 2: Modelos lineales de optimización con variables enteras.
Tema 3: Lenguajes de modelado de problemas de optimización (OPL, OML, AMPL,…)
Parte II: Métodos de resolución de problemas lineales continuos y enteros.
Tema 4: Programación lineal con variables continuas: método del Simplex.
Tema 5: Dualidad y sensibilidad de los modelos lineales
Tema 6: Programación entera: métodos de bifurcación-acotación y planos de corte.
Parte III: Aplicaciones industriales de la programación matemática.
Tema 7: Optimización de redes logísticas.
Tema 8: Optimización de procesos industriales.
Tema 9: Aproximación lineal de problemas no convexos y no lineales
Contenidos.
Introducción.
El objetivo de un modelo matemático es reproducir la realidad de la forma más fiel posible a fin de entender cómo se comporta y poder obtener respuestas a determinadas acciones. La optimización lineal se sirve de modelos para representar aquellos aspectos de la realidad que tienen influencia en las decisiones que optimizan el funcionamiento de un sistema. Tres son las etapas en el establecimiento de un modelo de optimización lineal:
1) Identificación de las posibles decisiones que pueden tomarse en el sistema y su representación en forma de variables: las variables de decisión.
2) Especificación del conjunto de valores de las variables de decisión que resultan admisibles en el sistema, es decir, el conjunto de restricciones que deben cumplir dichas variables.
3) Desarrollo de un modelo de costes del sistema, es decir, determinar el coste/beneficio asociado a cada decisión admisible.
Resultados de aprendizaje.
Nivel de dificultad.
Este tema de caracter general de la programación matemática no tiene especial dificultad para un alumno con conocimientos básicos de algebra lineal y programación.
En muchos problemas de programación lineal sólo tienen sentido aquellas soluciones en las que todas o algunas de las variables de decisión toman valores enteros. Este tipo de problema se denomina en general de programación lineal entera. Si todas las variables del problema deben ser enteras se habla de programación entera pura, pero si sólo algunas deben ser enteras y las restantes continuas se habla de programación lineal entera-mixta. Cuando las variables enteras están restringidas a los dos valores 0-1, se denominan variables binarias, y el problema correspondiente problema binario. La utilización de variables enteras en general y binarias en particular amplía notablemente las posibilidades de modelado de la programación lineal, haciendo posible la disyunción de restricciones, la implicación lógica entre restricciones y en general la incorporación al modelo de ciertos comportamientos no lineales de la realidad. En este tema analizamos algunas de las nuevas posibilidades que introducen las variables enteras desde el punto de vista del modelado de problemas. También estudiamos su expresión en el leguaje OPL.
Este tema tiene cierto grado de dificultad en la expresion de las relaciones lógicas entre restricciones utilizando variables binarias.
Varias son las alternativas que se presentan a la hora de implementar un modelo de optimización lineal en un computador. Cada una presenta sus ventajas e inconvenientes, por lo que la elección deberá hacerse en cada caso en función del uso que se le vaya a dar al modelo. Podemos señalar cuatro alternativas principales: 1) Hojas de cálculo con resolutor asociado, 2) Entornos de cálculo numérico y/o simbólico, 3) Biblioteca de algoritmos de optimización utilizables desde un lenguaje de programación de propósito general (Java, Fortran, C#, etc.) y 4) Lenguajes algebraicos de modelado. En este curso, por motivos de eficiencia, trabajaremos exclusivamente con la cuarta alternativa de los lenguajes de modelado, y utilizaremos específicamente el lenguaje OPL. Se trata de un lenguaje moderno con abundantes recursos expresivos, un resolutor muy potente, CPLEX, con amplias facilidades de conexión a diferentes fuentes de datos (bases de datos, hojas de cálculo, archivos de texto) y con la posibilidad de integración directa de los modelos diseñados en prácticamente todos los entornos modernos de desarrollo software.
Este tema suele tener dificultad para los alumnos que sólo tengan nociones de programación de tipo imperativo, ya que se introducen lenguajes algebraicos de tipo declarativo..
En este tema abordamos la forma de resolver problemas de programación lineal continua. El objetivo fundamental es entender la naturaleza del problema y el perfil computacional a que dan lugar estos métodos. Desde un punto de vista práctico los procedimientos manuales de resolución no tienen mucho interés porque hoy día existen abundantes herramientas informáticas que implementan de manera muy eficiente estos procedimientos. Aunque el tema se centra fundamentalmente en el algoritmo del Simplex, propuesto por Dantzig en 1947, comienza con una introducción a los métodos de resolución gráficos, que resultan muy intuitivos para entender la correspondencia entre la versión puramente algebraica de estos problemas y su representación geométrica. Después se introduce el concepto de solución básica factible, que juega un papel fundamental en la resolución de los problemas de programación lineal, ya que una solución óptima será siempre una solución básica factible y además porque el número de soluciones básicas factibles de un problema lineal continuo es finito, lo que acota considerablemente el procedimiento de búsqueda de la solución. A continuación se estudian los fundamentos teóricos del Simplex y los criterios de operación que dan lugar a una versión algebraica del algoritmo. Después se analiza la versión tabular de este algoritmo que simplifica su utilización manual. Finalmente introducimos los métodos que se utilizan para obtener una solución básica factible inicial para el método del Simplex.
Resultados de aprendizaje
Este tema no tiene especial dificultad para un alumno con conocimientos básicos de algebra lineal.
El análisis de sensibilidad para los modelos de programación lineal tiene por objetivo identificar el impacto sobre la solución del problema original tras determinadas modificaciones en los parámetros del problema, sin tener que resolver el problema nuevamente cada vez que se modifica uno de tales parámetros.
Este tema requiere conocimientos básicos de algebra lineal y una buena comprensión del tema anterior.
En muchos problemas de programación lineal sólo tienen sentido aquellas soluciones en las que todas o algunas de las variables de decisión toman valores enteros. Estos problemas proporcionan un marco de modelado flexible y eficiente para formular y resolver muchos problemas de ingeniería. Este tema proporciona una introducción a los principales algoritmos para obtener la solución a este tipo de problemas. En concreto, se estudian los métodos de bifurcación y acotación y el de los planos de corte. En el primero la solución original se obtiene resolviendo una secuencia ordenada de problemas que se obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales. En el segundo se resuelve el problema original relajado en el que se incluyen restricciones adicionales, denominadas planos de corte, que reducen la región factible sin excluir soluciones que cumplen las condiciones de integralidad.
Este tema requiere conocimientos básicos de algebra lineal, una buena comprensión de los dos temas anteriores, yconocimientos básicos de búsquedas heurísticas.
La logística se ocupa del proceso de planificación, implementación y control del flujo eficiente de mercancías, energía o información desde los puntos donde se originan hasta los puntos donde se consumen. Una red logística podemos verla como un grafo compuesto por nodos y arcos. Los nodos representan los agentes de una organización (factorías, almacenes, centros de distribución, clientes, etc.), y los arcos son los diferentes medios de transporte entre nodos, por ejemplo trenes, barcos gasoductos, poliductos, etc. En términos muy generales podemos decir que una red logística adquiere productos primarios (energía, información, materias primas, etc.), los transforma en productos finales y los distribuye a sus clientes. La gestión de una red logística consiste en tomar las decisiones que optimizan su funcionamiento. La función de óptimo se corresponde generalmente con una función de coste (minimización de gasto y maximización de beneficios) aunque pueden existir términos en esta función relacionados con otros aspectos del funcionamiento, como por ejemplo, la garantía de niveles de seguridad de los stocks. Un sistema de decisión logística parte del conocimiento de las alternativas de transporte y transformación de la red y determina el subconjunto que satisface unos objetivos preestablecidos. Estos sistemas de decisión se plantean frecuentemente como problemas de optimización matemática y serán objeto de estudio en este tema.
La dificultad principal de este tema está en la comprensión global de los objetivos que se pretenden conseguir con las redes logísticas de transporte..
La planificación de la producción en plantas de proceso es uno de los problemas más complejos e importantes para una amplia variedad de procesos industriales. Para el caso de plantas de proceso discontinuo el problema es planificar la producción sobre un horizonte de planificación discreto. Este tipo de problemas se conocen en la literatura como problemas DLSP (Discrete Lot Sizing and Scheduling Problems). En el caso más sencillo, un productor fabrica un artículo cuya demanda varía en el tiempo, de acuerdo con el gráfico de la figura, donde el tiempo pueden ser horas, días, semanas e incluso meses.
La dificultad principal de este tema está en la comprensión de los procesos industriales que se modelan en el mismo..
Introducción
Los problemas de programación lineal son muy comunes y cubren un amplio rango de aplicaciones. Sin embargo, en la vida real aparecen frecuentemente problemas que no tienen comportamientos lineales. Cuando alguna de las restricciones, la función objetivo, o ambos, son no lineales, se dice que se trata de un problema de programación no lineal. Los modelos de programación no-lineal son más complejos de resolver que sus análogos lineales. Sin embargo muchos de ellos es posible resolverlos mediante aproximaciones lineales.
Al ser un tema introductorio al modelado de sistemas no lineales no presenta ninguna dificultad especial...