Optimización Estocástica

La optimización estocástica trata problemas de Programación Matemática en cuya formulación aparece algún elemento aleatorio, es decir, mientras que en el caso determinístico todos los datos o parámetros que aparecen son números conocidos, en Programación Estocástica dichos parámetros (o parte de ellos ) no se conocen con certeza.

La programación estocástica tiene su inicio con los trabajos de Dantzig [28] y Beale [7]. En esa misma década alcanzó con Markowitz [52] una aplicación muy destacada al problema de selección de carteras lo cual lo llevaría a la consecución del Premio Nobel. Prekopa [62] propone dos definiciones para Programación Estocástica:

Definición 1 Es la ciencia que ofrece soluciones para problemas formulados en conexión con sistemas estocásticos, en los que el problema numérico resultante a resolver es un problema de Programación Matemática de tamaño no trivial.

Definición 2 Es una ciencia que trata problemas de Programación Matemática en los que algunos de los parámetros son variables aleatorias. Su metodología se basa en el estudio de las propiedades estadísticas del valor óptimo aleatorio o de otras variables aleatorias presentes en el problema o bién en la reformulación del problema a otro problema de decisión en el que se tiene en cuenta la distribución de probabilidad conjunta de los parámetros aleatorios.

Básicamente existen dos tipos de modelos de programación estocástica:

Modelos “Esperar y Ver" (“wait and see") o modelos de programación estocástica pasiva. Estos modelos consisten en esperar la ocurrencia de un evento incierto (realización de variables aleatorias) para luego optimizar. Sin embargo en ocasiones puede ser de gran interés conocer la distribución de probabilidad del valor objetivo óptimo o algunos de sus momentos (valor esperado o varianza) antes de conocer la realización de sus variables aleatorias. Tales problemas se llaman problemas de distribución y se estudian en: [10,54,62].

Modelos “aquí y ahora" (“here and now") o modelos de programación estocástica activa basados en optimización inmediata en base a alguna medida de probabilidad [23].

Por otro lado Ermoliev and Wets [30] proponen dos esquemas de modelos de programación estocástica: Modelos Adaptativos y Modelos con Recursos. En los modelos adaptativos, los cuales usan distribuciones posteriores, se presenta dos casos: problemas de distribución y modelos anticipados. En los problemas de distribución se puede obtener la distribución de probabilidad o algunas características de las variables aleatorias tales como: la distribución de probabilidad del valor óptimo aleatorio o la solución optimal, para el caso de programas lineales aleatorios. En el caso de los modelos anticipados sólo se tienen las distribuciones apriori de los parámetros. En cada uno de estos modelos, la función objetivo inducida o el conjunto factible pueden estar definidos en términos de otras probabilidades o momentos de funciones de distribución tales como:

a): Modelos probabilísticos: Los cuales usan probabilidades.
b): Modelos basados en Momentos: Los cuales usan momentos.
c): Modelos Híbridos: que vienen a ser una combinación de restricciones probabilísticas con función objetivo basada en momentos.

En los modelos con recursos, las variables de decisión de un problema de optimización bajo incertidumbre se dividen en dos etapas. Las variables de la primera etapa son aquellas que tienen que ser decididas antes de la realización actual de los parámetros de incertidumbre, mientras que las variables de la segunda etapa se interpretan como medidas correctivas o de recursos, que surgen debido a una realización particular de la incertidumbre. El concepto de recurso ha sido aplicado a la programación lineal, no lineal y entera. Estudios de optimización estocástica se pueden encontrar en los siguientes artículos:

“Optimization under uncertainty: state -of-the art and opportunities", [58]. En este artículo se revisa la teoría y metodología desarrollada para hacer frente a la complejidad de los problemas de optimización bajo incertidumbre.
“Uncertain Programming: Optimization Theory in Uncertain Environments", [45]; en donde se proporciona una breve introducción a la programación con incertidumbre, incluyendo ideas de modelado híbrido, algoritmos inteligentes y aplicaciones en sistemas de decisión.
Anteriormente se mencionó que los problemas de optimización estocástica son problemas de gran escala, por lo cual requieren de algún método de solución. Para este fin se puede consultar los siguientes artículos:
“Optimización bajo incertidumbre, técnicas de descomposición y aplicación en GRID",[44]; en donde se revisan los conceptos de optimización estocástica y se presentan dos enfoques de solución: Descomposición de Banders y Relajación Lagrangeana, con aplicación a la coordinación hidrotérmica. También se puede consultar el artículo:
“Stochastic programming approach to optimization under uncertainty", [72]. Aquí se plantea la solución de problemas de optimización estocástica mediante el Método de Montecarlo. Un método similar se encuentra en [42].

Se han desarrollado diversas aplicaciones de optimización estocástica, en las áreas de planeamiento de la producción [14], scheduling [12], localización [43], expansión de la capacidad [2], gestión de control y ambiente [13], telecomunicaciones [40], diseño y optimización de sistemas de procesos químicos [1], y finanzas [21]. Más recientes aplicaciones, destacan en la toma de decisión en emergencia a causa de inundaciones [34]; y en las decisiones de reemplazo en las empresas de manufactura [80].

Por otro lado, una clase importante de problemas de decisión y de optimización es el área de Scheduling, en donde se deben asignar recursos limitados a tareas que deben ser procesadas a lo largo del tiempo y bajo ciertas restricciones. En este caso los parámetros que intervienen en el problema son: tiempo de procesamiento, tiempos de preparación, fecha de iniciación o fecha de vencimiento; los cuales también presentan incertidumbre en algunos casos.

Por lo tanto, dichos parámetros son estudiados desde un enfoque estocástico ya que éstos se asumen como variables aleatorias con distribuciones de probabilidad conocidas. Mayores detalles se puede consultar en [12,17]; aquí los autores brindan un panorama general del enfoque estocástico para problemas de scheduling.