[pt] MÉTODO DE PARTIÇÃO PARA PROBLEMAS DE PROGRAMAÇÃO LINEAR ESTOCÁSTICA DOIS ESTÁGIOS COM RECURSO COMPLETO

[en] PARTITION-BASED METHOD FOR TWO-STAGE STOCHASTIC LINEAR PROGRAMMING PROBLEMS WITH COMPLETE RECOURSE

[pt] CARLOS ANDRES GAMBOA RODRIGUEZ

[pt] PROGRAMACAO ESTOCASTICA

[pt] METODO DE PARTICAO

[pt] METODO DE CENARIOS

[pt] OTIMIZACAO ROBUSTA

[en] STOCHASTIC PROGRAMMING

[en] PARTITION-BASED METHOD

[en] SAMPLE AVERAGE APPROXIMATION

[en] ROBUST OPTIMIZATION

[pt] A parte mais difícil de modelar os problemas de tomada de decisão do mundo real, é a incerteza associada a realização de eventos futuros. A programação estocástica se encarrega desse assunto; o objetivo é achar soluções que sejam factíveis para todas as possíveis realizações dos dados, otimizando o valor esperado de algumas funções das variáveis de decisão e de incerteza. A abordagem mais estudada está baseada em simulação de Monte Carlo e o método SAA (Sample Average Appmwimation) o qual é uma formulação do problema verdadeiro para cada realização da data incerta, que pertence a um conjunto finito de cenários uniformemente distribuídos. É possível provar que o valor ótimo e a solução ótima do problema SAA converge a seus homólogos do problema verdadeiro quando o número de cenários é suficientemente grande.Embora essa abordagem seja útil ali existem fatores limitantes sobre o custo computacional para obter soluções mais precisas aumentando o número de cenários; no entanto o fato mais importante é que o problema SAA é função de cada amostra gerada e por essa razão é aleatório, o qual significa que a sua solução também é incerta, e para medir essa incerteza e necessário considerar o número de replicações do problema SAA afim de estimar a dispersão da solução, aumentando assim o custo computacional. O propósito deste trabalho é apresentar uma abordagem alternativa baseada em um método de partição que permite obter cotas para estimar deterministicamente a solução do problema original, com aplicação da desigualdade de Jensen e de técnicas de otimização robusta. No final se analisa a convergência dos algoritmos de solução propostos.

[en] The hardest part of modelling decision-making problems in the real world, is the uncertainty associated to realizations of futures events. The stochastic programming is responsible about this subject; the target is finding solutions that are feasible for all possible realizations of the unknown data, optimizing the expected value of some functions of decision variables and random variables. The approach most studied is based on Monte Carlo simulation and the Sample Average Approximation (SAA) method which is a kind of discretization of expected value, considering a finite set of realizations or scenarios uniformly distributed. It is possible to prove that the optimal value and the optimal solution of the SAA problem converge to their counterparts of the true problem when the number of scenarios is sufficiently big. Although that approach is useful, there exist limiting factors about the computational cost to increase the scenarios number to obtain a better solution; but the most important fact is that SAA problem is function of each sample generated, and for that reason is random, which means that the solution is also uncertain, and to measure its uncertainty it is necessary consider the replications of SAA problem to estimate the dispersion of the estimated solution, increasing even more the computational cost. The purpose of this work is presenting an alternative approach based on robust optimization techniques and applications of Jensen s inequality, to obtain bounds for the optimal solution, partitioning the support of distribution (without scenarios creation) of unknown data, and taking advantage of the convexity. At the end of this work the convergence of the bounding problem and the proposed solution algorithms are analyzed.

DAVI MICHEL VALLADAO

BRUNO DA COSTA FLACH

ALEXANDRE STREET DE AGUIAR

DAVI MICHEL VALLADAO

2018-03-22

2017-04-25

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=33359@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=33359@2

https://doi.org/10.17771/PUCRio.acad.33359