Estocástica

O que acontece quando a tomada de decisão está sujeita a algum grau de incerteza?
Nessas situações, a programação linear não é a melhor abordagem para a otimização do problema, uma vez que ela está apoiada na pressuposição de certeza. Uma alternativa é utilizar a programação estocástica e construir uma formulação que considere a variação de alguns dos parâmetros do modelo.
Muitos modelos de programação estocástica são inicialmente formulados como modelos determinísticos. Se alguns dos parâmetros do modelo determinístico são incertos, ou seja, esses parâmetros podem variar, então é apropriado utilizar a programação estocástica para encontrar a solução ótima desse problema (Sen e Higle, 1999). O modelo determinístico permite calcular a solução ótima para cada um dos cenários separadamente, enquanto que o modelo estocástico considera o conjunto de todos os cenários simultaneamente, cada um com uma probabilidade de ocorrência associada.
Disponivel em : https://www.maxwell.vrac.puc-rio.br/12291/12291_4.PDF.
Um processo estocástico trata-se de problemas de otimização de parâmetros que assume uma distribuição de probabilidade discreta, onde o valor da variável só varia em um determinado instante de tempo, ou contínua onde a variável assume valores a qualquer instante de tempo. Estas distribuições de probabilidade podem ser divididas em:
Modelo de Recurso (Recours e Models): São modelos que usam ações corretivas para compensar a violação de restrições que surgiram após a realização das incertezas. Este modelo foi uma abordagem proposta por Dantzig (1955) e Beale (1955) para problemas de programação estocástica de dois estágios e até múltiplos estágios.
Modelos Probabilísticos (Chance-Constrained Programming): Este modelo descrito por Charnes e Cooper em 1959, permitem que algumas restrições de segundo estágio sejam expressas em termos de declarações probabilísticas sobre as decisões de primeiro estágio. As ações corretivas presentes no modelo de recurso são evitadas nesta abordagem, pois algumas restrições de segundo estágio podem ser violadas ao incorporarem uma medida de risco.

A incerteza num problema florestal

Uma empresa pretende se estabelecer no Noroeste do Mato Grosso, plantando florestas em 10.000 hectares. O faturamento da empresa será por meio da venda de madeira. O mercado local compra madeira de Teca, Pinus ou Eucalipto. As previsões são de que a madeira de Pinus possa ser vendida a um preço de 170 R$/m³, podendo variar de 90 a 200 R$/m³. Para a madeira de Eucalipto espera-se um preço de 150 R$/m³, podendo variar entre 90 e 200 R$/m³. Para a madeira de Teca, por sua vez, espera-se um valor de 230 R$/m³, podendo variar de 150 a 350 R$/m³. Além do mercado local, a madeira de Teca pode ser vendida num mercado especial, que paga um preço muito superior (720 R$/m³), no entanto, só é capaz de absorver uma quantidade máxima de madeira (máximo de 600.000 m³ de Teca).

Para manter suas próprias atividades (como manutenção de estradas, manutenção de cercas, entre outras), a empresa precisará de uma certa quantidade de madeira de Eucalipto (240.000 m³) e de Pinus (200.000 m³).

Para obter madeira, a empresa tem duas opções: plantar, arcando com o custo de implantação (em R$/ha), ou comprar no mercado (em R$/m³). Estudos de crescimento indicam que cada uma das culturas tem uma produção específica (em m³/ha) ao final de um ciclo de rotação. Os especialistas em silvicultura dizem que o Pinus tem potencial de produzir entre 200 e 300 m³/ha, com valor mais provável de 250 m³/ha. O Eucalipto tem potencial de produzir entre 210 e 380 m³/ha, com valor mais provável de 300 m³/ha. Já a Teca tem produção esperada de 130 m³/ha, podendo variar entre 80 e 180 m³/ha. Caso prefira comprar no mercado, a empresa conseguirá comprar madeira de Pinus a um valor de 238 R$/m³, e madeira de Eucalipto a um valor de 210 R$/m³.

Para ajudar na construção da formulação matemática, os analistas prepararam um quadro resumindo o plano de negócio da empresa considerando três cenários: o esperado, o pessimista e o otimista.

Parâmetros do plano de negócios:

Pinus Eucalipto Teca
Produção esperada (m³/ha) 250 300 130
Produção pessimista (m³/ha) 200 210 80
Produção otimista (m³/ha) 300 380 180
Custo de implantação (R$/ha) 1500 2300 4000
Preço de venda esperado (R$/m³) 170 150 230
Preço de venda pessimista (R$/m³) 90 90 150
Preço de venda otimistra (R$/m³) 200 200 350
Preço de venda mercado especial (R$/m³) 720
Preço de compra (R$/m³) 238 210
Demanda do mercado especial (m³) 600000
Demanda interna da empresa (m³) 200000 240000

O desejo da empresa é trabalhar buscando o máximo lucro possível. Para isto, a função objetivo do problema pode ser conceitualmente definida como:

max: lucro

Sabendo que o lucro, pode ser obtido ao se descontar os custos das receitas, a função objetivo pode ser reescrita como:

max: receitas - custos

Como as receitas desta empresa serão oriundas da venda de madeira, será necessário determinar o faturamento com madeira de Pinus, o faturamento com madeira de Eucalipto, o faturamento com madeira de Teca e o faturamento com madeira de Teca especial. A equação que determina a receita seria:

receitas = faturamento com madeira de pinus + faturamento com madeira de eucalipto + faturamento com madeira de teca +  faturamento com madeira de teca especial

Os custos estarão associados à implantação das culturas ou à compra de madeira no mercado local. Assim, os custos podem ser decompostos em: custo com a implantação de hectares de pinus, custo com a implantação de hectares de eucalipto, custo com a implantação de hectares de teca, custo com a compra de madeira de pinus e custo com a compra de madeira de eucalipto. A equação dos custos seria assim determinada:

custos = custo com implantação de pinus + custo com implantação de eucalipto + custo com implantação de teca + custo com a compra de madeira de pinus + custo com a compra de madeira de eucalipto

Para continuar com a formulação do problema, neste momento será considerado apenas o cenário esperado. Desta forma, o faturamento com madeira de pinus pode ser obtido pelo preço de venda de pinus (170 R$/m³) multiplicado pelo volume de pinus vendido, doravante representado pela variável PV. O faturamento com madeira de eucalipto pode ser obtido multiplicando o preço de venda de eucalipto (150 R$/m³) pelo volume de eucalipto vendido, doravante representado pela variável EV. O faturamento com madeira de teca pode ser obtido pelo preço de venda da teca (230 R$/m³) multiplicado pelo volume de teca vendido, agora representado pela variável TV. O faturamento com madeira de teca especial será obtido pelo volume de teca vendido no mercado especial, doravante representado por TE, multiplicado pelo preço de teca especial (720 R$/m³). A equação da receita pode ser assim reescrita:

receitas = 170 PV + 150 EV + 230 TV + 720 TE

O custo com a implantação de pinus pode ser obtido multiplicando a quantidade de hectares implantados com pinus, a partir de agora representado pela variável HP, pelo custo do hectare (1500 R$/ha). O custo com a implantação de eucalipto seria obtido multiplicando a quantidade de hectares implantados com eucalipto, agora representada pela variável HE, pelo custo de um hectare de eucalipto (2300 R$/ha). O custo com a implantação de teca seria obtido multiplicando a quantidade de hectares implantados com teca (variável HT) pelo custo de um hectare de teca (4000 R$/ha). Já o custo com a compra de madeira de pinus pode ser obtido pelo preço de compra (238 R$/m³) multiplicado pelo volume de madeira de pinus comprado (variável PC). O custo com a compra de madeira de eucalipto pode ser obtido pelo preço de compra (210 R$/m³) multiplicado pelo volume de madeira de eucalipto comprado (variável EC). A equação de custo pode ser assim reescrita:

custos = 1500 HP + 2300 HE + 4000 HT + 238 PC + 210 EC

As equações de receita e custo podem ser combinadas para reescrever a função objetivo considerando as variáveis e coeficientes do problema:

max: (170 PV + 150 EV + 230 TV + 720 TE) - (1500 HP + 2300 HE + 4000 HT + 238 PC + 210 EC)

Removendo os parênteses, a função objetivo fica:

max: 170 PV + 150 EV + 230 TV + 720 TE - 1500 HP - 2300 HE - 4000 HT - 238 PC - 210 EC;

Agora que a função objetivo já foi determinada, será necessário definir as restrições do problema. É importante reforçar, que neste momento está sendo considerado apenas o cenário esperado. A primeira restrição do problema é a área total da empresa, limitada em 10.000 hectares. Desta forma, os plantios de pinus, eucalipto e teca não podem ultrapassar esse valor:

AREA: HP + HE + HT <= 10000;

Outra restrição bastante óbvia, é a quantidade de madeira vendida no mercado especial, que está limitado em 600.000 m³:

ESPECIAL: TE <= 600000;

Um pouco menos óbvias, são as restrições que regulam os estoques de madeira de pinus, eucalipto e teca, respectivamente. Por exemplo, a quantidade de madeira de pinus que ‘entra’ na empresa, deve ser maior ou igual à quantidade de madeira de pinus que ‘sai’ da empresa. Em outras palavras, para poder vender ou usar madeira internamente, a empresa precisa ter a madeira em estoque. A empresa pode ter madeira em estoque e não usar, mas a empresa não poder usar uma madeira que não tem. Por isto a restrição do que ‘entra’ tem que ser maior ou igual (>=) ao que ‘sai’.

A madeira de pinus pode ‘entrar’ na empresa por meio do plantio (produção por hectare - 250 m³/ha multiplicado pelo número de hectares plantados - HP) ou por meio da compra (PC). A madeira de pinus pode ‘sair’ da empresa por meio da venda (PV) ou da utilização interna (200.000 m³). No caso do pinus, o balanço pode ser matematicamente descrito como:

PINUS: 250 HP + PC >= 200000 + PV;

O balanço do estoque de eucalipto pode ser determinado de forma semelhante. A quantidade de madeira de eucalipto que ‘entra’ na empresa, deve ser maior ou igual à quantidade de madeira de eucalipto que ‘sai’ da empresa. A madeira de eucalipto pode ‘entrar’ na empresa por meio do plantio (produção por hectare - 300 m³/ha multiplicado pelo número de hectares plantados - HE) ou da compra (EC). A madeira de eucalipto pode ‘sair’ da empresa por meio da venda (EV) ou da utilização interna (240.000 m³). No caso do eucalipto, o balanço pode ser matematicamente descrito como:

EUCALIPTO: 300 HE + EC >= 240000 + EV;

O balanço do estoque da teca pode ser determinado de forma semelhante. A quantidade de madeira de teca que ‘entra’ na empresa, deve ser maior ou igual à quantidade de madeira de teca que ‘sai’ da empresa. A madeira de teca só pode ‘entrar’ na empresa por meio do plantio (produção por hectare - 130 m³/ha multiplicado pelo número de hectares plantados - HT). A madeira de teca pode ‘sair’ da empresa por meio da venda local (TV) ou da venda especial (TE). No caso da teca, o balanço pode ser matematicamente descrito como:

TECA: 130 HT >= TV + TE;

A formulação matemática do problema no cenário esperado, pode ser assim definida:

max: 170 PV + 150 EV + 230 TV + 720 TE - 1500 HP - 2300 HE - 4000 HT - 238 PC - 210 EC;

AREA: HP + HE + HT <= 10000;
ESPECIAL: TE <= 600000;
PINUS: 250 HP + PC >= 200000 + PV;
EUCALIPTO: 300 HE + EC >= 240000 + EV;
TECA: 130 HT >= TV + TE;

De forma semelhante à construção do cenário esperado, os mesmo passos podem ser seguidos para a construção do cenário pessimista. O cenário pessimista teria a seguinte formulação matemática:

max: 90 PV + 90 EV + 150 TV + 720 TE - 1500 HP - 2300 HE - 4000 HT - 238 PC - 210 EC;

AREA: HP + HE + HT <= 10000;
ESPECIAL: TE <= 600000;
PINUS: 200 HP + PC >= 200000 + PV;
EUCALIPTO: 210 HE + EC >= 240000 + EV;
TECA: 80 HT >= TV + TE;

O cenário otimista também pode ser construído, seguindo os mesmos passos já apresentados anteriormente. Para facilitar a compreensão, os valores alterados no cenário pessimista estão em negrito:

max: 200 PV + 200 EV + 350 TV + 720 TE - 1500 HP - 2300 HE - 4000 HT - 238 PC - 210 EC;

AREA: HP + HE + HT <= 10000;
ESPECIAL: TE <= 600000;
PINUS: 300 HP + PC >= 200000 + PV;
EUCALIPTO: 380 HE + EC >= 240000 + EV;
TECA: 180 HT >= TV + TE;

Note que as variáveis dos três cenários são os mesmos. O que muda entre um e outro são os coeficientes em que a incerteza incide. Neste problema, os coeficientes que indicam preço de venda e produção de um hectare das culturas é que possuem características estocásticas (incerteza).

Até aqui, cada cenário foi representado por um problema de programação linear. Desta forma, é possível otimizar cada um dos cenários utilizando um software de otimização, ou mesmo manualmente pelo método simplex. O quadro a seguir apresenta a solução de cada cenário após otimização.

Solução ótima para cada cenário. Para facilitar a leitura da tabela, os valores do LPSolve foram arredondados para valores inteiros

Pessimista Esperado Otimista
Z (R$) 403.800.000 572.101.538 814.400.000
HE (ha) 1.500 4.585 6.667
HP (ha) 1.000 800 0
HT (ha) 7.500 4.615 3.333
PV (m³) 0 0 0
EV (m³) 75.000 1.135.384 2.293.333
TV (m³) 0 0 0
TE (m³) 600.000 600.000 600.000
PC (m³) 0 0 200.000
EC (m³) 0 0 0

Analisando cada cenário individualmente

No cenário esperado, a solução ótima recomenda realizar o plantio de 4.585 hectares de eucalipto, visando fornecer os 240.000 m³ para uso interno e ainda um faturamento com a venda de 1.135.384 m³ no mercado local. Também recomenda-se o plantio de 800 hectares de pinus suficiente apenas para suprir a demanda interna de 200.000 m³. Recomenda-se ainda o plantio de 4.615 hectares de teca, que serão suficientes para vender 600.000 m³ no mercado especial. Este plano de negócio irá gerar um lucro final de pouco mais de 572 milhões de reais.

No cenário pessimista, recomenda-se realizar o plantio de 1.500 hectares de eucalipto, visando fornecer os 240.000 m³ para uso interno e ainda um faturamento com a venda de 75.000 m³ no mercado local. Recomenda-se também o plantio de 1.000 hectares de pinus suficientes para suprir a demanda interna de 200.000 m³. Recomenda-se ainda o plantio de 7.500 hectares de teca, suficientes para vender os 600.000 m³ no mercado especial. Este plano de negócio irá gerar um lucro final de aproximadamente 403 milhões de reais.

No cenário otimista, recomenda-se realizar o plantio de 6.667 hectares de eucalipto, visando fornecer os 240.000 m³ para uso interno e ainda um faturamento com a venda de 2.293.333 m³ no mercado local. Não recomenda-se o plantio de pinus, sendo portanto necessário a compra de 200.000 m³ para suprir a demanda interna. Já os 3.333 hectares recomendados de teca serão suficientes para vender os 600.000 m³ no mercado especial. Este plano de negócio irá gerar um lucro final de pouco mais de 814 milhões de reais.

Analisando as três soluções, é possível perceber que a recomendação de plantio é diferente para cada cenário. No cenário esperado, recomenda-se o plantio 800 hectares de pinus, 4.585 hectares de eucalipto e 4.615 hectares de teca. Já no cenário pessimista, recomenda-se o plantio de 1.000 hectares de pinus, 1.500 hectares de eucalipto e 7.500 hectares de teca. Por fim, no cenário otimista, a recomendação é de plantar 6.667 hectares de eucalipto e 3.333 hectares de teca. Apesar dos três cenários serem facilmente modelados, e a respectiva solução ótima encontrada, existe um problema prático: qual dos três cenários deve ser de fato implantado?

Formulação considerando a incerteza

As variáveis envolvidas no processo de decisão podem ser divididas em duas partes: aquelas que acontecem antes da incerteza se materializar, e aquelas que acontecem depois da incerteza de materializar. Antes de listar as variáveis que ocorrem em cada momento, é importante reforçar que a incerteza ocorre nos coeficientes associados ao preço de venda e à produção de cada cultura. A empresa só irá saber o preço de venda e quanto cada cultura produziu de fato no momento da colheita e comercialização da madeira. Desta forma, na prática a empresa irá plantar as floresta sem saber qual dos cenários irá ocorrer. Somente no momento de cortar e comercializar a produção é que a empresa saberá se o cenário será o esperado, o pessimista ou o otimista.

Desta forma, definir se haverá a necessidade de comprar e vender madeira pode esperar até a incerteza de materializar. Já a recomendação de plantio não pode esperar. Definir quantos hectares de cada cultura deverão ser implantados é uma decisão imediata, que não pode esperar. Assim, as variáveis HP, HE e HT são variáveis que não podem esperar a materialização da incerteza. A empresa precisa saber imediatamente os valores recomendados para implantação. Já as variáveis PV, EV, TV, TE, PC e EC podem esperar até que a incerteza de materialize.

É possível obter uma solução que leve em conta todos os cenários possíveis simultaneamente? Qual a recomendação de plantio é a melhor possível, independente do cenário de incerteza?

O ganho em se considerar o problema desta forma advém justamente da flexibilidade de se postergar parte das decisões do problema, para após a realização da incerteza. Desta forma, as variáveis que serão postergadas, serão acrescidas do cenário a que dizem respeito. Variáveis que podem esperar a incerteza, mas estarão relacionadas ao cenário esperado são:

PVE, EVE, TVE, TEE, PCE, ECE

Note que as variáveis são as mesmas dos problemas individuais, porém, para diferenciá-las, um ‘E’ - indicando ‘Esperado’ foi adicionado no final. A variável PVE indica portanto volume de pinus vendido no mercado local se o cenário for o esperado. A mesma lógica de interpretação vale para as demais variáveis.
As variáveis que podem esperar a incerteza, mas estão relacionadas ao cenário pessimista são:

PVP, EVP, TVP, TEP, PCP, ECP

As variáveis que podem esperar a incerteza, mas estão relacionadas ao cenário otimista são:

PVO, EVO, TVO, TEO, PCO, ECO

A função objetivo do problema estocástico é portanto, uma união das funções objetivos dos cenários independentes, com exceção das variáveis HP, HE e HT, que serão as variáveis que precisam ser definidas antes do cenário de incerteza se concretizar. Ao unir os três cenários na função objetivo, será necessário associar uma probabilidade a cada cenário. Esta probabilidade representa o peso que cada cenário terá durante a otimização da função objetivo.

Assumindo que a probabilidade de cada cenário seja a mesma, isto é ⅓ para cada, será necessário ponderar as variáveis de cada cenário pela probabilidade. Veja que as cores ajudam a identificar cada um dos cenários: verde indica ‘esperado’, vermelho indica ‘pessimista’ e azul indica ‘otimista’.

max: - 1500 HP - 2300 HE - 4000 HT 
+ 1/3 (170 PVE + 150 EVE + 230 TVE + 720 TEE - 238 PCE - 210 ECE)
+ 1/3 (90 PVP + 90 EVP + 150 TVP + 720 TEP - 238 PCP - 210 ECP)
+ 1/3 (200 PVO + 200 EVO + 350 TVO + 720 TEO - 238 PCO - 210 ECO);

Para levar o modelo matemático para um software de otimização será necessário distribuir a probabilidade (aqui definida como ⅓) entre os coeficientes de cada cenário para eliminar os parênteses. O resultado da distribuição de um ⅓ em cada cenário é:

max: - 1500 HP - 2300 HE - 4000 HT 
+ 55.67 PVE + 50 EVE + 76.67 TVE + 240 TEE - 79.33 PCE - 70 ECE
+ 30 PVP + 30 EVP + 50 TVP + 240 TEP - 79.33 PCP - 70 ECP
+ 66.67 PVO + 66.67 EVO + 116.67 TVO + 240 TEO - 79.33 PCO - 70 ECO;

Para finalizar a formulação matemática do problema estocástico, será necessário criar as restrições para cada conjunto de variáveis utilizadas. Note que são as mesmas restrições da formulação independente, porém com as variáveis diferenciadas por cenário:

AREA: HP + HE + HT <= 10000;

ESPECIALE: TEE <= 600000;
PINUSE: 250 HP + PCE >= 200000 + PVE;
EUCALIPTOE: 300 HE + ECE >= 240000 + EVE;
TECAE: 130 HT >= TVE + TEE;

ESPECIALP: TEP <= 600000;
PINUSP: 200 HP + PCP >= 200000 + PVP;
EUCALIPTOP: 210 HE + ECP >= 240000 + EVP;
TECAP: 80 HT >= TVP + TEP;

ESPECIALO: TEO <= 600000;
PINUSO: 300 HP + PCO >= 200000 + PVO;
EUCALIPTOO: 380 HE + ECO >= 240000 + EVO;
TECAO: 180 HT >= TVO + TEO;

A formulação final do problema ficaria da seguinte forma:

max: - 1500 HP - 2300 HE - 4000 HT 
+ 55.67 PVE + 50 EVE + 76.67 TVE + 240 TEE - 79.33 PCE - 70 ECE
+ 30 PVP + 30 EVP + 50 TVP + 240 TEP - 79.33 PCP - 70 ECP
+ 66.67 PVO + 66.67 EVO + 116.67 TVO + 240 TEO - 79.33 PCO - 70 ECO;

AREA: HP + HE + HT <= 10000;

ESPECIALE: TEE <= 600000;
PINUSE: 250 HP + PCE >= 200000 + PVE;
EUCALIPTOE: 300 HE + ECE >= 240000 + EVE;
TECAE: 130 HT >= TVE + TEE;

ESPECIALP: TEP <= 600000;
PINUSP: 200 HP + PCP >= 200000 + PVP;
EUCALIPTOP: 210 HE + ECP >= 240000 + EVP;
TECAP: 80 HT >= TVP + TEP;

ESPECIALO: TEO <= 600000;
PINUSO: 300 HP + PCO >= 200000 + PVO;
EUCALIPTOO: 380 HE + ECO >= 240000 + EVO;
TECAO: 180 HT >= TVO + TEO;

Após levar formulação para um software e realizar a otimização do problema, a solução ótima deve ser interpretada em duas fases, conforme realização da incerteza. Primeiro, a implementação da solução ótima deve levar em consideração as variáveis que precisam ser implementadas antes da incerteza. Neste caso, a solução ótima indica o plantio de 1.000 hectares de pinus, 1.500 hectares de eucalipto e 7.500 hectares de teca, independente do cenário de incerteza. As demais variáveis deverão ser analisadas após a incerteza de realizar.

Caso o cenário pessimista se concretize, analisam-se as variáveis diferenciadas com o sufixo ‘P’. A solução indica que nenhuma madeira de pinus e teca será vendida no mercado local, 75.000 m³ de eucalipto serão vendidos, e 600.000 m³ de teca serão vendidos no mercado especial. Não será necessário comprar nem eucalipto, nem pinus.

Caso o cenário otimista se realiza, as variáveis com sufixo ‘O’ deverão ser analisadas. A solução indica que nenhum m³ de eucalipto nem de pinus serão comprados. Um total de 330.000 m³ de eucalipto serão vendidos, 100.000 m³ de pinus serão vendidos e 750.000 m³ de teca serão vendidos no mercado local. Serã ainda comercializado 600.000 m³ de teca no mercado especial.

Caso o cenário esperado se materialize, as variáveis com sufixo ‘E’ deverão ser analisadas. Neste cenário, a empresa deverá vender no mercado local 210.000 m³ de eucalipto, 50.000 m³ de pinus e 375.000 m³ de teca. No mercado especial serão vendidos 600.000 m³ de teca. Não será necessário comprar madeira de eucalipto, nem de pinus.

Desta forma, é possível perceber que a empresa dividiu o processo de decisão em dois estágios. No primeiro, decidiu quantos hectares de cada cultura deverão ser plantados, independente do cenário. As demais decisões poderão ser postergadas para quando a incerteza de materializar. A solução já indica como a empresa deverá agir em cada cenário futuro. Considerando o cenário estocástico e o processo decisório dividido em dua etapas, o lucro incorporando a incerteza é de aproximadamente 557 milhões de reais.

Playlist: Videoaulas Complementares

Programação Estocástica: Otimização em situações de incerteza

Introdução à Simulação de Monte Carlo & Otimização Estocástica

Otimização Estocástica Inteira

Modelos Probabilísticos para Computação - Aula 06 - Processos Estocásticos

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License