Programación estocástica

Programación estocástica (del inglés stochastic programming) es una rama de la programación matemática que desarrolla modelos y métodos para resolver problemas de optimización en condiciones de incertidumbre, donde algunos parámetros del modelo no se conocen con exactitud, sino que se representan como variables aleatorias con distribuciones de probabilidad conocidas o estimadas^[1]^[2].

A diferencia de los problemas deterministas, donde todos los datos se consideran constantes dadas, la programación estocástica tiene como objetivo encontrar una solución (o una política de toma de decisiones) que sea óptima en algún sentido estadístico. Generalmente, esto significa minimizar o maximizar la esperanza matemática de la función objetivo^[1]. La idea clave es encontrar una política de toma de decisiones que sea la mejor "en promedio" para todas las posibles realizaciones de los parámetros aleatorios, lo cual es especialmente relevante para problemas donde las decisiones se toman repetidamente en condiciones similares (por ejemplo, en la gestión de inventarios o sistemas energéticos)^[3].

Formulación matemática del problema

En su forma general, un problema de programación estocástica puede formularse como: $min_{x \in X} 𝔼 [f (x, ξ)]$ donde:

$x$ — es el vector de variables de decisión (soluciones) que se deben determinar.
$X$ — es el conjunto de soluciones factibles para $x$ , definido por restricciones deterministas.
$ξ$ — es un vector aleatorio que representa los parámetros inciertos del problema (por ejemplo, demanda, precios, condiciones climáticas).
$f (x, ξ)$ — es la función objetivo, cuyo valor depende tanto de la decisión tomada $x$ como de la realización del vector aleatorio $ξ$ .
$𝔼 [\cdot]$ — es el operador de esperanza matemática, calculado sobre la distribución de probabilidad del vector $ξ$ .

Un principio fundamental que subyace en los modelos estocásticos multietapa es el principio de no anticipación (del inglés non-anticipativity principle). Este establece que las decisiones tomadas en cualquier etapa solo pueden depender de la información disponible hasta ese momento y no pueden "anticipar el futuro"^[2].

Problema de dos etapas con recurso

El modelo más común es el problema de dos etapas con recurso (del inglés two-stage stochastic program with recourse)^[1]. El proceso de toma de decisiones se divide en dos etapas:

Primera etapa: Se toma una decisión "aquí y ahora" (here-and-now), determinando el vector $x$ . Esta decisión debe tomarse antes de que se conozca la realización específica del vector aleatorio $ξ$ .
Segunda etapa: Una vez que ocurre el evento aleatorio, se toma una decisión correctiva o de recurso (recourse decision), el vector $y (ξ)$ , con el fin de minimizar las consecuencias negativas o aprovechar las oportunidades favorables que surgen de la combinación de la decisión de la primera etapa $x$ y el resultado $ξ$ .

Matemáticamente, un problema de programación lineal estocástica de dos etapas se formula de la siguiente manera: $min_{x \in ℝ^{n_{1}}} {c^{T} x + 𝔼_{ξ} [Q (x, ξ)]}$ sujeto a las restricciones de la primera etapa: $A x = b, x \geq 0$ . Aquí, $Q (x, ξ)$ es la función de recurso (recourse function), que representa el valor óptimo del problema de la segunda etapa: $Q (x, ξ) = min_{y \in ℝ^{n_{2}}} {q (ξ)^{T} y ∣ T (ξ) x + W y = h (ξ), y \geq 0}$ donde $ξ$ es un vector aleatorio que incluye los parámetros $q (ξ), T (ξ)$ y $h (ξ)$ ; mientras que $c, A, b$ y $W$ son parámetros deterministas^[2].

Propiedades clave y teoremas

Convexidad: Uno de los resultados fundamentales de la teoría es que para un problema de programación lineal estocástica de dos etapas, la función de recurso esperada $Q (x) = 𝔼_{ξ} [Q (x, ξ)]$ es una función convexa. Esta propiedad es de gran importancia, ya que garantiza que el problema general de la primera etapa es un problema de programación convexa, para el cual existen métodos de solución eficientes y el óptimo global coincide con el local^[1].
Equivalente determinista: Si el vector aleatorio $ξ$ tiene un número finito de realizaciones posibles (escenarios) $ξ_{1}, \dots, ξ_{K}$ con probabilidades $p_{1}, \dots, p_{K}$ , el problema de programación estocástica puede reformularse como un único gran problema de optimización determinista. En este caso, la esperanza matemática se reemplaza por una suma ponderada sobre todos los escenarios. Sin embargo, el tamaño de este problema crece linealmente con el número de escenarios, lo que conduce a la "maldición de la dimensionalidad" y hace que este enfoque sea computacionalmente inviable para un gran número de escenarios^[2].

Comparación con la optimización robusta

La programación estocástica es uno de los varios enfoques para la optimización en condiciones de incertidumbre. Su diferencia clave con la optimización robusta radica en la forma en que se modela la incertidumbre y en el criterio de optimalidad^[4].

Comparación de enfoques para la optimización en condiciones de incertidumbre
Criterio	Optimización estocástica	Optimización robusta
Representación de la incertidumbre	Los parámetros son variables aleatorias con una distribución de probabilidad conocida	Los parámetros pertenecen a un conjunto de incertidumbre definido, no se requiere distribución
Criterio de optimalidad	Optimización de la esperanza matemática de la función objetivo	Optimización del peor caso (minimax)
Naturaleza de la solución	Una política que es óptima "en promedio", pero puede ser infactible para escenarios raros	Una solución garantizada para ser factible para todas las realizaciones; puede ser conservadora

Ejemplos

Problema del vendedor de periódicos (del inglés newsvendor problem): Un problema clásico de gestión de inventarios donde un vendedor debe decidir qué cantidad de un producto comprar sin conocer la demanda futura exacta. La solución equilibra el riesgo de pérdidas por excedentes con el riesgo de lucro cesante por escasez.
Problema del granjero: Un granjero decide cuántos acres de tierra destinar a diferentes cultivos en una superficie total, sin conocer el clima futuro que afectará el rendimiento. Una vez que se conoce el clima, el granjero puede tomar acciones correctivas (por ejemplo, vender el excedente o comprar la cosecha faltante en el mercado)^[5].

Véase también

Referencias

↑ ^1.0 ^1.1 ^1.2 ^1.3 Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). Lectures on Stochastic Programming: Modeling and Theory. Society for Industrial and Applied Mathematics (SIAM).
↑ ^2.0 ^2.1 ^2.2 ^2.3 Birge, J. R., & Louveaux, F. (2011). Introduction to Stochastic Programming (2nd ed.). Springer Science+Business Media.
↑ "Programación estocástica". Wikipedia. [1]
↑ Gorissen, B. L., Yanıkoğlu, İ., & den Hertog, D. (2015). A practical guide to robust optimization. Omega, 53, 124-137.
↑ Bricker, D. L. SLPwR: Farmer Problem. University of Iowa. [2]

[shapiro2009-1] 1.0 ^1.1 ^1.2 ^1.3 Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). Lectures on Stochastic Programming: Modeling and Theory. Society for Industrial and Applied Mathematics (SIAM).

[birge2011-2] 2.0 ^2.1 ^2.2 ^2.3 Birge, J. R., & Louveaux, F. (2011). Introduction to Stochastic Programming (2nd ed.). Springer Science+Business Media.

[wiki-sp-3] "Programación estocástica". Wikipedia. [1]

[gorissen2015-4] Gorissen, B. L., Yanıkoğlu, İ., & den Hertog, D. (2015). A practical guide to robust optimization. Omega, 53, 124-137.

[farmer-problem-uiowa-5] Bricker, D. L. SLPwR: Farmer Problem. University of Iowa. [2]

[1]

[2]

[3]

[4]

[5]

Programación estocástica

Contents

Formulación matemática del problema

Problema de dos etapas con recurso

Propiedades clave y teoremas

Comparación con la optimización robusta

Ejemplos

Véase también

Referencias

Navigation menu

Programación estocástica

Formulación matemática del problema

Problema de dos etapas con recurso

Propiedades clave y teoremas

Comparación con la optimización robusta

Ejemplos

Véase también

Referencias

Navigation menu

Search