Monografia Final

Introdução

Uma simulação é uma imitação de uma operação ou sistema do mundo real em função do tempo. Uma simulação envolve gerar e observar uma história artificial do sistema estudado podendo assim traçar diversas conclusões sobre a operação do sistema no mundo real (BANKS et al.,2005, p.3).

Para tal estudo, é necessário fazer “suposições” sobre o sistema a ser estudado. Tais “suposições” são normalmente feitas através de relações lógicas ou matemáticas, sendo estas chamadas de modelos. Para casos onde o modelo é simples, é possível utilizar métodos analíticos para se determinar a informação “exata” que se precisa, porém casos no mundo real costumam ser complexos demais para se obter uma solução analítica e, portanto, utiliza-se uma simulação realizada em computador. Em uma simulação computacional avalia-se um modelo numericamente e os dados obtidos são utilizados para “estimar” características do sistema (LAW e KELTON, 2000).

Simulação torna-se uma ferramenta apropriada para modificar e estudar interações internas dentro de um sistema muito complexo permitindo prever alterações que ocorreriam no mundo real. Simulação ainda pode ser utilizada como apoio pedagógico para reforçar metodologias de solução analítica (BANKS et. al, 2005, p.4).

Além disso, diversos sistemas modernos (projeto e análise de fábricas, determinação de requisitos de hardware, protocolos para redes de comunicação, projeto e operação de sistemas de transporte como aeroportos, rodovias, portos e metrôs, etc.) são complexos demais, logo suas interações internas podem ser tratadas apenas por via de simulações (BANKS et al., 2005, p.4).

Sistemas e Modelos de Simulação

De acordo com Schmidt e Taylor (apud LAW e KELTON, 2000) um 'sistema' é uma coleção de entidades que agem juntas e interagem para um mesmo fim lógico. Já que um sistema é o conjunto de variáveis que descrevem o sistema em um determinado instante.

O sistema pode ainda ser classificado entre discreto e contínuo. Um sistema discreto é aquele cujas variáveis mudam instantaneamente em certos tempos, enquanto em um sistema contínuo o estados das variáveis se altera continuamente. Um sistema dificilmente será totalmente discreto ou totalmente contínuo, mas é possível realizar tal classificação de acordo com o tipo de mudança predominante (LAW e KELTON, 2000).

Para se simular o sistema desejado é necessário criar um modelo de tal sistema. Um modelo é a representação de um sistema com o propósito de estudar o sistema. Para a maioria dos estudos, é necessário apenas considerar os aspectos do sistema que afetam o problema sob investigação (BANKS,2005,p. 12). Modelos ainda podem ser classificados entre matemáticos ou físicos. Modelos matemáticos utilizam notação matemática representando as relações lógicas e qualitativas do sistema. Modelos de simulação são um tipo específico de modelo de sistema.

Tais modelos de simulação ainda podem ser classificados como estáticos ou dinâmicos, determinísticos ou estocásticos. Os modelos de simulação estáticos representam o sistema em um ponto específico no tempo onde a decorrência do tempo não é relevante. Já os modelos de simulação dinâmicos representam sistemas que evoluem com o tempo. Modelos de simulação que não contém variáveis aleatórias são chamados de modelos determinísticos, enquanto que modelos estocásticos possuem uma ou mais variáveis aleatórias (LAW e KELTON, 2000).

Proposta

Apresentação didática do Método de Monte Carlo, seus aspectos históricos e aplicações, discutindo a essência do método num ambiente computacional, que é a geração de números pseudo aleatórios e suas limitações. Para tanto será realizado um estudo da fila do restaurante universitário do campus Curitiba da UTFPR a fim de colocar e demonstrar na prática o Método.

Justificativa

O Método de Monte Carlo é utilizado em diversas áreas do conhecimento, desde a própria informática, através da qual o método foi desenvolvido, até a administração. Entretanto, o método é normalmente usado puramente como uma ferramenta, não havendo uma preocupação de entendê-lo.

Considerando importante não apenas utilizar uma ferramenta, mas também entender seus fundamentos, é necessária uma abordagem didática do assunto. É a isto que este trabalho se propõe, expor didaticamente os fundamentos do Método de Monte Carlo para que as pessoas que o utilizam como ferramenta possam entender um pouco mais de seus princípios.

Objetivos

O objetivo geral deste trabalho é a apresentação didática do Método de Monte Carlo. Para tal, foram definidos os seguintes objetivos específicos:

• Estudo do Método de Monte Carlo no contexto de simulações;
• Estudo da fila do restaurante universitário, de modo a ilustrar o método.

Procedimentos

Os procedimentos podem ser divididos em duas seções: os procedimentos para a elaboração da monografia e os procedimentos para a elaboração dos aplicativos.

Para a elaboração da monografia, os procedimentos metodológicos constituem-se de três etapas:

• Pesquisa bibliográfica;
• Definição do sumário e;
• Edição e Revisão do texto.

Método de Monte Carlo

Segundo Prado (2009), o Método de Monte Carlo pode ser definido como “uma maneira de transformar um conjunto de números aleatórios em outro conjunto de variáveis , com a mesma distribuição da variável considerada.”

Para Machline (1985), dá-se o nome de Monte Carlo ao “método de simulação que consiste em gerar eventos aleatórios com dados”.

Nota-se que em ambos os conceitos estão presentes variáveis aleatórias, sendo este um ponto fundamental do Método. Trata-se de um método de várias aplicabilidades e que teve surgimento na década de 40, logo após a Segunda Guerra Mundial.

Aspectos Históricos

O método de Monte Carlo surgiu em meados dos anos 40, durante o projeto Manhattan da Segunda Guerra Mundial. Foi aplicado na pesquisa em fusão nuclear para construção da bomba atômica, mais especificamente, no estudo do comportamento dos nêutrons nas reações em cadeia em dispositivos de fissão.

Stanislaw Ulam foi um matemático americano que gostava de analisar, estatisticamente, situações cotidianas. Ao analisar, através de análise combinatória, a probabilidade de se ganhar uma partida de Paciência , perdeu muito tempo efetuando cálculos até perceber que seria mais produtivo realizar várias partidas e anotar os resultados, mas naquela época as técnicas de amostragem estatística tinham caído em desuso devido aos cálculos serem cansativos e volumosos.

Paralelamente a isso, um time de cientistas, engenheiros e técnicos trabalhava na construção do primeiro computador eletrônico – o ENIAC – na Universidade da Pensilvânia, na Filadélfia. Os mentores da equipe se inspiraram para a criação do computador elétrico ao ver filas e filas de mulheres fazendo contas em suas calculadoras de mesa. O computador eletrônico seria construído para lidar com tais processos.

Com a criação do ENIAC, Stanislaw Ulam viu a possibilidade de trazer de volta as técnicas de amostragem estatísticas e discutiu a idéia com John von Neumann, consultor em Aberdeen e Los Alamos. Ao ver a relevância da sugestão feita por Ulam, Neumann enviou uma carta às autoridades explicando uma possível aproximação estatística para o contorno do problema da difusão dos nêutrons em materiais físseis, encontrado durante a construção da bomba atômica.

Nesta carta, Neumman relacionou o problema de difusão dos nêutrons a uma partida de Paciência e relacionou também uma rodada aleatória das cartas a números aleatórios necessários para se tomar decisões ao longo do caminho, no caso do problema em questão. Por isso a necessidade de se ter uma fonte de números aleatórios distribuídos de forma não uniforme.

Muitas pessoas se interessaram pelo método sugerido por Neumman em sua carta e foi então que Nicholas Metropolis sugeriu um nome: método de Monte Carlo.

O Método

Os métodos de Monte Carlo utilizam experimentos de amostras estatísticas para determinar soluções aproximadas para uma variedade de problemas matemáticos. Tais métodos podem ser definidos como métodos de simulação estatística, onde o termo simulação estatística é aplicado genericamente a qualquer método que utilize uma sequência de números aleatórios para realizar uma simulação. Portanto, métodos de Monte Carlo realizam basicamente o mesmo processo.

O processo consiste em realizar diversas simulações utilizando números aleatórios e probabilidade para se obter uma aproximação da solução do problema. Como a solução é aproximada, analisar o erro é um fator importante para se obter uma solução apropriada. A tentativa de se minimizar esse erro é a razão para se haver tantos métodos de Monte Carlo diferentes.

Técnicas de Monte Carlo

Em situações onde o cálculo de uma integral pode se tornar algo extremamente complexo, Monte Carlo se torna uma ferramenta valiosa, pois pode provir uma solução aproximada com muito mais rapidez se comparada há outras técnicas.

Serão avaliados três diferentes métodos de Monte Carlo. A razão de se avaliar três métodos diferentes é que existem muitas considerações a serem feitas ao se utilizar Monte Carlo para se obter uma aproximação. Uma das principais, é minimizar o erro e obter uma aproximação válida. Outra preocupação é sobre qual método é melhor apropriado para o problema em questão e qual fornecerá o melhor resultado. Portanto, serão analisados quatro métodos diferentes, cada um com seus benefícios e requerimentos.

Monte Carlo (Crude Monte Carlo)

Utilizaremos está técnica para resolver a integral :

Inserir fórmula.

Uma descrição básico do método consiste em selecionar um número N, das amostras randômicas onde a ¡= s(valor da amostra) ¡= b. Para cada amostra, acha-se o valor de f(s), então soma-se todos os valores de f(s) obtidos e dividi-se por N, para obter uma média das amostras. Multiplica-se o valor obtido pelo intervalo (b-a) para se obter a integral (Pengelly, 2002).

Representação Matemática:

Inserir fórmula.

É possível determinar a variância das amostras pela fórmula seguinte:

Inserir fórmula.

Utilizando essa informação é possível determinar os intervalos de confiança e determinar o quão precisa a solução obtida é.

Aceitação e Rejeição de Monte Carlo

Considere a mesma integral do método anterior. No intervalo (a,b) deve-se encontrar o limite superior da função f(x) para qualquer valor de x. O intervalo (a,b) é então fechado por um retângulo que deve ser alto o suficiente para estar acima do limite superior. Assim é possível afirmar que toda a função f(x) no intervalo (a,b) está contida dentro do retângulo.

A partir disso, escolhem-se pontos randômicos de dentro do retângulo e verifica-se se estão abaixo ou acima do limite superior. Se o ponto estiver abaixo do limite superior, ele é tratado como uma amostra bem sucedida. Portanto, escolhem-se N pontos randomicamente e verifica-se quantos pontos foram amostras bem sucedidas. Ao finalizar a contagem, o valor da integral I é aproximado pela área do retângulo multiplicado pelo número de sucessos e dividido pelo número N de tentativas.

Representação matemática:

Inserir fórmula.

Sendo k o número de amostras bem sucessividades, N o número de tentativas, M é a área do retângulo feito.

Utilizando a mesma fórmula de variância do método anterior é possível analisar o erro deste método. Dos quatro métodos analisados este é a que possui a pior aproximação.

Amostra Estratificada

O principio básico desta técnica consiste separar o intervalo (a,b) em intervalos menores e realizar uma análise de Monte Carlo para cada subintervalo.

A razão para utilizar esse método é que ao invés de calcular a variância de uma só vez, é possível calcular a variância em intervalos menores e depois somá-los. Isso se torna útil caso a função possua trechos em que ela possua uma tendência a permanecer constante , ou seja, trechos onde a variância é pequena. Essa é a vantagem da amostra estratificada, pois ao dividir o intervalo é possível que haja certas propriedades vantajosas ao se analisar os intervalos.

Representação Matemática:

Inserir fórmula.

Com o intervalo (a,b) dividido em dois intervalos menores: (a,c) e (c,b).