Índice de conteúdos. Índice de conteúdos. Capítulo 6. Modelação e Simulação de Sistemas A simulação de sistemas Definição... - PDF
Índice de conteúdos. Índice de conteúdos. Capítulo 6. Modelação e Simulação de Sistemas A simulação de sistemas Definição...
Download "Índice de conteúdos. Índice de conteúdos. Capítulo 6. Modelação e Simulação de Sistemas...1. 1.A simulação de sistemas...1. 1.1.Definição..."
Ruy Marreiro Ramalho
1 Índice de conteúdos Índice de conteúdos Capítulo 6. Modelação e Simulação de Sistemas A simulação de sistemas Definição As razões de usar modelos de simulação Modelos de simulação Introdução Sistema Modelo Cenários Parâmetros do Modelo Propriedades dos modelos de simulação Introdução Elementos de um modelo de simulação Classificação dos modelos de Simulação Modelos determinísticos e estocásticos Modelos estáticos e dinâmicos Modelos contínuos e discretos Modelos de simulação dinâmicos discretos Componentes de um modelo de simulação Tipos de modelação Modelação orientada ao Evento Desenvolvimento de um projeto de simulação Formulação do problema Definição dos objetivos i -
2 Índice de conteúdos Planeamento do projeto Construção do modelo Recolha de informação Implementação do modelo Verificação Validação Desenho de experiências Execução do modelo e análise dos resultados Mais execuções do modelo? Documentação e relatório Implementação da solução Implementação/codificação de um modelo de simulação discreta Exemplo Exemplo Exemplo Exemplo Nível de detalhe dos modelos de simulação Modelos de simulação com filas de espera Introdução Estrutura de uma fila de espera Mecanismos de escalonamento Centros de serviço Análise de dados de entrada (inputs) Introdução Propriedades das distribuições teóricas Análise estatística dos dados de entrada (inputs) Geração de número aleatórios Métodos para gerar números aleatórios Métodos para gerar observações aleatórias Análise de resultados (outputs) Medidas de desempenho típicas Análise de resultados de um sistema Comparação de configurações alternativas de um sistema ii -
3 Índice de conteúdos 6.Modelos de simulação contínuos Modelos de simulação estáticos - método de Monte Carlo O método de Monte Carlo (ou simulação de Monte Carlo) Fases da simulação de Monte Carlo Exemplo Exercício - Admissão de utentes numa urgência iii -
5 Modelação e Simulação de Sistemas Capítulo 6. Modelação e Simulação de Sistemas 1. A simulação de sistemas 1.1. Definição A simulação computacional de sistemas, ou simplesmente simulação, consiste na utilização de determinadas técnicas matemáticas, utilizadas em computadores digitais, as quais permitem imitar o funcionamento de praticamente qualquer tipo de operação ou processo (sistemas) do mundo real. Existem, na literatura, muitas as definições de simulação. Para Schriber ("Simulation Using GPSS", 1974), simulação implica a modelação de um processo ou sistema, de tal forma que o modelo imite as respostas do sistema real numa sucessão de eventos que ocorrem ao longo do tempo. Embora Schriber seja considerado por muitos como o grande responsável pela aproximação entre programas de computadores e linguagens de simulação (foi um dos criadores do GPSS, a primeira linguagem comercial de computadores para simulação de sistemas), a sua definição não especifica que o modelo deva ser computacional, pois na época, ainda eram os modelos analógicos e físicos os usados para se estudar e analisar o comportamento de sistemas. Hoje, a simulação é quase sinónimo de simulação computacional digital, em que um modelo computacional é executado. Robert Shannon ("Systems Simulation: The Art and Science", 1975) definiu assim este tipo de modelo: Um modelo computacional é um programa de computador cujas variáveis apresentam o mesmo comportamento dinâmico e estocástico do sistema real que representa. Considerando a definição anterior, Pegden ("Introduction to Simulation Using Siman", 1991), apresentou uma definição mais completa, abrangendo todo o processo de simulação: simulação é o processo de projetar um modelo computacional de um sistema real e conduzir experiências com este modelo com o propósito de entender o seu comportamento e/ou avaliar estratégias para a sua operação. O autor entende a simulação como um processo mais amplo, compreendendo, não só a construção do modelo, mas também todo o método experimental que se segue, procurando: 1. Descrever o comportamento do sistema; 2. Construir teorias e hipóteses considerando as observações efetuadas; - 1 -
6 A simulação de sistemas 3. Usar o modelo para prever o comportamento futuro, isto é, os efeitos produzidos por alterações no sistema ou nos métodos utilizados na sua operação. A simulação tem sido, cada vez mais, aceite e utilizada como uma técnica que permite a analistas, dos mais diversos quadrantes (administradores, engenheiros, biólogos, informáticos, etc.), verificar ou encaminhar soluções, com a profundidade desejada, dos problemas com os quais lidam diariamente. Mais do nunca a simulação computacional tem sido utilizada, devendo-se este crescimento, sobretudo, à atual facilidade de utilização e sofisticação dos ambientes de desenvolvimento de modelos computacionais, aliadas ao crescente poder de processamento das estações de trabalho. Contando com interfaces gráficas cada vez mais amigáveis, destinadas às mais diversas plataformas e, principalmente, fazendo intenso uso da animação dos sistemas que estão sendo simulados, a simulação deixou para trás o estigma de ser utilizada apenas quando tudo mais já foi tentado As razões de usar modelos de simulação A simulação de modelos permite ao analista realizar estudos sobre os correspondentes sistemas para responder a questões do tipo O que aconteceria se?. O principal apelo ao uso desta ferramenta, é que tais questões podem ser respondidas sem que os sistemas em análise sofram qualquer perturbação, uma vez que os estudos são realizados no computador. A simulação computacional permite que tais estudos sejam realizados sobre sistemas que ainda não existem, levando ao desenvolvimento de projetos eficientes antes que qualquer mudança física tenha sido iniciada. Ao contrário dos modelos de otimização, um modelo de simulação é executado e não resolvido. As diferenças entre estas duas abordagens implicam que o modelo de simulação permite análises quase que a cada instante, isto é, à medida que vão sendo apresentadas novas descobertas sobre o comportamento do sistema modelado. A maioria dos modelos de simulação é do tipo entrada-saída, isto é, são modelos interativos aos quais se fornecem dados de entrada, obtendo-se respostas específicas para estes dados. Não são, por natureza, modelos de otimização, não oferecendo (a menos de um razoável esforço) a possibilidade de pesquisa de uma solução ótima. Estes modelos servem essencialmente para fazer análises do comportamento do sistema sob condições específicas. Normalmente, os modelos de simulação são utilizados com o objetivo de testar uma solução de um dado problema. Um estudo com modelos de simulação permite aos analistas considerarem níveis de detalhes mais elevados, permitindo que diferenças de comportamento, às vezes subtis, se venham a evidenciar. As abordagens tradicionais, pelo contrário, utilizam estudos preliminares estáticos e sofrem tantas simplificações que muitos projetos, depois de implantados, acabam por sofrer inúmeras modificações e adaptações
7 A simulação de sistemas De modo geral, as prncipais razões pelas quais se recomenda a utilização de modelos de simulação são as seguintes: 1. Sistema real inexistente. A simulação poderá ser usada para planear o futuro sistema; por exemplo, um novo hospital, uma nova fábrica ou um novo ambiente de suporte a negócios na Internet. 2. Experimentar com o sistema real é dispendioso. O modelo poderá indicar, com custos muito mais baixos, por exemplo, quais os benefícios de se investir num novo equipamento. 3. Experimentar com o sistema real não é apropriado. Dois casos típicos são os planeamentos do atendimento de situações de emergência e da assistência a um desastre aéreo num aeroporto. Toda a logística para accionar os serviços prestados pela polícia, bombeiros, ambulâncias, emergência hospitalar, etc., e a própria atuação destas entidades, podem ser modelada e testada no computador. Não se pode provocar um desastre para testar planos de emergência. As técnicas associadas aos modelos de simulação são, em geral, facilmente compreensíveis e justificáveis, quer para utilizadores como para os gestores que tomam a decisão de os aplicar nos seus projetos. Geralmente, esta aceitação deve-se a vários fatores, tais como: Tempo: no computador é possível realizar experiências que, se executados sobre o sistema real, poderiam consumir anos; Custo: embora a simulação em computador exija recursos humanos e alguns equipamentos, geralmente o custo de execução das experiências é muito baixo quando comparado com custo sobre o sistema real; Impossibilidade de experimentação direta: há situações em que experiências diretas no sistema real não podem ser realizadas por questões de segurança, tempo, acesso, inexistência (sistema em construção), etc.; Visualização: os computadores oferecem recursos que facilitam a visualização dos resultados de uma simulação (gráficos, tabelas, entre outros), bem como do estado do sistema durante a execução de um modelo; Repetição: depois de construído, um modelo de representação pode ser executado várias vezes a um custo muito baixo e de forma relativamente rápida; Interferência: um modelo é extremamente mais flexível para a realização de mudanças se comparado a um sistema real. Esta é uma característica bastante desejável no estudo de sistemas com objetivos de geração de informações de apoio a tomada de decisões. Semelhança com o realidade: a percepção de que o comportamento do modelo de simulação é muito semelhante ao sistema real. Os modelos de simulação podem ser considerados como uma descrição de sistemas reais. A execução de modelos de simulação em computador tem potencial para fornecer resultados mais precisos sem que seja preciso interferir no sistema real. Tais resultados, quando analisados - 3 -
8 A simulação de sistemas estatisticamente, produzem informações que podem contribuir grandemente para a tomada de decisões que visam a solução de problemas. Restringindo um pouco mais a simulação de sistemas para os meios computacionais, e considerando os modelos como um dos métodos de representação de sistemas, o seguinte conceito pode ser adotado: Simulação é uma técnica numérica para realizar experiências num computador digital, a qual envolve certos tipos de modelos lógicos que descrevem o comportamento de um sistema sobre extensos intervalos de tempo. Basicamente, a utilização de modelos de simulação pode oferecer vantagens quando é necessário: Estimar a distribuição de variáveis aleatórias; Testar hipóteses estatísticas; Comparar cenários representando diferentes soluções para o problema em estudo; Avaliar o comportamento de uma solução analítica; Avaliar um processo de tomadas de decisão em tempo real. Apesar das razões para se usar modelos de simulação parecerem claras, é a identificação do sistema/problema que leva à definição dos objetivos e do tipo de modelo e de estudo de simulação que deve ser desenvolvido. 2. Modelos de simulação 2.1. Introdução Os problemas que a indústria, serviços e organizações em geral enfrentam têm-se tornado de maiores dimensões e mais complexos, exigindo, cada vez mais, técnicas e procedimentos que ajudem no seu tratamento. Uma destas técnicas é a modelação e simulação de sistemas, cujo objetivo é representar o comportamento dos sistemas através de modelos matemáticos. A resolução de qualquer problema requer, em primeiro, que estes sejam bem definidos, ou seja, especificar com precisão suficiente os objetivos. Para tanto, é necessário um bom conhecimento do sistema em estudo para que se possa entender o problema sem qualquer tipo de dúvidas. A situação não é diferente quando se quer resolver problemas usando modelos de simulação. O sistema deve ser bem conhecido para que se possa detetar os problemas relacionados e traçar as metas a serem alcançadas. A simulação de sistemas pode ser dividida nas seguintes etapas básicas, também discutidas no âmbito da Investigação Operacional: Problema: identificação do problema apresentado pelo sistema em estudo, bem como das partes (sub-sistemas) que interferem no problema identificado (envolve recolha de amostras); - 4 -
9 Modelos de simulação Estudo do sistema: descrever o sistema em termos de componentes, atividades, entidades, eventos, restrições, propósitos que motivaram o uso da simulação para resolver o problema; Modelo: construção do modelo de representação do sistema em estudo, o qual precisa ser validado; Solução: realizar experiências sobre o modelo construído e utilizar as informações resultantes para propor soluções para o problema inicial; Operacionalizar solução: executar alterações no sistema real com base nos resultados da simulação; Realimentação: re-elaboração parcial do trabalho de acordo com os resultados obtidos na interferência sobre o sistema real. Etapas de um modelo de simulação Os objetivos essenciais do estudo das técnicas de simulação de sistemas concentram-se principalmente nas atividades de estudo do sistema real, na construção do modelo e na execução de experiências sobre o modelo Sistema Ao longo deste texto utilizou-se, ainda que de forma subjetiva, uma associação existente entre os conceitos de simulação, sistema e modelo. Simulação é um dos muitos métodos existentes para estudar e analisar sistemas. No caso da simulação computacional, são os modelos computacionais que são usados para estudar e analisar sistemas. Mas afinal, o que é um sistema e quais são os passíveis de serem modelados e analisados através da simulação? Para Taylor (Taylor, 1970), um sistema pode ser definido como um conjunto de objetos, como pessoas ou máquinas, por exemplo, que atuam e interagem com a intenção de alcançar um objetivo ou um objetivo lógico. São inúmeros os sistemas que podem ser resolvidos usando modelos de simulação. Alguns destes sistemas são os seguintes (apresentados por categorias): 1. Sistemas de produção: manufaturação e montagem; movimentação de peças e matéria prima; alocação de mão de obra; áreas de armazenamento; layout; etc
10 Modelos de simulação 2. Sistemas de transporte e gestão de stocks: redes de distribuição; armazéns e entrepostos; frotas; etc. 3. Sistemas computacionais: redes de computadores; redes de comunicação; servidores de redes; arquitetura de computadores; sistemas operativos; gestores de bases de dados; etc.. 4. Sistemas administrativos: seguradoras; operadores de crédito; agências financeiras; etc.. 5. Sistemas de prestação de serviços diretos ao público: hospitais; bancos; restauração; serviços de emergência (polícia, bombeiros etc..); serviços de assistência jurídica; etc.. De uma forma geral, os objetivos de um estudo específico sobre um sistema definem os objetos que devem constituir o modelo. Por exemplo, supondo que se pretende realizar um estudo sobre um supermercado. Se a entidade que pretende este estudo for um supervisor de caixas, possivelmente estará interessado em incluir no seu sistema, apenas os objetos do setor de atendimento nas caixas (subsistema) se o objetivo for pesquisar, por exemplo, a taxa de uso destes recursos, as filas que se formam ou qualidade dos serviços (considerando o tempo que um cliente leva para ser atendido). Por outro lado, se aquela entidade for um gestor de abastecimentos, deste mesmo supermercado, poderia estar interessado num estudo do setor (subsistema) correspondente à receção e armazenamento de mercadorias; neste caso, o conjunto de objetos do sistema em estudo deveria incluir o pessoal envolvido na receção, movimentação e armazenamento de produtos, os equipamentos utilizados, a disponibilidade de área de stocks, etc Modelo De modo geral, os modelos são utilizados para resolver problemas reais quando, para tal, isso implicaria custos elevados utilizando a via experimental ou muito complicados para tratamento analítico. A construção de um modelo pode visar encontrar a solução de um problema específico dentro de um sistema. Deste modo, pode existir um número variado de modelos para resolver um mesmo sistema, em que cada modelo respeita as características de um problema particular. Depois de definido um problema dentro de um sistema para o qual se pode construir um modelo, é necessário a existência de uma estrutura organizada para construir este modelo. Para tal, utilizase uma linguagem de simulação capaz de fornecer esta estrutura e permitir a tradução do modelo numa forma aceitável para o seu processamento no computador. Neste caso, o computador será utilizado para executar o modelo de forma a produzir saídas que possam ser analisadas, para que as decisões relacionadas com a resolução do problema possam ser implantadas. Com a ajuda de computadores é possível simular grande quantidade de eventos em curtos espaços de tempo. Através da execução de um modelo que representa um sistema, é possível fazer uma estimativa do comportamento futuro deste sistema. À execução de um modelo dá-se o nome de Simulação
11 Modelos de simulação De notar que a experimentação não se pode comparar à simulação. Enquanto que a experimentação é caracterizada por tentativas de mudanças no próprio sistema, a simulação é executada sobre uma representação do sistema. Para além disso, a experimentação pode ter um custo muito elevado, o que justifica, na maioria dos casos, a construção de modelos de simulação. Perante os resultados da execução de um modelo de simulação, são então realizadas análises de novas situações sobre as quais se tem pouco conhecimento, o que permite fornecer dados para a conceção de novas regras ou o ganho de experiência no projeto do próprio modelo. Os modelos devem também incorporar elementos reais de forma simples, mantendo uma relação custo x benefício coerente. Ou seja, deve-se evitar a construção de um modelo muito complexo que dificulte, ou mesmo impossibilite, a sua compreensão e manipulação. Deve-se também evitar a construção de modelos demasiado simples que não representem as propriedades desejáveis do sistema em estudo Cenários No contexto dos modelos de otimização, existem objetivos a serem alcançados pelo sistema que deve funcionar satisfazendo as restrições impostas pelo meio ambiente. Desta forma, a solução do problema em análise deve ser a que melhor atinge os objetivos entre as que satisfazem as restrições. A observação e o acompanhamento do comportamento do modelo, operando sobre uma determinada solução, são feitas para avaliar se as restrições estão sendo satisfeitas e se os objetivos estão sendo alcançados. É frequente uma solução para o problema poder representar uma configuração para o sistema ou uma política de operação do sistema. Assim, as diferentes alternativas de soluções do problema devem ser enumeradas para a definição dos cenários a serem avaliados durante as execuções da simulação. Pode acontecer que os cenários em comparação sejam tão distintos que sejam desenvolvidos dois ou mais programas para representa-los. Mesmo nestes casos considera-se que há um único modelo que seleciona o programa a ser executado de acordo com o cenário desejado Parâmetros do Modelo Os parâmetros do modelo definem o cenário de cada execução (simulação). Estes são controlados externamente pelo utilizador no início de cada execução e são constantes durante a simulação. Podem representar uma configuração específica para o sistema ou uma determinada política de operação do sistema. Podem também ser sementes de inicialização dos geradores de variáveis (aleatórias) independentes. Entre estes parâmetros estão a quantidade e a distribuição da procura do serviço, os algoritmos de escalonamento, o número médio de vezes que um cliente visita um dispositivo, o número de clientes num sistema fechado e a distribuição do tempo entre chegadas de clientes num sistema - 7 -
12 Modelos de simulação aberto. Alguns destes parâmetros caracterizam a carga do sistema, como seja, a distribuição do tempo entre chegadas de clientes. Pode-se dizer que a capacidade mais importante do modelador é a perceção de como o sistema se comporta, a capacidade de estimar o conjunto inicial de parâmetros do sistema e a capacidade de realizar análises de modificação dos parâmetros com precisão. 3. Propriedades dos modelos de simulação 3.1. Introdução A utilidade de um modelo está diretamente relacionada com a sua capacidade de incorporar elementos reais de forma simples. No entanto, um modelo deve conter os aspectos importantes do sistema real, sem que sua complexidade impossibilite a compreensão e manipulação do mesmo. Essa característica pode ser difícil de ser alcançada, pois modelos realistas raramente são simples, e modelos simples raramente são realistas. No que se refere aos modelos matemáticos para simulação em computadores, estes são constituídos por 4 elementos: componentes, variáveis, parâmetros e relações funcionais Elementos de um modelo de simulação Os componentes representam a parte do modelo de simulaçao sobre a qual são realizados os estudos. Os componentes dos modelos tendem a variar muito, dependendo do sistema que está sendo simulado. Por exemplo, num sistema de gestão de redes, podem ser considerados como componentes os objetos geridos, os agentes de gestão e as aplicações geridas. As variáveis são utilizadas nos modelos de simulação para relacionar os componente entre si. Dependendo da finalidade de uma simulação, uma variável pode ser classificada como: exógena, de estado e endógena. As variáveis exógenas são as variáveis independentes ou de entrada do modelo. São consideradas como tendo sido previamente determinadas e fornecidas, independentemente do sistema sobre o qual está sendo construído o modelo. Desta forma, estas variáveis podem ser vistas como atuantes sobre o modelo, mas não influenciadas por ele (a direção causa-efeito ocorre apenas no sentido variável exógena --> sistema). As variáveis exógenas podem ser classificadas como controláveis e não controláveis. As variáveis controláveis são as variáveis que podem ser manipuladas ou controladas pelas entidades incumbidas da decisão ou de estabelecer o programa de ação em relação ao sistema. Variáveis não controláveis são geradas pelas circunstâncias nas quais o sistema modelado existe, e não pelo próprio sistema ou pelas entidades incumbidas das decisões relativas a elas
13 Propriedades dos modelos de simulação As variáveis exógenas controláveis são tratadas como parâmetros. Estes parâmetros devem ser determinados pelas condições do problema ou pelas entidades encarregues da decisão. Tais condições ou entidades devem ser previamente lidos pelo computador como dados de entrada, ou geradas internamente se forem variáveis estocásticas (através de métodos pré-definidos). As variáveis de estado descrevem o estado de um sistema ou de um de seus componentes, quer no início de um determinado período de tempo, quer no seu término, ou ainda durante o decorrer de um certo período. Estas variáveis interagem com as variáveis exógenas e endógenas, de acordo com as relações funcionais previamente estabelecidas. O valor das variáveis de estado durante um determinado período de tempo pode depender do valor de variáveis exógenas de um período de tempo anterior e de variáveis de saída de períodos precedentes. Quando um componente utiliza na sua entrada parte da sua saída ocorre um "loop" no modelo. Estes "loops" podem ser utilizados para introduzir atrasos na simulação. Num sistema de gestão de redes, as variáveis de estado podem incluir o número de pedidos na fila, resultado de uma operação de gestão ou número de objetos selecionados. As variáveis endógenas são as dependentes ou de saída do sistema. São geradas pela interação das variáveis exógenas e de estado, de acordo com as características operacionais do sistema. Num sistema de gestão de redes, as variáveis endógenas são a média de operações realizadas com sucesso ou o conjunto de informações resultante da ocorrência de eventos nos objetos geridos. As relações funcionais que descrevem as interações das variáveis com os componentes de um modelo são duplas: identidades e características operacionais. Ambas são usadas para gerar o comportamento do sistema. As identidades podem tomar a forma de definições ou de proposições redundantes relativas aos componentes do modelo. Para um sistema de gestão, a métrica do tráfego entre uma estação servidor e um recurso remoto pode ser considerado um exemplo de relação funcional. Uma característica operacional é uma hipótese, geralmente uma equação matemática que relaciona as variáveis endógenas e de estado de um sistema com suas variáveis exógenas. Ao contrário dos componentes e das variáveis que podem ser diretamente observados no sistema real, os parâmetros das características operacionais apenas podem ser obtidos através da inferência estatística. 4. Classificação dos modelos de Simulação Existem diferentes classificações propostas para os modelos de simulação. Neste documento, os modelos de simulação são classificados em três grupos: determinísticos ou estocásticos, estáticos ou dinâmicos, e discretos ou contínuos. Desta forma, um modelo pode ser estocástico, dinâmico e discreto. Um exemplo com estas careterísticas são os modelos de simulação discretos
14 Classificação dos modelos de Simulação 4.1. Modelos determinísticos e estocásticos Nos modelos determinísticos não é permite às variáveis exógenas e endógenas serem variáveis aleatórias. Além disso, as características operacionais devem ser relações exatas e não funções de densidade de probabilidade. Os modelos determinísticos são computacionalmente menos exigentes do que os modelos estocásticos. Estes modelos podem geralmente ser resolvidos usando técnicas como a do cálculo de máximos e mínimos (técnica analítica). Em resumo, os métodos analíticos são mais eficientes do que os métodos de simulação, quando aplicados na resolução de problemas determinísticos. Os modelos são estocásticos quando pelo menos uma das características operacionais é dada por uma função de probabilidade. Geralmente são mais complexos que os modelos determinísticos. Deste modo, a simulação é mais adequada como método de análise e solução para os modelos estocásticos. Estes modelos são adequados à geração aleatória de dados para serem utilizados nas fases de observação ou de testes Modelos estáticos e dinâmicos Os modelos estáticos não consideram a variável de tempo. Geralmente a maioria dos trabalhos nas áreas da programação linear, não linear e na teoria dos jogos, têm sido relacionadas com modelos estáticos. No entanto, o uso de modelos de simulação pode não ser recomendado pelo facto da maioria dos modelos estáticos serem completamente determinísticos. Assim, as soluções podem normalmente ser obtidas por técnicas analíticas diretas. Os modelos matemáticos que tratam de interações variáveis com o tempo são chamados modelos dinâmicos (ocorrência de uma ordem termporal entre eventos) Modelos contínuos e discretos Um sistema pode ser modelado através de um modelo de mudança discreta (ou discreto) ou de um modelo de mudança contínua (ou contínuo). O tempo é a principal variável independente num modelo de simulação dinâmico. As restantes variáveis de estado podem ser consideradas como funções do tempo, portanto como variáveis dependentes. As variáveis de estado do sistema são classificadas de acordo com os valores que tomam ao longo da simulação. Os modelos dinâmicos são classificados de acordo com os instantes de tempo em que as variáveis de estado têm os seus valores alterados. Um modelo é discreto se todas as variáveis de estado têm os seus valores alterados apenas num número contável de instantes de tempo. Um modelo discreto é aquele em que as variáveis dependentes variam discretamente em pontos específicos do tempo simulado, referidos como tempo de evento. A variável tempo pode ser contínua ou discreta em tais modelos, dependendo se
15 Classificação dos modelos de Simulação as mudanças discretas nas variáveis dependentes podem ocorrer em qualquer ponto do tempo real ou unicamente em pontos predeterminados. Variável dependente num modelo discreto Um modelo é contínuo se todas as variáveis de estado têm os seus valores alterados a qualquer instante de tempo. Um modelo contínuo é aquele em que as variáveis dependentes podem variar continuamente ao longo do tempo simulado. Um modelo contínuo pode ser contínuo no tempo ou discreto no tempo, dependendo se os valores das variáveis dependentes estão sempre disponíveis em qualquer ponto do tempo simulado, ou apenas em pontos específicos. Variável dependente num modelo contínuo com tempo contínuo Variável dependente num modelo contínuo com tempo discreto
16 Classificação dos modelos de Simulação Algumas vezes pode ser útil modelar um sistema discreto como um modelo contínuo, considerando as entidades do sistema como um agregado e não como entidades individuais. Um exemplo de tal conveniência é a análise do movimento das partículas de um gás. Um modelo é misto se algumas variáveis de estado têm os seus valores alterados a qualquer instante de tempo e outras apenas num número contável de instantes de tempo. Um modelo misto é aquele em que as variáveis dependentes podem variar discretamente, continuamente, ou continuamente com saltos discretos superpostos. A variável tempo pode ser discreta ou contínua. O aspecto mais importante de uma simulação mista surge nas mudanças de variações discretas para contínuas e vice-versa. Uma linguagem de simulação mista deve conter meios de detetar tais ocorrências e modelar as suas consequências. Modelo misto Em resumo, chama-se simulação discreta à execução de um modelo de simulação discreto. Da mesma forma, chama-se simulação contínua à execução de um modelo de simulação contínuo. E, de simulação mista à execução de um modelo misto. 5. Modelos de simulação dinâmicos discretos 5.1. Componentes de um modelo de simulação Os modelos de simulação discretos (ou apenas simulação discreta), é um método de modelação da evolução de um sistema com o tempo, em que as variáveis de estado mudam instantaneamente em instantes particulares (discretos) de tempo. Os componentes de um modelo de simulação são os seguintes: - Entidade: é um objeto de interesse do sistema (exemplos: clientes numa fila de espera, máquinas num sistema de produção, etc.). - Atributo: são as propriedades de uma entidade, pois existem vários tipos e cada uma com as suas propriedades (exemplos: tipos de prioridades dos clientes numa fila de espera, velocidade das máquinas e sua capacidade, taxas de avaria, etc.)
17 - Atividade: representa um determinado período de tempo com duração específica, onde se verifica o desenvolvimento de um processo que utiliza recursos (exemplo: fazer depósitos numa agência bancária, soldar e perfurar num sistema produtivo, etc.). - Estado do sistema: é o conjunto de variáveis necessárias para descrever o sistema em qualquer instante, as quais estão relacionadas com o objetivo do estudo (exemplos: número de servidores ocupados ou desocupados, número de clientes à espera para serem atendidos, número de máquinas em funcionamento, paradas ou avariadas, etc.). - Evento/Acontecimento: é uma ocorrência instantânea que altera o estado do sistema (exemplos: chegada de um cliente, o terminar do serviço de um utente, uma nova avaria numa das máquinas, etc.). Os acontecimentos podem ser exógenos, no caso de terem origem fora do sistema, e endógenos, caso contrário. - Executivo: trata-se de um mecanismo existente na estrutura de qualquer programa de simulação, que permite manter permanentemente atualizada a informação sobre as entidades. Em particular, permite conhecer em cada instante qual o estado da entidade e por quanto tempo é que esta permanece naquele estado. Exemplo: serviço de atendimento com um servidor objectivo do estudo: - estimar o tempo médio de espera na fila; entidades: - cliente, - servidor; variáveis de estado: - estado do servidor (livre ou ocupado), - número de clientes na fila à espera de atendimento, - instante de chegada de cada cliente ao sistema, - instante de partida de um cliente após ser atendido; eventos/acontecimentos: chegada de um cliente, partida de um cliente (no fim do serviço). O objetivo de um modelo de simulação discreto é reproduzir as atividades das entidades envolvidas no sistema e, a partir daí, conhecer algo sobre o comportamento e desempenho do sistema. Isto é conseguido quando se definem os estados do sistema e se constroem as atividades que o movem de um estado para outro. O estado de um sistema é definido em termos de valores numéricos dados aos atributos das entidades. Um sistema está em determinado estado, quando todas as suas entidades estão em estados consonantes com o domínio dos valores dos atributos que definem aquele estado
18 Em simulação discreta, o estado do sistema só pode mudar nos tempos de eventos. Uma vez que o estado do sistema permanece constante entre tempos de eventos, uma descrição completa do estado do sistema pode ser obtida avançando o tempo simulado de um evento para outro. Este mecanismo é usado na maioria das linguagens para simulação discreta. Como os modelos de simulação discreta são dinâmicos, é necessário manter um registo do tempo simulado ao longo da simulação e um mecanismo para avançar o tempo de um instante para outro. O relógio de simulação é a variável de um modelo de simulação que regista o valor actual do tempo simulado. O relógio de simulação não tem uma unidade explícita (usa a mesma unidade dos parâmetros de entrada). O tempo simulado é diferente, quer do tempo de computador de execução da simulação, quer do tempo real. Relações entre evento, processo e atividade Tipos de modelação A formulação de um modelo de simulação discreta pode ser realizada de três formas: - pela definição das mudanças nos estados que podem ocorrer em cada tempo de evento; - pela descrição das atividades nas quais as entidades do sistema se envolvem e; - pela descrição do processo através do qual as entidades do sistema fluem. Um evento acontece num ponto isolado do tempo, no qual devem ser tomadas decisões de forma a iniciar ou terminar um atividade. Um processo é uma sequência ordenada de eventos e pode englobar várias atividades. Estes conceitos levam naturalmente a três alternativas de visão de um modelo de simulação discreto: - modelação orientada ao Evento; - modelação orientada à Atividade; - modelação orientada oa Processo
19 Modelação orientada ao Evento: Um sistema é modelado pela definição das mudanças que ocorrem no tempo de evento. A tarefa do modelador é determinar os eventos que podem causar a mudança no estado do sistema e desenvolver a lógica associada com cada tipo de evento. A simulação do sistema é produzida pela execução da lógica associada a cada evento, numa sequência ordenada no tempo. É este tipo de modelação que será estudado com mais detalhe neste documento. Modelação orientada à Atividade: O modelador descreve as atividades nas quais as entidades do sistema estão envolvidas e estabelece as condições que causam o início e o fim de uma atividade. Os eventos que iniciam ou terminam uma atividade não são escalonados pelo modelador, mas iniciados a partir das condições especificadas para a atividade. À medida que o tempo simulado avança, as condições de início ou fim de uma atividade são examinadas. Para se assegurar que cada atividade é levada em consideração, é necessário examinar todo o conjunto de atividades a cada avanço do tempo. Modelação orientada ao Processo: Muitas estruturas de modelos de simulação incluem sequências de eventos, as quais ocorrem em padrões definidos; por exemplo, uma fila de entidades à espera de um servidor. A lógica associada a tal sequência de eventos pode ser generalizada e definida por uma única afirmação. Uma linguagem para simulação pode então traduzir tal afirmação na sequência de eventos associada. Uma linguagem orientada ao processo emprega tais afirmações para modelar o fluxo das entidades no sistema. Estas afirmações definem uma sequência de eventos que é automaticamente executada pela linguagem de simulação Modelação orientada ao Evento Existem dois métodos possíveis para avançar o tempo no sistema a ser simulado: avanço por incremento de tempo fixo (fixed increment) e avanço para o próximo evento (next event). No método avanço por incremento de tempo fixo, um relógio virtual existente no computador permite registar o tempo instante a instante, mantendo a sequência correta dos acontecimentos. O tempo é atualizado por intervalos discretos uniformes (minutos, segundos, etc.), sendo o sistema observado em cada instante, de forma a saber se existe algum evento para ter início
20 No método de avanço para o próximo evento, o avanço é por tempo variável, uma vez que é concretizado através dos instantes em que se verificam os acontecimentos. Não se analisa o período durante o qual se executa a simulação instante a instante. 1. o relógio é inicializado a zero e são determinados os instantes dos eventos futuros; 2. o relógio é avançado para o instante do próximo evento a ocorrer; 3. o estado do sistema é atualizado de acordo com esse evento e são determinados os instantes de novos eventos; 4. os passos 2 e 3 são repetidos, até se cumprir uma condição de paragem pre-estabelecida. Exemplo: sistema de atendimento com um servidor (o método de avanço para o próximo evento) - t i = tempo de chegada do cliente i (t 0 = 0) - A i = t i t i-1 = tempo entre chegadas dos clientes i-1 e i - S i = tempo de atendimento do cliente i no servidor - D i = tempo de espera do cliente i na fila - c i = t i + D i + S i = tempo de partida do cliente i - e k = tempo do k-ésimo evento de qualquer tipo (chegada ou partida) A utilização do método de avanço por incremento de tempo fixo é, em geral, mais eficiente se os acontecimentos ocorrem de forma regular ou se não forem bem conhecidos (por exemplo, em sistemas complexos no controlo ou em fases iniciais de estudos de simulação). O método de avanço para o próximo evento, em contrapartida, tem a virtude da duração designada para a unidade de tempo não afetar a velocidade de computação, o que permite poupar tempo na execução do modelo. A escolha de um ou de outro depende da natureza do sistema a ser modelado e simulado. No entanto, verifica-se que a eficiência do primeiro método aumenta com o incremento do número das variáveis de estado, e da segundo, com a duração temporal média dos acontecimentos. Considere-se como exemplo um balcão de atendimento ao público. O objetivo do estudo deste sistema é estimar o número médio de clientes na fila, o tempo de espera médio dos clientes na fila e a percentagem de tempo de ocupação do servidor. Para tal, foram recolhidos dados (amostras)
21 relativos ao intervalo de tempo entre chegadas e à duração dos serviços, os quais estão sintetizados na tabela seguinte. Tempos entre chegadas (minutos) Frequência (%) Tempos de serviço (minutos) Frequência (%) Os Componentes do modelo de simulação são os seguintes: Entidades: clientes que chegam ao sistema para serem atendidos; Atributos: a disciplina da fila de espera admite-se ser FIFO (first in first out) Atividades: tempo de espera na fila, tempo despendido no sistema e tempo de serviço, geridos através das duas distribuições empíricas caracterizadas na tabela anterior; Estado do sistema: situação do servidor (ocupado ou livre), número de clientes na fila e número de clientes no sistema; Eventos: chegada de um cliente e partida após conclusão do serviço de um cliente específico. Os tempos entre chegadas e de serviços podem ser determinados através de processos comuns de amostragem. Para tal, geram-se números com igual probabilidade de escolha e independentes entre si (pseudoaleatórios). A tabela seguinte apresenta os resultados obtidos. Intervalo dos números pseudoaleatórios Tempos entre chegadas (minutos) Intervalo dos números pseudoaleatórios Tempos de serviço (minutos) Os resultados da simulação são os que constam na tabela seguinte: Número pseudoaleatório Intervalo de tempo entre chegadas (minutos) Tempo acumulado (minutos) Número pseudoaleatório Tempo de serviço (minutos) Tempo de conclusão de serviço (minutos) Tempo de espera (minutos) Tempos de disponibilidade do servidor (minutos)
22 O método de simulação utilizado é o de avanço para o próximo evento, pois o incremento é aquele onde se verificam eventos instantâneos com relevância (chegada de um cliente e o terminar do serviço de um clente). A tabela seguinte apresenta a evolução dos eventos. Relógio de simulação Evento Cliente Próxima chegada Fila Estado do servidor Próxima saída Tempo livre do servidor Tempo de espera Fila live 0-4 chegada ocupado (1) chegada partida 1-0 ocupado (2) chegada partida 2-0 ocupado (3) chegada partida 3-0 ocupado (4) chegada partida 4-0 ocupado (5) chegada partida 5-0 ocupado (6) chegada partida 6-0 ocupado (7) partida livre - - Atendendo aos objetivos do estudo, os valores estimados são os seguintes: - número médio de clientes na fila: 5/7 = 0.71 (71%) - tempo médio de espera dos clientes na fila: 16/7 = 2.3 minutos/cliente - percentagem de tempo de ocupação do servidor: (31-4)/31 = 27/31 = 0.87 (87%) 5.4. Desenvolvimento de um projeto de simulação O processo de construção de modelos que representam sistemas reais pode ser estruturado por uma sequência de etapas de forma a simplificar, agilizar e melhorar a fidelidade do modelo. A lista que a seguir se apresenta é clássica, isto é, quase todos os livros e trabalhos gerais sobre como proceder para solucionar um problema usando um processo de modelação e simulação do sistema é apresentada como se segue
23 Formulação do problema. Qualquer estudo de modelação e simulação deve iniciar-se pela formulação (depois da idenfificação) do problema que se pretende analisar. A compreensão total da situação, seja ela enumerada pelo cliente ou pelo analista, exige da parte do cliente um acordo e um entendimento completo da formulação proposta. Nesta fase, deverão ser preparadas um conjunto de hipóteses iniciais que terão de ser aceites pelo cliente. Mesmo assim, acontece com muita frequência o problema necessitar de ser reformulado durante o processo de desenvolvimento. Esta fase é das mais importantes do processo, pois irá condicionar todas as restantes atividades. A explicação sem
24 ambiguidade da situação é crucial, sob pena de se vir a chegar a uma solução que não corresponda à solução do problema real em avaliação Definição dos objetivos. Os objetivos devem ser indicados pelo conjunto de questões que deverão ser respondidas pelo estudo do processo. Os objetivos deverão ser precisos, razoáveis, compreensíveis, mensuráveis e orientados para a ação, permitindo distinguir o essencial do secundário. Se a definição dos objetivos é vaga, normalmente conduz a sucessos pouco claros. São os objetivos que explicitam os focos do projeto e, em último lugar, permitirão verificar o grau de sucesso deste. Para a definição dos objetivos, devem ser respondidas questões do tipo: a) por que o problema está a ser estudado? b) quais serão as respostas que o estudo espera alcançar? c) quais são os critérios para avaliação do rendimento do sistema? d) quais são as hipóteses e prerrogativas? e) que restrições e limites são esperados das soluções obtidas? Planeamento do projeto. No planeamento do projeto pretende-se ter a certeza de que se possuem recursos suficientes no que diz respeito a pessoal, suporte, gestão, hardware e software para realização do trabalho proposto. Além disso, o planeamento deve incluir uma descrição dos vários cenários que serão investigados e um cronograma temporal das atividades que serão desenvolvidas, indicando os custos e necessidades relativas aos recursos anteriormente citados Construção do modelo. O sistema real em análise é traduzido num modelo matemático, constituído por um conjunto de relações matemáticas e lógicas, de acordo com os componentes e a estrutura do sistema. O modelo construído consiste de uma descrição estática e de uma dinâmica. A descrição estática define os elementos do sistema e as suas características. A dinâmica define o modo como os elementos do sistema interagem causando mudanças no estado do sistema no decorrer do tempo. O modelador deve conhecer bem a estrutura e as regras de operação do sistema e saber extrair o essencial do sistema, sem incluir detalhes desnecessários. A quantidade de detalhes incluída no modelo deve ser baseada nos objetivos para o quais foi construído. Na construção do modelo deve-se traçar um esboço do sistema, de forma gráfica (fluxograma, por exemplo) ou algorítmica (pseudocódigo), definindo os componentes, descrevendo as variáveis e a interações lógicas que constituem o sistema. É recomendado que o modelo se inicie de forma simplificada e vá crescendo até alcançar algo mais complexo, contemplando todas as suas peculiaridades e características. O utilizador deve participar intensamente desta etapa
25 Recolha de informação. O aspeto mais complexo dos dado de entrada necessários para modelar um sistema é a recolha de dados em quantidade, qualidade e variedade, de forma a se desenvolver uma análise razoável. Em muitos casos é mesmo impossível ou muito difícil realizar esta tarefa, já que, por exemplo, poder-se-á estar a modelar um sistema original. Noutros casos, não existe tempo suficiente ou mãode-obra disponível para se conseguir uma recolha de informação extensiva. Os dados de entrada do sistema a simular são, normalmente, dados já existentes e não preparados especialmente para este fim. De salientar que, na maioria dos casos, os dados representam uma amostra do que pode ser utilizado ou do que existe disponível. Ao se afirmar que os dados são representativos, significa que são expressivos de uma população que apresenta uma certa regularidade ao longo do tempo, devendo a amostra refletir esta situação. Geralmente os dados de entrada são valores hipotéticos ou baseados em alguma análise preliminar, e dependem do objetivo do modelo. Estes dados são factos, informações e estatísticas fundamentais, que derivam de observações, experiências pessoais ou de arquivos históricos Implementação do modelo. O modelo de simulação construído é então codificado usando um qualquer linguagem de programação, seja ela imperativa ou de simulação; isto é, é construído o modelo implementado Verificação. Esta fase consiste em determinar se o modelo implementado reflete de forma adequada o modelo de simulação construído. Para tal, deve-se verificar se os resultados obtidos pela execução no computador são os esperados. Recomenda-se que a verificação seja efetuada de forma continuada, não sendo boa opção concluir a implementação do modelo sem se inicar a verificação Validação. A validação de um modelo é o processo que permite verificar, tendo em atenção os objetivos específicos do estudo, se o modelo de simulação e uma representação ajustada do sistema. Se o modelo é válido, em termos conceptuais, então poderá ser utilizado como suporte à tomada de decisões sobre o sistema. A maior ou menor facilidade da validação depende da complexidade do sistema e da sua real existência. De salientar que um modelo de simulação é construído para um fim específico e se é válido para este poderá não o ser para qualquer outro; ou seja, a sua validade é verificada para um conjunto de dados de entrada dentro de um determinado domínio, e não para valores fora dele. As medidas de desempenho utilizadas para validar o modelo deverão ser as mesmas que são utilizadas pelo decisor para avaliar o sistema, devendo haver a preocupação de quem desenvolve o
26 modelo de o avaliar ao longo de todo o processo de construção, não adiando este processo apenas para uma fase posterior à conclusão do modelo. Existe um conjunto de processos de natureza prática para se realizar uma conveniente validação de um modelo de simulação. Este conjunto pode ser dividido em duas categorias: a primeira inclui as designadas técnicas subjetivas e a segunda os processos formais. De entre as primeiras estão: a) validação em face: o modelo de simulação e o sistema real devem-se assemelhar face ao conhecimento que se tem do funcionamento do sistema; b) análise de sensibilidade: a variação dos valores de entrada deverá provocar mudanças nos resultados que sejam concordantes com uma alteração previsível; para tal, são utilizados cenários em que o comportamento real é conhecido previamente e que pode ser comparado com o comportamento obtido com a simulação; c) testes para condições extremas: o modelo deverá responder de forma adequada quando os valores de entrada se alteram para valores extremos; d) validação relativa às hipóteses do modelo de simulação: existem, para este caso, duas subcategorias de hipóteses: as estruturais (relacionadas com o funcionamento do sistema) e as ligadas aos dados. As técnicas formais incluem a validação das transformações de entrada-saída e utilizando dados históricos de entrada. O princípio básico da primeira reside na comparação dos valores de saída do modelo imlementado com aquele obtido no sistema real; neste processo são utilizados com frequência testes que permitem comparar valores médios ou outros parâmetros estatísticos. No segundo caso, em vez de se executar o modelo implementado com valores artificiais, utilizam-se dados do sistema recolhidos em períodos históricos; é de esperar que os resultados obtidos pelo modelo implementado sejam estatisticamente próximos dos observados no sistema real; esta comparação é realizada através de testes estatísticos. Após o modelo ser validado torna-se necessário necessário adaptá-lo a determinadas condições de funcionamento (realizar a calibração). A calibração do modelo é um passo significativo que ocorre normalmente entre o final da validação e o início da simulação Desenho de experiências. Os pontos a serem incluídos nesta fase são: a definição os cenários a serem simulados, o conjunto de decisões relativas à dimensão do período de simulação, o número de réplicas e as condições iniciais Execução do modelo e análise dos resultados. A execução do modelo e a análise dos resultados obtidos permitirá estimar as medidas de desempenho para o conjunto de cenários estabelecido
27 Mais execuções do modelo? A partir dos resultados obtidos através da execução do modelo já realizada, o analista poderá concluir que serão ainda insuficientes ou eventualmente ser aconselhável explorar novos cenários Documentação e relatório. Existem dois tipos de documentos a considerar: o primeiro relativo ao programa e o segundo inclui os designados por relatórios de progresso. A documentação relativa à programação é importante, pois o programa pode vir a ser utilizado posteriormente pelo analista ou por alguém diferente; desta forma, torna-se porventura necessário conhecer a forma de operar o programa. A existência de relatórios de progresso é importante, já que traduzem a história escrita do desenvolvimento do projeto; esta poderá revelar a cronologia do trabalho concretizado, das decisões tomadas, o que funcionou e não funcionou, etc Implementação da solução. O sucesso desta fase depende da forma como os passos anteriores foram concretizados. Assim como o grau de envolvimento do utilizador final ao longo de todo o processo, é um factor de sucesso. Se os resultados do sistema virem a ser melhorados pelos resultados obtidos no modelo de simulação, o projeto poderá ser considerado um sucesso Implementação/codificação de um modelo de simulação discreta Na fase de implementação do modelo de simulação é necessário ter em conta duas entidades importantes: as variáveis e as rotinas associadas ao modelo. Para além das variáveis já referidas, - estado do sistema: conjunto de variáveis que descrevem o estado do sistema num instante de tempo, e - relógio de simulação: variável que regista o instante atual do tempo simulado, existem, pelo menos, mais duas: - lista de eventos: lista com os próximos instantes de tempo em que cada tipo de evento vai ocorrer, e - contadores estatísticos: variáveis que guardam informação estatística, recolhida ao longo da simulação, sobre o desempenho do sistema. As rotinas necessárias são, pelo menos, as seguintes: rotina de inicialização: subprograma que inicializa o estado do sistema no instante 0 rotina de gestão de tempo: subprograma que determina o próximo evento da lista de eventos e avança o relógio de simulação rotinas dos eventos: subprogramas (um por tipo de evento) que actualizam o estado do sistema quando ocorre um evento
28 biblioteca de rotinas: conjunto de subprogramas que geram observações aleatórias das distribuições de probabilidade que são utilizadas pelo modelo gerador de relatórios: subprograma que calcula no fim da simulação (a partir dos contadores estatísticos) medidas de desempenho do sistema e produz um relatório programa principal: subprograma que chama a rotina de gestão de tempo e passa o controlo para a correspondente rotina do evento; este programa também verifica as condições de paragem e chama o gerador de relatórios no fim da simulação. Um possível algoritmo associado à implementação do modelo de simulação é o seguinte: 5.6. Exemplo 1 Enunciado do problema: Serviço de atendimento de clientes com apenas um servidor. Funcionamento do sistema (uma barbearia): os clientes chegam à barbearia e esperam numa cadeira se o barbeiro estiver ocupado; o barbeiro serve os clientes por ordem de chegada; - o cliente abandona a barbearia após o corte de cabelo terminar;
29 Dados de entrada para a simulação do sistema (inputs): instantes de chegada dos clientes ao sistema tempo de duração do serviço de cada cliente Número de cliente Instantes de chegada (min) Tempos de serviço (min) Objetivos: - simular este sistema até todos os clientes serem atendidos - calcular as seguintes medidas de desempenho (outputs): - tempo médio de permanência dos clientes no sistema - tempo médio de espera dos clientes - número médio de clientes no sistema - número médio de clientes em espera - taxa de ocupação do servidor Construção do modelo de simulação: eventos: evento de chegada e evento de partida; variáveis de estado: número de cliente, fila de espera (FIFO), número de clientes na fila, tipo de evento e estado do servidor (ocupado ou livre); lista de eventos: próximo evento de chegada (tempo) e próximo evento de partida (tempo); contadores estatísticos: tempo de permanência dos clientes no sistema, tempo de espera dos clientes na fila, número de clientes que passaram pelo sistema, número de clientes que passaram pela fila e tempo de ocupação do servidor (barbeiro)
30 Algoritmo (eventos): 5.7. Exemplo 2 Enunciado do problema: Serviço de atendimento de clientes com dois servidores. Funcionamento do sistema (agência de viagens): - dois agentes trabalham em paralelo no balcão de uma agência de viagens - os clientes, ao chegarem, formam uma única fila à espera do primeiro agente livre - se ambos os agentes estiverem livres, o cliente escolhe o Agente 1. Dados de entrada para a simulação do sistema (inputs): tempos entre chegadas: - os tempos entre chegadas de clientes seguem uma distribuição exponencial negativa com valor esperado de 2.0 minutos; - estes tempos podem ser gerados a partir de números aleatórios uniformes entre 0 e 1 com a seguinte fórmula: x = µ*ln(1-r), onde r~u(0, 1) e µ é o valor esperado;
31 - tempos de serviço: - os tempos médios de serviço são iguais para os dois agentes; - os tempos de serviço têm duas parcelas: um tempo constante de 1 minuto para o contacto inicial e um tempo variável uniforme entre 0.5 e 2.0 minutos; - para gerar valores aleatórios uniformemente distribuídos entre A e B pode usar a fórmula: x = A+(B-A)*r, onde r~u(0, 1), A é o limite inferior e B o limite superior Objetivos: - simular o sistema até todos os clientes serem atendidos - calcular as seguintes medidas de desempenho (outputs): - taxa de ocupação de tempo dos dois agentes - tempo médio de espera dos clientes - tempo médio de permanência dos clientes no sistema - número médio de clientes que passaram pela fila de espera - número médio de clientes que passaram pelo sistema (que foram atendidos) Construção do modelo de simulação (estruturas de dados): Variáveis de estado do sistema - Tipo de evento (chegada, partida1 ou partida2 TipoEvento) - Número do cliente (inteiro - NumCliente) - Estado do Agente 1 (ocupado ou livre - EstadoAgente1) - Estado do Agente 2 (ocupado ou livre - EstadoAgente2) - Fila de espera de clientes com os tempos de chegada (fila reais FilaEventosChegada) Relógio de simulação - Relógio de simulação (real - Clock) Lista de eventos - Tempo do próximo evento de chegada (real - TempoProximaChegada) - Tempo de partida do cliente no Agente 1 (real - TempoPartida1) - Tempo de partida do cliente no Agente 2 (real - TempoPartida2) Contadores estatísticos - Tempo total de espera dos clientes (real - TempoTotalEspera) - Tempo de ocupação do Agente 1 (real - TempoOcupacaoAgente1) - Tempo de ocupação do Agente 2 (real - TempoOcupacaoAgente2) - Tempo total de permanência dos clientes no sistema (real - TempoTotalPermanencia) - Número de clientes que passaram pelo sistema (inteiro NumClientesSistema) - Número total de clientes que passaram pela fila de espera (inteiro - TotalClientesFila)
32 Algoritmo: Rotina de inicialização (T0): NumClientesSistema 0 EstadoAgente1 livre EstadoAgente2 livre FilaEventosChegada [] Clock 0.0 TempoProximaChegada T0 TempoPartida1 TempoPartida2 TempoTotalEspera 0 TempoOcupacaoAgente1 0 TempoOcupacaoAgente2 0 TempoTotalPermanencia 0 TotalClientesFila 0 Rotina de gestão de tempo (TempoProximaChegada, TempoPartida1, TempoPartida2): Devolve o mínimo de { TempoProximaChegada, TempoPartida1, TempoPartida2 } Devolve o tipo de evento que lhe está associado (chegada, partida1 ou partida2) Rotinas de eventos: Evento de Chegada (Tempo) Marcar próximo evento de chegada (consultar sequência de instantes de chegada): TempoEntreChegadas consultar sequência de valores respetiva TempoProximaChegada Tempo + TempoEntreChegadas Se (EstadoAgente1 = ocupado) Então Se (EstadoAgente2 = ocupado) Então FilaEventosChegada Inserir(Tempo, FilaEventosChegada) TotalClientesFila TotalClientesFila + 1 Senão NumClientesSistema NumClientesSistema + 1 EstadoAgente2 ocupado TempoServico consultar sequência de valores respetiva TempoPartida2 Tempo + TempoServico (Marcar evento de partida deste cliente) TempoOcupacaoAgente2 TempoOcupacaoAgente2 + TempoServico TempoTotalPermanencia TempoTotalPermanencia + TempoServico Fim_Se
33 Senão NumClientesSistema NumClientesSistema + 1 EstadoAgente1 ocupado TempoServico consultar sequência de valores respetiva TempoPartida1 Tempo + TempoServico (Marcar evento de partida deste cliente) TempoOcupacaoAgente1 TempoOcupacaoAgente1 + TempoServico TempoTotalPermanencia TempoTotalPermanencia + TempoServico Fim_Se Evento de Partida 1 (Tempo) Se (FilaEventosChegada = []) Então EstadoAgente1 livre TempoPartida1 Senão TempoChegadaCliente Frente(FilaEventosChegada) TempoEsperaCliente Tempo - TempoChegadaCliente NumClientesSistema NumClientesSistema + 1 TempoServico consultar sequência de valores respetiva TempoPartida1 Tempo + TempoServico (Marcar evento de partida deste cliente) FilaEventosChegada Remover(FilaEventosChegada) TempoTotalEspera TempoTotalEspera + TempoEsperaCliente TempoOcupacaoAgente1 TempoOcupacaoAgente1 + TempoServico TempoTotalPermanencia TempoTotalPermanencia + TempoServico + TempoEsperaCliente Fim_Se Evento de Partida 2 (Tempo) Se (FilaEventosChegada = []) Então EstadoAgente2 livre TempoPartida2 Senão TempoChegadaCliente Frente(FilaEventosChegada) TempoEsperaCliente Tempo - TempoChegadaCliente NumClientesSistema NumClientesSistema + 1 TempoServico consultar sequência de valores respetiva TempoPartida2 Tempo + TempoServico (Marcar evento de partida deste cliente) FilaEventosChegada Remover(FilaEventosChegada) TempoTotalEspera TempoTotalEspera + TempoEsperaCliente
34 TempoOcupacaoAgente2 TempoOcupacaoAgente2 + TempoServico TempoTotalPermanencia TempoTotalPermanencia + TempoServico + TempoEsperaCliente Fim_Se Programa principal: 1) T0 tempo do primeiro evento de chegada (consultar sequência de valores respetiva) 2) Executar rotina de inicialização (T0) 3) (Clock, TipoEvento) Rotina de gestão de tempo (TempoProximaChegada, TempoPartida1, TempoPartida2) 4) Se (TipoEvento = Chegada) Então NumClientes NumClientes + 1 Executar rotina Evento de chegada (Clock) Se (NumClientes = MaximoClientes) Então TempoProximaChegada Fim_Se Senão Se (TipoEvento = Partida1) Então Executar rotina Evento de partida 1 (Clock) Senão Executar rotina Evento de partida 2 (Clock) Fim_Se Fim_Se 5) Se (Continuar simulação) Então Regressar a 3) Senão Calcular medidas de desempenho Escrever relatório Fim_Se Simular manualmente: começar por calcular os instantes de chegada e os tempos de serviço (tabela seguinte): Número de cliente Tempos entre chegadas (min) Instantes de chegada (min) Tempos de serviço (min)
35 para a simulação manual, utilizar um quadro com as seguintes entradas: Clock Evento NC TPC FilaEC EA1 TP1 EA2 TP2 TTP TOA1 TOA2 TCF NCS TTE [ ] livre livre Chegada ocup Partida livre Chegada ocup Partida livre Chegada ocup Chegada ocup Chegada [12.7] Partida1 - - [ ] Chegada [14.6] Partida2 - - [ ] Partida livre Partida livre Chegada ocup Chegada ocup Partida livre Partida livre Exemplo 3 Enunciado do problema: Sequenciamento de tarefas num job-shop. Funcionamento do sistema: são processadas 4 tipos de peças com 3 máquinas: Torno, Fresadora e Rectificadora; cada tipo de peça tem uma sequência de operações distinta; das peças a aguardar processamento numa máquina, é escolhida primeiro aquela que tiver menor tempo de operação; neste momento há 4 tarefas a realizar: 4 peças, uma de cada tipo. Tipo peças Máquinas T F R - F F T - R R T F - T F R T - R Dados de entrada para a simulação do sistema (inputs): - este problema poderia ser generalizado com chegadas de peças ao sistema com intervalos de tempo probabilísticos tempos de processamento probabilísticos adopção de outras regras de sequenciamento
36 usar a sequência de operações (máquina e tempo de processamento) da tabela seguinte Objetivos: Tipo peças Máquinas simular manualmente este sistema até processar todas as tarefas calcular as seguintes medidas de eficiência: - tempo total de processamento (ou makespan) - tempo médio de fluxo das tarefas - tempo médio de espera das tarefas - taxa média de ocupação das máquinas Nota: este problema poderia ser generalizado com chegadas de peças ao sistema com intervalos de tempo probabilísticos tempos de processamento probabilísticos adopção de outras regras de sequenciamento 5.9. Exemplo 4 Enunciado do problema (primeira fase): Ao chegar à sala do professor, o estudante deve esperar numa fila até que chegue a sua vez para ser atendido. Quando chega a sua vez, o estudante conversa com o professor e depois abandona a sala dando oportunidade para que um outro estudante possa ser atendido. Apenas por uma questão de simplicidade, vamos assumir que o tempo de chegada dos estudantes e o tempo gasto por cada estudante no atendimento são conhecidos (valores que constam na tabela). Estudante Objetivos: Tempo de chegada (minutos) Tempo de atendimento (minutos) Estudante Tempo de chegada (minutos) Tempo de atendimento (minutos) Tempo médio que um estudante gasta a tirar dúvidas com o professor e - Percentagem do tempo que o professor fica ocupado a tirar dúvidas. Componentes do modelo: Entidades: estudantes que vão tirar dúvidas e o professor que atende os estudantes; Atributos: considera-se que os estudantes são atendidos por ordem de chegada à fila (FIFO);
37 Atividades: tempo de espera do estudante na fila, tempo total gasto pelo estudante no sistema e tempo de ocupação do professor no atendimento aos estudantes; Estado do sistema: situação do professor (ocupado ou livre), número de estudantes na fila de espera e número de estudantes na sala (a serem atendidos); também se poderia considerar o número total de estudantes no sistema; Eventos: chegada de um estudante à fila para ser atendido e partida de um estudante depois de ser atendido pelo professor (e que deixa o sistema); o início do atendimento de um estudante não é um evento, pois coincide com a chegada de um estudante (se professor livre) ou com a partida de um estudante depois de atendido pelo professor (se fila não vazia). Para ilustrar a simulação pode-se traçar o retrato dinâmico do estado do sistema, pelo processamento dos eventos de chegada e saída de estudantes ordenados no tempo. A simulação manual do exemplo, correspondente às entradas da tabela inicial, pode ser apresentada de acordo com duas visões. A visão do estudante (descrição orientada ao processo) e a visão da ocorrência ordenada dos eventos, no caso da visão do professor (descrição orientada ao evento). A tabela seguinte apresenta a visão do estudante, assumindo inicialmente que: - não havia estudantes no sistema, - o professor estava livre e - o primeiro aluno chegou no tempo 6.0 minutos. Nesta tabela, - as colunas 1 e 2 foram tiradas da tabela inicial; - a coluna 3 depende se o aluno anterior já partiu do sistema; o valor da coluna é o maior valor entre o tempo de chegada do estudante e o tempo de partida do aluno imediatamente anterior; - a coluna 4 é a soma da coluna 3 com o valor do tempo de atendimento dado na tabela inicial; - a coluna 5 computa o tempo que o estudante passa na fila, simplesmente subtraindo do tempo que o estudante começa a ser atendido (coluna 3), o tempo em que o estudante chegou ao sistema (coluna 2); - a coluna 6 calcula o tempo que um estudante passa no sistema, subtraindo o seu tempo de chegada (coluna 2), do seu tempo de saída (coluna 4). O tempo médio que um estudante passa no sistema pode ser facilmente calculado pela tabela abaixo, sendo seu valor igual a 9.75 minutos. Aluno Tempo de chegada ao sistema Tempo de início de atendimento Tempo de saída do sistema Tempo de espera na fila Tempo total no sistema
38 A tabela seguinte apresenta uma descrição do exemplo com modelação orientada ao evento: os eventos são listados em ordem cronológica, na qual se pode calcular a percentagem de ocupação do professor, cujo valor é igual a 78%. Para manter a ordem cronológica dos eventos, foi necessário manter um calendário de futuros eventos a serem processados, o que foi conseguido colocando pela ordem correta os eventos de chegada e de partida dos estudantes. A ordem correta do processamento dos eventos foi obtida deste calendário, que vai sempre fornecer com exatidão o próximo evento a ser processado. Tempo de evento Aluno Tipo do evento Número de alunos na fila Número de alunos no sistema Estado do Professor Tempo de ocupação do Professor livre chegada 0 1 ocupado partida 0 0 livre chegada 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado partida 0 0 livre chegada 0 1 ocupado chegada 1 2 ocupado partida 0 1 ocupado partida 0 0 livre chegada 0 1 ocupado partida 0 0 livre
39 Qualquer que seja a visão de descrição do exemplo, a lógica associada ao processo de chegada e partida de estudantes depende do estado do sistema. No caso da chegada do estudante, se o professor está livre ele tornase ocupado, entrando o estudante para atendimento, tendo o seu tempo de partida escalonado para o tempo corrente mais o seu tempo de atendimento. Se o professor estiver ocupado, o estudante entra na fila de espera, aumentando o número de alunos em espera. No caso de partida de um estudante, se existe algum outro estudante em espera, o estado do professor mantém-se ocupado, o número de estudantes na fila é decrementado de uma unidade, o novo estudante entra para atendimento, sendo sua partida escalonada para o tempo corrente mais o seu tempo de atendimento. Contudo, se a fila de espera estiver vazia, simplesmente o estado do professor é alterado para livre. Enunciado do problema (segunda fase): Alterar o modelo incluindo mais uma entidade permanente denominada "Reprografia". O tempo de chegada nesta entidade permanente é igual ao tempo de saída do atendimento na entidade "Professor". Os tempos de atendimento na Reprografia são apresentados na tabela que se segue. Objetivos: Aluno Tempo de atendimento Média de tempo que os alunos permanecem no sistema - Tempo médio de espera na fila da Reprografia - Percentual de pausa da Reprografia Enunciado do problema (terceira fase): Alterar o modelo incluindo mais uma entidade permanente denominada "Biblioteca". Esta entidade permanente deve ser incluída entre a entidade "Professor" e a entidade "Reprografia". Assim, o aluno, após ser atendido pelo professor dirige-se à "Biblioteca" e de seguida à "Reprografia". O tempo de chegada à entidade permanente "Biblioteca" é igual ao tempo de partida da entidade "Professor". O tempo de chegada à entidade permanente "Reprografia" passa a ser o tempo de partida da entidade "Biblioteca"
40 A entidade "Biblioteca" possui uma característica diferente das outras. A biblioteca não possui limite de atendimentos simultâneos em função do espaço disponível para acesso aos livros. Assim que o estudante chega à "Biblioteca" o atendimento é imediatamente iniciado. Neste caso, é essencial tomar cuidado com a ordem de partida dos estudantes da "Biblioteca". A inexistência de uma fila pode fazer com que a ordem de partida seja diferente da ordem de chegada, o que irá interferir no comportamento da próxima entidade permanente. Os tempos de atendimento na "Biblioteca" são os apresentados na tabela que se segue. Aluno Tempo de atendimento , Objetivos: - Tempo médio de permanência dos estudantes no sistema - Tempo médio de espera na fila da "Reprografia" - Percentagem de tempo sem utilização da "Biblioteca" e da "Reprografia" Observação: a entidade "Biblioteca", assim como as demais entidades, fica sem utilização quando não houver nenhuma entidade temporária a usar os seus serviços. Enunciado do problema (quarta fase): A entidade permanente "Professor" deve ser alterada para atender, em simultâneo, até dois alunos. Ou seja, representar o comportamento de um setor de atendimento com dois professores. Utilizar os mesmos tempos de chegada e de atendimento para simular o sistema com esta nova característica. Objetivos: - Tempo médio de permanência dos estudantes no sistema - Tempo médio de espera na fila da "Reprografia" - Percentagem de tempo sem utilização da "Biblioteca" e da "Reprografia"
41 Enunciado do problema (quinta fase): Nesta etapa os estudantres números 4 e 7 regressam à "Biblioteca" para levar mais bibliografia após serem atendidos na entidade "Reprografia". Ao saírem da biblioteca (usando o mesmo tempo de atendimento da primeira passagem) passam novamente pela "Reprografia" (também utilizando o mesmo tempo de atendimento da primeira passagem) e depois abandonam o sistema. O regresso destes estudantes à entidades permanentes anteriores deve ser realizado de forma consistente no tempo de simulação. Objetivos: - Tempo médio de permanência dos estudantes no sistema - Tempo médio de espera na fila da "Reprografia" - Percentagem de tempo sem utilização da "Biblioteca" e da "Reprografia" Observação: a entidade "Biblioteca", assim como as demais entidades, fica sem utilização quando não houver nenhuma entidade temporária a usar os seus serviços Nível de detalhe dos modelos de simulação O nível de detalhe de um modelo de simulação é a quantidade de aspetos do sistema real que são incluídos no modelo. Desta forma, quando maior for o nível de detalhe, maior será o tempo e o custo de modelação, alguns aspetos podem ser desprezados sem prejuízo dos objetivos do estudo. O nível de detalhe que o modelo deve capturar: é determinado pelos objetivos do estudo de simulação, deve ser consistente com os dados disponíveis para alimentar o modelo, é um compromisso entre realismo e custo, deve abranger aspetos que credibilizem o modelo, mesmo que sejam irrelevantes para a sua validação. Em sistemas complexos o estudo pode ser hierárquico: primeira aproximação por via analítica ou com modelo de simulação grosseiro, segunda aproximação com maior detalhe, apenas incorporando os fatores relevantes. Exemplos de modelos com diferentes níveis de detalhe: - Sistema 1: produção job-shop, com m máquinas e n tipos de peças conjunto de máquinas de diferentes tipos diferentes tipos de peças, com distintas sequências de operação
42 - Opções de nível de detalhe: quanto ao tempo de setup - não considerar tempos de setup - considerar um tempo de setup médio constante e incluí-lo no tempo de serviço - considerar os tempos de setup em função do último tipo de peça produzido e do próximo tipo de peça a produzir quanto à movimentação de stocks entre máquinas - considerar ou não tempos de movimentação entre máquinas - considerar ou não limitação de espaço de stock - Sistema 2: caixas de supermercado, com n filas e n servidores - opções de nível de detalhe: quanto à selecção da fila por parte dos clientes, que escolhem - uma fila aleatoriamente - a fila mais curta - a fila mais curta e mudam de fila se alguma fila próxima ficar mais curta modelar ou não filas especiais - filas expresso para pequeno volume de compras - filas prioritárias para grávidas modelar ou não situações de excepção - interrupção para verificar preço não marcado Modelos de simulação com filas de espera Introdução O reconhecimento da existência de filas de espera verifica-se em todas as atividades que exigem um determinado serviço, com capacidade de fornecimento limitado. O estudo destes fenómenos é muito importante, pois são geradores de custos, seja o tempo de espera dos clientes que vão usar o serviço, ou o número de servidores que são colocados à disposição do sistema para servirem os clientes (quanto maior o número, maior o custo). Note-se que o tempo de espera pode ser reduzido à custa do aumento do número de servidores; no entanto, com o aumento de servidores, aumenta o preço do serviço. Assim, o problema que se coloca, na maioria dos casos, é definir o ponto de custo total mínimo que corresponderá naturalmente a uma capacidade de serviço que se pretende determinar Estrutura de uma fila de espera Nestes modelos admite-se que os clientes são gerados através de uma fonte (input source) cuja capacidade de produção pode ser finita (limitada) ou infinita (ilimitada). No caso da fonte finita, o
43 número de potenciais clientes é fixo, sendo que o número de clientes que existem no sistema (os que esperam e os que estão a ser servidos) afeta, em qualquer instante, o número de potenciais clientes fora do sistema. No caso da fonte infinita esta interação (clientes do sistema vs potenciais clientes) é considerada sem significado. Na generalidade dos modelos considerados admite-se que o intervalo entre chegadas de clientes tem uma distribuição estatística que deverá ser especificada. O comportamento dos clientes deve também ser caracterizado, sendo as seguintes decisões mais vulgarmente utilizadas: - recusa (balking): os clientes recusam-se a entrar no sistema se a fila é demasiada longa; - desistência (reneging): os clientes abandonam o sistema se esperam pelo serviço demasiado tempo; - apostas (jockeying): um cliente decide mudar de fila para conseguir atingir o serviço mais rapidamente. A decisão de balking é determinística, enquanto as de reneging e jockeying são probabilísticas. A indicação da dimensão da fila deve ser caracterizada, podendo ser finita ou infinita. A dimensão infinita é a mais utilizada, mesmo para situações onde se consideram valores razoavelmente elevado, já que esta restrição complica de forma significativa a análise Mecanismos de escalonamento Os mecanismos de escalonamento são utilizados para definir como os clientes são selecionados para entrar num servidor, quanto este se encontrar disponível (são conhecidos como disciplina da filas). Existem inúmeros mecanismos, sendo os mais usados os seguintes: - FCFS (first come first served): os clientes entram no servidor exatamente pela mesma ordem com que chegam ao centro de serviço correspondente; - LCFS (last come fisrt served): tem a estrutura de uma pilha onde o último cliente a chegar ao centro é o que entrará no servidor logo que este fique disponível. Alguns autores consideram esta disciplina preemptiva (quando um cliente chegar ao centro, o cliente que estiver a ser servido é retirado do servidor e colocado no topo da pilha, entrando o novo cliente no servidor; assim que este completar o seu serviço, o cliente no topo da pilha entra novamente no servidor). - RR (round robin): os clientes são servidos por um intervalo de tempo pequeno (um quantum); se o serviço não é completado neste tempo, ele é colocado no final da fila e um outro cliente entra no servidor até que se esgote o seu quantum ou termine o serviço; - PS (processos sharing): todos os clientes dividem a capacidade do centro de serviço, como se executassem em paralelo (comparada a RR, com quantum = 0); - IS (infinite server): não existe fila, todos os clientes são servidos assim que chegam ao centro de serviço;
44 - com prioridades: os clientes entram nos servidores de acordo com classes de prioridades preestabelecidas; este mecanismo pode ser nonpreemptive (PRTY - nonpreemptive priority), se o cliente em serviço não é afetado quando um cliente com maior prioridade chega ao centro; o processo é preemptive (PRTYPR - preemptive-resume priority), se a chegada de um cliente com prioridade superior ao centro tirar de serviço o de prioridade mais baixa (que está a ser servido), que só reentrará no servidor quando todos os clientes com prioridades mais elevadas que a sua forem servidos Centros de serviço Um centro (mecanismo) de serviço consiste em um ou mais servidores (também denominados de postos de atendimento), correspondentes a recursos do sistema modelado, e uma área de espera (fila) para os clientes que irão ser servidos (atendidos). As estruturas mais comuns associadas a um centro de serviço são as seguintes (figura que se segue): (a) 1 fila e 1 servidor, (b) 1 fila e 2 servidores, (c) 2 filas e 1 servidor, (d) 1 fila e vários servidores, (e) várias filas e 1 servidor, e (f) várias filas e vários servidores. Um sistema pode também ser modelado usando vários centros de serviço interligados (sistema com várias fases). Desta forma, quando um cliente deixa um centro de serviço, deverá existir um método para determinar qual o centro de serviço para onde seguirá aquele cliente; este processo denomina-se de roteamento. Desta forma, as estruturas mais comuns de sistemas com vários
45 centros de serviço, são as seguintes (figura que se segue): (a) cada centro com 1 fila e 1 servidor, (b) cada centro com 1 fila e vários servidores, (c) cada centro com várias filas e vários servidores. Todos os casos descritos são modelos abertos, pois representam sistemas com um ou vários centros de serviço, mas em que qualquer um dos centros é utilizado apenas uma vez. No entanto, há sistemas em que um ou mais dos seus centros de serviço podem ser utilizados mais do que uma vez; nestes casos, estes sistemas são modelados com modelos fechados ou mistos (ver figura seguinte): (a) abertos, (b) fechados, e (c) mistos
46 5.12. Análise de dados de entrada (inputs) Introdução Um dos aspetos mais importantes na implementação de modelos de simulaçao é a forma como se caracterizam os dados de entrada (inputs) do modelo. De facto, o aspeto mais difícil da modelação dos dados de entrada é obter dados com suficiente qualidade, quantidade e variedade de forma a se conduzir uma análise razoável. A forma como são obtidos é também, muitas vezes, um fator determinante e condicionante do desenvolvimento da investigação a concretizar, já que: - são escolhidos em sequência diferente daquela porque foram observados, o que conduz à impossibilidade de verificar hipóteses fundamentais como, por exemplo, a independência; - poderão estar agregados em classes ou unidades que não permitem um outro tipo de agregação mais conveniente em termos de análise; - a precisão da recolha poderá não ser adequada ao estudo a realizar; - os valores poderão provir de mais do que um processo, sem qualquer descriminação da origem. É nestas circunstâncias que são recomendados os seguintes procedimentos de natureza prática: - sempre que possível, recolher entre 100 e 200 observações; para amostras de menores dimensões é significativa a redução da qualidade da análise; no entanto, para amostras de maiores dimensões os ganhos são marginais; - recolher dados com pelo menos mais um ou duas casas decimais em relação à forma como se exprimem os valores de referência, como por exemplo, a média e a mediana; - quando se está interessado num resultado intermédio entre dois valores observado, deve-se começar por recolher esses dados e só depois determinar os resultados pretendidos através de cálculos manuais ou com a assistência de software de suporte; - se é evidente ou se suspeita-se que o comportamento do sistema depende do período de tempo considerado, deve-se recolher várias amostras para cada um dos intervalos de tempo onde ocorrem essas variações. No caso de ser possível recolher dados de uma variável aleatória de entrada, a sua utilização em simulação é, em geral, concretizada em três formas distintas: - os valores são utilizados diretamente na simulação; trata-se de um processo recomendado na validação do modelo, comparando o resultado (output) com o verificado no sistema; no entanto, não existe, na maior parte dos casos, informação suficiente para se desenvolver um conjunto de testes necessário para uma análse adequada dos resultados; - os dados recolhidos são utilizados para definir uma função de distribuição empírica qualquer; este processo é preferível ao anterior, já que permite, para a situação contínua, a geração de um valor entre os valores máximo e mínimo observados;
47 - técnicas estatísticas de inferência utilizadas para se ajustarem distribuições teóricas através de testes de hipóteses; é preferível este processo ao anterior, pelas seguintes razões: - a distribuição empírica apresenta algumas irregularidades, em particular se existe uma amostra de dimensão reduzida a moderada; - a distribuição empírica permite apenas a geração de um valor entre um valor mínimo e valor máximo observados; - existem muitas vezes razões de natureza física que a sua ponderação levam à utilização de uma distribuição teórica ajustada aos dados; - uma distribuição teórica é uma forma compacta de representar os dados, sendo fácil de alterar em experiências de simulações alternativas. No entanto, há também razões contrárias à utilização de distribuições teóricas, como sejam: - podem não existir distribuições teóricas que se ajustem de forma adequada aos dados; - podem ser gerados valores elevados mesmo com probabilidades reduzidas, sendo recomendado truncar a distribuição teórica ajustada. O comportamento aleatório do sistema é recriado no modelo com a caracterização dos dados com distribuições de probabilidade. Exemplos de fontes de aleatoriedade: Tipo de sistema Produção Comunicações Transportes Fontes de aleatoriedade tempos de processamento tempo entre falhas de uma máquina tempo de reparação de máquinas tamanho de lotes de encomenda proporção de defeitos tempo entre chegadas de mensagens tipo de mensagem tamanho da mensagem tempo de carga de navios tempo entre chegadas de passageiros ao metro A importância da escolha da distribuição é demonstrada pelo seguinte exemplo, correspondente a um sistema de produção composto por uma máquina e uma fila de espera: tempo entre chegadas: segue distribuição exponencial com média de 1 minuto, tempo de serviço: existem 200 observações, mas a distribuição é desconhecida,
48 experiência: - são ajustadas 5 distribuições distintas às observações, - simulação do sistema com 100 corridas independentes até processar 1000 peças. Distribuição ajustada ao tempo de serviço Exponencial Gama Weibull Log-normal Normal Tempo médio de espera Número médio em espera Proporção de esperas 20 min min relativo n relativo % relativo conclusão: os resultados são muito díspares, apesar de todas as distribuições ajustadas serem estatisticamente válidas. Perante o problema de existir dados recolhidos no sistema real (obervações) mas desconhecer-se a distribuição de que provêm (se alguma!), deve-se começar por fazer o ajuste de uma distribuição teórica a um conjunto de observações, da seguinte forma: 1. selecção de um tipo de distribuição localização ( ) 2. estimação dos parâmetros da distribuição escala ( ) 3. aplicação de testes estatísticos à qualidade de ajuste forma Depois, verificar a distribuição de tempos tipicamente encontrada na prática: só valores x > 0 assimétrica com cauda à direita Propriedades das distribuições teóricas As distribuições teóricas podem ser divididas em dois grupos: contínuas e discretas. Por sua vez, as distribuições contínuas mais usadas em simulação são: uniforme, exponencial negativa, normal, log-normal e triangular. As distribuições discretas mais usadas são: empírica e de Poisson
49 a) Distribuição uniforme (contínua) A distribuição uniforme tem o desenvolvimento gráfico apresentado na figura. A sua função de densidade pode ser representada por: { f( X) = 1 b a, se a X b 0, se X < a ou X > b A sua função de distribuição é dada por: F(X) = {0, se X < a 1 b a, se a X b 1, se X > b Os parâmetros da distribuição são os seus limites de variação, com a < b e a,b R. Tem média = (a + b) / 2 e variância = (b a) 2 / 12. Os estimadores de máxima verosimilhança dos parâmetros são: â = min 1 n i X i e b = max 1 n i X i Ou seja, para uma amostra de dimensão n, o menor valor das observações é o estimador de a e o de maior valor o estimador de b. A distribuição uniforme permite modelar uma variável aleatória que se suspeita variar entre a e b (entre os quais os valores são equiprováveis) e sobre a qual pouco mais se conhece. A distribuição uniforme entre 0 e 1 é essencial na geração de números pseudoaleatórios e de outras distribuições. b) Distribuição exponencial negativa (contínua) A distribuição exponencial negativa tem o desenvolvimento gráfico apresentado na figura. A sua função de densidade é representada formalmente por: { 1 f( X) = ( ) exp X, se X 0 0, se X < 0 A função de distribuição é dada por: F(X) = exp( ) {1 X, se X 0 0, se X < 0 A média e variância desta distribuição são: m e m 2. O estimador de máxima verosimilhança de m é calculado aravés de: n = X = 1 n ( i=1 X i)
50 Ou seja, a média dos n valores recolhidos para amostra. Esta distribuição apresenta um conjunto de propriedades, das quais se referem as seguintes: - se s = m então existe uma elevada variabildade, - P(x [ m, 3.7 m]) = 95%. Esta distribuição é utilizada normalmente para caracterizar o intervalo de tempo entre chegadas de clientes a um sistema, o tempo de serviço, o tempo entre falhas de equipamento, etc. c) Distribuição normal (contínua) A distribuição normal (também conhecida por de Gauss ou Gaussiana) tem o desenvolvimento gráfico apresentado na figura. A área a azul escuro está a menos de um desvio padrão (σ) da média. Numa distribuição normal, isto representa cerca de 68% do conjunto, enquanto dois desvios padrões desde a média (azul médio e escuro) representam cerca de 95%, e três desvios padrões (azul claro, médio e escuro) cobrem cerca de 99.7%. Este fato é conhecido como regra , ou a regra empírica, ou a regra dos 3-sigmas. Esta distribuição tem uma função de densidade com a estrutura seguinte: f( X) = 1 2 π exp ( (X )2 2 2 ), X e > 0 onde m e s representam o valor médio e o desvio padrão da distribuição. A função de distribuição não tem uma forma explícita. Os estimadores de máxima verosimilhança da média e do desvio padrão podem ser calculados através dos valores amostrais, de acordo com as expressões seguintes: = X, = [ n 1 n s 2 ] 1 /2 e s 2 = n ( X i X) 2 i=1. n 1 Esta distribuição apresenta um conjunto de propriedades, das quais se referem as seguintes: - A distribuição normal de média 0 e variância 1 designa-se por normal reduzida N(0,1); qualquer normal pode ser transformada em normal reduzida através de uma relação linear. - Se existem k variáveis aleatórias independentes, a sua soma segue uma distribuição normal de média igual à soma das médias e variância igual à soma das variâncias (teorema de limite central). - Quando s 0 a distribuiçao normal torna-se degenerada para m. A distribuição normal é utilizada normalmente para descrever vários tipos de erros, valores que representam a soma de grande número de outras quantidades, etc
51 c) Distribuição log-normal (contínua) A distribuição log-normal tem o desenvolvimento gráfico apresentado na figura (para para µ = 0 e diferentes valores de σ). A função de densidade desta distribuição representa-se formalmente por: { 1 f( X) = X 2π exp ( ) )2 (ln(x) 2 2, X > 0 0, X 0 Não existe fórmula para a função densidade acumulada. A forma desta distribuição depende do valor de s (parâmetro de forma), sendo m um fator de escala. Esta distribuição é válida apenas X > 0, podendo o seu valor médio, variância e moda serem calculados, respetivamente, através de: e + 2, e (e 2 1) e e 2 Os valores de máxima verosimilhança para a média e desvio padrão são dados por: n ln( X i n ) i=1 i=1 ( ln(x i ) ) 2 = e =. n n A distribuição log-normal aparece naturalmente como o produto de várias variáveis independentes (sempre positivas). Esta distribuição está particularmente adaptada para modelar o tempo de desenvolvimento de tarefas ou de quantidades iguais à soma de outras quantidades. d) Distribuição triangular (contínua) A sua representação gráfica é a apresentada na figura. A sua função de densidade pode ser representada formalmente por: { 2(X a) (b a)(c a), se a X c f( X) = 2(b X) (b a)(b c), se c < X b 0, outro valor