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.

1. Formulación de un modelo de programación lineal.
2. Propiedades del modelo lineal.
3. Interpretación económica del problema de programación lineal.
4. Introducción al lenguaje de modelado OPL (Optimization Programming Language).
5. Representación gráfica de los problemas de programación lineal.
6. Clasificación de los problemas de programación lineal  según el tipo de solución.
7. Formulación matricial del problema de programación lineal.
8. Formulación de algunos problemas prácticos de programación lineal. 

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.

• Aprender a formular el modelo de un problema de programación lineal.
• Conocer las propiedades de los modelos de programación lineal.
• Conocer la expresión de un modelo de programación lineal con lenguajes de modelado.
• Conocer los elementos básicos del lenguaje de modelado OPL.
• Saber los tipos de soluciones que pueden tener los problemas de programación lineal.
• Modelar matemáticamente y resolver en OPL varios problemas de programación lineal.

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.

Contenidos.

1. Dominios de aplicación de la Programación Entera.
2. Variables indicadoras: control del valor de una variable continua.
3. Modelado de la disyunción entre dos restricciones lineales utilizando variables binarias.
4. Conversión de variables enteras en binarias.
5. Expresión del producto de dos variables binarias.
6. Expresión del producto de una variable binaria por otra continua no negativa.
7. Variables indicadoras: control de la imposición de una restricción lineal.
8. Representación de operadores lógicos.

Introducció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.

Resultados de aprendizaje.

• Conocer la programación lineal entera y los dominios de aplicación.
• Aprender a formular el modelo de un problema de programación lineal entera.
• Modelar relaciones lógicas entre restricciones con variables binarias.
• Expresar un problema entero general como un problema binario.
• Modelar y resolver en OPL varios problemas típicos de programación lineal entera.
• Expresar algunos comportamientos no lineales como problemas enteros.

Nivel de dificultad.

Este tema  tiene cierto grado de dificultad en la expresion de las relaciones lógicas entre restricciones utilizando variables binarias.

Contenidos.

1. Alternativas para el desarrollo de modelos de optimización.
2. Lenguajes de modelado.
3. Entorno de desarrollo para OPL.
4. Perfil operativo de la programación con restricciones (CP).
5. Perfil operativo de la programación lineal continua.
6. Estructura general de un programa OPL.
7. Parámetros formales.
8. Conexión de OPL con una hoja de cálculo.
9. Ejemplos de utilización de OPL.

Introducción.

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.

Resultados de aprendizaje.

• Conocer las diferentes alternativas para expresar y ejecutar problemas de optimización.
• Estudiar la estructura general de un lenguaje de modelado a través de OPL.
• Conocer los principios operativos de los tipos de problemas expresables en OPL.
• Utilizar las construcciones iterativas y operadores de agregación.
• Intercambiar datos  entre OPL y una hoja de cálculo Excel.

Nivel de dificultad.

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..

Contenidos.

1. Resolución gráfica de problemas lineales.
2. Formas equivalentes de un problema de programación lineal.
3. Forma canónica y estándar de un problema de programación lineal.
4. Conceptos básicos de programación lineal.
5. Correspondencia entre los puntos extremos y las soluciones básicas factibles.
6. Búsqueda exhaustiva de soluciones básicas.
7. Método del Simplex.

Introducción.

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

• Resolver  de forma gráfica un problema de programación lineal continuo.
• Estudiar las formas equivalentes de representación de los problemas lineales.
• Aprender los conceptos de álgebra  para resolver programas lineales continuos.
• Resolver un problema de programación lineal por enumeración de soluciones básicas.
• Resolver un problema lineal utilizando la versión algebraica del simplex.
• Resolver un problema de programación lineal utilizando la versión tabular del simplex.

Nivel de dificultad.

Este tema no tiene especial dificultad para un alumno con conocimientos básicos de algebra lineal.

Contenidos.

1. Sensibilidad en la programación lineal.
2. Dualidad en la programación lineal.
3. Obtención del problema dual a partir del primal.
4. Teoremas de dualidad.
5. Ejemplos.        

Introducción.

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.

Resultados de aprendizaje.

• Conocer el concepto de sensibilidad en la programación lineal.
• Conocer el concepto de dualidad en la programación lineal.
• Aprender a formular el modelo del problema dual asociado al primal.
• Establecer la relación entre las sensibilidades del problema primal y las soluciones del dual.

Nivel de dificultad.

Este tema requiere conocimientos básicos de algebra lineal y una buena comprensión del tema anterior.

Contenidos.

1. Características generales de los problemas de programación lineal entera.
2. Método de resolución de problemas enteros mediante bifurcación y acotación.
3. Técnicas de pre-procesamiento de problemas enteros.
4. Generación de planos de corte para problemas binarios.
5. Método híbrido de bifurcación y planos de corte.

Introducció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. 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.

Resultados de aprendizaje.

• Conocer las principales técnicas de programación entera.
• Estudiar el método de bifurcación y acotación.
• Analizar las diferentes estrategias de búsqueda en el algoritmo bifurcación y acotación.
• Utilizar el algoritmo para anterior para resolver pequeños problemas de programación entera.
• Manejar algunas técnicas de pre-procesamiento para problemas binarios.
• Generar planos de corte en problemas de programación lineal entera binarios.
• Conocer el método de bifurcación y  planos de corte (branch@cut).

Nivel de dificultad.

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.

Contenidos.

1. Redes logísticas: niveles en la gestión de una red logística.
2. Redes de transporte.
3. Redes de conducción de fluidos.
4. Modelo lineal de una red de fluidos: dimensión espacial.
5. Modelo lineal de una red de fluidos: dimensión temporal.

Introducción.

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.

Resultados de aprendizaje.

• Conocer el planteamiento de la gestión de una red de transporte logístico como un problema de optimización matemática.
• Estudiar redes logísticas de transporte.
• Estudiar redes  logísticas de conducción de fluidos.
• Analizar y plantear algunos ejemplos.

Nivel de dificultad.

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..

Contenidos.

1. Problemas de planificación de la producción.
2. Planificación de la producción de electricidad en centrales térmicas.
3. Planificación de la producción de diferentes derivados en una refinería.

Introducción.

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.

Resultados de aprendizaje.

• Analizar ejemplos de problemas de optimización de un proceso industrial.
• Abordar un problema similar como proyecto en el que el alumno debe:

• Desarrollar un modelo matemático del mismo.
• Implementarlo mediante la herramienta ILOG OPL Studio.
• Obtener la solución óptima en un escenario concreto.
• Proponer mejoras en el modelo para contemplar un mayor número de características.

Nivel de dificultad.

La dificultad principal de este tema está en la comprensión de los procesos industriales que se modelan en el mismo..

Contenidos.

1. Programación matemática no-lineal.
2. Funciones separable.
3. Restricción SOS1 y SOS2.
4. Modelado de la función lineal por tramos (picewise).
5. Función lineal de dos o más variables.
6. Ejemplo de aproximación lineal de 2 variables.

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.

Resultados de aprendizaje

• Conocer el concepto de convexidad  aplicados a la función objetivo y a las restricciones de un problema de optimización.
• Utilizar el concepto de programación  separable.
• Definir e implementar las restricciones sobre conjuntos ordenados de variables SOS1 y SOS2.
• Aproximar una función no-lineal de una variable por una lineal a tramos utilizando SOS2 y/o variables binarias.
• Aproximar una función no-lineal de dos variables utilizando SOS2.

Nivel de dificultad.

Al ser un tema introductorio al modelado de sistemas no lineales no presenta ninguna dificultad especial...