El objetivo de la asignatura consiste en presentar los conceptos básicos, nuevas tecnologías de modelización y desarrollos algorítmicos para introducir un adecuado tratamiento de la incertidumbre en problemas de programación matemática en los que, a parte de los parámetros conocidos y de los parámetros no conocidos pero controlables por el modelo (comúnmente llamados variables), existen otros parámetros exógenos desconocidos por el modelizador en el momento de la toma de decisiones y sobre los que no tiene control. Un adecuado tratamiento de la información de que se dispone sobre estos parámetros es crucial para la obtención de soluciones al problema que, por definición, no pudiendo ser óptimas para todos y cada uno de los problemas deterministas que corresponden a la realización de dichos parámetros, sí en cambio sean soluciones robustas El problema de la incertidumbre se ha venido tratando regularmente en la literatura sobre programación matemática desde 1955, año en el que se publicaron los trabajos seminales sobre la materia debidos a Beale y Dantzig, independientemente. No obstante, dado el alto grado de sofisticación que la resolución del problema requiere, un tratamiento para resolver problemas prácticos de programación matemática con incertidumbre no se ha podido abordar hasta la eclosión del maridaje de Ciencias Matemáticas y Ciencias de la Computación en los años 80. En los avances teóricos en Programación Estocástica se trata la incertidumbre a base de utilizar el riesgo con esquemas en los mismos modelos de programación matemática y, por tanto, en su correspondiente algoritmia. Es muy frecuente, por otra parte, observar la reducción de toda la información estocástica que se tiene sobre el problema a meros promedios de los valores de los parámetros inciertos. De esta forma, en lugar de proporcionar soluciones para un problema estocástico, se proporcionan soluciones para un problema determinista que, puede que no exista, con el riesgo inherente que conlleve la solución a proporcionar, que incluso puede que ni siquiera sea factible para muchos escenarios. La solución del modelo, llamada solución robusta, minimiza el "pesar de tomar una solución erronea". Se consideran dos tipos de funciones de mérito, sean, la minimización de la deviacion esperada de la solución robusta con respecto a la solución óptima para los escenarios, y la minimización del valor esperado de la función objetivo sobre el conjunto de escenarios. Se contemplan tres tipos de recursiín, sean, simple, parcial y total (o completa). Se estudian diferentes represntaciones matemáticas del modelo determinista equivalente al modelo estocástico, sea, representación compacta, representación por variables divididas via grupos de escenarios y representacion por variables divididas via escenarios. Así mismo se estudian tres tipos de decomposiciones, sean descomposición de Benders, descomposición Lagrangiana (aumentada) y descomposición basada en programación dinámica estocástica.
Objetivos globales teoría
El objetivo de la asignatura consiste en presentar los conceptos básicos, nuevas tecnologías de modelización y desarrollos algorítmicos para introducir un adecuado tratamiento de la incertidumbre en problemas de programación matemática en los que, a parte de los parámetros conocidos y de los parámetros no conocidos pero controlables por el modelo (comúnmente llamados variables), existen otros parámetros exógenos desconocidos por el modelizador en el momento de la toma de decisiones y sobre los que no tiene control. Un adecuado tratamiento de la información de que se dispone sobre estos parámetros es crucial para la obtención de soluciones al problema que, por definición, no pudiendo ser óptimas para todos y
cada uno de los problemas deterministas que corresponden a la realización de dichos parámetros, sí en cambio sean soluciones robustas
Temas Teoría (Contenidos)
Tema 1. Optimización bajo incertidumbre. Motivación
1.1 Introducción. Casos ilustrativos
1.2 Formulación general del modelo
1.3 Formulación de la aversión al riesgo y condiciones probabilísticas
1.4 Conceptos básicos en el análisis de la bondad de la solución estocástica
Tema 2. Modelización estocástica vía Análisis de Escenarios
2.1 Introducción
2.2 Modelo de inmunización de escenarios
2.2.1 Presentación general
2.2.2 Formulación matemática
2.2.3 Función de infactibilidad
2.3 Procedimiento jerárquico en dos pasos
2.4 Optimización robusta
2.4.1 Recursión simple, parcial y plena
2.4.2 Principio de no anticipatividad
2.5 Representaciones equivalentes
2.6 Generación del arbol de escenarios
2.6.1. Redes neuronales artificiales
2.6.2 Análisis de conglomerados
2.6.3 Simulación de Monte Carlo
Tema 3. Representación compacta de modelos estocásticos
3.1 Condiciones de enlace multietapa
3.2 Formulación matemática
3.3 Metodología para la obtención de una solución inicial
3.4 Descomposición de Benders
Tema 4. Representación basada en variables divididas de modelos estocásticos
4.1 Introducción
4.2 Caso ilustrativo. Descomposición de Benders
4.3 Descomposición Lagrangiana
4.3.1 Relajación Lagrangiana
4.3.2 Descomposición Lagrangiana Aumentada
4.4 Problemas estocásticos con condiciones de enlace multietapa
4.4.1 Formulación matemática
4.4.2 Descomposición de Benders
4.4.3 Descomposición Lagrangiana Aumentada
Tema 5. Programación estocástica 2-etapas
5.1 Formulación matemática
5.2 Interpretación geométrica de la descomposición de Benders en el problema estocástico 2-etapas.
5.3 Utilización de la descomposición de Benders. Representación compacta
5.3.1 Algoritmo DBC
5.3.2 Metodología para la computación en paralelo
5.4 Utilización de la descomposición de Benders. Representación con variables divididas
5.4.1 Algoritmo DBVD
5.4.2 Metodología para la computación en paralelo
5.5 Utilización de la descomposición Lagrangiana Aumentada. Representación con variables divididas por grupos de escenarios
5.5.1 Algoritmia DLAG
5.5.2 Metodología para la computación en paralelo
5.6 Utilización de la Descomposición Lagrangiana Aumentada. Representación con variables divididas por escenarios
Tema 6. Programación dinámica estocástica
6.1 Presentación general
6.2 Entorno algorítmico a utilizar
6.2.1 Módulos básicos
6.2.2 Esquema propuesto
6.3 Utilización de la función de coste futuro esperado
6.4 Obtención de la función de coste futuro esperado
6.4.1 Formulación matemática
6.4.2 Coste futuro esperado en función de las variables de enlace
6.5 Estimación de los niveles de referencia de las variables de enlace
Prácticas
Las prácticas de la asignatura consisten en la modelización y resolución de un problema de programación estocástica utilizando el software de optimización CPLEX. En cada sesión práctica el alumno deberá ir avanzando en la modelización, resolución o confección del informe que deberá presentar para evaluación.
Metodología Docente
La parte teórica se desarrollara en el aula de teoría mediante la presentación de los distintos temas que componen la asignatura. Las prácticas se desarrollarán en el aula de Informática con el software más apropiado para su desarrollo.
Sistema de Evaluación
Se realizará un trabajo modelizando y resolviendo un caso por ordenador que supondrá el 50% de la nota de la asignatura. Este caso se puede realizar de forma individual o por un equipo de dos alumnos. El caso es auditable. El examen supondrá el otro 50% de la evaluación y consistirá en una serie de preguntas para cuya contestación no se podrá utilizar apuntes, ni libros. Nota: El trabajo a realizar por ordenador será el mismo para dos convocatorias consecutivas, comenzando desde la primera.
Imprimir información de la asignatura