Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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 0
2

Represente 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.

3

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 0
4

Resolva 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.

5

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

  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 referência da publicação
    Copiado.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 9780387982175
    Copiado.