Programação Linear Estocástica — Otimização sob Incerteza com Parâmetros Aleatórios
- Proposto por
- George B. Dantzig
- Ano
- 1955
- Tipo
- Stochastic optimization model
- Família
- Simulation / optimization
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Programação Linear Estocástica (PLE) estende a programação linear clássica para cenários onde alguns parâmetros do modelo — custos, demandas, disponibilidade de recursos — são incertos e modelados como variáveis aleatórias.
Ao otimizar custos esperados sobre uma distribuição de probabilidade de cenários, a PLE produz decisões que permanecem factíveis e quase ótimas em uma gama de futuros possíveis, em vez de um único estado de mundo assumido.
A intuição por trás do método
A programação linear clássica assume que cada coeficiente é conhecido com precisão. Na prática, a demanda futura, os preços e os rendimentos são incertos. A PLE incorpora essa incerteza diretamente no modelo: em vez de otimizar para um cenário fixo, o planejador escolhe ações de primeira etapa agora, observa qual cenário se materializa e, em seguida, toma ações de recurso para corrigir qualquer deficiência ou excedente. O objetivo minimiza o custo total esperado em todos os cenários, equilibrando os custos de compromisso com os custos esperados de recurso. Isso espelha a lógica gerencial real — você decide hoje o que pré-encomendar e, amanhã, pode comprar mais com um prêmio ou vender o excedente com desconto.
História
A programação estocástica foi pioneira por George Dantzig, que introduziu o modelo de dois estágios em 1955, logo após desenvolver o método simplex. Beale (1955) propôs independentemente ideias semelhantes. O campo foi sistematizado pelo influente livro-texto de Birge e Louveaux de 1997 e pelo desenvolvimento do algoritmo de decomposição L-shaped (Benders) nas décadas de 1960-1980. A PLE agora fundamenta decisões operacionais em energia, logística e finanças em todo o mundo.
Quando usar
Use PLE quando: (1) parâmetros de entrada chave são genuinamente incertos e podem ser caracterizados por uma distribuição de probabilidade ou conjunto de cenários empíricos; (2) decisões devem ser tomadas antes que a incerteza se resolva, mas ações corretivas são possíveis depois com custo; (3) o objetivo e as restrições são lineares nas variáveis de decisão. Aplicações típicas incluem planejamento de produção, projeto de cadeia de suprimentos, despacho de energia e otimização de portfólio. NÃO use PLE quando: a incerteza não pode ser quantificada probabilisticamente (use otimização robusta em vez disso); a relação entre decisões e resultados é não linear ou inteira (use programação inteira estocástica ou programação dinâmica estocástica); o conjunto de cenários é muito grande para enumerar e a decomposição é computacionalmente infactível; ou quando uma análise de sensibilidade determinística mais simples é suficiente para entender o impacto da incerteza.
Limitações e considerações
- Requer a especificação de uma distribuição de probabilidade ou conjunto de cenários para parâmetros incertos — essa suposição de distribuição é frequentemente difícil de validar.
- O fardo computacional cresce rapidamente com o número de cenários e variáveis de primeira etapa; problemas grandes exigem decomposição e recursos significativos do solver.
- Restrito a objetivo e restrições lineares; estruturas não lineares ou inteiras exigem extensões que adicionam mais complexidade.
- O objetivo de valor esperado pode ignorar riscos de cauda; variantes avessas ao risco (CVaR, restrições de chance) adicionam sobrecarga de modelagem e computacional.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Incorpora diretamente a incerteza probabilística na otimização, produzindo decisões robustas em todos os cenários, em vez de para um único futuro assumido.
- A estrutura de dois estágios espelha de perto os processos de decisão reais: comprometer agora, adaptar depois com recurso.
- O Valor da Solução Estocástica (VSS) e o EVPI fornecem métricas principadas para comunicar o benefício da modelagem da incerteza.
- Bem suportado por algoritmos maduros (decomposição L-shaped / Benders) e solvers comerciais (CPLEX, Gurobi).
- Escala para problemas práticos grandes via decomposição; paralelizado entre cenários.
Aplicações
- Planejamento de sistemas de energia elétrica e compromisso de unidades sob geração renovável e demanda incertas.
- Projeto de rede de cadeia de suprimentos com demanda de clientes, prazos de entrega ou custos de transporte incertos.
- Planejamento de safra e irrigação sob chuvas e preços de commodities incertos.
- Otimização de portfólio financeiro com retornos de ativos incertos sob restrições orçamentárias e regulatórias.
- Gerenciamento de receita e escalonamento de tripulação de companhias aéreas sob demanda de passageiros incerta.
- Pré-posicionamento de suprimentos de ajuda em logística humanitária antes de cenários de desastre incertos.
Como funciona
Como funciona
Formule o modelo de dois estágios: as variáveis de primeira etapa x representam decisões aqui-e-agora tomadas antes que a incerteza seja resolvida; o objetivo minimiza o custo de primeira etapa c^T x mais o custo esperado de recurso E[Q(x,xi)] sobre o vetor aleatório xi. As restrições Ax = b devem ser satisfeitas para as decisões de primeira etapa, independentemente do cenário.
Fórmula
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0Represente o vetor aleatório xi através de um conjunto discreto de cenários {xi_1, ..., xi_S} cada um com probabilidade p_s somando 1. Os cenários podem ser extraídos de dados históricos, elicitação de especialistas ou amostragem de Monte Carlo. A qualidade do conjunto de cenários determina criticamente a qualidade da solução; técnicas de redução de cenário (por exemplo, agrupamento por distância de Wasserstein) são comumente aplicadas para manter o tamanho do problema tratável.
Para cada cenário xi_s, resolva o subproblema de recurso: dada a decisão de primeira etapa x, encontre a ação corretiva mais barata y_s que satisfaça W y_s = h(xi_s) - T(xi_s) x, y_s >= 0. Se nenhum recurso factível existir, uma grande penalidade (ou infactibilidade) é incorrida, sinalizando que a decisão de primeira etapa foi muito agressiva.
Fórmula
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0Resolva a forma extensiva completa (todos os cenários empilhados como um grande LP) para conjuntos de cenários pequenos a médios, ou aplique a decomposição de Benders (método L-shaped) para conjuntos grandes. O método L-shaped adiciona iterativamente cortes de otimalidade e factibilidade a um problema mestre até a convergência, explorando a estrutura de bloco diagonal dos subproblemas de cenário.
Avalie a qualidade da solução através do Valor da Solução Estocástica (VSS) — o ganho sobre a solução determinística de valor médio — e o Valor Esperado da Informação Perfeita (EVPI) — o limite superior do que a previsão perfeita valeria. Relate a decisão de primeira etapa x*, o custo total esperado e os custos de recurso por cenário para comunicar o perfil de risco aos tomadores de decisão.
Erros comuns
- Usar poucos cenários produz uma solução enviesada que tem desempenho ruim fora da amostra; sempre valide com teste fora da amostra de cenários.
- Confundir a solução determinística de valor médio (inserir valores esperados) com a solução estocástica — o VSS pode ser grande mesmo quando os parâmetros parecem estáveis.
- Ignorar a factibilidade do recurso: se o subproblema de segundo estágio puder ser infactível para alguns cenários, o modelo precisa de restrições de recurso completas ou penalidades explícitas.
- Sobreajuste à distribuição histórica de cenários sem teste de estresse contra cenários de cauda ou adversários, especialmente em aplicações de cadeia de suprimentos ou financeiras.
- Tratar LP estocástico como substituto direto para otimização robusta quando o tomador de decisão é realmente avesso à incerteza em vez de neutro em relação ao valor esperado.
Perguntas frequentes
Qual é a diferença entre programação linear estocástica e otimização robusta?
A PLE minimiza o custo esperado sobre uma distribuição de probabilidade de cenários e permite ações de recurso após a resolução da incerteza. A otimização robusta, em vez disso, otimiza o pior caso sobre um conjunto de incerteza sem assumir uma distribuição de probabilidade e tipicamente produz uma única solução fixa que é factível para todos os cenários. A PLE é preferível quando as probabilidades podem ser estimadas; a otimização robusta é preferível quando apenas o conjunto de incerteza é conhecido ou quando a proteção contra risco de cauda é primordial.
Quantos cenários são tipicamente necessários?
Isso depende da dimensão do problema e da complexidade distribucional. Dezenas a algumas centenas de cenários frequentemente são suficientes para problemas de planejamento se gerados inteligentemente (por exemplo, via correspondência de momentos ou redução de cenários). A aproximação de média de amostra (SAA) baseada em Monte Carlo pode exigir milhares de cenários para soluções de alta precisão, com intervalos de confiança guiando a convergência.
A PLE pode lidar com decisões inteiras ou binárias?
Não diretamente — variáveis inteiras exigem Programação Inteira Estocástica (PIE) ou Programação Mista-Inteira Estocástica (PMIE), que são substancialmente mais difíceis computacionalmente. A PLE se aplica apenas quando todas as variáveis de decisão são contínuas.
O que o Valor da Solução Estocástica (VSS) mede?
VSS = Custo Esperado da Solução Determinística de Valor Médio - Ótimo Estocástico Verdadeiro, onde EEV é o custo esperado da solução determinística de valor médio avaliada sobre todos os cenários, e RP é o verdadeiro ótimo estocástico (problema de recurso). Um VSS alto indica que ignorar a incerteza e usar parâmetros médios leva a resultados substancialmente piores.
Quais solvers e softwares suportam programação linear estocástica?
Solvers comerciais como CPLEX e Gurobi podem resolver a forma extensiva diretamente. Frameworks de código aberto incluem leitores de formato SMPS, PySP (parte do Pyomo) e o pacote Julia StochasticPrograms.jl. Para problemas de larga escala, implementações personalizadas de decomposição L-shaped são comuns em pesquisa e indústria.
Métodos relacionados
Fontes
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 referência da publicaçãoCopiado.Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 9780387982175Copiado.