Saltar al contenido
Volver a los resultados

Programación Lineal Estocástica — Optimización bajo Incertidumbre con Parámetros Aleatorios

Propuesto por
George B. Dantzig
Año
1955
Tipo
Stochastic optimization model
Familia
Simulation / optimization

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Programación Lineal Estocástica (PLE) extiende la programación lineal clásica a entornos donde algunos parámetros del modelo —costos, demandas, disponibilidad de recursos— son inciertos y se modelan como variables aleatorias.

Al optimizar los costos esperados sobre una distribución de probabilidad de escenarios, la PLE produce decisiones que se mantienen factibles y casi óptimas en un rango de futuros posibles, en lugar de para un único estado del mundo asumido.

La intuición detrás del método

La programación lineal clásica asume que cada coeficiente se conoce con precisión. En la práctica, la demanda futura, los precios y los rendimientos son inciertos. La PLE incorpora esta incertidumbre directamente en el modelo: en lugar de optimizar para un escenario fijo, el planificador elige acciones de primera etapa ahora, observa qué escenario se materializa y luego toma acciones de recurso para corregir cualquier déficit o excedente. El objetivo minimiza el costo total esperado en todos los escenarios, equilibrando los costos de compromiso con los costos de recurso esperados. Esto refleja la lógica gerencial real: hoy se decide qué pre-ordenar, y mañana se puede comprar más con un recargo o vender el excedente con un descuento.

Historia

La programación estocástica fue iniciada por George Dantzig, quien introdujo el modelo de dos etapas en 1955, poco después de desarrollar el método simplex. Beale (1955) propuso ideas similares de forma independiente. El campo fue sistematizado por el influyente libro de texto de Birge y Louveaux de 1997 y por el desarrollo del algoritmo de descomposición en forma de L (Benders) en las décadas de 1960 a 1980. La PLE ahora sustenta decisiones operativas en energía, logística y finanzas en todo el mundo.

Cuándo usarlo

Utilice la PLE cuando: (1) los parámetros de entrada clave son genuinamente inciertos y pueden caracterizarse por una distribución de probabilidad o un conjunto de escenarios empíricos; (2) las decisiones deben tomarse antes de que se resuelva la incertidumbre, pero las acciones correctivas son posibles después a un costo; (3) el objetivo y las restricciones son lineales en las variables de decisión. Las aplicaciones típicas incluyen la planificación de la producción, el diseño de la cadena de suministro, la gestión de energía y la optimización de carteras. NO utilice la PLE cuando: la incertidumbre no puede cuantificarse probabilísticamente (utilice optimización robusta en su lugar); la relación entre decisiones y resultados es no lineal o entera (utilice programación entera estocástica o programación dinámica estocástica); el conjunto de escenarios es demasiado grande para enumerar y la descomposición es computacionalmente inviable; o cuando un análisis de sensibilidad determinista más simple es suficiente para comprender el impacto de la incertidumbre.

Limitaciones y consideraciones

  • Requiere especificar una distribución de probabilidad o un conjunto de escenarios para los parámetros inciertos; esta suposición distribucional a menudo es difícil de validar.
  • La carga computacional crece rápidamente con el número de escenarios y variables de primera etapa; los problemas grandes requieren descomposición y recursos significativos del solucionador.
  • Restringido a objetivos y restricciones lineales; las estructuras no lineales o enteras requieren extensiones que añaden mayor complejidad.
  • El objetivo de valor esperado puede ignorar los riesgos de cola; las variantes aversas al riesgo (CVaR, restricciones de probabilidad) añaden sobrecarga de modelado y computacional.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Incorpora directamente la incertidumbre probabilística en la optimización, produciendo decisiones robustas en todos los escenarios en lugar de para un futuro único asumido.
  • El marco de dos etapas refleja fielmente los procesos de decisión reales: comprometerse ahora, adaptarse después con recurso.
  • El Valor de la Solución Estocástica (VSS) y el EVPI proporcionan métricas basadas en principios para comunicar el beneficio de modelar la incertidumbre.
  • Bien respaldado por algoritmos maduros (descomposición en forma de L / Benders) y solucionadores comerciales (CPLEX, Gurobi).
  • Escala a grandes problemas prácticos mediante descomposición; paralelizable entre escenarios.

Aplicaciones

  • Planificación de sistemas de energía eléctrica y compromiso de unidades bajo incertidumbre en la generación renovable y la demanda.
  • Diseño de redes de cadena de suministro con demanda de clientes, tiempos de entrega o costos de transporte inciertos.
  • Planificación de cultivos y riego bajo incertidumbre en las precipitaciones y los precios de los productos básicos.
  • Optimización de carteras financieras con rendimientos de activos inciertos bajo restricciones presupuestarias y regulatorias.
  • Gestión de ingresos de aerolíneas y programación de tripulaciones bajo demanda incierta de pasajeros.
  • Posicionamiento previo de suministros de ayuda humanitaria antes de escenarios de desastre inciertos.

Cómo funciona

Cómo funciona

1

Formule el modelo de dos etapas: las variables de primera etapa x representan decisiones "aquí y ahora" tomadas antes de que se resuelva la incertidumbre; el objetivo minimiza el costo de primera etapa c^T x más el costo de recurso esperado E[Q(x,xi)] sobre el vector aleatorio xi. Las restricciones Ax = b deben cumplirse para las decisiones de primera etapa, independientemente del escenario.

Fórmula
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

Represente el vector aleatorio xi mediante un conjunto discreto de escenarios {xi_1, ..., xi_S}, cada uno con una probabilidad p_s que suma 1. Los escenarios pueden derivarse de datos históricos, de la opinión de expertos o de muestreo Monte Carlo. La calidad del conjunto de escenarios determina críticamente la calidad de la solución; las técnicas de reducción de escenarios (p. ej., agrupamiento por distancia de Wasserstein) se aplican comúnmente para mantener el tamaño del problema manejable.

3

Para cada escenario xi_s, resuelva el subproblema de recurso: dada la decisión de primera etapa x, encuentre la acción correctiva más barata y_s que satisfaga W y_s = h(xi_s) - T(xi_s) x, y_s >= 0. Si no existe un recurso factible, se incurre en una gran penalización (o infactibilidad), lo que indica que la decisión de primera etapa fue demasiado agresiva.

Fórmula
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

Resuelva la forma extensa completa (todos los escenarios apilados como un gran problema de programación lineal) para conjuntos de escenarios pequeños a medianos, o aplique la descomposición de Benders (método en forma de L) para conjuntos grandes. El método en forma de L añade iterativamente cortes de optimalidad y factibilidad a un problema maestro hasta la convergencia, explotando la estructura diagonal por bloques de los subproblemas de escenario.

5

Evalúe la calidad de la solución mediante el Valor de la Solución Estocástica (VSS) —la ganancia sobre la solución determinista de valor medio— y el Valor Esperado de la Información Perfecta (EVPI) —el límite superior de lo que valdría una previsión perfecta. Informe la decisión de primera etapa x*, el costo total esperado y los costos de recurso por escenario para comunicar el perfil de riesgo a los tomadores de decisiones.

Errores comunes

  • Usar muy pocos escenarios produce una solución sesgada que tiene un rendimiento deficiente fuera de la muestra; siempre valide con pruebas de escenarios fuera de la muestra.
  • Confundir la solución determinista de valor medio (sustituir valores esperados) con la solución estocástica; el VSS puede ser grande incluso cuando los parámetros parecen estables.
  • Ignorar la factibilidad del recurso: si el subproblema de la segunda etapa puede ser infactible para algunos escenarios, el modelo necesita restricciones de recurso completas o penalizaciones explícitas.
  • Sobreajuste a la distribución de escenarios históricos sin realizar pruebas de estrés contra escenarios de cola o adversos, especialmente en aplicaciones de cadena de suministro o financieras.
  • Tratar la programación lineal estocástica como un reemplazo directo de la optimización robusta cuando el tomador de decisiones es en realidad adverso a la incertidumbre en lugar de neutral al valor esperado.

Preguntas frecuentes

¿Cuál es la diferencia entre la programación lineal estocástica y la optimización robusta?

La PLE minimiza el costo esperado sobre una distribución de probabilidad de escenarios y permite acciones de recurso después de que se resuelve la incertidumbre. La optimización robusta, en cambio, optimiza el peor caso sobre un conjunto de incertidumbre sin asumir una distribución de probabilidad y típicamente produce una única solución fija que es factible para todos los escenarios. La PLE es preferible cuando las probabilidades pueden estimarse; la optimización robusta es preferible cuando solo se conoce el conjunto de incertidumbre o cuando la protección contra riesgos de cola es primordial.

¿Cuántos escenarios se necesitan típicamente?

Esto depende de la dimensión del problema y la complejidad distribucional. Decenas a unos pocos cientos de escenarios a menudo son suficientes para problemas de planificación si se generan de manera inteligente (p. ej., mediante ajuste de momentos o reducción de escenarios). La aproximación de la media muestral (SAA) basada en Monte Carlo puede requerir miles de escenarios para soluciones de alta precisión, con intervalos de confianza que guían la convergencia.

¿Puede la PLE manejar decisiones enteras o binarias?

No directamente; las variables enteras requieren Programación Entera Estocástica (SIP) o Programación Entera Mixta Estocástica (SMIP), que son sustancialmente más difíciles computacionalmente. La PLE se aplica solo cuando todas las variables de decisión son continuas.

¿Qué mide el Valor de la Solución Estocástica (VSS)?

VSS = EEV - RP, donde EEV es el costo esperado de la solución determinista de valor medio evaluada en todos los escenarios, y RP es el verdadero óptimo estocástico (problema de recurso). Un VSS alto indica que ignorar la incertidumbre y usar parámetros promedio conduce a resultados sustancialmente peores.

¿Qué solucionadores y software admiten la programación lineal estocástica?

Los solucionadores comerciales como CPLEX y Gurobi pueden resolver la forma extensa directamente. Los marcos de código abierto incluyen lectores de formato SMPS, PySP (parte de Pyomo) y el paquete Julia StochasticPrograms.jl. Para problemas a gran escala, las implementaciones personalizadas de descomposición en forma de L son comunes en la investigación y la industria.

Métodos relacionados

Fuentes

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    Abrir referencia de la publicación
    Copiado.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 9780387982175
    Copiado.