Baixe o app para aproveitar ainda mais
Prévia do material em texto
Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Modelagem de Sistemas Discretos Baseado em: • Introdução à Pesquisa Operacional. Hillier e Lieberman. 2013. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Dicas para Problemas Numéricos de Teoria das Filas 1. Verifique se com as fórmulas gerais é possível resolver. Se sim, proceder desta forma. Se não, verificar próximo item. 2. Determine qual o tipo de fila é M/M/1; M/M/2; M/M/s; M/G/1; M/D/1; M/Ek/1; M/Ek/2; D/M/s; Ek/M/1; Ek/M/2, etc. 3. Calcule ρ. Se ρ≥1, então o sistema de filas é instável, mal dimensionado, não é possível calcular as características da fila. 4. Se ρ<1, então utilizar as equações ou os gráficos correspondentes para efetuar os cálculos. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Exemplo Fórmulas Gerais q João e José são dois barbeiros em uma barbearia que eles possuem e dirigem. Eles têm duas cadeiras de barbear para clientes que estão esperando por um corte de cabelo e, portanto, o número de clientes na barbearia varia entre 0 e 4. Para n = 0, 1, 2, 3, 4, a probabilidade Pn de que exatamente n clientes se encontrem na barbearia é P0 = 1/16, P1 = 4/16 , P2 = 6/16 , P3 = 4/16, P4 -=1/16: a. Calcule L. Como você descreveria o significado de L para João e José? b. Para cada um dos possíveis valores do número de clientes no sistema de filas, especifique quantos clientes se encontram na fila. Calcule então Lq. Como você descreveria o significado de Lq para João e José? c. Dado que chegue uma média de quatro clientes por hora e permaneçam para cortar o cabelo, determine W e Wq. Descreva esses dois valores em termos significativos para João e José. d. Dado que João e José são igualmente rápidos nos cortes de cabelo, qual é a duração média de um corte de cabelo? Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com M/M/1 – Primeiro Exemplo ´Clientes chegam em um sistema de filas com um único atendente de acordo com um processo de Poisson em uma taxa média de 10 por hora. Se o atendente trabalhar continuamente, o número de clientes que podem ser atendidos em uma hora tem uma distribuição de Poisson com média 15. a. Determine a proporção de tempo durante o qual ninguém está esperando para ser atendido. b. Qual a probabilidade de um cliente chegar sem precisar esperar na fila? Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com M/M/1 – Segundo Exemplo ´ O balcão de uma choperia é servida por um atendente. Os fregueses chegam de acordo com um processo de Poisson, a uma taxa média de 15 por hora. Eles são atendidos em uma base FIFO e, por causa da qualidade do chope , esperam se necessário. O tempo de atendimento de cada freguês é distribuído segundo uma exponencial , com média 45 segundos. a. número médio de fregueses esperando para serem atendidos. b. tempo que um freguês deve esperar para ser atendido c. probabilidade de um freguês gastar mais de 15 minutos d. probabilidade de o atendente estar desocupado Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Exemplo M/M/s – Hospital Municipal ´ Para o problema da sala de emergências do Hospital Municipal, o administrador concluiu que os casos de emergência chegam, em sua maioria, de forma aleatória (um processo de entrada de Poisson), de modo que os tempos entre atendimentos possuem uma distribuição exponencial. Ele também concluiu que o tempo gasto por um médico tratando os casos segue, aproximadamente, uma distribuição exponencial. Assim, ele optou pelo modelo M/M/s para um estudo preliminar desse sistema de filas. Projetando para o ano que vem os dados disponíveis para o turno do início da noite, ele estima que os pacientes chegarão em uma taxa média de 1 a cada 1/2 hora. Um médico precisa em média de 20 minutos para atender cada paciente. Portanto, com uma hora sendo a unidade de tempo: !" = !$ e !& = !' Logo: 𝜆 = 2 e 𝜇 = 3 As duas alternativas consideradas são para continuar a ter apenas um médico durante esse turno (s=1) ou então disponibilizar um segundo médico (s =2). Em ambos os casos, 𝜌 = "-.& < 1, Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Exemplo M/M/s – Hospital Municipal ´ de forma que o sistema deveria aproximar-se de uma condição de estado estável. Na verdade, como 𝜆 é ligeiramente distinto durante outros turnos, o sistema jamais atingirá realmente uma condição de estado estável, porém o administrador acha que os resultados de estado estável fornecerão uma boa aproximação. ´ Com base nestes resultados, avaliar quantos médicos são necessários. Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Exemplo M/G/1 e M/D/1 ´Maria opera uma banquinha de café expresso. Os clientes chegam de acordo com um processo de Poisson a uma taxa média de 30 por hora. O tempo necessário para Maria servir um cliente tem uma distribuição normal com média de 75 segundos e desvio padrão 60 segundos. a) Use o modelo M/G/1 para encontrar L, Lq, W e Wq. b) Suponha que Maria seja substituída por uma máquina automática de café expresso que precise exatamente de 75 segundos para cada cliente operar. Encontre L, Lq, W e Wq. c) A que se deve a diferença entre Lq nas letras a e b? Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com ( ) å å å å ¥ = -¥ = - -- ¥ = ¥ = = ÷ ø ö ç è æ = = = += = = -= = = = 0 1 0 0 0 11 021 0 . . . . 1 . . ).( . . . n nn n n nn nn nn n q qq sn nq n n n P CP PCP C WW WL WL PsnL PnL s s ll µµµ lll µ l l µ lr µµ ! ! { } ( ) { } ( ) ( )lµµ l rw lµ w lµµ l lµ l r r r r r rµ rµ - = => - = => - = - = - = -= = = -- -- . . 1 ).( 1 1 . .1. .1. 2 0 0 q t q o to q n n n n W etP W etP L L P PP C Fórmulas Gerais Fórmulas M/M/1 Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com Fórmulas M/M/2 Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com 𝜇1 = 2. 𝜇 ∀ 𝑛 > 2𝜇1 = 𝑛. 𝜇 ∀ 𝑛 ≤ 2𝜌 = 𝜆2. 𝜇 𝑃7 = 11 + 𝜆𝜇 + 𝜆 𝜇9 $2 − 𝜆 𝜇9𝑃! = " &⁄ . 𝑃7𝑃1 = < =9 >$ >?@ . 𝑃7 ∀ 𝑛 ≥ 2𝐿C = 𝑃7. 𝜆 𝜇9 $𝜌2. 1 − 𝜌 $ 𝑊C = 𝐿C𝜆𝑊 = 𝑊C + 1𝜇𝐿 = 𝜆. 𝑊C + 1𝜇 = 𝐿C + 𝜆𝜇 𝑃 EFG7 = 𝑃7 + 𝑃!𝑃 EFHI = 1 − 𝑃 EFG7 . 𝑒 K$& !KL I 𝑃 EHI = 𝑒K&I. 1 + 𝑃7. 𝜆 𝜇9 $2 1 − 𝜌 . 1 − 𝑒K&I !K" &91 − 𝜆 𝜇9 ∀ 𝜆 𝜇9 ≠ 1 𝑃 EHI = 𝑒K&I. 1 + 𝑃7. 𝜆 𝜇9 $2 1 − 𝜌 . 𝜇𝑡 ∀ 𝜆 𝜇9 = 1 Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com ( ) ï ï ï î ïï ï í ì ³" ÷ ø öç è æ ££" ÷ ø öç è æ = ú ú ú ú û ù ê ê ê ê ë é ÷ ø ö ç è æ ÷ ø öç è æ- ÷ ø öç è æ + ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ ÷ ø öç è æ = ï ï ï î ïï ï í ì ³" ÷ ø öç è æ ££" ÷ ø öç è æ = = £"= >"= - - = - å snP ss snP nP s sn P sn ss sn nC s snn sns sn n n n s s n n sn n n n n n 0 0 1 0 0 . !. 0. ! .1 1. !! 1 !. 1 ! . . . µ l µ l µ l µ l µ l µ l µ l µ lr µµ µµ Fórmulas M/M/s Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com ( ) { } ( ) ( ) { } { } { }( ) ( ) tsqq s n nq sts t q q q q s q ePtP PP s e s P etP LL WW LW s P L .1.. 1 0 1. 0 . 2 0 .01 0 1 1 . 1!. .1. 1 1!. .. rµ µ lµ µ ww w µ lr µ l w µ l µ l r rµ l -- - = ÷ ø öç è æ --- - =-=> ÷ ø ö ç è æ == ú ú ú ú ú û ù ê ê ê ê ê ë é ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ -- ÷÷ ø ö çç è æ - - ÷ ø öç è æ +=> += += = - ÷ ø öç è æ = å Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com ( ) ( ) { } ( ) ( ) { } { } { }( ) ( ) tsqq s n nq sts t q q q q s q sn n n n s s n n sn n n n n n ePtP PP s e s P etP LL WW LW s P L snP ss snP nP s sn P sn ss sn nC s snn sns .1.. 1 0 1. 0 . 2 0 0 0 1 0 0 .01 0 1 1 . 1!. . 1. 1 1!. .. . !. 0. ! .1 1. !! 1 !. 1 ! . . . rµ µ lµ µ ww w µ lr µ l w µ l µ l r rµ l µ l µ l µ l µ l µ l µ l µ l µ lr µµ µµ -- - = ÷ ø öç è æ --- - - - = - =-=> ÷ ø ö ç è æ == ú ú ú ú ú û ù ê ê ê ê ê ë é ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ -- ÷÷ ø ö çç è æ - - ÷ ø öç è æ +=> += += = - ÷ ø öç è æ = ï ï ï î ïï ï í ì ³" ÷ ø öç è æ ££" ÷ ø öç è æ = ú ú ú ú û ù ê ê ê ê ë é ÷ ø ö ç è æ ÷ ø öç è æ- ÷ ø öç è æ + ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ ÷ ø öç è æ = ï ï ï î ïï ï í ì ³" ÷ ø öç è æ ££" ÷ ø öç è æ = = £"= >"= å å ( ) ( ) ( )k k n n k k q q q n k n kk n n n n PP kL LW LW PLL kn knP P kn knC -== - + - - = = = --= ïî ï í ì >" £" - - = - - = ÷÷ ø ö çç è æ ÷ ø öç è æ = ïî ï í ì >" £"÷ ø öç è æ = å å - = + + + + = 1.. 1 .1 1 1 0 . 1 1 1 11 0 1 0 1 1 0 1 1 0 0 lll r r r r l l r r r r r µ l µ l Fórmulas M/M/s Fórmulas M/M/1/k Fórmulas M/G/1 ( ) µ l r r rsl r 1 1.2 . 1 222 0 += = += - + = -= q q q q q WW L W LL L P Fórmulas M/D/1 São as mesmas do M/G/1, considerando-se s2 = 0. Única alteração: ( )r r - = 1.2 2 qL Prof Dsc Paulo Ribas – prof.paulo.ribas@gmail.com
Compartilhar