Programação Estocástica

Programação Estocástica (do inglês, stochastic programming) é um ramo da programação matemática que desenvolve modelos e métodos para resolver problemas de otimização em condições de incerteza, onde alguns parâmetros do modelo não são conhecidos com exatidão, mas são representados como variáveis aleatórias com distribuições de probabilidade conhecidas ou estimadas.

Diferentemente dos problemas determinísticos, onde todos os dados são considerados constantes conhecidas, a programação estocástica tem como objetivo encontrar uma solução (ou uma política de tomada de decisão) que seja ótima em algum sentido estatístico. Mais frequentemente, isso significa minimizar ou maximizar a esperança matemática da função objetivo. A ideia central é encontrar uma política de decisão que seja a melhor "em média" para todas as possíveis realizações dos parâmetros aleatórios, o que é especialmente relevante para problemas onde as decisões são tomadas repetidamente em condições semelhantes (por exemplo, no gerenciamento de estoques ou sistemas de energia).

Formulação Matemática do Problema

De forma geral, um problema de programação estocástica pode ser formulado como: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ onde:

• $x$ — o vetor de variáveis de decisão (soluções) que precisa ser determinado.
• $X$ — o conjunto de soluções viáveis para $x$, definido por restrições determinísticas.
• $\xi$ — o vetor aleatório que representa os parâmetros incertos do problema (por exemplo, demanda, preços, condições climáticas).
• $f(x,\xi )$ — a função objetivo, cujo valor depende tanto da decisão $x$ tomada quanto da realização do vetor aleatório $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — o operador de esperança matemática, calculado sobre a distribuição de probabilidade do vetor $\xi$.

Um princípio crucial que fundamenta os modelos estocásticos multiestágio é o princípio da não antecipação (do inglês, non-anticipativity principle). Ele afirma que as decisões tomadas em qualquer estágio podem depender apenas das informações disponíveis até aquele momento e não podem "olhar para o futuro".

Problema de Dois Estágios com Recurso

O modelo mais comum é o problema de dois estágios com recurso (do inglês, two-stage stochastic program with recourse). O processo de tomada de decisão é dividido em dois estágios:

1. Primeiro estágio: Uma decisão "aqui e agora" (here-and-now) é tomada — o vetor $x$ é determinado. Essa decisão deve ser tomada antes que a realização específica do vetor aleatório $\xi$ seja conhecida.
2. Segundo estágio: Após a ocorrência do evento aleatório, uma decisão corretiva ou de recurso (recourse decision) é tomada — o vetor $y(\xi )$, que visa minimizar as consequências negativas ou aproveitar as oportunidades favoráveis resultantes da combinação da decisão do primeiro estágio $x$ e do resultado $\xi$.

Matematicamente, um problema de programação linear estocástica de dois estágios é formulado da seguinte maneira: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ sujeito às restrições do primeiro estágio: $Ax=b,x\ge 0$. Aqui, $Q(x,\xi )$ é a função de recurso (recourse function), que representa o valor ótimo do problema do segundo estágio: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ onde $\xi$ é um vetor aleatório que inclui os parâmetros $q(\xi ),T(\xi )$ e $h(\xi )$; enquanto $c,A,b$ e $W$ são parâmetros determinísticos.

Propriedades e Teoremas Fundamentais

• Convexidade: Um dos resultados fundamentais da teoria é que, para um problema de programação linear estocástica de dois estágios, a função de recurso esperada $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ é uma função convexa. Essa propriedade é de grande importância, pois garante que o problema geral do primeiro estágio seja um problema de programação convexa, para o qual existem métodos eficientes de solução e o ótimo global coincide com o ótimo local.
• Equivalente determinístico: Se o vetor aleatório $\xi$ tem um número finito de realizações possíveis (cenários) ${\xi }_1,\dots ,{\xi }_K$ com probabilidades $p_1,\dots ,p_K$, o problema de programação estocástica pode ser reformulado como um único e grande problema de otimização determinística. Nesse caso, a esperança matemática é substituída por uma soma ponderada sobre todos os cenários. No entanto, o tamanho desse problema cresce linearmente com o número de cenários, o que leva à "maldição da dimensionalidade" e torna essa abordagem computacionalmente inviável para um grande número de cenários.

Comparação com a Otimização Robusta

A programação estocástica é uma das várias abordagens para otimização em condições de incerteza. Sua principal diferença em relação à otimização robusta reside na forma como a incerteza é modelada e no critério de otimalidade.

Comparação de abordagens para otimização em condições de incerteza

Critério	Otimização Estocástica	Otimização Robusta
Representação da incerteza	Parâmetros são variáveis aleatórias com uma distribuição de probabilidade conhecida	Parâmetros pertencem a um conjunto de incerteza definido, sem necessidade de distribuição
Critério de otimalidade	Otimização da esperança matemática da função objetivo	Otimização para o pior caso (minimax)
Natureza da solução	Uma política ótima "em média", que pode ser inviável para cenários raros	Uma solução garantidamente viável para todas as realizações; pode ser conservadora

Exemplos

• Problema do jornaleiro (do inglês, newsvendor problem): Um problema clássico de gerenciamento de estoque onde um vendedor deve decidir a quantidade de um produto a ser comprada sem conhecer a demanda futura exata. A decisão equilibra o risco de perdas por excesso de estoque e o risco de lucro perdido por falta de produto.
• Problema do fazendeiro: Um fazendeiro decide quantos acres de terra alocar para diferentes culturas em uma área total, sem saber as condições climáticas futuras que afetarão o rendimento das colheitas. Depois que o clima se torna conhecido, o fazendeiro pode tomar ações corretivas (por exemplo, vender o excesso de colheita ou comprar o que faltou no mercado).

Ver também

• Programação matemática
• Pesquisa operacional
• Otimização robusta
• Programação dinâmica
• Teoria de controle