Documentação Final
(→Método de Monte Carlo) |
(→Geração de Números Aleatórios) |
||
| Linha 151: | Linha 151: | ||
=Geração de Números Aleatórios= | =Geração de Números Aleatórios= | ||
| + | ==Introdução sobre Números Aleatórios== | ||
| + | ==Geração de Números Pseudoaleatórios== | ||
| + | ==Gerador Linear Congruente== | ||
| + | ==Testes para números aleatórios== | ||
=Estudo da Fila do Restaurante Universitário= | =Estudo da Fila do Restaurante Universitário= | ||
Edição de 09h44min de 30 de novembro de 2010
Tabela de conteúdo |
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.
