Monografia Final
(→Aceitação e Rejeição de Monte Carlo) |
|||
(52 edições intermediárias de um usuário não apresentadas) | |||
Linha 1: | Linha 1: | ||
− | = | + | =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). | 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). | ||
Linha 11: | Linha 9: | ||
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). | 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. | 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. | ||
Linha 21: | Linha 19: | ||
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). | 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). | ||
− | ==2 | + | ==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 : | ||
+ | |||
+ | <math>I = \int\limits_{a}^{b} f(x) dx</math> | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <math>I = \frac{b-a} {N} \sum_{i=0}^n f(x_i)</math> | ||
+ | |||
+ | |||
+ | É possível determinar a variância das amostras pela fórmula seguinte: | ||
+ | |||
+ | <math>s^2 = \frac{1} {n-1} \sum_{i=1}^n (x_{i}-X)^2</math> | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <math>I = \int\limits_{a}^{b} f(x) dx \approx \frac{k}{N} M (b-a)</math> | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <math>I = \int\limits_{a}^{c} f(x)dx + \int\limits_{c}^{b} f(x)dx</math> | ||
+ | |||
+ | Com o intervalo (a,b) dividido em dois intervalos menores: (a,c) e (c,b). | ||
+ | |||
+ | ==Aplicações e Problemas Específicos== | ||
+ | |||
+ | De acordo com Barros (2005), há duas aplicações básicas para o Método de Monte Carlo. A primeira delas diz respeito à avaliação empírica de uma distribuição estatística teórica. Esta é uma aplicação bastante utilizada no ensino estatístico. A segunda aplicação, e mais comum, é o uso do Método de Monte Carlo para estudar os efeitos que estão por trás de determinadas estatísticas. | ||
+ | |||
+ | ===Agulha de Buffon=== | ||
+ | |||
+ | O problema da agulha de Buffon data de 1777 e é um dos problemas mais antigos na área de probabilidade e geometria (ROSA et al., 2002). No problema da agulha de Buffon, observa-se que quando uma agulha de comprimento k é aleatoriamente lançada em direção a linhas paralelas com 2k de distância umas das outras, a razão entre o número de lançamentos pelo número de 'acertos' (número de vezes em que a agulha cruza uma linha) se aproxima do valor de PI. (BARROS, 2005). A ilustração abaixo mostra os conceitos do problema da agulha de Buffon: | ||
+ | |||
+ | Inserir imagem. | ||
+ | Figura 01: Agulha de Buffon | ||
+ | Fonte: Rosa et al. (2002). | ||
+ | |||
+ | ===Cálculo do Pi=== | ||
+ | |||
+ | De acordo com Rosa et al, é possível calcular o valor de pi através do Método de Monte Carlo, inicialmente considerando uma circunferência inscrita em um quadrado. Ou seja, o lado do quadrado será o dobro do raio da circunferência. | ||
+ | |||
+ | Sabendo-se que a área da circunferência Ac = PI R² e a área do quadrado Aq = l² = (2R)² = 4R², temos que a relação entre as duas áreas é | ||
+ | |||
+ | <math>\frac{Aq}{Ac} = \frac{4R^2}{\pi R^2}</math> | ||
+ | |||
+ | Logo, | ||
+ | |||
+ | <math>\frac{Aq}{Ac} = \frac{4}{\pi}</math> | ||
+ | |||
+ | Isolando PI, temos que | ||
+ | |||
+ | <math>\pi = \frac{4 Ac}{Aq}</math> | ||
+ | |||
+ | Com o Método de Monte Carlo, é possível gerar números aleatórios que seriam 'lançados' na área do quadrado. Portanto | ||
+ | |||
+ | <math>\pi = \frac{4 \times (n\acute{u}mero\ de\ pontos\ que\ cairam\ dentro\ da\ circunfer\hat{e}ncia)}{(n\acute{u}mero\ de\ lancamentos)}</math> | ||
+ | |||
+ | ==Limitações== | ||
+ | |||
+ | Para Lawrence (2004), O método de Monte Carlo tem algumas limitações atribuídas. Elas são ligadas ao seu procedimento intrinsecamente estatístico mecânico, resultando em um escopo de sua resposta que pode ser demasiado abrangente para certas aplicações. | ||
+ | |||
+ | |||
+ | Ainda, a eficácia do método está diretamente correlacionada com a estatística disponível do processo em questão, podendo ser utilizado somente em casos que a mesma seja suficientemente abundante. esta forma, o método de Monte Carlo é limitado por sua abordagem estatística. Entretanto, em certos casos pode ser a única alternativa, ou ainda, reduzir bastante a complexidade da resolução. | ||
+ | |||
+ | =Geração de Números Aleatórios= | ||
+ | |||
+ | De acordo com Taha (1997), os números pseudoaleatórios utilizados pelo método de Monte Carlo são usados para determinar atributos (como energia, direção de escape, etc.) de uma partícula lançada e interações da partícula com o meio. Analisando essa situação, as seguintes propriedades de números pseudoaleatórios são desejáveis: | ||
+ | |||
+ | *As sequências de números pseudoaleatórios não devem ser correlacionadas. | ||
+ | *O gerador utilizado deve ser capaz de produzir sequências durante um longo período sem repetição. | ||
+ | *A sequência gerada deve ser uniforme e imparcial. | ||
+ | *O gerador deve ser eficiente. | ||
+ | |||
+ | Para Warnock (1987), verdadeiros números aleatórios podem ser gerados somente por dispositivos eletrônicos mas como os modelos de simulação são executados em computadores, isso torna-se inviável por ser lento para esse propósito. Outra desvantagem é que as etapas de depuração, verificação e validação dos modelos de simulação, às vezes, exigem que as sequências possam ser repetidas e como os dispositivos eletrônicos são regidos pela lei do acaso, torna-se impossível duplicá-las. A saída para esse impasse é gerar os números aleatórios baseando-se em operações aritméticas, conhecidos como pseudoaleatórios | ||
+ | |||
+ | Perin Filho (1995), afirma que muitos dos geradores de números aleatórios são baseados em eventos físicos, utilizando equipamentos simples, tais como roletas, ou complexos, como dispositivos eletrônicos ou radioativos. Porém, estes geradores raramente são utilizados em uma simulação de sistema, por serem 'lentos, dispendiosos e de difícil implementação'. Utiliza-se normalmente rotinas computacionais em simulação, sendo divididas em duas fases: a primeira na qual são gerados números aleatórios com distribuição uniforme, e a segunda na qual tais números são transformados em um valor da variável desejada. | ||
+ | |||
+ | ==Geradores Lineares (Congruentes)== | ||
+ | |||
+ | Dentre os métodos existentes para a geração de números aleatórios, o da congruência multiplicativa é o mais empregado. Este método utiliza dois parâmetros inteiros (alfa e beta) além da semente s0 (Perin Filho, 1995). | ||
+ | |||
+ | O número inteiro gerado é obtido através da equação: | ||
+ | |||
+ | <math>s_i = (\beta * s_{i-1})\ mod\ \alpha</math> | ||
+ | |||
+ | em que mod é o operador de resto. | ||
+ | |||
+ | O número inteiro gerado é obtido pela parte não inteira da divisão: | ||
+ | |||
+ | <math>\frac{\beta * s_{i-1}}{\alpha}</math> | ||
+ | |||
+ | Definir parâmetros alfa e beta que gerem números aleatórios para quaisquer sementes é difícil. Uma regra geral é a de que beta não pode ser divisível por alfa, evitando-se assim que <math>s_i = 0</math>. | ||
+ | |||
+ | |||
+ | Nota-se também que o menor i para o qual <math>s_i = s_0</math> equivale ao período da seqüência. | ||
+ | |||
+ | Usualmente, os métodos de congruência utilizam regras de atualização conforme equação abaixo, nas quais alfa, beta, gama e teta são parâmetros inteiros. | ||
+ | |||
+ | <math>s_i = (\theta * s_{i-1} + \gamma * s_{i-1} + \beta)\ mod\ \alpha </math> | ||
+ | |||
+ | Outro tipo de gerador é gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão: | ||
+ | |||
+ | <math>x_{n+1} = (Ax_n + C)(mod\ M)</math> | ||
+ | |||
+ | onde: xn = é o enésimo membro da seqüência A, C, M = são parâmetros que podem ser ajustados por conveniência e para assegurar a natureza pseudo-aleatória da seqüência. | ||
+ | |||
+ | Por exemplo: M, o módulo, é freqüentemente o tamanho de uma palavra no computador e A, o multiplicador, é escolhido para produzir um longo período de seqüência e boas propriedades estatísticas. | ||
+ | |||
+ | Exemplo prático: <math>x_0</math> = 13, A = 21, C = 1, M = 32 | ||
+ | |||
+ | Seqüência produzida: 13, 18, 24, 25, 14, 7, 20, 5, 10... | ||
+ | |||
+ | ==Testando Geradores de Números aleatórios== | ||
+ | |||
+ | Um teste básico que deve ser feito para validar um novo gerador é o teste de uniformidade. A partir deste é possível medir o nível de aceitação entre a distribuição da amostra dos números gerados e a distribuição uniforme teorizada. Dois diferentes testes podem ser realizados : O Kolmogorov-Smirnov e o teste to qui quadrado (BANKS et al.,2005) . | ||
+ | |||
+ | ===Teste Kolmogorov-Smirnov === | ||
+ | |||
+ | Este teste compara a função contínua e uniformemente distribuída F(x)com a função empírica Sn(x) obtida das amostras de N observações. Por definição: | ||
+ | |||
+ | <math>F(x) = x; 0 \le x \le 1</math> | ||
+ | |||
+ | Se a amostra dos números gerados é <math>R_1, R_2, ..., Rn</math>, então a função empírica Sn(x) pode ser definida por: | ||
+ | |||
+ | <math>Sn(x) = \frac{n\acute{u}meros\ de\ R_1, R_2, ..., R_n\ que\ s\tilde{a}o\ \le x}{N}</math> | ||
+ | |||
+ | Conforme N aumenta, Sn(x) deve se tornar uma aproximação melhor de F(x), contanto que a hipótese de que a uniformidade exista seja verdadeira. O teste de Kolmogrov-Smirnov é baseado na maior diferença entre F(x) e Sn(x). Ou seja: | ||
+ | |||
+ | <math> D = \mid F(x) - Sn(x) \mid</math> | ||
+ | |||
+ | Esse valor é então tabelado em função de N na tabela de Kolmogrov-Smirnov. Para testar a uniformidade de uma função, seguem-se as seguintes etapas: | ||
+ | |||
+ | *Etapa 1: Arrumam-se os valores obtidos em ordem crescente, sendo que o valor <math>R_(i)</math> denotará sempre o menor i-ésimo valor das observações: | ||
+ | |||
+ | <math>R_1 \le R_2 \le ... \le R_n</math> | ||
+ | |||
+ | *Etapa 2: Computa-se: | ||
+ | |||
+ | <math>D+ = max(1 \le i \le N) \left \{ \frac{i}{n} - R_{i} \right \}</math> | ||
+ | |||
+ | <math>D- = max(1 \le i \le N) \left \{ R_{i} - \frac{i-1}{N} \right \}</math> | ||
+ | |||
+ | *Etapa 3: Computar <math>D = max(D+;D-)</math>. | ||
+ | |||
+ | *Etapa 4: Localizar na tabela o valor critico de <math>D_\alpha</math> para o nível específico de significância alfa e o tamanho da amostra N. | ||
+ | |||
+ | *Etapa 5: Se a amostra estatística D é maior que o valor crítico <math>D_\alpha</math> então a hipótese de que a amostra provém de uma distribuição uniforme é rejeitada. Se <math>D \le \alpha</math> então conclui-se que não detectou-se diferenças entre a distribuição da amostra e a distribuição uniforme desejada. | ||
+ | |||
+ | ===Teste do Qui quadrado=== | ||
+ | |||
+ | O teste do qui quadrado usa a amostra estatística: | ||
+ | |||
+ | <math>X_0^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}</math> | ||
+ | |||
+ | onde <math>O_i</math> é o número observado no i-ésima ensaio e <math>E_i</math> é o número esperado da i-ésima ensaio e n é o número de ensaios. Para uma distribuição uniforme o número esperado <math>E_i</math> em cada ensaio é dado por: | ||
+ | |||
+ | <math>E_i = \frac{N}{n}</math> | ||
+ | |||
+ | Onde N é o número de observações e n o número de ensaios. A partir destas informações pode-se demonstrar que a distribuição da amostra de <math>X_0^2</math> é aproximadamente uma distribuição qui quadrado n-1 graus de liberdade. Observação: Um ensaio pode ser equivalente a um certo número de observações. Exemplo: n = 10 (10 observações equivalem a 1 ensaio). | ||
+ | |||
+ | Após obtido o valor de <math>X_0^2</math> compara-se com os valores da tabela do qui quadrado. Caso o <math>X_0^2</math> obtido seja menor, a hipótese de que se trata de uma distribuição uniforme não é rejeitada. | ||
+ | |||
+ | ===Considerações Sobre os Testes=== | ||
+ | |||
+ | No teste do qui quadrado é recomendado escolher n e N tal que cada <math>E_i</math> seja maior ou igual a 5. | ||
+ | |||
+ | *Tanto o teste de Kolmogorov-Smirnov e o teste do qui quadrado são aceitáveis para se testar uniformidade contanto que o tamanho da amostra seja grande. | ||
+ | |||
+ | *Entre os dois, o teste de Kolmogorov-Smirnov é o mais recomendado. Além disso, o teste de Kolmogorov-Smirnov pode ser aplicado a pequenas amostras enquanto que o teste do qui quadrado só é válido para amostras muito grandes (N maior ou igual a 50) (BANKS et al.,2005). | ||
+ | |||
+ | ==Teste de Autocorrelação== | ||
+ | |||
+ | O teste de autocorrelação preocupa-se em descobrir se há ou não uma relação de dependência ente os números obtidos em uma sequência. Exemplo: | ||
+ | |||
+ | Considere a seguinte sequência de números: | ||
+ | |||
+ | 0,12_0,01_0,23_0,28_0,89_0,31_0,64_0,28_0,83_0,93 | ||
+ | |||
+ | 0,99_0,15_0,33_0,35_0,91_0,41_0,60_0,27_0,75_0,88 | ||
+ | |||
+ | 0,68_0,49_0,05_0,43_0,95_0,58_0,19_0,36_0,69_0,87 | ||
+ | |||
+ | Aparentemente, todos estes números parecem ser randômicos e provavelmente passariam pelo teste de frequência apresentado anteriormente. Porém, ao analisarmos a quinta e a décima coluna pode-se verificar que sempre há um número grande naquelas posições. Como 30 números é uma amostra pequena não é possível afirmar se realmente há alguma relação entre os números obtidos. Será apresentado um método para se afirmar se tal relação existe em uma determinada amostra. Tal relação pode ser números muito altos, muito baixos ou podem se alternar entre muito altos e muito baixos (BANKS et al.,2005). | ||
+ | |||
+ | O teste requer computação de autocorrelação cada m números (m também conhecido como lag, será chamado de intervalo m a partir daqui), começando pelo i-ésimo número. Portanto autocorrelação entre os seguintes números é de interesse: | ||
+ | |||
+ | <math>R_i,\ R_{i+m},\ R_{i+2m},\ ...,\ R_{i+(M+1)m}</math> | ||
+ | |||
+ | O valor M é o maior número inteiro possível tal que <math>i + (M+1)m \le N</math>, onde N é o número total de valores na sequência. Caso a autocorrelação seja diferente de zero, isso implicaria que há uma falta de independência, portanto o seguinte teste de hipótese é apropriado: | ||
+ | |||
+ | <math>H_0 : \rho_{im}\ = 0</math> | ||
+ | |||
+ | <math>H_1 : \rho_{im} \ne 0</math> | ||
+ | |||
+ | Para valores muito altos de M, a distribuição do estimador de <math>\rho_im</math>, denotado de<math>\hat{\rho}_{im}</math> é aproximadamente normal se os valores de <math>R_i,\ R_{i+m},\ R_{i+2m},\ ...,\ R_{i+(M+1)m}</math> são independentes. Portanto, o seguinte teste estatístico pode ser feito: | ||
+ | |||
+ | <math>Z_0 = \frac {\hat{\rho}_{im}}{\sigma_{\hat{\rho}_{im}}}</math> | ||
+ | |||
+ | Onde <math>Z_0</math> é distribuído de forma normal com variância igual a 1, sob a suposição de independência para um M muito grande. As fórmulas de <math>\hat{\rho}_{im}</math> e desvio padrão de <math>\hat{\rho}_{im}</math> são dadas por Schmidt e Taylor [1970] conforme seguem: | ||
+ | |||
+ | <math>\hat{\rho}_{im} = \frac{1}{M+1} ( \sum_{k=0}^{M} R_{i+km} * R_{i+(k+1)m}) - 0.25</math> | ||
+ | |||
+ | e | ||
+ | |||
+ | <math>\sigma_{\hat{\rho}_{im}} = \frac{\sqrt{13M + 7}}{12(M+1)}</math> | ||
+ | |||
+ | Após computar-se <math>Z_0</math>, não se rejeita a hipótese <math>H_0</math> de que os números são independentes se | ||
+ | |||
+ | <math>-Z_{\alpha/2} \le Z_0 \le Z_{\alpha/2} </math> onde alfa é o nível de significância e <math>Z_{\alpha/2} </math> é obtido da tabela presente nos Anexos. | ||
+ | |||
+ | Se <math>\rho_{im} > 0</math> isso significaria uma autocorrelação positiva, onde a cada valor sucessivo (obtido a partir do intervalo m) há uma probabilidade maior do que a esperada de se obter valores próximos um do outro (um valor muito alto seguido de outro ou valor muito baixo seguido do outro). | ||
+ | |||
+ | Caso <math>\rho_{im} < 0</math> isso significaria uma autocorrelação negativa, onde há uma alternância de valores altos e baixos a cada intervalo m. | ||
+ | |||
+ | Caso <math>\rho_{im} = 0</math> significaria que obtivemos independência nos números analisados a cada intervalo m. | ||
+ | |||
+ | =Considerações Finais= | ||
+ | |||
+ | A simulação do fenômeno de interesse é obtida associando-se números aleatórios a eventos e à sua probabilidade de ocorrência. Esta é a ideia de um modelo de simulação genérico e é também empregada, portanto, no Método de Monte Carlo. Apesar de o Método de Monte Carlo não ser um modelo de simulação propriamente dito, sua origem e seu uso está intrinsecamente ligado à simulação. | ||
+ | |||
+ | Nesta abordagem didática do Método, procurou-se, portanto, apresentar esta ligação do Método com a simulação que ocorre desde sua concepção em Los Alamos para a resolução da questão da fissão nuclear. É curioso observar que métodos estatísticos que tornariam a concepção do Método de Monte Carlo possível já datavam de antes da década de 50, porém foi apenas com a criação do computador eletrônico que sua execução passou a ser efetivamente viável. | ||
+ | |||
+ | Porém, para compreender o Método de Monte Carlo, além dos aspectos históricos, é necessário conhecer aquilo que p torna possível, que são os geradores de números pseudoaleatórios existentes em um ambiente computacional. Como comentado antes, o Método é possível de ser realizado sem o uso de um computador, uma vez que ele é baseado em métodos estatísticos, porém, neste caso, ele se torna impraticável para realizar simulações que gerem dados realísticos de sistemas complexos do mundo real. | ||
+ | |||
+ | Portanto, a geração de números pseudoaleatórios em um ambiente computacional não é, necessariamente essencial ao Método, mas é o que o torna útil em aplicações práticas. O entendimento dos geradores de números aleatórios é parte do conhecimento a respeito do Método de Monte Carlo, e as características de cada gerador devem ser conhecidas de forma a se aplicar o gerador mais adequado a cada situação. | ||
+ | |||
+ | Com este trabalho foi possível, por fim, compreender os conhecimentos atrelados ao Método de Monte Carlo assim como a importância de todos eles para que o Método possa ser utilizável em situações reais. | ||
+ | |||
+ | =Referências= | ||
+ | |||
+ | *BANKS, J.; CARSON II, J.S.; NELSON, B.L. '''Discrete event system simulation'''. 4.ed. New Jersey: Prentice Hall, 2005. | ||
+ | |||
+ | *BARROS, Emílio A. C.. '''Aplicações de Simulação Monte Carlo e Bootstrap'''. 2005, 52 f. Monografia (Bacharelado em Estatística) – Departamento Acadêmico de Estatística, Universidade Estadual de Maringá, Maringá, 2005. Disponível em <http://www.des.uem.br/graduacao/Monografias/Monografia_Emilio.pdf>. Acesso em 05 set. 2010. | ||
+ | |||
+ | *ECKHARDT, Roger. '''Stan Ulam, John von Neumann, and The Monte Carlo Method'''. Los Alamos Science, Los Alamos, no. 15, p. 131-137, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-13.pdf >. Acesso em: 05 set. 2010. | ||
+ | |||
+ | *FREITAS FILHO, Paulo José de. '''Introdução à modelagem e simulação de sistemas: com aplicações em Arena'''. 2. ed. Florianópolis: Visual Books, 2001. | ||
+ | |||
+ | *LAW, A.M.; KELTON, W.D. '''Simulation modeling and analysis'''. 3. ed. Boston: McGraw-Hill, 2000. | ||
+ | |||
+ | *LAWRENCE, Denis. Note on Monte Carlo Analysis. Apresentado na Comissão de Comércio, Wellington, Nova Zelândia, 2004. Disponível em < http://www.med.govt.nz/upload/16173/meyrick-monte-carlo.pdf > acesso em 30 de outubro de 2010. | ||
+ | |||
+ | *MACHLINE, Claude, MOTTA, Ivan de Sá, SCHOEPS, Wolfgang, WEIL, Kurt E. '''Manual de Administração da Produção''', Vol. II. Rio de Janeiro: Fundação Getúlio Vargas,1985. | ||
+ | |||
+ | *METROPOLIS, Nicholas; Ulam, S. '''The Monte Carlo Method'''. Journal of the American Statistical Association, vol. 44, No. 247 (Sep. 1949), pp. 335-341. | ||
+ | |||
+ | *______. '''The Beginning of The Monte Carlo Method'''. Los Alamos Science, Los Alamos, no. 15, p. 125-130, 1987. Disponível em: <http://library.lanl.gov/cgi-bin/getfile?15-12.pdf>. Acesso em: 05 set. 2010. | ||
+ | |||
+ | *PENGELLY, Jonathan. '''Monte Carlo Methods'''. Disponível em <http://www.cs.otago.ac.nz/cosc453/student_tutorials/monte_carlo.pdf>. Acesso em 20 de setembro de 2010. | ||
+ | |||
+ | *PRADO, Darci Santos do. '''Teoria das filas e da simulação'''. 4. ed. Belo Horizonte: Editora de Desenvolvimento Gerencial, 2009. | ||
+ | |||
+ | *ROSA, Fernando H. F. P. da; COSTA, Matheus Moreira; TORTELLA, Tiago Luiz; JUNIOR, Vagner Aparecido. '''Método de Monte Carlo e Aproximações de PI'''. Disponível em < http://www.feferraz.net/files/lista/montecarlopi.pdf >. Acesso em 05 set. 2010. | ||
+ | |||
+ | *TAHA, Hamdy A. '''Operations research: an introduction'''. 6.ed. Upper Saddle River: Prentice Hall, c1997. | ||
+ | |||
+ | *WARNOCK, Tony. '''Random-Number Generators'''. Los Alamos Science, Los Alamos, no. 15, p. 137-141, 1987. Disponível em: <http://library.lanl.gov/cgi-bin/getfile?00418729.pdf>. Acesso em: 05 set. 2010. |
Edição atual tal como 12h25min de 6 de novembro de 2010
Tabela de conteúdo |
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 :
<math>I = \int\limits_{a}^{b} f(x) dx</math>
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:
<math>I = \frac{b-a} {N} \sum_{i=0}^n f(x_i)</math>
É possível determinar a variância das amostras pela fórmula seguinte:
<math>s^2 = \frac{1} {n-1} \sum_{i=1}^n (x_{i}-X)^2</math>
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:
<math>I = \int\limits_{a}^{b} f(x) dx \approx \frac{k}{N} M (b-a)</math>
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:
<math>I = \int\limits_{a}^{c} f(x)dx + \int\limits_{c}^{b} f(x)dx</math>
Com o intervalo (a,b) dividido em dois intervalos menores: (a,c) e (c,b).
Aplicações e Problemas Específicos
De acordo com Barros (2005), há duas aplicações básicas para o Método de Monte Carlo. A primeira delas diz respeito à avaliação empírica de uma distribuição estatística teórica. Esta é uma aplicação bastante utilizada no ensino estatístico. A segunda aplicação, e mais comum, é o uso do Método de Monte Carlo para estudar os efeitos que estão por trás de determinadas estatísticas.
Agulha de Buffon
O problema da agulha de Buffon data de 1777 e é um dos problemas mais antigos na área de probabilidade e geometria (ROSA et al., 2002). No problema da agulha de Buffon, observa-se que quando uma agulha de comprimento k é aleatoriamente lançada em direção a linhas paralelas com 2k de distância umas das outras, a razão entre o número de lançamentos pelo número de 'acertos' (número de vezes em que a agulha cruza uma linha) se aproxima do valor de PI. (BARROS, 2005). A ilustração abaixo mostra os conceitos do problema da agulha de Buffon:
Inserir imagem.
Figura 01: Agulha de Buffon Fonte: Rosa et al. (2002).
Cálculo do Pi
De acordo com Rosa et al, é possível calcular o valor de pi através do Método de Monte Carlo, inicialmente considerando uma circunferência inscrita em um quadrado. Ou seja, o lado do quadrado será o dobro do raio da circunferência.
Sabendo-se que a área da circunferência Ac = PI R² e a área do quadrado Aq = l² = (2R)² = 4R², temos que a relação entre as duas áreas é
<math>\frac{Aq}{Ac} = \frac{4R^2}{\pi R^2}</math>
Logo,
<math>\frac{Aq}{Ac} = \frac{4}{\pi}</math>
Isolando PI, temos que
<math>\pi = \frac{4 Ac}{Aq}</math>
Com o Método de Monte Carlo, é possível gerar números aleatórios que seriam 'lançados' na área do quadrado. Portanto
<math>\pi = \frac{4 \times (n\acute{u}mero\ de\ pontos\ que\ cairam\ dentro\ da\ circunfer\hat{e}ncia)}{(n\acute{u}mero\ de\ lancamentos)}</math>
Limitações
Para Lawrence (2004), O método de Monte Carlo tem algumas limitações atribuídas. Elas são ligadas ao seu procedimento intrinsecamente estatístico mecânico, resultando em um escopo de sua resposta que pode ser demasiado abrangente para certas aplicações.
Ainda, a eficácia do método está diretamente correlacionada com a estatística disponível do processo em questão, podendo ser utilizado somente em casos que a mesma seja suficientemente abundante. esta forma, o método de Monte Carlo é limitado por sua abordagem estatística. Entretanto, em certos casos pode ser a única alternativa, ou ainda, reduzir bastante a complexidade da resolução.
Geração de Números Aleatórios
De acordo com Taha (1997), os números pseudoaleatórios utilizados pelo método de Monte Carlo são usados para determinar atributos (como energia, direção de escape, etc.) de uma partícula lançada e interações da partícula com o meio. Analisando essa situação, as seguintes propriedades de números pseudoaleatórios são desejáveis:
- As sequências de números pseudoaleatórios não devem ser correlacionadas.
- O gerador utilizado deve ser capaz de produzir sequências durante um longo período sem repetição.
- A sequência gerada deve ser uniforme e imparcial.
- O gerador deve ser eficiente.
Para Warnock (1987), verdadeiros números aleatórios podem ser gerados somente por dispositivos eletrônicos mas como os modelos de simulação são executados em computadores, isso torna-se inviável por ser lento para esse propósito. Outra desvantagem é que as etapas de depuração, verificação e validação dos modelos de simulação, às vezes, exigem que as sequências possam ser repetidas e como os dispositivos eletrônicos são regidos pela lei do acaso, torna-se impossível duplicá-las. A saída para esse impasse é gerar os números aleatórios baseando-se em operações aritméticas, conhecidos como pseudoaleatórios
Perin Filho (1995), afirma que muitos dos geradores de números aleatórios são baseados em eventos físicos, utilizando equipamentos simples, tais como roletas, ou complexos, como dispositivos eletrônicos ou radioativos. Porém, estes geradores raramente são utilizados em uma simulação de sistema, por serem 'lentos, dispendiosos e de difícil implementação'. Utiliza-se normalmente rotinas computacionais em simulação, sendo divididas em duas fases: a primeira na qual são gerados números aleatórios com distribuição uniforme, e a segunda na qual tais números são transformados em um valor da variável desejada.
Geradores Lineares (Congruentes)
Dentre os métodos existentes para a geração de números aleatórios, o da congruência multiplicativa é o mais empregado. Este método utiliza dois parâmetros inteiros (alfa e beta) além da semente s0 (Perin Filho, 1995).
O número inteiro gerado é obtido através da equação:
<math>s_i = (\beta * s_{i-1})\ mod\ \alpha</math>
em que mod é o operador de resto.
O número inteiro gerado é obtido pela parte não inteira da divisão:
<math>\frac{\beta * s_{i-1}}{\alpha}</math>
Definir parâmetros alfa e beta que gerem números aleatórios para quaisquer sementes é difícil. Uma regra geral é a de que beta não pode ser divisível por alfa, evitando-se assim que <math>s_i = 0</math>.
Nota-se também que o menor i para o qual <math>s_i = s_0</math> equivale ao período da seqüência.
Usualmente, os métodos de congruência utilizam regras de atualização conforme equação abaixo, nas quais alfa, beta, gama e teta são parâmetros inteiros.
<math>s_i = (\theta * s_{i-1} + \gamma * s_{i-1} + \beta)\ mod\ \alpha </math>
Outro tipo de gerador é gerador de Lehmer. A seqüência é definida numa coleção de inteiros através da fórmula de recursão:
<math>x_{n+1} = (Ax_n + C)(mod\ M)</math>
onde: xn = é o enésimo membro da seqüência A, C, M = são parâmetros que podem ser ajustados por conveniência e para assegurar a natureza pseudo-aleatória da seqüência.
Por exemplo: M, o módulo, é freqüentemente o tamanho de uma palavra no computador e A, o multiplicador, é escolhido para produzir um longo período de seqüência e boas propriedades estatísticas.
Exemplo prático: <math>x_0</math> = 13, A = 21, C = 1, M = 32
Seqüência produzida: 13, 18, 24, 25, 14, 7, 20, 5, 10...
Testando Geradores de Números aleatórios
Um teste básico que deve ser feito para validar um novo gerador é o teste de uniformidade. A partir deste é possível medir o nível de aceitação entre a distribuição da amostra dos números gerados e a distribuição uniforme teorizada. Dois diferentes testes podem ser realizados : O Kolmogorov-Smirnov e o teste to qui quadrado (BANKS et al.,2005) .
Teste Kolmogorov-Smirnov
Este teste compara a função contínua e uniformemente distribuída F(x)com a função empírica Sn(x) obtida das amostras de N observações. Por definição:
<math>F(x) = x; 0 \le x \le 1</math>
Se a amostra dos números gerados é <math>R_1, R_2, ..., Rn</math>, então a função empírica Sn(x) pode ser definida por:
<math>Sn(x) = \frac{n\acute{u}meros\ de\ R_1, R_2, ..., R_n\ que\ s\tilde{a}o\ \le x}{N}</math>
Conforme N aumenta, Sn(x) deve se tornar uma aproximação melhor de F(x), contanto que a hipótese de que a uniformidade exista seja verdadeira. O teste de Kolmogrov-Smirnov é baseado na maior diferença entre F(x) e Sn(x). Ou seja:
<math> D = \mid F(x) - Sn(x) \mid</math>
Esse valor é então tabelado em função de N na tabela de Kolmogrov-Smirnov. Para testar a uniformidade de uma função, seguem-se as seguintes etapas:
- Etapa 1: Arrumam-se os valores obtidos em ordem crescente, sendo que o valor <math>R_(i)</math> denotará sempre o menor i-ésimo valor das observações:
<math>R_1 \le R_2 \le ... \le R_n</math>
- Etapa 2: Computa-se:
<math>D+ = max(1 \le i \le N) \left \{ \frac{i}{n} - R_{i} \right \}</math>
<math>D- = max(1 \le i \le N) \left \{ R_{i} - \frac{i-1}{N} \right \}</math>
- Etapa 3: Computar <math>D = max(D+;D-)</math>.
- Etapa 4: Localizar na tabela o valor critico de <math>D_\alpha</math> para o nível específico de significância alfa e o tamanho da amostra N.
- Etapa 5: Se a amostra estatística D é maior que o valor crítico <math>D_\alpha</math> então a hipótese de que a amostra provém de uma distribuição uniforme é rejeitada. Se <math>D \le \alpha</math> então conclui-se que não detectou-se diferenças entre a distribuição da amostra e a distribuição uniforme desejada.
Teste do Qui quadrado
O teste do qui quadrado usa a amostra estatística:
<math>X_0^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}</math>
onde <math>O_i</math> é o número observado no i-ésima ensaio e <math>E_i</math> é o número esperado da i-ésima ensaio e n é o número de ensaios. Para uma distribuição uniforme o número esperado <math>E_i</math> em cada ensaio é dado por:
<math>E_i = \frac{N}{n}</math>
Onde N é o número de observações e n o número de ensaios. A partir destas informações pode-se demonstrar que a distribuição da amostra de <math>X_0^2</math> é aproximadamente uma distribuição qui quadrado n-1 graus de liberdade. Observação: Um ensaio pode ser equivalente a um certo número de observações. Exemplo: n = 10 (10 observações equivalem a 1 ensaio).
Após obtido o valor de <math>X_0^2</math> compara-se com os valores da tabela do qui quadrado. Caso o <math>X_0^2</math> obtido seja menor, a hipótese de que se trata de uma distribuição uniforme não é rejeitada.
Considerações Sobre os Testes
No teste do qui quadrado é recomendado escolher n e N tal que cada <math>E_i</math> seja maior ou igual a 5.
- Tanto o teste de Kolmogorov-Smirnov e o teste do qui quadrado são aceitáveis para se testar uniformidade contanto que o tamanho da amostra seja grande.
- Entre os dois, o teste de Kolmogorov-Smirnov é o mais recomendado. Além disso, o teste de Kolmogorov-Smirnov pode ser aplicado a pequenas amostras enquanto que o teste do qui quadrado só é válido para amostras muito grandes (N maior ou igual a 50) (BANKS et al.,2005).
Teste de Autocorrelação
O teste de autocorrelação preocupa-se em descobrir se há ou não uma relação de dependência ente os números obtidos em uma sequência. Exemplo:
Considere a seguinte sequência de números:
0,12_0,01_0,23_0,28_0,89_0,31_0,64_0,28_0,83_0,93
0,99_0,15_0,33_0,35_0,91_0,41_0,60_0,27_0,75_0,88
0,68_0,49_0,05_0,43_0,95_0,58_0,19_0,36_0,69_0,87
Aparentemente, todos estes números parecem ser randômicos e provavelmente passariam pelo teste de frequência apresentado anteriormente. Porém, ao analisarmos a quinta e a décima coluna pode-se verificar que sempre há um número grande naquelas posições. Como 30 números é uma amostra pequena não é possível afirmar se realmente há alguma relação entre os números obtidos. Será apresentado um método para se afirmar se tal relação existe em uma determinada amostra. Tal relação pode ser números muito altos, muito baixos ou podem se alternar entre muito altos e muito baixos (BANKS et al.,2005).
O teste requer computação de autocorrelação cada m números (m também conhecido como lag, será chamado de intervalo m a partir daqui), começando pelo i-ésimo número. Portanto autocorrelação entre os seguintes números é de interesse:
<math>R_i,\ R_{i+m},\ R_{i+2m},\ ...,\ R_{i+(M+1)m}</math>
O valor M é o maior número inteiro possível tal que <math>i + (M+1)m \le N</math>, onde N é o número total de valores na sequência. Caso a autocorrelação seja diferente de zero, isso implicaria que há uma falta de independência, portanto o seguinte teste de hipótese é apropriado:
<math>H_0 : \rho_{im}\ = 0</math>
<math>H_1 : \rho_{im} \ne 0</math>
Para valores muito altos de M, a distribuição do estimador de <math>\rho_im</math>, denotado de<math>\hat{\rho}_{im}</math> é aproximadamente normal se os valores de <math>R_i,\ R_{i+m},\ R_{i+2m},\ ...,\ R_{i+(M+1)m}</math> são independentes. Portanto, o seguinte teste estatístico pode ser feito:
<math>Z_0 = \frac {\hat{\rho}_{im}}{\sigma_{\hat{\rho}_{im}}}</math>
Onde <math>Z_0</math> é distribuído de forma normal com variância igual a 1, sob a suposição de independência para um M muito grande. As fórmulas de <math>\hat{\rho}_{im}</math> e desvio padrão de <math>\hat{\rho}_{im}</math> são dadas por Schmidt e Taylor [1970] conforme seguem:
<math>\hat{\rho}_{im} = \frac{1}{M+1} ( \sum_{k=0}^{M} R_{i+km} * R_{i+(k+1)m}) - 0.25</math>
e
<math>\sigma_{\hat{\rho}_{im}} = \frac{\sqrt{13M + 7}}{12(M+1)}</math>
Após computar-se <math>Z_0</math>, não se rejeita a hipótese <math>H_0</math> de que os números são independentes se
<math>-Z_{\alpha/2} \le Z_0 \le Z_{\alpha/2} </math> onde alfa é o nível de significância e <math>Z_{\alpha/2} </math> é obtido da tabela presente nos Anexos.
Se <math>\rho_{im} > 0</math> isso significaria uma autocorrelação positiva, onde a cada valor sucessivo (obtido a partir do intervalo m) há uma probabilidade maior do que a esperada de se obter valores próximos um do outro (um valor muito alto seguido de outro ou valor muito baixo seguido do outro).
Caso <math>\rho_{im} < 0</math> isso significaria uma autocorrelação negativa, onde há uma alternância de valores altos e baixos a cada intervalo m.
Caso <math>\rho_{im} = 0</math> significaria que obtivemos independência nos números analisados a cada intervalo m.
Considerações Finais
A simulação do fenômeno de interesse é obtida associando-se números aleatórios a eventos e à sua probabilidade de ocorrência. Esta é a ideia de um modelo de simulação genérico e é também empregada, portanto, no Método de Monte Carlo. Apesar de o Método de Monte Carlo não ser um modelo de simulação propriamente dito, sua origem e seu uso está intrinsecamente ligado à simulação.
Nesta abordagem didática do Método, procurou-se, portanto, apresentar esta ligação do Método com a simulação que ocorre desde sua concepção em Los Alamos para a resolução da questão da fissão nuclear. É curioso observar que métodos estatísticos que tornariam a concepção do Método de Monte Carlo possível já datavam de antes da década de 50, porém foi apenas com a criação do computador eletrônico que sua execução passou a ser efetivamente viável.
Porém, para compreender o Método de Monte Carlo, além dos aspectos históricos, é necessário conhecer aquilo que p torna possível, que são os geradores de números pseudoaleatórios existentes em um ambiente computacional. Como comentado antes, o Método é possível de ser realizado sem o uso de um computador, uma vez que ele é baseado em métodos estatísticos, porém, neste caso, ele se torna impraticável para realizar simulações que gerem dados realísticos de sistemas complexos do mundo real.
Portanto, a geração de números pseudoaleatórios em um ambiente computacional não é, necessariamente essencial ao Método, mas é o que o torna útil em aplicações práticas. O entendimento dos geradores de números aleatórios é parte do conhecimento a respeito do Método de Monte Carlo, e as características de cada gerador devem ser conhecidas de forma a se aplicar o gerador mais adequado a cada situação.
Com este trabalho foi possível, por fim, compreender os conhecimentos atrelados ao Método de Monte Carlo assim como a importância de todos eles para que o Método possa ser utilizável em situações reais.
Referências
- BANKS, J.; CARSON II, J.S.; NELSON, B.L. Discrete event system simulation. 4.ed. New Jersey: Prentice Hall, 2005.
- BARROS, Emílio A. C.. Aplicações de Simulação Monte Carlo e Bootstrap. 2005, 52 f. Monografia (Bacharelado em Estatística) – Departamento Acadêmico de Estatística, Universidade Estadual de Maringá, Maringá, 2005. Disponível em <http://www.des.uem.br/graduacao/Monografias/Monografia_Emilio.pdf>. Acesso em 05 set. 2010.
- ECKHARDT, Roger. Stan Ulam, John von Neumann, and The Monte Carlo Method. Los Alamos Science, Los Alamos, no. 15, p. 131-137, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-13.pdf >. Acesso em: 05 set. 2010.
- FREITAS FILHO, Paulo José de. Introdução à modelagem e simulação de sistemas: com aplicações em Arena. 2. ed. Florianópolis: Visual Books, 2001.
- LAW, A.M.; KELTON, W.D. Simulation modeling and analysis. 3. ed. Boston: McGraw-Hill, 2000.
- LAWRENCE, Denis. Note on Monte Carlo Analysis. Apresentado na Comissão de Comércio, Wellington, Nova Zelândia, 2004. Disponível em < http://www.med.govt.nz/upload/16173/meyrick-monte-carlo.pdf > acesso em 30 de outubro de 2010.
- MACHLINE, Claude, MOTTA, Ivan de Sá, SCHOEPS, Wolfgang, WEIL, Kurt E. Manual de Administração da Produção, Vol. II. Rio de Janeiro: Fundação Getúlio Vargas,1985.
- METROPOLIS, Nicholas; Ulam, S. The Monte Carlo Method. Journal of the American Statistical Association, vol. 44, No. 247 (Sep. 1949), pp. 335-341.
- ______. The Beginning of The Monte Carlo Method. Los Alamos Science, Los Alamos, no. 15, p. 125-130, 1987. Disponível em: <http://library.lanl.gov/cgi-bin/getfile?15-12.pdf>. Acesso em: 05 set. 2010.
- PENGELLY, Jonathan. Monte Carlo Methods. Disponível em <http://www.cs.otago.ac.nz/cosc453/student_tutorials/monte_carlo.pdf>. Acesso em 20 de setembro de 2010.
- PRADO, Darci Santos do. Teoria das filas e da simulação. 4. ed. Belo Horizonte: Editora de Desenvolvimento Gerencial, 2009.
- ROSA, Fernando H. F. P. da; COSTA, Matheus Moreira; TORTELLA, Tiago Luiz; JUNIOR, Vagner Aparecido. Método de Monte Carlo e Aproximações de PI. Disponível em < http://www.feferraz.net/files/lista/montecarlopi.pdf >. Acesso em 05 set. 2010.
- TAHA, Hamdy A. Operations research: an introduction. 6.ed. Upper Saddle River: Prentice Hall, c1997.
- WARNOCK, Tony. Random-Number Generators. Los Alamos Science, Los Alamos, no. 15, p. 137-141, 1987. Disponível em: <http://library.lanl.gov/cgi-bin/getfile?00418729.pdf>. Acesso em: 05 set. 2010.