Edição atual tal como 19h18min de 1 de dezembro de 2010

Introdução

Uma simulação é uma imitação de uma operação ou de um 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 de 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).

Assim, a 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, bem como 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 (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, por exemplo) são complexos demais e 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.

Um sistema pode ser classificado em discreto ou contínuo. Um sistema discreto é aquele cujas variáveis mudam instantaneamente em certos tempos, enquanto que em um sistema contínuo o estado 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 um sistema desejado é necessário criar um modelo de tal processo. Um modelo é a representação de um sistema com o propósito de estuda-lo. Para a maioria dos estudos, é necessário apenas considerar os aspectos do método que afetam o problema sob investigação (BANKS,2005,p. 12). Modelos ainda podem ser classificados em matemáticos ou físicos. Modelos matemáticos utilizam notação matemática representando as relações lógicas e qualitativas do sistema. Os físicos são aqueles gerados manualmente, como arremesso de moedas e lançamento de dados, por exemplo.

Os modelos matemáticos e físicos de simulação ainda podem ser classificados em 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

Este trabalho se propõe a apresentar o Método de Monte Carlo, seu desenvolvimento histórico e algumas aplicações, sua implementação em ambientes computacionais, a geração de números pseudo-aleatórios e suas limitações envolvidas. Para tanto foi realizado um estudo da fila do restaurante universitário do campus Curitiba da UTFPR a fim de mostrar na prática como o Método pode ser utilizado.

Justificativa

O Método de Monte Carlo é utilizado em diversas áreas de aplicações, tais como a computação, onde o método foi desenvolvido, até a administração. Entretanto, observa-se em geral um grande esforço na aplicação do método, deixando em segundo plano a compreensão de seus fundamentos e limitações.

Este é justamente neste aspecto que este trabalho se baseia, ou seja, expor os fundamentos do Método de Monte Carlo para que as pessoas que o utilizam como ferramenta possam entender um pouco mais seus princípios.

Objetivos

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

• Análise do Método de Monte Carlo no contexto de simulações;
• Coleta de dados e aplicação do Método à 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, prevem-se três etapas:

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

Para a elaboração do aplicativo, os seguintes procedimentos foram adotados:

• Coleta de dados sobre a fila do Restaurante Universitário,
• Programação.

Método de Monte Carlo

Segundo Sobol (1994), o Método de Monte Caro é “um método numérico de solução de problemas matemáticos através da simulação de variáveis aleatórias”.

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. Para a melhor compreensão do Método, começaremos com o conceito de Acerto-ou-Erro, que o baseia.

Acerto-ou-Erro

Para a compreensão inicial do Método de Monte Carlo, Sobol (1994) apresenta um exemplo simples de Acerto-ou-Erro (Hit-or-Miss). Para isso, podemos considerar uma região S contida em um quadrado unitário de lado l = 1, conforme figura abaixo:

Inserir figura.

Observa-se que há pontos distribuídos pela região do quadrado. Tais pontos foram lançados aleatoriamente na região. Estes lançamentos são realizados de forma que todos os pontos do quadrado têm igual probabilidade de serem atingidos, ou seja, o acerto em uma determinada região não é mais provável do que o acerto em alguma outra dentro do quadrado. Supondo que foram realizados N lançamentos, teremos, então, N pontos distribuídos na área do quadrado unitário. Consideremos, ainda, que N' pontos acertaram a região S. Com isso, é possível concluir geometricamente que a área da região S é, aproximadamente, a razão N'/N. Quanto maior for N, maior será a precisão desta aproximação. No exemplo da figura acima, temos que N = 25 e N' = 14. A área da região S é, então, aproximadamente 0,56 (Sobol, 1994).

Seguindo o mesmo princípio de Acerto-ou-Erro, é possível calcular o valor de π considerando uma circunferência inscrita em um quadrado. A figura abaixo ilustra esta configuração (Rosa et al.).

Inserir figura.

Assim como o exemplo anterior, podemos considerar a área da circunferência como S e o quadrado no qual ela está inscrita com lado unitário l = 1. Assim, realizando N lançamentos aleatórios na região do quadrado, com N' acertos na área da circunferência podemos obter a área da circunferência pela razão N'/N.

Entretanto, neste caso a fórmula para o cálculo da área da circunferência é conhecida assim como a do quadrado. Tratando-se de uma circunferência inscrita em um quadrado, sabe-se que l = 2r.

Analiticamente, a razão N'/N representa a razão da área da circunferência AC pela área do quadrado AQ. Sendo conhecidas as fórmulas para o cálculo de área tanto da circunferência quanto do quadrado e sabendo-se que l = 2r, temos que:

<math>\frac{A_c}{A_q} = \frac{\pi r^2}{(2r)^2}</math>

Simplificando e rearranjando a fórmula, temos então que:

<math>\pi = 4\frac{A_c}{A_q}</math>

Considerando N lançamentos aleatórios na região do quadrado, é possível, então, estimar o valor de π por:

<math>\pi = 4\frac{N}{N'}</math>

Na prática, o Método de Monte Carlo não é utilizado para o cálculo de áreas por haver outros métodos que apresentam uma maior precisão para este fim. Porém, para a estimativa de volume de um sólido, o Método de Monte Carlo é, muitas vezes, a única alternativa viável para a solução do problema (Sobol, 1994).

O Método de Monte Carlo

Com os exemplos sobre Acerto-ou-Erro, pode-se afirmar que o Método de Monte Carlo “fornece uma solução aproximada para uma variedade de problemas matemáticos ao realizar experimentos de amostragem estatística” (Pengelly, 2002).

Ainda de acordo com Pengelly (2002), o Método de Monte Carlo engloba técnicas que realizam diversas simulações utilizando números aleatórios e probabilidade para obter uma aproximação da solução do problema. “O que define o Método de Monte Carlo é o uso de números aleatórios em sua simulação”.

Exemplo Lava-car

Freitas Filho (2008), demonstra a aplicação do Método de Monte Carlo em um sistema de Fila Simples, análogo aos guichês de atendimento presentes em bancos, cinemas, pedágios, etc. A aplicação utilizada como exemplo foi um serviço de lava-car, que conta com uma máquina multifuncional (molha, ensaboa, enxágua e seca) e um funcionário que a opera. Neste sistema, é possível que um cliente chegue e não possa ser atendido imediatamente e, neste caso, ele será encaminhado para uma área de espera (fila).

Inserir figura.

O dono do lava-car, almejando melhorar os ganhos do posto, considera realizar algumas mudanças em seu estabelecimento para que mais clientes possam ser atendidos. Porém, ele tem receio em realizar um investimento sem conhecer qual mudança de desempenho isso pode gerar. Algumas dúvidas lhe ocorreram a respeito de seu estabelecimento:

• A área de espera é suficiente ou há clientes que desistem por falta de espaço?
• O tempo de realização do serviço é aceitável?
• É necessário contratar mais um funcionário para períodos de alta demanda?

Para responder a estas perguntas e decidir a respeito do investimento, é possível empregar três técnicas para o estudo deste sistema:

• Utilizar o “bom senso”;
• Tratamento por modelagem analítica;
• Tratamento por modelagem e simulação de sistemas.

O emprego do “bom senso” trata-se de empregar o conhecimento de “experiências anteriores e um pouco de adivinhação”. Freitas Filho batiza esta alternativa como “achometria”. Poucas informações são obtidas através deste método.

O tratamento por modelagem analítica emprega, na maioria dos casos, a teoria das filas. Neste exemplo, seria empregado um conjunto de fórmulas matemáticas com as quais é possível responder às perguntas do proprietário. Entretanto, vários casos de interesse não possuem solução analítica e, portanto, a simulação se mostra como alternativa viável.

Para se realizar a modelagem e simulação, é necessário, primeiramente, coletar dados do sistema real. Estes dados dizem respeito ao tempo decorrido entre a chegada de um cliente e do próximo, e o tempo necessário para se realizar a lavagem. Para a simulação não deve-se utilizar a média dos valores obtidos, mas sim os próprios dados coletados. Com o lava-car, foi obtida a tabela com os dados abaixo:

Inserir figura.

A linha “Probabilidade” indica a probabilidade de ocorrência do respectivo tempo entre chegadas ou de serviço. Foram colhidas três amostras do sistema, sendo de 10, 12 e 15 minutos para o Tempo Entre Chegadas e 9, 10 e 11 para Tempo de Serviço. Na simulação, o Tempo Entre Chegadas – TEC – e o Tempo de Serviço – TS - assumirão aleatoriamente um dos seus três valores respectivos.

Com esses dados, é possível simular a chegada de clientes assim como o tempo de atendimento de ada um deles. Fazendo a simulação para a chegada de 15 clientes, temos que:

Inserir figura.

A partir dos valores de soma apresentados em algumas das colunas da tabela, é possível calcular algumas estatísticas.

• <math>Tempo\ M\acute{e}dio\ na\ Fila = \frac{\sum tempo\ na\ fila}{N\acute{u}mero\ total\ de\ clientes} = \frac{2}{15} = 0,13 min</math>

• <math>Probabilidade\ de\ entrar\ na\ fila = \frac{N\acute{u}mero\ de\ clientes\ que\ esperam}{N\acute{u}mero\ total\ de\ clientes} = \frac{2}{15} = 0,13 = 13,33%</math>

• <math>Probabilidade\ de\ operador\ livre = \frac{\sum tempo\ livre\ do\ operador}{Tempo\ total\ simulado} = \frac{52}{203} = 0,26 = 25,62%</math>

• <math>Tempo\ M\acute{e}dio\ de\ Serviço = \frac{\sum TS}{N\acute{u}mero\ total\ de\ clientes} = \frac{151}{15} = 10,06 min</math>

• <math>Tempo\ M\acute{e}dio\ no\ Sistema = \frac{\sum tempo\ no\ sistema}{N\acute{u}mero\ total\ de\ clientes} = \frac{153}{15} = 10,2 min</math>

Estes valores obtidos já respondem a duas perguntas sobre as quais o proprietário tinha dúvidas: se o tempo de atendimento é aceitável e se é necessário contratar um outro funcionário. Foi possível concluir que um cliente passa, em média, 10,2 minutos no lava-car e que o operador permanece ocioso 25,62% do seu tempo em serviço, ou seja, ele está ocupado 74,38% do tempo.

Neste exemplo de Freitas Filho (2008), pode-se observar que com um procedimento simples de simulação, possível de ser feito até mesmo manualmente, consegue-se extrair informações relevantes a respeito do sistema.

Ainda deste exemplo, podem-se destacar alguns pontos relevantes ao Método de Monte Carlo. O primeiro diz respeito às variáveis aleatórias. Determinou-se, através da obtenção de dados do sistema real, que o tempo entre chegadas poderia ser de 10, 12 ou 15 minutos, porém, na simulação, a ocorrência de um tempo ou de outro foi gerada aleatoriamente, respeitando a probabilidade de ocorrência de cada um. O gerador utilizado neste exemplo gera números aleatórios no intervalo [0,1] e o algoritmo decide qual o valor a qual ele corresponde. As propriedades e características dos Geradores de Números Aleatórios serão explicados em maiores detalhes no capítulo 3.

Alguns conceitos de Estatística

Como visto anteriormente na definição de Pengelly (2002) e visto no exemplo do lava-car, o Método de Monte Carlo está intrinsecamente ligado à técnicas estatísticas. Portanto, é importante a compreensão de alguns conceitos de Estatística utilizados no Método.

De acordo com Silva et al. (1999), “estatística é um conjunto de métodos e processos quantitativos que serve para estudar e medir os fenômenos coletivos”. Fenômenos coletivos podem ser entendidos como conjuntos de dados que possuem um mesmo significado. Pode-se citar, como exemplo, os Tempos Entre Chegadas do lava-car. Apesar de seus valores não serem sempre os mesmos, o significado atrelado a eles é sempre a diferença do tempo de chegada entre um cliente e o anterior. É este fenômeno coletivo, este conjunto de valores, o que a estatística estuda e mede.

Medidas de Tendência Central

Na estatística, as Medidas de Tendência Central são aquelas que indicam um valor em torno do qual o conjunto de valores observados estão dispersos. As principais medidas de tendência central são a média, a mediana e a moda (Perin Filho, 1999).

Considerando o conjunto de valores observados <math>{x_1, x_2, ..., x_n}</math>, a média aritmética simples do conjunto pode ser definida por:

<math>\bar{x} = \frac{\sum x_i}{n}</math>

sendo <math>\bar{x}</math> a notação para média. Soong (2004) faz uma analogia da média com o centro de massa de um corpo.

A mediana trata-se de uma medida tal que metade dos valores do conjunto são menores ou iguais a ela e metade são maiores ou iguais a ela (Perin Filho, 1999). Trata-se, portanto do valor que ocupa a posição central no conjunto ordenado (Silva et al., 1999).

Finalmente, a moda é definida como o elemento do conjunto que apresenta a maior frequência (Silva et al., 1999). Realizando a analogia a um corpo de massa, a moda seria um pico de densidade (Soong, 2004).

Pode-se observar que destas medidas de tendência central, a moda é a única que pode ser definida em um conjunto que não apresente relação de ordem. Pode-se citar, como exemplo, um conjunto cinco pessoas envolvidas em uma universidade, cuja relação com esta é de {professor, estudante, funcionário, estudante, estudante}. É possível dizer que a moda do conjunto é estudante, porém não há sentido em se obter a média ou mediana deste conjunto (Perin Filho, 1999).

Medidas de Dispersão

Com as medidas de tendência central é possível extrair informações importantes a respeito do conjunto estudado, porém apenas elas não são o suficiente para caracterizar o conjunto (Silva et al., 1999).

Considerando os conjuntos <math>x_1 = {1, 99}</math> e <math>x_2 = {50, 50}</math> observa-se que em ambos os casos, <math>\bar{x} = 50</math>, porém os conjuntos <math>x_1</math> e <math>x_2</math> são diferentes.

As medidas de dispersão expressam “o quão próximo os valores do conjunto encontram-se dispersos em torno de uma medida de tendência central”. As principais medidas de dispersão são a variância, o desvio-padrão e a amplitude.

A variância é a medida que expressa a dispersão de um elemento qualquer <math>x_i</math> da média <math>\bar{x}</math>. Ela pode ser expressa por:

<math>\sigma^2 = \frac{\sum x_i - \bar{x}}{n}</math>

sendo n o número total de elementos no conjunto analisado. Quanto maior for o valor da variância, mais dispersos estão os elementos do conjunto em relação a sua média. Uma variância <math>\sigma^2 = 0</math> significa que todos os elementos do conjunto possuem um mesmo valor, que é, portanto, também a sua média <math>\bar{x}</math> (Soong, 2004).

O desvio-padrão <math>\sigma</math> trata-se da raiz quadrada da variância e expressa o mesmo significado desta, sendo expresso por:

<math>\sigma = \sqrt{\sigma^2}</math>

O desvio-padrão, porém, conta com a vantagem de estar na mesma unidade dos valores do conjunto estudado, o que facilita para se fazer comparações. Já a amplitude é a simplesmente a diferença entre o maior e o menor valor do conjunto (Perin Filho, 1999).

<math>amplitude\ =\ maior\ -\ menor</math>

Utilizadas juntamente com as medidas de tendência central, as medidas de dispersão oferecem informações relevantes a respeito do conjunto analisado.

Probabilidade

Segundo Perin Filho (1999), o que define probabilidade é o experimento aleatório, “um experimento cujo resultado não pode ser determinado a priori”. Nos exemplos sobre Acerto-ou-Erro da seção 2.1 deste trabalho, utilizou-se um experimento aleatório tal que a probabilidade de acerto era igual para todos os pontos da área total analisada. Neste caso, a distribuição de frequência do conjunto gerado será uniforme.

Frequência refere-se ao número de elementos do conjunto estudado que se encontram em uma determinada faixa de valor. Em uma distribuição de frequência, todas as faixas de valores nas quais o conjunto se subdivide devem ter um mesmo tamanho (Silva et al., 1999).

Na seção 2.1 foi observada a distribuição uniforme de probabilidade. Esta é a distribuição que todos os geradores de números aleatórios (capítulo 3) devem possuir, porém na maioria dos casos de simulação, a variável de interesse apresenta outro tipo de distribuição. Neste caso, é necessário realizar uma transformação na distribuição uniforme para que ela assuma a forma da variável de interesse.

Segundo Freitas Filho (2008), as distribuições normais, lognormais e uniformes são comuns e facilmente reconhecidas, conforme gráficos abaixo:

Inserir figura.
Inserir figura.
Inserir figura.

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. Desta 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

Introdução sobre Números Aleatórios

Números Aleatórios são um dos ingredientes básicos quando realiza-se uma simulação de um sistema discreto. A maioria das linguagens de programação possui ou permite criar uma sub-rotina,objeto ou função que seja capaz de gerar números aleatórios (BANKS et al.,2005).

Números Aleatórios apresentam duas propriedades estatísticas importantes: uniformidade e independência. Uniformidade indica que todo número aleatório possui a mesma probabilidade de serem “sorteados”, ou seja:

<math>f(x) = 1,0 \le x \le 10</math>, caso contrário

Como a função f(x) demonstra, qualquer valor de x entre 0 e 1 possui a mesma probabilidade de ocorrência.

Independência significa que todo número aleatório sorteado não é afetado por resultados das amostras anteriores, ou seja, a probabilidade de se observar um número é independente dos valores anteriormente observados.

Geração de Números Pseudoaleatórios

Ao se gerar números aleatórios por meio de um método conhecido (uma rotina computacional, por exemplo) retira-se o potencial para verdadeira aleatoriedade, portanto estão sendo gerados números pseudoaleatórios Se o método é conhecido, os números sorteados podem ser replicados, portanto pode-se argumentar que os números não são verdadeiramente aleatórios. O objetivo de qualquer método de geração de números aleatórios é produzir sequências de números que imitem as propriedades ideais de uniformidade e independência dos números verdadeiramente aleatórios (BANKS et al.,2005).

Na geração de números pseudoaleatórios podem ocorrer certos problemas ou erros. Tais erros são relacionados as propriedades dos números aleatórios, por exemplo:

• Os números gerados podem não estar distribuídos uniformemente.
• A média dos números gerados pode ser muito alta ou muito baixa
• A variância dos números gerados pode ser muito alta ou muito baixa
• Pode haver dependência entre os números gerados.

Tais erros podem ser detectados por meio de testes de uniformidade e independência. Se tais erros forem detectados o gerador deve ser substituído por um mais adequado.

Ao se utilizar rotinas computacionais para se gerar números aleatórios, há algumas considerações a serem feitas:

• A rotina deve ser rápida, pois operações individuais utilizam pouco processamento, mas uma simulação pode precisar de milhões de números aleatórios.
• A rotina deve ser portátil para diferentes computadores e linguagens de programação garantindo que a rotina produza os mesmos resultados independente da onde for executada.
• A rotina deve possuir um ciclo suficientemente longo. O ciclo representa quantos números o gerador pode gerar sem repetir sequências já geradas.
• Deve ser possível replicar uma sequência já gerada. Dada as condições iniciais, deve ser possível gerar a mesma sequência de números aleatórios independente da onde estejam sendo gerados.
• Os números gerados devem possuir características próximas dos números verdadeiramente aleatórios, ou seja, uniformidade e independência.

Gerador Linear Congruente

Um gerador comumente utilizado é o Linear Congruente, proposto inicialmente por Lehmer em 1951. Esse método produz uma sequência de números entre zero e m-1 seguindo a seguinte relação recursiva:

<math>X_{i+1} = (aX_i + c) mod\ M</math>, <math>i = 0, 1, 2...</math>

Onde “mod” é o operador de resto.

O valor inicial <math>X_0</math> é chamado de semente, a é o multiplicador, c o incremento em o módulo. A seleção para esses parâmetros afeta drasticamente as propriedades estatísticas do gerador. Variações do gerador linear congruente são comuns na geração de números aleatórios.

Testes para números aleatórios

Já fora discutido que uma sequência de números produzida por um gerador de números aleatórios deve possuir propriedades próximas a de números verdadeiramente aleatórios, sendo estas uniformidade e independência.

Para verificar-se se as propriedades foram alcançadas, um número de testes podem ser realizados. Tais testes podem ser colocados em duas categorias:

• Teste de Frequência: Compara a distribuição dos números gerados com a distribuição uniforme (Exemplos: Kolmogorov-Smirnov e teste do Qui Quadrado).
• Teste de Autocorrelação: Compara a correlação entre os números gerados com uma amostra ideal de correlação (a amostra ideal seria igual a zero, indicando que são idealmente independentes) (BANKS et al.,2005).

Estudo da Fila do Restaurante Universitário

Com o objetivo de se estudar o Método de Monte Carlo, aplicando-o em um caso real, foi estudada a fila do Restaurante Universitário do Campus Curitiba. Para realizar tal estudo foi necessário, primeiramente, coletar dados sobre o sistema real. Dados sobre três variáveis foram coletadas:

• número de pessoas que estavam na fila;
• número de pessoas se servindo no buffet (em atendimento) e;
• tempos que as pessoas demoravam no atendimento.

Foram coletadas amostras de cinco em cinco minutos destas variáveis entre os horários de 11 horas e 35 minutos e 13 horas. As tabelas abaixo mostram os dados coletados.

Inserir figura.

Inserir figura.

Através da Tabela 4.1, é possível plotar um gráfico do número de pessoas na fila pelo horário. Observa-se, assim como era esperado, que há uma concentração maior de pessoas na fila nos horários próximos às 12 horas, horário que representa o início do horário de almoço para a maioria dos estudantes, professores e funcionário da Universidade.

Inserir figura.

Na seção 2.3.3 foram abordadas algumas distribuições de probabilidade mais comuns. Abaixo segue a distribuição de frequência obtida do número de pessoas na fila do RU, sendo tomados intervalos de 20 em 20.

Inserir figura.

Apesar de termos estudado algumas das distribuições de probabilidade mais usuais, não foi possível enquadrar a distribuição em nenhuma delas.

É possível que, obtendo mais amostras, a distribuição adquiri-se uma forma semelhante a alguma constante na literatura. Entretanto, neste estudo, por falta de tempo para a obtenção de novas amostras e estudo mais profundo, trabalhou-se apenas com os valores de média, tanto do tamanho da fila quanto para o tempo em atendimento.

Para realizar o estudo da fila do Restaurante Universitário fizemos um aplicativo na linguagem de programação Java. Este aplicativo conta com um Gerador Linear Congruente, que gera as entradas aleatórias de tamanho de fila e tempo em atendimento. Os resultados obtidos pelo estudo, assim como o código-fonte do aplicativo estão disponíveis na documentação deste trabalho (http://www.dainf.ct.utfpr.edu.br/wiki/index.php/2010bEquipe05).

Pudemos observar que o uso do Método de Monte Carlo em simulação com este estudo da fila do Restaurante Universitário não é tão simples, sendo que teríamos considerar mais variáveis aleatórias no nosso estudo, além de anotar dados durante mais dias.

Considerações Finais

Nesta monografia sobre o método de Monte Carlo, procurou-se apresentar o método didaticamente e apresentá-lo implementado em ambientes computacionais juntamente com seu desenvolvimento histórico e algumas aplicações. É 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 sua viabilidade em ambientes computacionais é necessário conhecer aquilo que o torna possível, que são os geradores de números pseudoaleatórios existentes em um ambiente computacional. Com o auxílio computacional, o método de Monte Carlo se torna uma ferramenta poderosa quanto a simulações de sistemas complexos. 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 torna-se necessariamente essencial ao Método, permitindo seu uso em simulações por exemplo. Consequentemente, 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.

Como proposta para estudos posteriores é possível coletar mais dados sobre o restaurante universitário como , por exemplo, entrada de pessoas em diferentes horários, tempo de permanência e saída de pessoas. A partir desses dados, será possível teorizar uma distribuição de probabilidade do restaurante universitário e conseqüentemente realizar uma simulação. Tal simulação poderá fornecer informações diversas sobre o funcionamento restaurante universitário como, por exemplo, períodos no qual o restaurante encontra-se lotado ou as consequências de se modificar algo dentro do restaurante.

Por fim, com este trabalho foi possível 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.

• FREITAS FILHO, Paulo José de. Introdução à modelagem e simulação de sistemas: com aplicações em Arena. 2. ed. Florianópolis: Visual Books, 2008.

• 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.

• 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.

• 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 <www.feferraz.net/files/lista/montecarlopi.pdf>. Acesso em 05 set. 2010.

• SILVA, E. M.; GONÇALVES, W.; SILVA, E. M.; MUROLO, A.C.. Estatística para os Cursos de: Economia, Administração e Ciências Contábeis. 3. ed. São Paulo: Editora Atlas S. A., 1999.

• SOBOL, Ilya M. A primer for the Monte Carlo Method. Boca Raton: CRC Press, 1994.

• SOONG, T. T.. Fundamentals of Probability and Statistics for Engineers. Inglaterra: Wiley, 2004.

Anexo 1: Tabela de Graus de Liberdade

Anexo 2: Aspectos Históricos de Monte Carlo

Foi no ano de 1945 que o primeiro computador eletrônico foi construído e foi também nessa época que um método estatístico, conhecido até então por amostragem estatística, neste novo cenário foi rebatizado como Método de Monte Carlo.

Durante a segunda guerra mundial, um time de cientistas, engenheiros e técnicos trabalhava para a construção do primeiro computador eletrônico – o ENIAC (Electronic Numerical Integrator And Computer) – 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.

Neste momento, John Neumann era um consultor em Aberdeen e Los Alamos. Por diversas razões, ele estava interessado na questão termonuclear, estudada por um colega húngaro em Los Alamos. A construção do ENIAC estava quase concluída, e Neumann convenceu as autoridades de Aberdeen de que o problema que tinha em mãos seria um teste mais exaustivo ao dispositivo do que fazer uma série de contas.

E foi graças ao desenvolvimento do ENIAC que fez com que Stanislaw Ulam considerasse o ressurgimento de técnicas estatísticas, e ele comentou esta ideia com John von Neumann. Este foi o impulso inicial que levou ao surgimento do Método de Monte Carlo.

O Método pode ser explicado da maneira em que foi empregado para resolver a questão termonuclear. Considerando um núcleo esférico de material de fissão cercado por uma casca de um determinado material, supõe-se a distribuição inicial de nêutrons em posição e velocidade, mas desconsideram-se os efeitos radioativos e hidrodinâmicos. A ideia é, então, seguir o desenvolvimento de cadeias individuais de nêutrons como consequência de escape, dispersão, absorção e fissão.

Em cada estágio, uma sequência de decisões tem que ser tomada baseada em probabilidades estatísticas apropriadas aos fatores físicos e geométricos, sendo a primeira decisão tomada no tempo t=0, quando um nêutron é selecionado para ter uma determinada velocidade e uma determinada posição no espaço. As próximas decisões são referentes à posição da primeira colisão, assim como à natureza da colisão. Caso ocorra uma fissão, o número de nêutrons que surgem deve ser decidido com base nesses dados, e cada um desses nêutrons terá comportamento como o do primeiro. Desta forma, é possível criar uma história de cada nêutron.

Fonte: METROPOLIS, Nicholas. 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.