Home

PROCESSOS ESTOCÁSTICOS E TEORIA DE FILAS

1. 30 chegadas hora t 15 minutos WW 0 25 gt 10 clientes l L h 2 minutos tempoentre chegadas E X S A 30 A 30 a 22 5 chegadas processode Poisson Processos Estoc sticos e Teoria de Filas 150 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 13 A ocupa o m dia de uma lanchonete de fast food de 50 pessoas Sabe se que chegam a lanchonete 100 pessoas hora e que em m dia uma pessoa demora 20 para fazer sua refei o a Quanto tempo demora um cliente dentro da lanchonete b Qual a percentagem deste tempo gasta na fila 100 pessoas hora u l pessoa 20 min 3 pessoas hora L 50 pessoas W ai LL AW EE 100 2 b W w w bw w Lw ll minutos u u 2 3 6 30min 100 10min x x 33 3 14 Um n mero indeterminado de duplas de alpinistas se dirige a uma montanha com o intuito de escal la Na base do lance inicia da escalada h um plat onde s cabem dois alpinistas e o caminho at este plat estreito e ngreme Um dos guias do grupo esta na entrada deste caminho orientando a subida para o plat De l ele n o pode ver nem ouvir o que se passa em cima mas baseado na experi ncia procura evitar que mais de uma dupla esteja esperando na base do lance dada a falta de espa o Ele sabe que o lance consome em m dia 12 minutos de cada dupla se ela deseja que o plat fique sem superlota o em 84 d
2. Too 0 97 T00 0 977 Too 0 9387 Za 0 037 o0 0 0370 Se Zu 0 0290 Tio 0 907 0 97 To 0 0290 Zoo F Zautfet fusl T 0 0032 Anualidade m dia 100 Too 400 T411 300 to T10 1 12 58 20 DOFOGO uma companhia produtora de fog es famosos pela sua qualidade A companhia tem uma pol tica de 2 anos de garantia onde ela garante a substitui o de qualquer fog o que falhe durante este per odo A companhia est planejando fazer uma campanha promocional onde pretende estender a garantia para tr s anos Como forma deavaliar o impacto desta nova pol tica foram coletados os seguintes dados 3 dos fog es novos falham durante o primeiro ano de opera o 5 dos fog es com mais de um ano de uso falham durante o segundo ano de opera o 7 dos fog es com mais de dois anos de uso falham durante o terceiro ano de opera o Observe que um fog o substitu do n o coberto pela garantia a Use cadeias de Markov para predizer quantos fog es dever o ser repostos com a nova pol tica Processos Estoc sticos e Teoria de Filas 129 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Supondo que o custo de repor um fog o seja de 100 e que a DOFOGO venda 10 000 fog es por ano qual o impacto monet rio da mudan a de pol tica de garantia Pol tica de garantia de 3 anos 0 97 0 95 0 1 2 3 F nn ol o 097 0o io op 0 O O 1 O O 0 95 0 0 05 0 93 EE SR S
3. l J pd k 1 Fiji TEE Traga 0 Dessa forma R torna se uma matriz estoc stica e portanto representando as transi es para alguma cadeia de Markov Da teoria de Cadeias de Markov diz se que um estado i comunica se com outro estado j i j quando poss vel em algum n mero de etapas partir de i e alcan ar j Isto existe uma sequ ncia de esta es io i i4 i2 i3 ix j de modo que para algum ndice k gt 0 tem se gt 0 EEM A A EE et Ly fun fois te Ir A fim de garantir que todos os centros de servi o possam receber usu rios e que os fregueses que entram tenham probabilidade positiva de sair em algum momento acrescenta se mais duas condi es al m das mencionadas anteriormente d Todos os n s da rede poder o receber usu rios externos de forma direta ou indireta Isto V j e J ou gt 0 ou existe um i tal que A gt 0ei e O usu rio servido em i tem probabilidade positiva de sair da rede em uma ou mais etapas Ou seja Vie J ou ri J 1 gt 0 ou existe um j e J tal que rj J 1 gt 0 e i gt j Com as condi es acima a cadeia de Markov associada matriz R ser recorrente J n o nula e as equa es de tr fego 7 zs A meJ ter o solu o nica Pode k 1 se interpretar y como a taxa total de entradas ao n m e J sendo resultado da composi o das chegadas externas com as sa das de esta es que se movimentam para o centro m Seja N
4. qual os incidentes de entrada ocorrem tem que ser igual a taxa m dia qual os incidentes de sa da ocorrem g A primeira premissa para a exist ncia de um sistema de filas que a capacidade de servi o deve ser em m dia menor do que a demanda pelo servi o muito embora ela possa ser instantaneamente maior h Um processo exponencial de chegadas pode ser caracterizado por um n mero elevado de tempos entre chegadas pequenos e raros os tempos entre chegadas grandes i O modelo de filas que representa um supermercado com 5 caixas onde o processo de chegadas Poisson e servi o exponencial denominado M M 1 j Em um sistema com restri es de tamanho da fila a condi o de estabilidade do sistema de filas que o fator de utiliza o seja menor que 1 k A afirmativa o tempo ocioso do sistema igual a um menos o fator de utiliza o v lida para qualquer sistema de filas de servidor nico l A taxa de sa da de um sistema de filas em equil brio igual a taxa de entrada somente se o servidor for exponencial m Um servidor Erlang equivalente a um conjunto de servidores exponenciais em s rie Mostre que com respeito ao tamanho m dio no sistema s o verdadeiras as seguintes afirma es a A fila M M 1 sempre melhor que a fila M M 2 se ambas tem o mesmo p b O sistema M M 2 sempre melhor que o sistema com duas filas M M 1 independentes cada uma recebendo metade das
5. Logo a ger ncia n o deve mandar o atendente fazer o curso 1 1hora 23 K sucata recebe uma m dia de 15 pedidos por dia de um certo modelo antigo de carro do qual ela pode atender a 20 pedidos por dia Entretanto se menos que 3 carros forem alugados a companhia perde dinheiro da seguinte forma se somente 2 carros s o alugados a perda de 220 dia se somente 1 carro for alugado a perda de 260 dia e se nenhum carro for alugado a perda de 290 dia As perdas s o naturalmente compensadas pelos ganhos quando 3 ou mais carros s o alugados Considerando apenas as perdas qual ser o valor esperado do preju zo por dia Assuma chegadas e servi o Poisson e que n o existe limita o de tamanho nem desist ncias da fila MM 1 A 15 pedidos dia u 20 pedidos dia n 2 1 0 aa 0 75 u 20 alugados perda gt 220 dia gt 260 dia gt 290 dia E preju zo 290p 260p 220p 290 1 p 260 1 p p 220 1 p p 290 0 25 260 0 25 0 75 220 0 25 0 5625 152 2 dia Processos Estoc sticos e Teoria de Filas 157 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 7 2 x 3 No 4 NA 5 6 Lista de Exerc cios Complementares 71 Processos Estoc sticos n P X jlX i e Considere um processo erg dico x e Ee e o no qual p n m lim Py D pelo menos tr s interpreta es distintas para os valores 77 HA
6. es de estabilidade para a rede b Esboce o diagrama de transi o de estados c Calcule a probabilidade de que existam mais de 2 pessoas na rede para 120 c h Ly 150 ch Liz 180c h 100 200 250 oO 36 Num certo problema de fila os clientes chegam seguindo a distribui o de Poisson com taxa m dia de 4 ch Observou se que o tempo m dio de atendimento de 10 min com vari ncia de 25 min Supondo que o modelo M Ey 1 razo vel para este problema encontre o n mero esperado de clientes no sistema e o tempo que um cliente t pico espera aguardar na fila 37 A coordena o do concurso vestibular de uma determinada universidade deseja prever a quantidade de fiscais salas necess rios para o bom andamento do concurso Est o inscritos 5000 6000 candidatos que ser o igualmente divididos pelas diversas salas Cada candidato ao chegar dever se dirigir a sua sala e ali deixar um documento de identidade com um fiscal No ato de devolu o da prova o fiscal dever conferir o nome nela escrito com o documento identificar visualmente o candidato e devolver lhe o documento este processo leva em m dia 15 segundos por candidato Ao planejar o processo baseada em experi ncia anterior a coordena o conta com um ritmo de devolu o considerando o universo de todos os 5000 6000 candidatos de 80 100 provas por minuto em m dia nos ltimos 15 minutos do prazo de realiza o da prova Para evitar tumulto na devo
7. o de efetuar o pagamento com cart o de cr dito que era uma opera o realizada sequencialmente a passagem das mercadorias por um caixa de supermercado passou a ser realizada no pr prio caixa Supondo tempos entre chegadas e tempos de servi o exponenciais e que o tempo de efetuar o pagamento do cart o tem dura o equivalente ao tempo de passagem das mercadorias pelo caixa analise as duas situa es sob o ponto de vista do cliente e do supermercado Construa os modelos representativos das duas situa es e a partir deles fa a suas an lises 51 O processo de produ o de um produto constitu do de 3 est gios Em m dia um novo produto come ado no est gio 1 a cada 6 minutos O tempo m dio de processamento em cada est gio dado respectivamente por 3 minutos 2 minutos e 1 minuto Ap s passar pelo 30 est gio o produto inspecionado assuma que isto n o toma tempo 10 dos produtos s o inteiramente reprovados e voltam ao est gio 1 para um completo reprocessamento 20 s o parcialmente reprovados e voltam para o est gio 2 para sofrerem reprocessamento dos est gios 2 e 3 Em m dia quantas unidades do produto est o no sistema Assuma que todos os tempos entre chegadas e de servi o tem distribui o exponencial e que cada est gio seja constitu do de um nico servidor 52 A rede de postos Prod leo combina esta es de abastecimento e de lavagem de autom veis em todo o Grande Rio A Prod leo d uma lavagem
8. o lucro bruto m dio di rio resultante da fabrica o e venda das pe as 191 30 c Quanto tempo em m dia demora para produzir se uma pe a com qualidade A 3 3 dias Processos Estoc sticos e Teoria de Filas 162 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 3 4 5 6 7 2 Lista de Exerc cios de Teoria de Filas Marque V ou F se considerar a afirmativa respectivamente verdadeira ou falsa a A primeira premissa para a exist ncia de um sistema de filas que a capacidade de servi o deve ser em m dia maior do que a demanda pelo servi o muito embora ela possa ser instantaneamente menor b Em um sistema com restri es de tamanho da fila a condi o de estabilidade do sistema de filas que o fator de utiliza o seja menor que 1 c Um processo exponencial de chegadas pode ser caracterizado por um n mero elevado de tempos entre chegadas pequenos e raros os tempos entre chegadas grandes d O modelo de filas que representa um supermercado com 5 caixas onde o processo de chegadas Poisson e servi o exponencial denominado M M 5 e A afirmativa o tempo ocioso do sistema igual a um menos o fator de utiliza o v lida para qualquer sistema de filas f Em um processo Nascimento e Morte para qualquer estado do sistema n n 0 1 2 a taxa m dia n mero de ocorr ncias esperadas por unidade de tempo
9. o pedido de refei o para uma pessoa O tempo m dio de atendimento de uma comanda de 10 minutos e 30 segundos e os fregueses chegam ao restaurante m dia de 5 por hora no hor rio que nos interessa Apesar da boa reputa o da casa a clientela amea a Processos Estoc sticos e Teoria de Filas 170 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP abandon la por causa da demora no atendimento A ger ncia pensa ent o em ampliar a cozinha e colocar outra cozinheira com outra ajudante a Qual o tempo esperado gasto por um cliente no restaurante nas condi es atuais e com a amplia o b Quantos clientes estar o esperando ser atendidos nos dois casos 45 Um caixa de banco trabalha numa ag ncia na qual frequentemente 4 caixas est o em atividade ao mesmo tempo a presen a de mais de destes funcion rio menos frequente Ele foi acometido de uma doen a card aca e o parecer do m dico do banco indicou uma perda de produtividade de 40 ou seja ele teria que passar esta parte do tempo inativo As condi es mais exigentes do trabalho ocorrem exatamente quando h apenas 4 caixas na ag ncia nestes hor rios a experi ncia indica uma demanda m dia pelas caixas de 192 clientes por hora Cada caixa inclusive o pr prio pode atender em m dia 60 clientes por hora Se ele n o puder dispor do repouso necess rio durante o trabalho ter que ser aposentado Qual
10. Day Mo Pos Ms 1 mM Mo 3 Mos 1 Poo Mos Poi Ms Poz Mo 1 mM z m 10 mo l Pio fia Piit Mi Piz mM 1 1 3 mo m 2 ms 1 Pio Mos Pii Mg Piz M 1 1 3 mo m 9 mo 1 Doo Mos Bai Ms Pas mo 1 2 3 m m 13 Classifique os diversos estados das cadeias de Markov a seguir dadas por sua matriz de transi o Calcule as probabilidades estacion rias 0 7 03 0 ai P O0 0 8 0 2 wed OLHO Todos os estados s o recorrentes Processos Estoc sticos e Teoria de Filas 119 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP x 0 17 0 47 x 0 228 T 0 27 0 37 m 0 6 m a m l m 0 1714 1 6 1 3 1 2 e s b P 1 6 1 3 1 2 Doe 1 6 1 3 1 2 N Todos os estados s o recorrentes m 1 6 1 3 1 2 Subcadeia absorvente com estados recorrentes Es 1 4 3 8 3 8 1 c P 0 0 1 d 1 d Estado 1 transiente ch 3 4 A 1 0 R 3 4 3 4 1 Matriz de transi o da subcadeia absorvente 0 1 Zeg m 1 2 P gt 2 3 2 1 0 m m 1 m 1 2 Dado que o estado 1 foi absorvido existe probabilidade de 0 5 de estar no estado 2 ou 3 Processos Estoc sticos e Teoria de Filas 120 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 O 1 2 Sc mig Q o 2 5 0 3 5 Os estados 1 e 3 s o recorrentes e Estado 2 n o absorvente e Nem recorrente Para os estados 1
11. a uma dire o do que outra e assumindo que o b bado em quest o consegue se equilibrar nesse corredor inclinado Sem perder a generalidade imagine que a probabilidade do passo ser para frente igual a p e que a probabilidade do passo ser para tr s igual a q 1 p Como j vimos t DX SE D al n Neste caso se p gt q no tempo t 0 E X gt 0 e crescente com t Ou seja a medida que o tempo passa espera se que o b bado esteja descendo a ladeira Examinando a express o 2n t ela e zero quando 2n t Ou seja podemos entend la como sendo a chance de que metade dos passos seja pra frente e metade pra tr s Fica f cil de ver isso examinando um caso extremo como que essa probabilidade se comporta Para um caso em que p 0 99 e q 0 01 vejam a chance de se andar mais para um lado que para o outro pela express o acima 3 3 PASSEIO ALEAT RIO COM TAMANHO DO PASSO VARI VEL DISCRETE TIME CONTINUOS SPACE RANDOM WALK Reduzindo um pouco nossas suposi es suponha que n o suporemos mais a suposi o de que os passos s o do mesmo tamanho Pra voc que viajou s dissemos que n o tem mais aquela coisa dos passos serem do mesmo tamanho Agora a distribui o do tamanho do passo normalmente distribu da com m dia O e desvio padr o o amp gt N 0 oi Processo Auto regressivo m dia Processos de Revers o a m dia Podemos escrever ainda de forma mais gen rica a posi o do b bado como sendo X 0 0 X
12. o matricial PO gt PD pOD D I Ae onde Di Po Pis P D Po Po P31 P32 P33 Analogamente p 3 Pai para cada i j kes P P P P P PP P De uma maneira geral podemos estabelecer a equa o de Chapman Kolmogorov PO ptb plo Di 7 Seja EA a probabilidade de estar no estado j no instante 1 como mostra a Figura 1 2 estado est gio 1 2 Figura 1 2 Probabilidade de estar no estado j no instante 1 Podemos escrever a D 0 a 0 1 0 P 5P Py tP Py tP Pa p F p p para cada i j ieS Em nota o matricial Processos Estoc sticos e Teoria de Filas COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP p p P p P De uma maneira geral podemos estabelecer o vetor de estado no instante n n Ei p k p p P Processos Estoc sticos e Teoria de Filas 10 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 2 PROBABILIDADE DE PRIMEIRA PASSAGEM E PRIMEIRO RETORNO Seja a igualdade REM sr A o 1 Se zt i a probabilidade de 1 passagem isto a probabilidade de que o processo esteja no estado j no tempo n e n o antes dado que ele estava no estado i no tempo 0 Se j i i a probabilidade de 1 retorno isto a probabilidade de que sejam necess rios n passos at atingir o estado j pela 1 vez dado que o
13. 1 Suponha que os recursos totais do jogador e do seu oponente sejam N Se o capital de qualquer um dos jogadores cair abaixo do ponto em que eles pudessem pagar caso perdessem o jogo seguinte o jogo termina a Desenhe o diagrama de transi o de estados e determine a matriz de transi o b Suponha que os dois jogadores concordem em que se o capital de qualquer dos dois cair para 1 eles far o o pr ximo jogo com chances iguais ganhar o ou perder o 1 com igual probabilidade Desenhe o diagrama de transi o de estados e determine a matriz de transi o para este caso c No caso descrito na letra b suponha que o jogador 1 tem 3 e o jogador 2 tem 2 qual a probabilidade do jogador 1 ganhar o jogo d Quantas jogadas durar o jogo 24 Perfura se um po o e medida que a perfura o avan a uma s rie de perfis s o realizados Suponha que o po o possa ser classificado em quatro estados rotulados como se segue Em curso Com desvio ligeiro Com desvio acentuado Abandonado por estar t o fora de curso que n o se consegue mais atingir o alvo Suponha ainda que Xn represente o estado do sistema ap s a n sima corre o de curso e que o comportamento do po o possa ser modelado por uma cadeia de Markov com a seguinte matriz de probabilidade de transi o Processos Estoc sticos e Teoria de Filas 36 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 0 0 0 P
14. 2 quando est leve permanece leve no minuto seguinte 50 das vezes 3 se est pesado assim permanece no minuto seguinte com 40 de probabilidade 4 se est moderado ent o a probabilidade de permanecer moderado no minuto seguinte depende da intensidade no minuto anterior 20 se estava leve 50 se estava moderado e 30 se estava pesado e 5 quando est moderado passa a pesado no minuto seguinte com probabilidades iguais a 60 se estava pesado no minuto anterior 20 se estava moderado e 60 se estava leve a Defina um processo estoc stico que represente o problema esboce o diagrama de transi es escreva a matriz das probabilidades de transi o e classifique o processo e os seus estados A longo prazo em que propor es do tempo o tr nsito ficar leve moderado e pesado c Em quantos minutos em m dia o tr nsito leve se torna pesado 13 Considere um problema de PL com cinco solu es b sicas vi veis e uma nica solu o tima Assuma que o m todo simplex comece da pior solu o b sica vi vel e em cada pivoteamento exista igual probabilidade de mover para qualquer solu o b sica vi vel melhor Em m dia quantos pivoteamentos ser o necess rios para encontrar a solu o tima do PL Processos Estoc sticos e Teoria de Filas 160 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 14 Um jogador joga um jogo limpo no qual as chances s o 2 contra 1 Em ou
15. 7T p constante com 1 lt p lt 1 T gt passonormalmente distribu dos com m dia zero e desvio o Tomando o valor esperado dessa express o temos E X EI X 7 E X El pE X E r HX Lol l Limite quando t E X gt Processo Estacion rio Antes de voc pensar que nada mais faz sentido porque achamos uma express o que n o depende de t e ainda chamamos de processo estacion rio tendo dito anteriormente que isso n o aconteceria observe que a express o anterior era um caso particular desse Processos Estoc sticos e Teoria de Filas 96 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP caso onde o era zero e o p era um Nesse caso a express o do regime estacion rio d 0 0 Continua n o existindo regime permanente para o personagem em quest o Note se tratar de um Processo Aleat rio de Tempo Cont nuo com as seguintes propriedades A Propriedade de Markov falta de mem ria valor futuro s depende do estado atual B Se realiza a incrementos Independentes a distribui o de probabilidades de uma mudan a no processo em um dado intervalo de tempo independente de qualquer outro intervalo sem superposi o de tempo C A probabilidade de uma transi o em um intervalo finito de tempo normalmente distribu da com uma vari ncia que aumenta linearmente com o intervalo de tempo Essas propriedades s o algumas ca
16. Al m de descrever com boa aproxima o diversas situa es pr ticas os processos de Poisson incorporam facilidades no tratamento matem tico proporcionadas pela falta de mem ria da distribui o exponencial As distribui es de Erlang e hiperexponencial s o tamb m bastante utilizadas Modelos mais complicados envolveriam poss veis depend ncias entre as chegadas como por exemplo a situa o onde uma chegada de certo tipo aumentaria ou diminuiria a chance de ocorr ncia de outro tipo de chegada As chegadas mencionadas acima podem ser unit rias ou em um bloco batches Neste caso al m do tempo entre chegadas tamb m o tamanho dos blocos aleat rio Por exemplo em aeroportos internacionais a chegada de passageiros de um certo v o ao posto alfandeg rio se d em bloco onde o tamanho do bloco a lota o do avi o Existem situa es em que as chegadas dependem do n mero de usu rios no sistema podendo at ocorrer a situa o em que uma chegada n o se junta fila Isto pode ocorrer por decis o do usu rio ou por limita o no espa o para espera O caso cl ssico conhecido como sistema com perda loss system originou se do estudo de tr fego telef nico onde o usu rio completa a cnamada ou obt m sinal de ocupado e exclu do do sistema Chegadas com usu rios impacientes que abandonam a fila ap s algum tempo de espera podem tamb m ser modeladas b Servi o Da mesma forma que o processo de cheg
17. FLUXO QUE SAI FLUXO QUE ENTRA Para an lise atrav s da Lei de Conserva o de Fluxo consideremos a Figura 1 6 abaixo 1 2 Q 1 2 2 1 3 ne Figura 1 6 Exemplo Lei de Conserva o de Fluxo Processos Estoc sticos e Teoria de Filas 13 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A matriz P de probabilidades de transi o de estados para este exemplo encontra se descrita a seguir EN Za gek dd E ES A RE E a n fem enem 2 2 3 3 Conserva o do fluxo wa a PART e T pp pj SE CR RRE 3 3 pa 1 311 2 3 I 1 21 1 311 1 31 combina o linear 1 20 1 31 IL IL II 1 IL 0 323 Resulta em T 0 387 TL 0 290 Processos Estoc sticos e Teoria de Filas 14 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 5 TEMPO M DIO DE 1 PASSAGEM RECORR NCIA Seja Ni vari vel aleat ria que representa o n mero de est gios necess rios para atingir j pela 1 vez partindo der PIN n e distribui o do tempo de 1 passagem 1 retorno nm E N gt nf n 1 e 1 retorno i j JI j fra o do tempo que o processo passa no estado j mj 1 II o per odo m dio entre a ocorr ncia de j e Tempo m dio de 1 passagem i j Condicionado ao estado no est gio 1 mi 1 com probabilidade p Mi 1 M com probabilidad
18. FO 10 2 6 56 h FO 10 2 10 8 30 h 11 Modele usando teoria de filas um sistema em que o servi o tomar sol na praia Considere que as chegadas a praia seguem um processo Poisson de taxa e que o tempo que cada pessoa passa na praia aleat rio podendo ser aproximado por uma distribui o exponencial com m dia 1 u a Desenhe o diagrama de transi o de estados b Obtenha as equa es de recorr ncia n S X Ae c Calcule P sugest o o ae n 0 M d Obtenha L Ly W Wg A A OROS oS a tt IN e q a en Onde n n mero de pessoas na praia A Taxa m dia de chegada nu Taxa m dia de pessoas na praia A 0 Ap UP D eh Processos Estoc sticos e Teoria de Filas 149 c d COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 1 Ap Jup gt P Pi Po 2 u 2u A 2 AP 3Up gt P auf ae Po A n Apa D Pa Pai a Po DU n u P_ 2 P Pod p F al 1 Como 3 gt e n 0 n o l P Logo De zl Po Du e NE pe 12 An lises anteriores indicam que a chegada de clientes em uma dada ag ncia dos correios segue uma distribui o exponencial com m dia de 30 chegadas por hora Voc esta fazendo um levantamento na ag ncia e na presente hora j decorridos 15 min j chegaram 10 clientes Quantos clientes voc espera que ainda cheguem na presente hora Justifique
19. O sapo circula entre estas 4 plantas pulando de uma para outra as quais s o numeradas arbitrariamente de 1 a 4 A probabilidade do sapo pular de uma planta para outra inversamente proporcional a dist ncia entre elas isto o sapo prefere pular para uma planta mais perto do que para uma mais longe As dist ncias entre as plantas s o 2 3 4 6 5 2 3 2 2 6 7 1 2 3 3 4 Processos Estoc sticos e Teoria de Filas 34 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP a Defina a matriz de transi o b Calcule as probabilidades de regime permanente c Interprete estas probabilidades em termos do comportamento do sapo d Explique do ponto de vista do sapo o que significam as hip teses de Markov e de estacionariedade 19 Se segura Companhia de Seguras classifica seus clientes de acordo com seu hist rico de acidentes do cliente Um cliente que n o tenha tido nenhum acidente nos ltimos dois anos tem uma anualidade de 100 Clientes que tenham tido acidentes em ambos os anos tem uma anualidade de 400 Clientes que tenham tido acidente em somente um dos ltimos dois anos tem uma anualidade de 300 Um cliente que tenha tido um acidente no ltimo ano tem 10 de chance de ter um acidente no ano corrente Se o cliente n o tiver tido nenhum acidente no ltimo ano ele tem 3 de chance de ter um acidente no ano corrente Para um dado ano qual a an
20. Suponha que voc conduziu uma s rie de testes sobre um procedimento de treinamento e verificou que a seguinte matriz de probabilidades descreve o conjunto de respostas corretas e incorretas i 1 simo teste Correto Incorreto j simo Correto 0 95 0 05 teste Incorreto 0 01 0 99 a Que propor o de respostas corretas se pode esperar de um estagi rio absolutamente treinado b Que propor o de respostas corretas se pode esperar de um estagi rio ap s quatro repeti es do procedimento caso a resposta inicial seja igualmente poss vel de ser correta ou incorreta c Qual a probabilidade de que se obtenha pela primeira vez uma resposta correta exatamente quatro tentativas ap s uma resposta incorreta d Qual o n mero m dio de tentativas para que se obtenha uma resposta correta ap s ter obtido uma resposta incorreta 0 01 MET aa emite E 0 05 a 095 0 05 7 0957 00l7 70 1 6 0 01 0 99 m 5 6 To m 1 Propor o esperada de respostas corretas de um estagi rio Processos Estoc sticos e Teoria de Filas 132 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP absolutamente treinado ac 1 6 16 67 b ps po po 0903 0 097 0903 0 097 08173 0 1827 00194 0 9806 00194 09806 Tome 0 9634 0 8173 0 1827 49 vill PO 0 5 0 5 Pe E l l 0 0365 0 9634 0 4269 0 5731 Propo
21. apresentem as seguintes propriedades Processos Estoc sticos e Teoria de Filas 7 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 Um n mero finito de estados 2 A propriedade markoviana 3 Probabilidades de transi o estacion rias 4 Um conjunto de probabilidades iniciais P X 1 para todo i 1 2 1 PROBABILIDADE DE TRANSI O EM V RIOS EST GIOS A exist ncia de probabilidades de transi o estacion rias em um est gio tamb m implica que para cada je n n 0 1 2 PIX an J X i PIX jJ lX i para todos fl Estas probabilidades condicionais s o usualmente denotadas por pj e s o chamadas de probabilidades de transi o em n est gios Os processos com essas caracter sticas s o tamb m chamados de processos homog neos no tempo ps Gi A matriz que armazena as probabilidades de transi o em n est gios denotada por PO p Seja pj a probabilidade de transi o do estado i para o estado j em 2 est gios como mostra a Figura 1 1 a seguir estado est gio 1 2 Figura 1 1 Probabilidade de Transi o do estado i para o estado j em 2 est gios Podemos escrever 2 a a a a a a Pj SPa Py TDR Pa tP Pj prs gt p Py para cada i j k i z j Processos Estoc sticos e Teoria de Filas 8 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Em nota
22. e Para sistemas cuja altera o de estado se de por acr scimo de 1 cliente EE t P D Isto o n mero de clientes encontrado na chegada igual ao n de clientes deixados por uma sa da e Probabilidade de Transi o da Cadeia de Markov Sejam q N de clientes deixados no sistema pela partida det V n de clientes que chegaram durante a execu o do servi o de C que tem n dura o Xn Servidor Ch Ch 1 Figura 2 17 Probabilidade de Transi o da Cadeia de Markov 1 Processos Estoc sticos e Teoria de Filas 72 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP q i P Plo j Dado que a d imposs vel d z dni A P O O q a 0o 0 0 o O 0 0 0 Onde o PV k Vn depende da dura o de X e n o de n em regime estacion rio Plx lt x P x lt x B x Ph k pb EL PV k a f Pf k x lt X lt x dxhx Pf k X x x dx Para chegadas Poisson a X PV k a Eau Sejam p Axe p lt 1 condi o de ergodicidade Equa o fundamental da M G 1 Servidor Ch Cn 1 Figura 2 18 Probabilidade de Transi o da Cadeia de Markov 2 Processos Estoc sticos e Teoria de Filas 73 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP a Jtuuge d zU d Vau se q 0 1 se gt 0 Ag fa O se ost
23. est expandida em uma s rie de pot ncias de Z isto se x z le n 0 ent o X n o coeficiente de Z y por conseguinte os valores de X n podem ser encontrados por inspe o para n 0 1 2 c Exemplo 3 Ache X n para n 0 1 2 3 4 quando Kik Z E SC 0 2 Solu o Dividindo o numerador pelo denominador obt m se Processos Estoc sticos e Teoria de Filas 86 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP x 2 102 17Z 18 42 18 682 Ao comparar esta expans o X Z em uma s rie infinita S x z n 0 obt m se X 0 0 X 1 10 X 2 17 X 3 18 4 X 4 18 68 Na maioria dos casos n o t o simples identificar o t rmino geral mediante a observa o de alguns valores da sequ ncia O m todo mais utilizado a decomposi o em fra es parciais de X Z Em vista da unicidade da transformada Z pode se utilizar a tabela de similaridades de transformadas para identificar as sequ ncias correspondentes d Exemplo 4 Encontre a transformada inversa de Pad A z 2 2 1 atrav s do m todo de expans o em fra es parciais x z Solu o Expandindo em fra es parciais tem se que 4 3 1 2 2 Gu GC Usando una tabela de transformadas tem se X n 9n2 2 3 para n 0 1 2 x z Processos Estoc sticos e Teoria de Filas 87 COPPE Universidade Federal do Rio de Janeir
24. n o h limite na sala de espera e o atendimento na ordem de chegada Por outro lado a fila G E2 3 15 tem chegadas seguindo uma distribui o geral m a Ei g Processos Estoc sticos e Teoria de Filas 42 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP o servi o segue a distribui o de Erlang 2 existem 3 servidores a capacidade m xima do sistema 18 note que a fila m xima tem comprimento 15 e como nada foi mencionado a disciplina de atendimento FCFS De forma resumida ent o podemos apresentar o seguinte formato A B c onde A representa a distribui o de chegadas B representa a distribui o do servi o e c indica o n mero de esta es de servi o Como a distribui o de Poisson inclui as propriedades do processo Markoviano a nota o usada para A e B M quando temos um processo de Poisson 2 1 4 TERMINOLOGIA E NOTA ES A menos que seja dito o contr rio as seguintes nota o e terminologia padr es ser o usadas deste ponto em diante Tabela 2 1 Terminologias usadas em Teoria das Filas Estado do Sistema N mero de clientes no sistema de fila N mero de clientes esperando um servi o ou estado do sistema Comprimento da Fila f menos o n mero de clientes sendo servidos N t N mero de clientes no sistema de fila no tempo t t gt 0 Probabilidade de que exatamente n clientes estejam no sistema de fila no tempo t dado
25. o ou ent o usar uma m quina autom tica No balc o s podem ser atendidos em m dia 180 pessoa por hora enquanto a m quina pode atender exatamente 4 pessoas por minuto A cada hora 270 pessoas em m dia procuram o bar para tomar caf a probabilidade de uma pessoa preferir o balc o de 0 6 Qual a demora m dia de uma pessoa que procura o bar desde que entra at ser servida de caf 162 o Ri u 180 com h Pe MM gt We ER po MA io w u 240 com h Pu gt M D 1 gt Wu W 0 6 Wg 0 4 Wum IDA u A 180 162 Balc o W 0 0555h 3 minutos 20 segundos M quina L gt L gt W MIDI p 0 045 2 2 L p 0 43 0 184 pessoas 1 2 l p 2 1 0 45 L L SS 0 184 0 45 0 634 A Wy 0 00587 horas 21 segundos W 0 6 0 0555 0 4 0 00587 0 0357 horas W 2 minutos 8 segundos 3 Uma frota de traineiras consome gelo para conservar o peixe durante o tempo passado no mar O gelo vem em camionetas que transportam 1 tonelada cada 50 barras e que no dia da entrega chegam raz o de 5 por hora em m dia O pessoal encarregado da descarga tira 1 barra a cada 12 segundos em m dia O gelo custa 20 a tonelada e no ver o a perda devida ao derretimento de cerca de 1 quilo por minuto e por tonelada de gelo Qual o custo esperado do gelo que chega a ser embarcado A 5 camionete hora Processos Estoc sticos e Teoria de Filas 141 COPPE Universidade Federal do Rio de Janeiro Programa de Enge
26. o 0O 4 0 v50 0 o io 0 0 1 1 428 0 408 0 571 0 142 0 082 0 204 E I1 0 nee 0 1 428 O O 0 285 0 714 a Probabilidade de que uma rvore com menos de 3m morra antes de ser vendida a 3m 0 571 57 b Valor esperado de venda se uma rvore com menos de 3m plantada Vesp 20 0 142 30 0 082 50 0 204 15 50 1 3 CADEIA DE MARKOV EM TEMPO CONT NUO Uma cadeia de Markov em tempo continuo e como a designa o indica uma cadeia de Markov em que a vari vel tempo continua representando instantes ou momentos de Processos Estoc sticos e Teoria de Filas 19 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP tempo e n o per odos de tempo como para as cadeias em tempo discreto Assim uma cadeia de Markov em tempo continuo um processo estoc stico DO t gt 0 com a propriedade de Markov ou seja a propriedade de estar no estado j num momento futuro depende apenas do estado presente e n o dos estados visitados em qualquer momento passado Considerando a Gr fico 1 1 abaixo temos estado Gr fico 1 1 Processo de Markov em Tempo Continuo 0 t A na a i p P A processo homog neo probabilidade que o sistema esteja no estado j no instante t dado que ele estava no estado ino instante O bg oli No exemplo temos Polt Polt P S GE num Suposi es e O processo satisfaz a propriedade de Markov
27. ou com i unidades dada por P quando n gt 17 Uma loja de m quinas fotogr ficas estoca um modelo de m quina fotogr fica particular que pode ser encomendado semanalmente Sejam D Ds Dj vari veis aleat rias que representam a demanda pelas m quinas durante a semana i Seja X o estoque existente de m quinas e X o n mero de m quina dispon veis ao final da semana i S bado noite a loja faz uma encomenda que ser entregue em tempo para a abertura da loja na 2 feira A pol tica de encomendas da loja s S 1 3 ou seja se no S bado a noite a quantidade de m quinas em estoque for menor que s 1 nenhuma m quina em estoque ent o a loja encomendar at S 3 m quinas caso contr rio nenhuma m quina ser encomendada suposto que haja perdas de vendas quando a demanda exceder o estoque dispon vel As vari veis aleat rias podem ser avaliadas iterativamente pela express o _ maxi 3 D Ojsex lt 1 max X D O seX gt 1 Considerando que a demanda tem uma distribui o de Poisson com m dia 1 a matriz de transi o de uma etapa dada por 0 080 0 184 0 368 0 368 0 632 0 368 0 0 Po 0 264 0 368 0 368 0 0 080 0 184 0 368 0 368 a Descreva como a matriz de transi es pode ter sido obtida b Se o processo iniciou com um estoque de 3 m quinas qual o tempo esperado para que o estoque se esgote c Qual a probabilidade de encontrar o estoque com 0 1 2 3 e 4 m
28. 08 Au tm 1 Ty 4 5 Quantidade de Mharba comprada por ano Nm N TM 4 16 bilh es Lucro obtido Lu Nm 2 1 500 milh es 3 66 bilh es Como Ly gt Ly ent o vale a pena contratar a empresa de propaganda Processos Estoc sticos e Teoria de Filas 112 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 07 Uma companhia com um v o s 7h45 da manh entre Rio e Bras lia n o quer que o v o se atrase dois dias seguidos na mesma escala Se o v o sai atrasado um dia a companhia faz um esfor o especial no dia seguinte para que o v o saia no hor rio e obt m sucesso em 90 das vezes Se o v o n o saiu atrasado no dia anterior a companhia n o toma provid ncias e o v o sai como escalado em 60 das vezes Que percentual de vezes o v o sai atrasado Qual o tempo m dio entre dois v os no hor rio 0 9 q Se CET OO 0 4 09 Tir 0 4 Ty z Tar 4 13 T 9 13 Tar tiy 1 Percentual das vezes que o v o sai atrasado nar 4 13 30 8 Tempo m dio entre dois v os no hor rio tempo m dio de 1 retorno MHH 1 nH 13 9 1 44 dias 08 A baco sistemas de computa o registra a cada semana uma demanda equiprov vel de 1 ou 2 de seu modelo A500 Todos os pedidos devem ser atendidos do estoque existente Duas pol ticas de estoque est o sendo consideradas Pol tica I Se o estoque de 2 ou menos unidades coloca se um pedido de forma que
29. 1 2 1 4 1 4 0 0 1 2 1 4 1 4 0 0 0 1 a Se o po o come ou com um desvio ligeiro qual a probabilidade de que ele eventualmente entre em curso b Se o po o tem chances iguais de come ar com desvio ligeiro e acentuado qual a probabilidade de que ele eventualmente entre em curso 25 Na teoria de an lise de cr dito determinados autores verificaram que a estimativa dos valores considerados como devedores duvidosos costuma seguir dois passos b sicos descritos a seguir Classificam se as contas por idade que refletem o estado em que a conta se encontra um m s de atraso dois meses de atraso etc Estima se uma expectativa de perda para cada estado geralmente com base na pol tica da empresa situa o econ mico financeira do cliente e outros fatores relevantes para a an lise do cr dito O segundo t pico merece uma an lise mais detalhada sendo que atualmente diversos m todos principalmente na rea de econometria est o sendo desenvolvidos Entretanto poss vel desenvolver um m todo para estimar a probabilidade de devedores duvidosos com base nas Cadeias de Markov atrav s do atraso e da inadimpl ncia existente para uma determinada carteira de cr dito de uma institui o financeira Se em uma determinada data fizermos um levantamento de uma carteira de cr dito poderemos facilmente verificar os seguintes estados das contas em carteira Au valores a serem recebidos que ainda n o venceram ou seja est o em dia o
30. 2 25 pessoas 0 2 litros 1h x litros 2 25h x 0 45 litros consumo individual Consumo total 0 45 2 25 1 0125 litros 20 Um mec nico de manuten o de m quinas de c pia eletrost tica trabalha por contrato para a Prefeitura Ele pode consertar em m dia 3 m quinas por dia e o Processos Estoc sticos e Teoria de Filas 154 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP contrato por ele assinado prev que todo chamado seja atendido no mesmo dia com 90 de certeza Qual a capacidade mensal do servi o com este padr o de atendimento u 3 m quinas dia p E gt 0 9 gt 2 7m quinas dia u p 0 9 L L L L gt L 0 9 m g 23 dias teis 20 7 21 mag m s L W L 1 a u A 3 2 7 03 deoi Ap 2 7 0 9 s wie 3 01 8 Im quinas 21 Uma loja de autope as tem estacionamento com espa o para 10 carros Os carros chegam segundo um processo Poisson a uma m dia de 10 por hora Sabe se tamb m que o tempo que eles permanecem estacionados tem distribui o exponencial com m dia de 10 min Determine c O n mero m dio de vagas ociosas no estacionamento d A probabilidade de um carro que chegue n o encontre lugar para estacionar x Sugest o Para valores de k grandes use Es ST n on A 10 carros hora u 10carro 10 minutos 6 carros hora ei Let CO Ti ob Processos Estoc sticos e Teoria de Filas 1
31. 23 17 5 clientes hora 24 W 4 horas 25 a 12min b 3 pessoas 26 51 9 27 3 3 frascos 28 Pa l p 1 p po pop 29 3 8 dias 30 a 16 7 b 8 c 3 4min 31 b 12 c infinito c Processo Poisson 32 a 8 pessoas b 2h 40 min 33 4 bombas C 3 175 861 704 C 4 121 254 600 34 35 36 1 5 clientes 12 5 min 37 64 fiscais 38 14 min Processos Estoc sticos e Teoria de Filas 176 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 39 b 2h 45 c 3h 50 40 1 41 25 58 h 42 a 1 96 carros b 5 86 43 11 caixas 44 a 1 4h e 0 24h b 6 125 clientes e 0 325 clientes 45 Aposentar o caixa pois um caixa passa ociosa 22 do tempo 40 46 47 a 2 5 clientes b 97 45 clientes c 65 cl h Processos Estoc sticos e Teoria de Filas 177 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP FORMUL RIO DE TEORIA DE FILAS F rmulas Gerais L 2W DnP Lg AWg Xn s P W W A DmPh u 2uP Dr AS F rmulas M M 1 Pn 1 p p L p 1 p W u 2 F rmulas M G 1 Po 1 p Lg 120 p 2 1 p F rmula Erlang La k 1 2k p 1 9 F rmula M M S Onde DU gt s dado pela tabela abaixo _P j2s q sUu p S 2 S 3 S 4 S 5 S 6 S 7 0 10 0 02 0 00 0 00 0 00 0 00 0 00 0 20 0 07 0 02 0 00 0 00 0 00 0 00 0 30 0 14 0 07 0 04 0 02 0 01 0 00 0 40
32. 3 Naa 1 2 Ss 6 5 2 5 1 3 1 3 2 5 3 5 3 5 6 5 0 1 2 1 5 4 5 a a 0 r Probabilidade do disco ficar com D dado que estava com C acp 4 5 Probabilidade do disco ficar com B dado que estava com A aag 2 5 16 Considere um jogador que a cada lance de um jogo tem uma probabilidade p de ganhar uma unidade e probabilidade q 1 p de perder uma unidade Assumindo que sucessivos lances s o independentes qual a probabilidade que come ando com i unidades a fortuna do jogador alcance n antes de chegar a 0 p p p p p p p p Se i 0 gt Po 0 Se i n 5 P 1 D ain probabilidade do processo ser absorvido em n dado que come ou em i Pa 5 p l Ps E Se Eid pP qP pP qP ED Pi Pu P 1 P S Processos Estoc sticos e Teoria de Filas 124 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Ent o para i 1 P p 2 p P Lp P 4 D 2 i 2 P Pp 2 P VER P P P Somando as linhas acima para i variando de 1 a i 1 temos de Wa A se 1 z1 p 1 p p iP se L 1 P Somando as linhas acima para i variando de 1 a n 1 temos a e Como P e e pl p 1 a p 2 1 l See n 2 Processos Estoc sticos e Teoria de Filas 125 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Logo Lais p di a p t se Se n 2 A probabilidade de ganhar o jogo dado que come
33. 79 2 6 1 FUN O GERADORA DE MECHER Eeer eege dae 79 2 6 2 PROPRIEDADES DA FUN O GERADORA DE MOMENTOS 81 Processos Estoc sticos e Teoria de Filas 2 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 6 3 TRANSFORMADA 2 iimesessesiaesesaeasarierineerseseseentasaeraresne care neaaaasasesesaaa o 83 EXERCICIOS PROPOSTOS DE TEORIA DAS FILAS ee 88 3 MOVIMENTO BROWNIANO ecrreeerereeerereeeememe me cecenenereeraranareseenema sa cececeneneerenanananeo 94 3 1 PASSEIO ALEAT RIO DISCRETO DISCRETE TIME DISCRETE STATE RANDOM MALI srs cassia e SS E a ST iiS 94 3 2 PASSEIO ALEAT RIO COM DESVIO DISCRETE RANDOM WALK WITH DEVIATION ses a pn E E RU E 95 3 3 PASSEIO ALEAT RIO COM TAMANHO DO PASSO VARI VEL DISCRETE TIME CONTINUOS SPACE RANDOM WALK een 96 3 4 PROCESSO DE WIENER ii erererereeeememe merece ceeneererereenee manera see aenas 97 3 5 GENERALIZA O PROCESSO DE WIENER COM DESVIO nn 98 3 6 REPRESENTA O DO MOVIMENTO BROWNIANO POR PASSEIO ALEAT RIO 99 4 REFER NCIAS BIBLIOGR FICAS ee 102 5 LISTA DE EXERCICIOS RESOLVIDOS DE PROCESSOS ESTOCASTICOS 104 6 LISTA DE EXERCICIOS RESOLVIDOS DE TEORIA DAS FILAS 140 7 Lista de Exerc cios Complementares cinssrrasernesecenosereasananasennasecensseneasanananas 158 Processos Estoc sticos e Teoria de Filas 3 COPPE Universidade Federal do Rio de
34. Az z Eq Transformada de P K para MIG 1 Para o caso MIMI b x ge B s z LEE DEZ D B A Ag z EE O o 5 Z Plg k P 1 p Processos Estoc sticos e Teoria de Filas 71 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP e MI G 1 gt Distribui o do tempo de espera S s P s oi AB S s A Wie Cais AB s s 4A Para MIMI B s a S u SO S u 4 e Distribui o do per odo ocupado O servi o n o terminado no sistema no tempo t ou O tempo necess rio para esvaziar o sistema de todos os clientes presentes no instante t Servidor conservativo sistema permanece ocupado enquanto houver cliente no sistema e os clientes s partem do sistema quando o mesmo estiver completamente servido Para sistema conservativo Au independente da disciplina do servi o F y distribui o do per odo ocioso G y distribui o do per odo ocupado MII gt F y 1 e tempo de chegada exponencial G s gt TC per odo ocupado G s B s A A G s Processos Estoc sticos e Teoria de Filas 78 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 6 Anexo 2 6 1 FUN O GERADORA DE MOMENTOS Nesta se o ser introduzido um importante conceito matem tico que possui muitas aplica es aos modelos probabil sticos Para um desenvolvimento rigoroso do assunto seria necess rio u
35. Explique o que um processo estoc stico a Estacion rio e b Markoviano Quatro cidades s o ligadas por uma sistema vi rio esquematizado na figura abaixo Existe no sistema um conjunto de N carros Cada manh um carro que chega na cidade na noite anterior carregado e despachado sua rota escolhida com igual probabilidade entre todas as rotas que deixem a cidade independentemente do que acontece com os demais carros Encontre a propor o aproximada de carros que estar o em cada cidade em cada noite Qual o tempo m dio que um carro demorar a retornar a cada cidade visitada 4 3 1 Idem com 5 cidades 2 4 2 5 3 Um modelo unidimensional de uma part se movendo em uma caixa com paredes el sticas consiste dos seguintes estados CN N 1 1 0 1 2 N Se a part cula n o est em um dos n s extremos ent o ela se move para a esquerda ou direita com probabilidade Lo Se ela est em um dos estados extremos ent o ela se move com probabilidade 1 para o estado anterior Encontre as probabilidades estacion rias de distribui o Uma m quina pode estar em dois estados funcionando ou quebrada Quando funciona d um lucro de 480 por per odo e quando est quebrada as despesas s o de 160 por per odo Considerando a situa o de regime permanente Funcionando Quebrada Funcionando 0 8 0 2 Quebrada 0 6 0 4 a Calcule o ganho m dio por per odo b Verifique se um plano de manuten
36. Janeiro Programa de Engenharia de Produ o PEP 1 PROCESSOS ESTOC STICOS 1 1 DESCRI O E DEFINI O DE PROCESSOS ESTOC STICOS Segundo Lieberman um processo estoc stico uma cole o de vari veis aleat rias indexadas X onde t um ndice definido num conjunto T Assim um processo estoc stico a descri o de um fen meno aleat rio que varia com o tempo O processo estoc stico X X X pode representar a cole o das quantidades de carros que passam por um determinado ponto de uma rodovia a evolu o dos n veis de estoque semanais de uma firma o comportamento de uma part cula de g s varia es nas qualidades dos produtos varia es nos pre os de a es vendas numa determinada loja evolu o do n mero de desempregados num determinado pa s etc O processo estoc stico Y Y Y representa a evolu o populacional brasileira desde o ano de 1998 como mostra a Tabela 1 1 Tabela 1 1 Evolu o populacional brasileira 1998 1999 2000 2001 2002 Habitantes 161 790 311 163 947 554 169 590 693 172 385 826 174 632 960 Fonte Denatran Os valores assumidos por um processo estoc stico s o denominados estados e o conjunto de todos os estados poss veis dito espa o de estados 1 1 1 PROCESSO ESTOC STICOS CONT NUOS DISCRETOS Os processos estoc sticos podem ser classificados como a Em rela o ao Estado Estado Discreto cadeia X t definido sobre um
37. Markovianos e pode ser verificada para sistemas mais gerais Supondo que seja uma constante para todo n Num processo de fila em estado de equil brio foi provado que L AW Al m disso a mesma prova tamb m mostra que LA Wa Processos Estoc sticos e Teoria de Filas 44 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Se os n o forem iguais ent o poder ser substitu do nestas equa es por a taxa m dia de chegada a longo prazo Supondo agora que o tempo m dio de servi o seja uma constante 1 u para todo n gt 1 Segue ent o que W W 1 u Estas rela es s o extremamente importantes porque permitem que todas as quatro quantidades fundamentais L W Ly W sejam imediatamente determinadas assim que uma delas seja encontrada analiticamente Isto muito bom porque algumas destas quantidades frequentemente s o muito mais f ceis de encontrar que outras quando estamos resolvendo um modelo de fila a partir de princ pios b sicos 2 1 6 EXEMPLOS DE SISTEMAS DE FILAS REAIS Uma classe importante dos sistemas de filas que todos n s encontramos em nossas vidas di rias a dos sistemas de servi o comerciais onde os clientes recebem servi os de organiza es comerciais Muitas destas organiza es envolvem servi os de pessoa a pessoa num local fixo tal como uma barbearia os barbeiros s o os servidores servi o de caixa no banco as caixa
38. Obs Desenvolva a partir do diagrama de transi o de estados as express es necess rias para a solu o do problema 454 r P Sistema 0 1 ad E P Sistema 0 1 2 3 1 1 p 4 c P Sistema 0 5 3 gt u SG O SERGE Cliente perdido clientes que chegam quando o sistema est cheio a Ap up gt De tpl SIE 1 A A 1 12 P A E ie 42 86 dos clientes potenciais desistem A u 11 47 7 43 Processos Estoc sticos e Teoria de Filas 145 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b c 0 APo UP 1 A PtHP 2 A Pot 4P 3 AP H4P P P Po STEE Up Ap A P Po A A Hope Dy A A A 3 La D rh H H B l o p p 1 gt P 0 3657 27 Pil gt gt gt 1 0 3657 16 Bm BA P 0 1543 ie 15 43 s o perdidos n 0 De 5 1 p 0 3041 gt P p 24 0 3041 z 1024 P 0 0722 ie 7 22 s o perdidos 8 Uma empresa de nibus envia seus nibus para manuten o de rotina a cada 25 000 Km A garagem fica aberta 24 horas por dia atendida por um nico funcion rio o qual capaz de revisar um nibus de cada vez O tempo que ele gasta exponencialmente distribu do com uma m dia de 4 horas Os nibus chegam garagem segundo um processo de Poisson a uma taxa m dia de 12 por dia Os motoristas entretanto s o instru dos a n o entrar na garagem se l j existirem quatro ou mais
39. Programa de Engenharia de Produ o PEP Mz t Mx t My t exp 44t 07 exp ut 054 exp 44 tu 0 07 Isto representa a fgm de uma vari vel aleat ria normalmente distribu da com valor JA b H 2 Z deg esperado 44 44 e vari ncia O to Portanto Z ter uma distribui o normal Ver Teorema 3 Teorema 4 Sejam X4 Xn Vari veis aleat rias independentes Suponha que X tenha distribui o de Poisson com par metro a a4 An Teorema 5 Suponha que a distribui o de X X sejam vari veis aleat rias independentes Sya 2 2 E S X X X ter distribui o de Xi cada uma com distribui o N 0 1 Ent o Teorema 6 Seja Z X X onde X s o r vari veis aleat rias independentes e identicamente distribu das cada uma com distribui o exponencial de mesmo par metro a e r Ent o Z ter uma distribui o gama com par metro a e r Considera es Finais A fgm constitui um poderoso instrumento muito poderoso para estudo de v rios aspectos das distribui es de probabilidades O emprego muito til no estudo de somas de vari veis aleat rias independentes e identicamente distribu das e na obten o de v rias regras aditivas 2 6 3 TRANSFORMADA Z Esta se o tem a finalidade de resumir alguns conceitos de Transformada Z necess rios aos estudos de Teoria das filas A transformada Z desempenha para processos discretos o mesmo papel que a transformad
40. a qual envolve 3 semanas de aprendizagem pr tica Pelas experi ncias anteriores a companhia espera que somente 60 dos candidatos da fase te rica passem para a fase pr tica com os 40 restantes sendo desligados do programa de treinamento Dos que fazem a parte pr tica 70 s o graduados como supervisores 10 enviados para repeti la e 20 dispensados a Desenhe o diagrama de transi o de estados b Quantos supervisores pode a companhia esperar formar de seu programa normal de treinamento se existem 45 pessoas na fase te rica e 21 na fase pr tica 10 No instante 0 eu tenho 1 Nos instantes 1 2 3 eu jogo um jogo no qual eu aposto 1 A cada lance tenho uma probabilidade p de ganhar 1 e probabilidade q 1 p de perder 1 Meu objetivo aumentar meu capital para 4 e t o logo eu o consiga eu saio do jogo assim como se eu ficar sem nenhum dinheiro a Construa a matriz de probabilidades de transi o e o diagrama de transi o de estados para a cadeia de Markov que modela o jogo b Ap s 2 jogadas qual a probabilidade que eu tenha 2 E 3 c Porque n o razo vel para este jogo falar em probabilidades de regime permanente 11 O livro de did tico PO A Solu o vende 1 milh o de exemplares a cada ano Alguns dos leitores conservam o livro enquanto outros vendem o livro de volta para a livraria Suponha que 90 de todos os estudantes que compram um novo livro o vendam de volta que 80 dos estudantes que com
41. ao jogador Il se der coroa o jogador Il que paga R 1 ao jogador Considere que a quantidade total de dinheiro em jogo isto a soma das quantias possu das pelos dois jogadores de R 5 Modele o jogo como uma cadeia de Markov Dado que o jogador come ou o jogo com R 3 calcule o tempo esperado do jogo e a probabilidade de que cada um dos jogadores ven a o jogo isto alcance R 5 15 Quatro meninos A B C e D brincam de lan ar disco Se o menino A recebe o disco lan a o para B C ou D com iguais probabilidades se C recebe o disco lan a o para A ou D com iguais probabilidades se B ou D recebem o disco ficam com o mesmo Modele o problema como uma cadeia de Markov Desenhe tamb m o diagrama de transi o de estados a Se o disco est com C qual a probabilidade de D ficar com o disco b Se A est com o disco qual a probabilidade do disco terminar com B Processos Estoc sticos e Teoria de Filas 33 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 16 Considere um jogador que a cada lance de um jogo tem uma probabilidade p de ganhar uma unidade e probabilidade q 1 p de perder uma unidade Assumindo que sucessivos lances s o independentes qual a probabilidade que come ando com i unidades a fortuna do jogador alcance n antes de chegar a 0 17 Uma loja de m quinas fotogr ficas estoca um modelo de m quina fotogr fica particular que pode ser encomendado sem
42. c as ag ncias banc rias adotaram o sistema de fila nica para o atendimento dos caixas em substitui o ao antigo sistema onde cada caixa tinha sua fila Quais foram as consegii ncias desta mudan a para os clientes Para simplificar considere que as chegadas de clientes podem ser descritas por um processo de Poisson com taxa constante e que os caixas atendem num tempo com distribui o exponencial todos com a mesma m dia Ilustre sua explica o com exemplos num ricos Seja a fila M M 1 0 fila com overflow mostrada na figura abaixo Seja N t o n mero de fregueses no instante t Modele a fila como um processo estoc stico construa o diagrama de transi o de estados escreva o gerador infinitesimal obtenha a distribui o estacion ria Obtenha o empo m dio entre overflows A gt K 0 u E overflow 10 Desenhe o diagrama de transi o de estados para a rede fechada de filas abaixo com 2 clientes D E Ho JL D 11 Quais as condi es para que um sistema de filas permane a est vel Analise as situa es em que o sistema infinito e finito 12 Seja um sistema de filas de servidor nico com processo Poisson de chegadas com taxa m dia e com taxa m dia de servi o Analise o que acontece com o tempo m dio de um cliente na fila e no sistema bem como o n mero m dio de clientes na fila e no sistema quando voc varia a distribui o do tempo de servi o Sugest o A partir do modelo M G 1 a
43. chegada de clientes por segundo igual a um tempo m dio entre chegadas de 1 A segundos e vari ncia 6 igual a 1 12 e Hist ria passada sumarizada N t n de fregueses no sistema no instante t Xo t tempo de servi o j recebido pelo fregu s em servi o no instante t As defini es acima s o necess rias uma vez que a distribui o do tempo de servi o n o necessariamente sem mem ria Neste caso verifica se que o processo aleat rio N t n o um processo Markoviano Entretanto o vetor N t Xo t um processo de Markov e um vetor de estado apropriado para o sistema MI G 1 uma vez que ele sumariza toda a hist ria passada N t Xo t gt Sumariza o passado Cadeia de Markov Processos Estoc sticos e Teoria de Filas 71 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Analisando o sistema nos instantes de partida X o t 0 e Cadeia de Markov embutida nos instantes de partida II I Igualdade entre distribui es estacion rias No modelo M G 1 vale a igualdade entre as distribui es estacion rias em tempo cont nuo e as imersas nos instantes de chegadas e partidas Distribui o do n de clientes no sistema Para obtermos Distribui o do tempo de espera Distribui o do tempo ocupado e Chegadas Poisson P N t k Probabilidade de um cliente que chegue no instante t encontre K clientes no sistema P NG k Pe
44. chegadas desde que os dois sistemas tenham a mesma taxa de servi o por servidor Discuta sistemas de filas onde o servi o seja ficar estacionado Analise os casos onde a popula o e a fila sejam infinitas e finitas e onde o servidor possa ser considerado infinito Deduza explique intuitivamente a express o de Little L AW Esboce num gr fico abaixo a fam lia de curvas P F S p para um sistema de filas M M S Justifique sua resposta Explique as dificuldades para se resolver um sistema de rede de filas explicitando as hip teses adotadas para super las Processos Estoc sticos e Teoria de Filas 163 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 7 8 9 Considere um sistema de fila com um nico atendente com a distribui o de chegadas Poisson com taxa m dia de chegada conhecida Suponha que a distribui o do tempo de servi o desconhecida por m com taxa m dia de servi o u conhecida a Compare o tempo m dio de espera na fila se a distribui o dos tempos de servi o fosse i exponencial ii constante iii Erlang com quantidade de varia o isto o desvio padr o metade entre os casos constante e exponencial b Qual o efeito no tempo m dio de espera na fila e no comprimento m dio da fila se ambos e u s o dobrados e a escala da distribui o do tempo de servi o modificada correspondentemente De h alguns anos para
45. com taxa de chegada um processo de Poisson de taxa Ou ainda Um processo de Poisson com par metro de chegada a um servidor exponencial gera um processo de Poisson de sa da com a mesma taxa Considere a rede de filas da Figura 2 10 Rede de filas Markovianas com 2 esta es Seja d t a fun o de distribui o de probabilidade fdp que descreve o intervalo entre partidas da fila 1 e seja sua transformada de Laplace denotada por D s Quando um cliente sai da fila 1 existem duas situa es poss veis um segundo cliente est dispon vel na fila e pronto para ser atendido ou a fila est vazia No primeiro caso o tempo at que o pr ximo cliente saia da fila 1 ser distribu do exatamente como um tempo de servi o desta fila e neste caso teremos D vain B s Por outro lado se a fila 1 est vazia at a partida do primeiro cliente deve se esperar pela soma de dois intervalos sendo o primeiro o tempo at que o segundo cliente chegue e o pr ximo sendo o tempo de atendimento ou tempo de servi o do segundo cliente como estes dois intervalos s o independentemente distribu dos ent o a fdp da soma deve ser a convolu o das fdp s de cada intervalo Certamente a transformada da soma das fdp s ser o produto das transformadas das fdp s individuais ent o tem se D lee A s B s onde A s tempo at a primeira chegada B s tempo do pr ximo servi o Sabe se que
46. dados de seis faces No primeiro lan amento se tirarmos 7 ou 11 n s ganhamos imediatamente Se tirarmos 2 3 ou 12 perdemos imediatamente Se o resultado do primeiro lan amento for 4 5 6 8 9 10 n s continuamos a lan ar os dados at obtermos um 7 quando perdemos ou at obtermos o mesmo resultado que o primeiro lan amento quando ganhamos Use os seus conhecimentos de Cadeias de Markov para determinar nossa probabilidade de vit ria 04 A Gazeta da Produ o tem as seguintes informa es a respeito de seus assinantes Durante o primeiro ano 20 dos assinantes cancelam suas assinaturas Daqueles que completaram o 10 ano 10 cancelam sua assinatura no 20 ano Daqueles que assinam por mais de 2 anos 4 ir o cancel los durante algum dos pr ximos anos Em m dia qual a dura o de uma assinatura da Gazeta da Produ o Processos Estoc sticos e Teoria de Filas 30 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 05 O tempo em Pedra Azul pode ser descrito como dependente do tempo nos dois ltimos dias pelo seguinte mecanismo i se os ltimos dois dias foram ensolarados ent o existe 95 de chance de amanh tamb m ser ensolarado ii se ontem esteve chuvoso e hoje ensolarado ent o com 70 de chance amanh ser ensolarado iii se ontem estava ensolarado e hoje est chuvoso ent o amanh ser um dia chuvoso com 60 de chance iv se os dois ltimos dias foram chuvosos
47. decis o voc que o gerente da ag ncia tomar a respeito deste funcion rio 46 H uma lei que determina que pessoas idosas devem ter atendimento priorit rio nas ag ncias banc rias O cumprimento rigoroso desta lei obrigaria a n o atender qualquer n o idoso enquanto houvesse pelo menos um idoso na fila No entanto praticamente todas as ag ncias banc rias adotaram um procedimento modificado de atender a lei que consiste em reservar um ou mais caixas para o atendimento especial dos idosos deixando os demais caixas para o atendimento dos outros clientes a Na sua opini o este procedimento atende a lei Porque Suponha que em certa ag ncia chegam em m dia 30 clientes por hora dos quais 30 s o idosos H tr s caixas na ag ncia dos quais um destinado exclusivamente para o atendimento de idosos Os outros dois trabalham no sistema de fila nica O tempo de atendimento m dio de 3 minutos por cliente idoso ou n o b Qual o tempo m dio de perman ncia espera atendimento de um cliente idoso na ag ncia E de um cliente n o idoso Qual o tamanho m dio de cada uma das filas c Qual seria o tempo m dio de perman ncia de um cliente se todos os clientes fossem indistintamente atendidos por todos os caixas E o tamanho m dio da fila d Que procedimento de atendimento voc recomendaria nesta situa o Porque e Se a lei fosse cumprida rigorosamente qual seria o tempo m dio de perm
48. dia do regime transiente Diz se que e o n mero m dio de vezes que o estado transiente z ocupado dado que o estado inicial i i pertencente aos estados transientes Se i z ent o e Ypey keT Se i z ent o e 1 9 Prek keT E e i z pertencente aos estados transientes E 1 0 12 d a dura o m dia do regime transiente dado que o estado inicial i d gt e 13 je Dura o m dia do processo se ele est no estado i e termina no estado j D do fa a Pr Ou Du para 1 transiente e j absorvente k transiente OBS fazendo b a r e B er teremos B 1 0 xA y y Exemplo Uma floresta constitu da de dois tipos de rvores aquelas com at 3 metros e as maiores do que 3 metros A cada ano 40 das rvores com at 3m morrem 10 s o vendidas por 20 cada 30 permanecem com at 3 metros e 20 crescem para acima de 3m Das rvores maiores do que 3m a cada ano s o vendidas 50 por 50 cada 20 por 30 cada e 30 permanecem na floresta a Qual a probabilidade de que uma rvore com menos de 3m morra antes de ser vendida Processos Estoc sticos e Teoria de Filas 18 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Se uma rvore com menos de 3m plantada qual o seu valor esperado de venda AB uma O 3 0 3 0 2 i04 01 0O 0 3 Os 030 0 02 05 P M 0 ERT vo o0 0 0 1 0 0 vso o0 o
49. do sistema real necess rio especificar a forma assumida de cada uma destas distribui es Para ser til a forma assumida deveria ser suficientemente realista para que o modelo forne a predi es razo veis enquanto que ao mesmo tempo fosse suficientemente simples para que o modelo fosse matematicamente trat vel Nestas bases a distribui o de probabilidade mais importante na teoria das filas a distribui o exponencial Suponhamos que a vari vel aleat ria T represente ou o tempo entre chegadas ou o tempo de servi o Quais as implica es de supormos que T tenha uma distribui o exponencial para um modelo de filas Para explorar isso necess rio examinar cinco propriedades chave da distribui o exponencial PROPRIEDADE 1 f t uma fun o estritamente decrescente de t t gt 0 km a 1 t A Figura 2 1 Propriedade 1 da Distribui o Exponencial na Teoria das Filas Uma consequ ncia da propriedade 1 que P O lt T lt At gt PIt lt T lt t At Processos Estoc sticos e Teoria de Filas 46 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Para quaisquer valores estritamente positivos de At e t Isto decorre do fato de que essas probabilidades s o a rea sob a curva Feit dentro do intervalo de comprimento At indicado e de que a altura m dia da curva menor para a segunda probabilidade que para a primeira Por isso n o apena
50. ent o amanha ser um dia chuvoso com 80 de chance poss vel modelar o tempo em Pedra Azul como uma cadeia de Markov Explique porque e construa o diagrama de transi o de estados 06 Suponha que no mercado existem apenas duas marcas de cerveja Mharba e rtica Dado que a ltima compra de uma pessoa foi uma de Mharba existe 90 de chance de que sua pr xima compra seja de Mharba Dado que a ltima compra de uma pessoa foi de rtica existe uma probabilidade de 80 de que sua pr xima compra seja de rtica a Represente o problema por uma cadeia de Markov apresentando a matriz de probabilidades de transi o e o diagrama de transi o de estados b Dado que uma pessoa acabou de comprar Mharba quanto tempo ser necess rio para que outra compra de Mharba seja realizada E de tica Como voc interpreta o tempo neste caso c Suponha ainda que cada consumidor fa a uma compra de cerveja por semana 1 ano 52 semanas e que existam 100 milh es de consumidores de cerveja Uma unidade de cerveja vendida por 2 e custa cervejaria 1 Por 500 milh es por ano uma firma de propaganda garante diminuir de 10 para 5 a fra o dos clientes de Mharba que mudam para rtica depois de uma compra Deve a cervejaria Mharba contratar a empresa de propaganda 07 Uma companhia com um v o s 7h45 da manh entre Rio e Bras lia n o quer que o v o se atrase dois dias seguidos na mesma escala Se o v o sai atrasado um dia a compan
51. existam mais de 2 pe as espera do processamento Qual a fra o esperada do tempo de funcionamento da linha relativa a ocorr ncia de congestionamento 18 A sa da de um t nel uma pista com 2 faixas de tr nsito em m o nica 100 metros mais adiante h um sinal luminoso que abre o tr nsito a cada 20 segundos deixando passar de cada vez 10 carros Em um dado momento os carros est o saindo do t nel raz o de 24 por minuto em m dia Sabendo se que cada carro ocupa 10 metros de sua faixa de tr nsito pergunta se a Qual o tamanho m dio do trecho de pista ocupado pelos carros b O sinal engui ou e a CET colocou provisoriamente um agente de tr nsito que abre o tr nsito em m dia a cada 20 segundos Qual a probabilidade que a fila invada o t nel 19 Uma famosa vidente acostumada a prever o futuro de pol ticos tem sua agenda cheia de entrevistas marcadas raz o de uma por hora dia de 8 horas Ela dedica em m dia 45 minutos a cada cliente e para suavizar a espera da clientela manda servir caf com bolinhos na sala de espera Uma pequena quest o alimentar se cada pessoa toma uma x cara de caf 100 ml a cada meia hora quantos litros de caf dever o ser preparados em m dia por dia 20 Um mec nico de manuten o de m quinas de c pia eletrost tica trabalha por contrato para a Prefeitura Ele pode consertar em m dia 3 m quinas por dia e o contrato por ele assinado prev que todo chamado s
52. fica aberta 24 horas por dia atendida por um nico funcion rio o qual Processos Estoc sticos e Teoria de Filas 89 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 9 Kc capaz de revisar um nibus de cada vez O tempo que ele gasta exponencialmente distribu do com uma m dia de 4 horas Os nibus chegam garagem segundo um processo de Poisson a uma taxa m dia de 12 por dia Os motoristas entretanto s o instru dos a n o entrar na garagem se l j existirem quatro ou mais nibus mas retornar ao despachante para nova autoriza o Determine a O valor esperado de tempo que um nibus aguarda na garagem b a perda esperada de dinheiro por dia pela companhia devido capacidade limitada da garagem se o custo de enviar um nibus a ela e t lo de volta sem revisar 80 Suponha que todos os propriet rios de carros completem seus tanques quando o n vel atinge exatamente a metade Normalmente uma m dia de 7 5 clientes por hora se dirigia a um posto de gasolina com uma nica bomba O tempo m dio de atendimento de 4 minutos Com a greve dos caminhoneiros ocorrida a pouco tempo um certo p nico se instalou Para modelar este fen meno suponha que os propriet rios passaram a completar o tanque quando o n vel est em 3 4 do tanque Como cada propriet rio est colocando menos gasolina no tanque durante uma visita ao posto assuma que o tempo m dio de
53. frente ou pra tr s caso bidimensional s A probabilidade dele ir pra frente ou pra tr s 1 2 ele est em um ch o plano e o corredor n o tem fim g Cada passo independe dos outros Com isso temos que X Kuken onde e uma vari vel aleat ria com a seguinte distribui o discreta P e 1 Das 1 1 2 Pes E Se X 0 AR ue RA AR t para valor impar de t Ent o X t d UL 2 t para valor par der Como s existem duas op es a distribui o de X binominal O Gr fico 3 1 abaixo ilustra os poss veis estados do sistema Processos Estoc sticos e Teoria de Filas 94 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Gr fico 3 1 Poss veis Estados do Sistema n para frente Depois det passos t n para tr s Posi o do bebum ser t nX D n D gt 2n t t n t n t t t P X 2n t A 1 H De nj 2 2 nj 2 n Como o X varia com t este processo n o estacion rio Neste caso seno tempo t 0 X 0 Ent o E X 0 vt gt 0 No tempot com p 1 2 em qualquer tempo EIN JK VI gt t 3 2 PASSEIO ALEAT RIO COM DESVIO DISCRETE RANDOM WALK WITH DEVIATION Processos Estoc sticos e Teoria de Filas 95 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Agora vamos imaginar o caso em que o corredor tem uma inclina o Ou seja mais f cil mais prov vel que ele v
54. i 1 ser uma morte por exemplo partida de um cliente por significar um decr scimo do n vel da popula o Processos Estoc sticos e Teoria de Filas 24 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Considere a Figura 1 8 abaixo GE DOLE Hun Figura 1 8 Processo de Nascimento e Morte A 0 Abi Aaz Aa Sendo assim AM Au L o Ka Ao Aun Aan Anna Por quest o de simplicidade de nota o usaremos h 42 A h 4 e Ao u A Aas l Uma outra abordagem para o problema usando a Lei de Conserva o do Fluxo FLUXO QUE SAI FLUXO QUE ENTRA 0 TIA 1 Ile 0 A 1 II 1 1 An zl A4 11 4 0 TL A TLIHA u I u 0 Processos Estoc sticos e Teoria de Filas 25 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP ILIA u 1 4 11 u 2 LA u ILA u Iu 0 u IL HM u Resolvendo o sistema temos A Sall 1 to 4m4 UU 0 Fb nein UUU rfi do Aih Ahaha 1 U Mai Uzu 0 Para resolvermos o sistema necess rio que a s rie a converg ncia da s rie 1 3 5 PROCESSO DE POISSON Considere a Figura 1 9 A A A A A A A A SDS SOS Figura 1 9 O processo de Poisson Equa o de Chapman Kolmogorov equivalente no caso cont nuo dP t PHA dt A A 0 O Poo t Dat Polt A O 4A A Ee 25 pes e
55. lei tel Zi a Para z 1 v D 2B 0 2x B s x Processos Estoc sticos e Teoria de Filas 15 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Se 2 B s x 2 Elv Elv Aix L n m dio de clientes no sistema A x 2 1 p L Elg p Sabe se que a vari ncia do tempo de servi o Ee 2 A L a E 2 1 p L p L Ly n m dio de clientes na fila Zoo lt 2p 2 o X ee EE 2 xX E Ent o F rmula de Pollaczek Khintchine Usando a f rmula de Little temos as express es para a m dia do tempo de perman ncia no sistema W e para a media do tempo de perman ncia na fila W4 L 1 e A Al 2 0 L 1 KE e A AN Zap Exemplos 1 MMA We UAP 2 MIDI o 0 e U p Processos Estoc sticos e Teoria de Filas He COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Outra forma de obtermos a m dia do tempo de perman ncia no sistema e na fila W e Wa respectivamente Considere a Figura 2 18 abaixo gt WII GE MGN Figura 2 18 Modelo M G L AW La A Wa W L EE Tempo de vida residual do cliente no atendimento BS x 2x os VR 2 E Para o caso espec fico da Exp u Tun H e Distribui o do n de clientes no sistema P im 0 2 Elz 0 2 B A A Q z S z d p z B A
56. lt t 1 e Generalizando temos que PT a T lt t 1 e 29 Portanto o tempo entre eventos consecutivos em um processo de Poisson tem distribui o exponencial 1 3 7 SUPERPOSI O DE PROCESSOS DE POISSON Se A um processo de Poisson com taxa 4 e B um processo de Poisson com taxa A ent o C tamb m um processo de Poisson com taxa A 4 4 1 3 8 DECOMPOSI O DE PROCESSOS DE POISSON Se A um processo de Poisson ent o B e C ser o processos de Poisson se a separa o for probabil stica e independente Processos Estoc sticos e Teoria de Filas 28 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 3 9 TEOREMA DE KHINTHINE A superposi o de um grande n mero de processos de renova o tempos entre eventos independentes e identicamente distribu das i i d aproximadamente um processo de Poisson Processos Estoc sticos e Teoria de Filas 29 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 4 EXERCICIOS PROPOSTOS DE PROCESSOS ESTOC STICOS 01 Uma floresta constitu da de dois tipos de rvores aquelas com at 3 metros e as maiores do que 3 metros A cada ano 40 das rvores com at 3m morrem 10 s o vendidas por 20 cada 30 permanecem com at 3 metros e 20 crescem para acima de 3m Das rvores maiores do que 3m a cada ano s o vendidas 50 por 50 cada 20 por 30 cada e 30 pe
57. nibus mas retornar ao despachante para nova autoriza o Determine a o valor esperado de tempo que um nibus aguarda na garagem b a perda esperada de dinheiro por dia pela companhia devido capacidade limitada da garagem se o custo de enviar um nibus a ela e t lo de volta sem revisar 80 oBogogogo o Processos Estoc sticos e Teoria de Filas 146 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A Ire u P P Po p l p p p p 1 Po 1 2 4 8 16 1 gt pen 31 E ESIR E EE eegene EE a ER aq a e horas 4 6 nibus dia u A 12 nibus dia ep L TnP o6 41 2 8 4 16 2 8 12 64 Sp 31 31 31 31 31 31 31 dos SO odds Ee A 3112 nibus 16 b Perda 2 p custo 12 dia 80 495 48 dia 31 9 Suponha que todos os propriet rios de carros completem seus tanques quando o n vel atinge exatamente a metade Normalmente uma m dia de 7 5 clientes por hora se dirigia a um posto de gasolina com uma nica bomba O tempo m dio de atendimento de 4 minutos Com a greve dos caminhoneiros ocorrida a pouco tempo um certo p nico se instalou Para modelar este fen meno suponha que os propriet rios passaram a completar o tanque quando o n vel est em 3 4 do tanque Como cada propriet rio est colocando menos gasolina no tanque durante uma visita ao posto assuma que o tempo m dio de servi o tenha ca do para 3 1 2 minutos Como o
58. o estoque inicial na pr xima semana seja de 4 unidades Pol tica Il Se o estoque de 1 ou menos unidades coloca se um pedido de forma que o estoque inicial na pr xima semana seja de 3 unidades Os seguintes custos s o observados na baco e Custo de comprar um computador 4 000 e Custo de manter o computador em estoque 100 semana computador e Custo de efetuar um pedido 500 al m do custo de 4 000 por computador Qual pol tica tem o menor custo semanal esperado Modelo Estoque Transi o gt Mudan a de semana Estado n de pe as em estaque no fim de semana antes de repor o estoque P D P D 2 0 5 Pol tica Estoque m ximo ao fim da semana 3 Estoque m nimo ao fim da semana 1 Processos Estoc sticos e Teoria de Filas 113 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Q n A zb 1 2 8 ON 1 0 0505 Se P 2 0 0505 3 0 5 0 5 0 Transi es da parte superior implicam em pedidos m 0 5 7 m 0 5 m 0 5 7 0 5 7 A a 2 m 0 5 7 0 5 7 72i m a a 1 Custo de manuten o do estoque 100 n m dio de computadores em estoque S100 1 7 2 m 3 m 8100 1 42 543 5 e 216 67 Os pedidos s s o feitos quando tem as transi es de estado 152 153 252 258 m42 tempo esperado para o estoque sair de 1 e ir para 2 ms frequ ncia relativa dado que o estoque estava em 1 e passou para 2 mo lt Di
59. o n mero no tempo 0 N mero de servidores canais de servi o paralelo no sistema de fila Taxa m dia de chegada n mero esperado de chegadas por tempo unit rio de novos clientes quando n clientes est o no sistema Taxa m dia de servi o para todo o sistema n mero esperado de Un clientes concluindo o servi o por tempo unit rio quando n clientes est o no sistema u p Vide par grafo seguinte Quando An for uma constante para todo n esta constante ser denotada por A quando a taxa m dia de servi o por servidor ocupado for uma constante para todo n gt 1 esta constante ser denotada por u neste caso un S u quando n gt s de modo que todos os s servidores estar o ocupados Nestas circunst ncias 1 e 1 u s o o tempo entre chegadas esperado e o tempo entre servi os esperado respectivamente Tamb m p N o fator de utiliza o da instala o de servi o isto a fra o de tempo su esperada em que os servidores est o ocupados porque eu representa a fra o da Processos Estoc sticos e Teoria de Filas 43 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP capacidade do servi o do sistema su que est sendo utilizada em m dia pelos clientes que chegam A Tamb m necess ria alguma nota o para descrever os resultados do estado de equil brio Quando um sistema de fila tenha come ado a operar recentemente o estado do
60. odo uma bola escolhida aleatoriamente e trocada para a outra caixa a Calcule a fra o do tempo que uma caixa ir conter 0 1 2 ou 3 bolas b Se a caixa 1 n o cont m bolas em m dia quanto tempo ser decorrido at que ela contenha 1 2 e tr s bolas O processo uma bola escolhida aleatoriamente e ent o trocada de caixa Processos Estoc sticos e Teoria de Filas 118 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Ex Estado caixa 1 cont m uma bola Se a bola escolhida estiver na caixa 1 ela ser trocada de caixa e a caixa 1 passar a ter O bolas com probabilidade 1 3 que a probilidade de escolher essa bola Se a bola escolhida estiver na caixa 2 ela ir para a caixa 1 que passar a ter 2 bolas com probabilidade 2 3 que a probabilidade de escolher a bola da caixa 2 1 3 1 3 Estado n bolas na caixa 1 1 3 2 3 1 Transi o trocar uma bola de caixa Est gio 1 per odo 1 2 3 1 3 o 1 2 3 Ta 1 3 7 zano 0 O 1 0 0 T T 2 3 T Ge P 1 13 0 23 0 EE a z 0 375 2 0 23 0 18 z 0 375 31 0 0 10 m Sa 7 0 125 Mota T m 1 a Fra o do tempo que a caixa 1 ir conter 0 1 2 ou 3 bolas dado por zo 14 T2 Ta b Dado que a caixa 1 n o cont m bolas em m dia o tempo decorrido at que ela contenha 1 2 e 3 bolas dado por mo Mo2 e mos respectivamente mo 1 Po Mm Poz Ma Dan Ma mo 1 Mo 1 Poo Moz
61. odos dedicados manuten o d Quantos equipamentos ser o consumidos retirados da produ o por ano 52 semanas em m dia e Quantas opera es e quantas manuten es em m dia ser o realizadas por ano A ger ncia estuda uma forma de aumentar a quantidade anual de opera es realizadas de forma lucrativa A alternativa considerada consiste em realizar duas opera es antes de submeter o equipamento manuten o em vez de fazer a manuten o ap s uma opera o apenas Como antes em 10 dos casos o equipamento ficar irrecuper vel ao final da primeira opera o A ger ncia avalia que a probabilidade de perder o equipamento ao final da segunda opera o aumentar em rela o primeira e ser igual a 20 devido aos defeitos n o consertados e ao desgaste acumulado na primeira opera o f Calcule para esta alternativa os valores correspondentes aos itens b c d e e acima g Suponha que cada opera o contribui com um acr scimo de 20 mil reais para o lucro da companhia j descontados os seus custos diretos exceto a compra do equipamento e o custo da manuten o j informados acima Na sua opini o a alternativa em estudo deve ser adotada Por que 12 O tr nsito em determinada via urbana observado e classificado conforme a intensidade em leve moderado ou pesado Ap s muitas observa es verifica se que o tr nsito 1 nunca passa diretamente de leve para pesado ou vice versa
62. p nico afetaL e W Processos Estoc sticos e Teoria de Filas 147 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 4 7 5 clh L aia gt 4 15 clh A L l W 7 89min 15 cl h T5Sclh gt tanque ISclh lt 5 tanque EE 4h L 5 carros W 20 min 10 Mec nicos que trabalham no Centro Automotivo Classe A devem retirar as ferramentas e pe as que necessitam de uma ferramentaria Uma m dia de 10 mec nicos por hora chegam procurando por pe as Atualmente a ferrameniaria possui um ferramenteiro que recebe 6 00 por hora e que leva em m dia 5 minutos para atender a cada pedido estimado que cada mec nica produz 10 00 de servi os por hora cada hora que o mec nico gasta na ferramentaria custa a oficina 10 00 A oficina est analisando a possibilidade de contratar um ajudante de ferramenteiro a 4 00 por hora Se este ajudante for contratado o ferramenteiro ter possibilidade de atender a uma requisi o em 4 minutos em m dia Assuma que os tempos entre chegadas e de servi o s o exponenciais Deve o ajudante ser contratado Processos Estoc sticos e Teoria de Filas 148 a b COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 10 mec hora 44 12 ped hora 4 15 ped hora FO Ee W e 6 00 h h FO 104 W 10 00 Gi 10 A 15 h 1 2 12 10 r A De Tb Ee 2 15
63. per odo recebendo em m dia 3 pedidos por hora para reparos na rede el trica Ela disp e de 5 equipes de reparo uma equipe levando em m dia 90 minutos para chegar ao local do defeito e efetuar o reparo O congelador leva 6 horas para descongelar Ap s este tempo o camar o ter de ser preparado a fim de que n o se estrague Sem acesso para o caminh o de g s e n o havendo fog o lenha dispon vel pergunta se se a dona da casa em quest o poder esperar ou n o conseguir usar o camar o para o seu almo o 25 As pessoas que atenderam a um an ncio de emprego colocado por uma empresa passam por uma entrevistadora com a qual necess rio marcar hora nessa base 6 pessoas por hora s o agendadas e cada entrevista leva em m dia 8 minutos As pessoas passam ent o ao servi o m dico da empresa onde um m dico as submete a tr s exames cada um com dura o m dia de 5 minutos H dois m dicos fazendo este atendimento a Quanto tempo em m dia uma pessoa demorar para iniciar uma entrevista b Quantas pessoas em m dia estar o no departamento m dico em um dado momento 26 Em uma ag ncia banc ria h dois guich s para atender apenas a retiradas Os clientes que as desejam chegam raz o e 25 por hora em m dia e se dirigem ao guich 1 cujo caixa conhecido por sua rapidez leva em m dia 1 5 minutos para atender a um cliente Se um cliente encontrar este guich ocupado e o guich 2 desocupado ent o ele se d
64. probabilidade Desenhe o diagrama de transi o de estados e determine a matriz de transi o para este caso c No caso descrito na letra b suponha que o jogador 1 tem 3 e o jogador 2 tem 2 qual a probabilidade do jogador 1 ganhar o jogo d Quantas jogadas durar o jogo a 1 1 QB 2 3 2 3 2 3 2 3 2 3 2 3 O SOS OS GO 13 1 3 1 3 3 1 3 1 3 1 3 Jogador 1 ganha 2 com probabilidade 1 3 perde 1 com probabilidade 2 3 1 2 3 4 Ma N Ni E 0 l o 0 1 3 0 0 0 o 283 2 23 0 O 18 0 0 0 0 0 3 O 23 0 0 0 0 0 0 0 4 0 O 23 0 0 0 0 0 0 P ER RARE RES A DIR NR SE N 3 0 0 0 0 0 O 13 0 0 N 2 0 0 0 0 23 0 o 13 0 N 1 0 0 0 0 O 23 0 13 0 F 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 b q 1 DEN A s Eu 2 e A O OROROORO ORORO 1 3 3 1 3 1 3 1 3 Processos Estoc sticos e Teoria de Filas 134 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 3 4 Ma M N1 N 0 1 o 12 0 0 0 0 0 o 12 2 23 0 0o 1 3 0 0 0 0 0 3 o 23 0 0 0 0 0 0 0 41 0 o 23 0 0 0 0 0 0 P a RR SR N 3 0 0 0 0 0 g 13 0 0 N 2 0 0 0 0 2 3 DO 13 0 N 1 0 0 0 0 O 12 0 12 0 N 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 2 2 3 2 3 1 2 o DIDI DO 1 2 e My 1 3 1 3 1 2 3 4 5 0 1f 0 1 2 0 0 0 1 2 1 2 3 4 Su 23 0 0 18i0 O RE a EE g Aer E Ee SO E E l Q 2 12 18 03 06 SEW ZE BD EE 4 04 06 06 1 2 of o D SE EK ee 5 0 1 0 2 0 8 Probabilidade do jogador 1 ganhar dado que come o
65. processo come a no estado i 1 n n i SS repara f lt pj n gt l n Ty n Spe SH po k 8 F fi para cada ij a matriz de primeira passagem primeiro retorno 1 2 3 CLASSIFICA O DE ESTADO Processos Irredut veis cada estado pode ser alcan ado de qualquer outro atrav s de uma sequ ncia de transi es caso contr rio o processo dito redut vel A Figura 1 3 mostra um exemplo de processo redut vel K ou Doado Cof e e Figura 1 3 Exemplo de Processo Redut vel Estado Recorrente se j aconteceu uma vez certo que ir ocorrer novamente ou seja existe uma probabilidade n o nula do estado vir a acontecer no futuro n lim p para cada i Processos Estoc sticos e Teoria de Filas 11 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Estado Transiente ir ocorrer um determinado n mero de vezes e posteriormente n o ocorrer mais lim po para cada i j estado transiente Dese Vale ressaltar que um processo finito e irredut vel tem todos os estados recorrentes Estado Nulo estado recorrente por m com o tempo de recorr ncia infinito Estado n o nulo tempo de recorr ncia finito Estado Peri dico estados s podem ocorrer em tempo fixo Considere a Figura 1 4 neste caso os estados 1 e 2 s podem ser alcan ados num tempo fixo igual a 2 e od Figura 1 4 Exemplo de Estado Peri dico A d
66. seguintes par metros a 0 2 ano o 1 ano dx 024 1 06 E 12 12 1 1 X X gt di e dt t 1 60 12 X X EE r At 60 J12 t Onde s N 0 1 Podemos simular esse processo em planilhas eletr nicas onde o pr ximo elemento o primeiro somado de uma constante e um fator perturbador dado pelo s 3 6 REPRESENTA O DO MOVIMENTO BROWNIANO POR PASSEIO ALEAT RIO Seja x um Processo de Markov com incrementos independentes Ou seja a probabilidade de um valor futuro de x depende somente de onde o processo est agora e a probabilidade de subir ou descer em cada per odo independente do que acontece nos per odos pr vios Considere seu incremento como uma vari vel aleat ria Ax que assume os valores ou Ah com probabilidades p e q respectivamente Considere sua posi o inicial sendo Xo O gr fico 3 2 abaixo ilustra as realiza es poss veis associadas as suas probabilidades em 3 tempos Processos Estoc sticos e Teoria de Filas 99 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Xo 3Ah p 0 E Kat Abt Xo Mh D Xo Ze d pei RR 2 Xy24h q Xv34h IS q t 0 t 1 t 2 t 3 Gr fico 3 2 Poss veis Estados do Sistema E Ax GE Sc p a ah Elas E plan at sn p a sn ah o Ax v ac Efa aefa ehar ela eat a Ax AN E pda 1 p Ak 4pqAh Consideremos agora que vamos dividir o tem
67. ser interpretada como equivalente soma de k vari veis aleat rias regidas por distribui es exponenciais iguais Admitamos que o intervalo entre chegadas sucessivas seja regido por uma distribui o de Erlang de ordem k definida pela fun o densidade de probabilidade k j EJ Fir ro e t20 O valor esperado de t dado por ht e a vari ncia de t por 1 Varlt k Para k 1 tem se a distribui o exponencial e o processo de chegada Poisson medida que k aumenta a vari ncia tende a zero Var t 0 a dispers o relativa da distribui o diminui atingindo a situa o determin stica quando k Neste caso a distribui o de Erlang representa exemplos de tempos de chegadas peri dicos ou regulares isto um intervalo constante de 1 1 entre chegadas A Figura 2 5 Distribui o de Erlang mostra o comportamento da distribui o de Erlang para diferentes k Frequentemente a distribui o de Erlang apresentada pelo s mbolo Ex Processos Estoc sticos e Teoria de Filas 60 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP ft Figura 2 5 Distribui o de Erlang Em resumo se T4 To Tk s o vari veis aleat rias com distribui es exponenciais id nticas e com valor esperado igual a r ent o T T4 T2 Tk tem distribui o de Erlang com par metros k e Chama se de servi o completo a soma de k sub
68. servidor continuamente ocupado tenha uma distribui o exponencial com par metro o A propriedade 4 ent o tem a ver com a implica o resultante quanto a distribui o de probabilidade do n mero de Processos Estoc sticos e Teoria de Filas 49 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP vezes em que este tipo de incidente ocorre dentro de um espa o de tempo espec fico Em particular fazendo com que X t seja o n mero de ocorr ncias no tempo t t gt 0 onde o tempo O designa o instante em que se come a a contar A implica o que ot e PIX t n BE sparan 0 1 2 n isto X t tem uma distribui o de Poisson com par metro at Por exemplo com n 0 P X t 0 e o qual exatamente a probabilidade da distribui o exponencial de que o primeiro incidente ocorra depois do tempo t A m dia desta distribui o de Poisson EIX D at de modo que o n mero esperado de incidentes por tempo unit rio a Assim dito ser a taxa m dia a qual os incidentes ocorrem Quando os incidentes s o contados em uma base cont nua o processo de contagem X t t gt 0 dito ser um processo de Poisson com par metro o a taxa m dia Esta propriedade fornece informa es teis sobre as conclus es dos servi os quando os tempos dos servi os t m uma distribui o exponencial com par metro u Isto feito definindo se X t como o n mero de co
69. tempo de servi o para este tipo de situa o Por outro lado consideremos o tipo de situa o em que as tarefas espec ficas requeridas dos servidores sejam diferentes de cliente para cliente A natureza geral do servi o pode ser a mesma porem o tipo especifico e a quantidade de servi o diferem Por exemplo este seria o caso no problema do quarto de emerg ncia do Hospital Municipal Os m dicos encontram uma grande variedade de problemas m dicos Na maioria dos casos eles podem fornecer o tratamento necess rio bem rapidamente porem ocasionalmente um paciente requer cuidados extensivos Uma distribui o de tempo de servi o exponencial parece bastante plaus vel para este tipo de situa o de servi o Se T representar os tempos entre chegadas a propriedade 1 exclui situa es em que clientes potenciais que se aproximem do sistema de fila tendam a atrasar a sua entrada se virem outro cliente entrando na sua frente Por outro lado isto inteiramente consistente com o fen meno comum de chegada ocorrendo aleatoriamente que ser descrito por propriedades subsequentes Processos Estoc sticos e Teoria de Filas 47 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP PROPRIEDADE 2 Falta de Mem ria Esta propriedade pode ser definida matematicamente como P T gt t At T gt At P T gt t Para quaisquer quantidades positivas t e At Em outras palavras a distribui o de p
70. um processo Poisson a uma taxa m dia de 20 por hora mas a entrada proibida sempre que o posto estiver lotado A lavagem e a limpeza s o feitas manualmente e o tempo consumido exponencialmente distribu do Sob condi es normais cada plataforma est ocupada com um carro durante uma m dia de 5 minutos Entretanto quando dois ou mais carros est o esperando por atendimento o procedimento de lavagem acelerado reduzindo o tempo m dio de atendimento para 4 minutos Determine a o n mero esperado de carros no posto de lavagem b o tempo esperado que um carro permanece no posto se ele n o impedido de entrar 43 Estudos realizados pelo pessoal t cnico de um grande supermercado determinaram que 20 da clientela adquire 10 itens ou menos em uma compra Se um a caixa pode registrar 5 itens por minuto em m dia quantas caixas para uma m ximo de 10 itens caixas expressas dever o ser instaladas para que o tempo m dio dispendido por um cliente desde a chegada fila de caixa at sua sa da da mesma n o ultrapasse 3 minutos na previs o de uma demanda m dia de 750 clientes por hora pelo supermercado Despreze o tempo de pagamento e considere que todos os clientes dessas caixas adquirem exatamente 10 itens 44 Um excelente restaurante de comida nordestina situado em uma cidade pr xima ao Rio de Janeiro tem em sua cozinha uma cozinheira e uma ajudante que trabalham em conjunto para atender a uma comanda uma comanda
71. 0 23 0 14 0 09 0 06 0 04 0 03 0 50 0 33 0 24 0 17 013 0 10 0 08 0 55 0 39 0 29 0 23 0 18 0 14 0 11 0 60 0 45 0 35 0 29 0 24 0 20 0 17 0 65 0 51 0 42 0 35 0 30 0 26 0 21 0 70 0 57 0 51 0 43 0 38 0 34 0 30 0 75 0 64 0 57 0 51 0 46 0 42 0 39 0 80 0 71 0 65 0 60 0 55 0 52 0 49 0 85 10 78 0 73 0 69 0 65 0 62 0 60 0 90 0 85 0 83 0 79 0 76 0 74 0 72 0 95 0 92 0 91 0 89 0 88 0 87 0 85 Processos Estoc sticos e Teoria de Filas 178
72. 2 3 1 L WIN m Olojo miao 0 2 0 5 0 2 L a Qual a fra o do tempo durante a qual cada partido governa em m dia PE 37 1 PC 28 69 PD 34 3 b Quanto tempo decorre em m dia desde uma vit ria do Partido da Esquerda at que o Partido da Direita ganhe duas elei es n o necessariamente consecutivas 35 anos Suponha que em uma linha de montagem final para carros haja o seguinte conjunto de regras 1 Dois convers veis n o podem jamais se seguir na linha porque a quantidade de trabalho desequilibraria a linha 2 Uma perua deve ser seguida de um sedam para equilibrar a linha 3 Um sedam tanto pode ser seguido por uma perua como por um convers vel mas n o por um outro sedam Somente estes tr s modelos s o produzidos na linha Monte uma matriz de transi o poss vel para estas regras inserindo as letras a b c d etc para os valores n o definidos numericamente pelas regras acima a A cadeia irredut vel b Qual a probabilidade de que ap s um convers vel o pr ximo ocorra na linha com um espa o de diferen a separado por outro ve culo Use as letras a b c d se necess rias c Se P uma matriz de transi o de um passo que interpreta o daria no ij simo elemento de Pn para n grande d Suponha que se firmou um contrato para entregar 10 000 carros ao final de um m s Destes 10 000 aproximadamente 50 tinham que ser sedam 10 ti
73. 4 1 2 24 1 6 0 8 0 8 1 6 24 1 2 0 4 0 8 1 2 1 6 Processos Estoc sticos e Teoria de Filas 122 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 2 3 4 5 0 OT o 1 2 0o 070012 2 1 2 0 1 2 0 0 0 P 3 0 1 2 0 12700 4 O 0 12 0 12 0 5 0 0 0 0 1 07 of 0 0 0 00 1 d dura o do regime transiente dado que saiu do estado i Dura o m dia do jogo dado que jogador come ou com 3 ds X e 0 8 1 6 2 4 1 2 6 lan amentos de moeda 5 0 1 0 2 08 2 04 0 6 A ER 83 0 6 04 4 0 8 0 2 Probabilidade do jogador ganhar as5 0 6 Probabilidade do jogador Il ganhar probabilidade do jogador perder aso 0 4 15 Quatro meninos A B Ce D brincam de lan ar disco Se o menino A recebe o disco lan a o para B C ou D com iguais probabilidades se C recebe o disco lan a o para A ou D com iguais probabilidades se ou D recebem o disco ficam com o mesmo Modele o problema como uma cadeia de Markov Desenhe tamb m o diagrama de transi o de estados a Se o disco est com C qual a probabilidade de D ficar com o disco b Se A est com o disco qual a probabilidade do disco terminar com B C B D Al O 18 13 1 3 Ps o 12 00 12 lee CDS 0 D 0o corso 1 Processos Estoc sticos e Teoria de Filas 123 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 3 E O S 1 3 e 1
74. 55 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A 0 AP HP gt P Era A 2 1 Ap 2up gt P af aw A Ge 2 Ap 3Up gt P P a 3 Po 3u 3 u n n n APaa DOUD gt D Pai a Be gt D p n 0 1 2 10 ng n u n bpe 1 gt p Assim E E Pr ao n e a vagas ociosas total de vagas dispon veis vagas utilizadas L 10 1 66 8 33 L E A 6 10 aop 8 32500 b Pio VOiel fr 22 Considere um sistema com um nico atendente tendo uma distribui o de chegadas Poisson com 4 10 c h Atualmente o atendente trabalha de acordo com uma distribui o exponencial com um tempo m dio de servi o de 5 min A ger ncia tem a sua disposi o um curso de treinamento que ter como resultado uma melhora decr scimo na vari ncia do tempo de servi o por m com um leve aumento da m dia Ap s a execu o do curso estima se que o tempo m dio de servi o aumentar para 5 5 min por m o desvio padr o decrescer de 5 para 4 min Deve a ger ncia mandar o atendente fazer este curso Processos Estoc sticos e Teoria de Filas 156 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP MIMI A 10 ch Hy 1c 5 minutos 12 c hora Ho 1c 5 Sminutos Objetivo redu o do tempo de espera no sistema W SE 2a 0 5hora 30minutos gt p 12 10 Wa de i u 10 9 10
75. 772 2 3 3 5 6 11 6 11 3 5 2 3 Probabilidade de vit ria ae a ie 35 72 0 49 Probabilidade de derrota rp a p 37 72 0 51 Probabilidade de Ganhar dado que no primeiro lan amento tirou 6 P G 6 a se 5 11 04 A Gazeta da Produ o tem as seguintes informa es a respeito de seus assinantes Durante o primeiro ano 20 dos assinantes cancelam suas assinaturas Daqueles que completaram o 1 ano 10 cancelam sua assinatura no 2 ano Daqueles que assinam por mais de 2 anos 4 ir o cancel los durante algum dos pr ximos anos Em m dia qual a dura o de uma assinatura da Gazeta da Produ o 0 1 CP 1 0 04 1 0 8 E U 0 0 1 0 0 0 9 os 0 09 0 04 1ano P ano 1ano Cancela 1 0 8 18 0 1 225 O 0 25 1 ano 0 0 0 0 Tano 0 8 0 0 0 di dura o m dia do regime transiente assinatura dado estado inicial i d 198 anos d Se gt d 23 5 anos E d 25 anos Dura o m dia de uma assinatura 19 8 anos 0 0 9 0 96 0 tano Cancela 0 2 0 1 0 04 1 Processos Estoc sticos e Teoria de Filas 110 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 05 O tempo em Pedra Azul pode ser descrito como dependente do tempo nos dois ltimos dias pelo seguinte mecanismo i se os ltimos dois dias foram ensolarados ent o existe 95 de chance de amanh tamb m ser ensola
76. 87 0 897 0 427 E Q Ayl 0 2 08 0 333 A 0 706 1 795 0 855 Al 0 2 0 2 0 7 A gt 0 684 0 769 1 795 An Pag Aol 0 064 0 936 A ER A 0 128 0 872 Ap 0 269 0 731 Valor esperado a ser pago ano pag 800 000 ani pag 120 000 an gt pag 80 000 911 920 Processos Estoc sticos e Teoria de Filas 139 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 6 LISTA DE EXERCICIOS RESOLVIDOS DE TEORIA DAS FILAS 1 Considere a rede de filas aberta com um nico n como mostrada abaixo Chegadas y gt HI partidas externas KE D O n nico uma fila M M 1 com taxa de servi o qu Um fregu s retorna ao n com probabilidade p depois de completar seu servi o A disciplina da fila PEPS primeiro a chegar primeiro a ser servido Pergunta se c Quanto vale y taxa total de chegada ao n 1 d Qual o intervalo permitido para varia o de p para que o sistema permane a est vel 1 itera o y 2 ad 3 yY yp yp n v yp yp yp yp H gt 00 a 7 nc A y p gt A p b dns A Condi o 0O lt P lt l gt 0 lt lt l Mi oe A as o lt lt 1 p ml p D 0 lt p lt 1 Mi Processos Estoc sticos e Teoria de Filas 140 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 No bar de um aeroporto uma pessoa pode escolher entre tomar um caf servido no balc
77. EAE Er A 0 03 0 05 3l 0 0 0i 0 0 07 FL o o 1 0 97 0 9275 O 0 03 0 8626 0 1434 A 1 0 R 0 1 0 95 O 0 05 0 8835 0 1165 O 0 1 0 93 0 07 0 93 0 07 a n de fog es que dever o ser substitu dos agr 14 34 Pol tica de garantia de 2 anos 0 97 0 95 TT 0 1 2 F 0 o i o 0 97 0 0 03 0 05 0 P 1 0 0 95 0 05 SE Ee Ke Tas o 2 0 0 1 0 Fl o 00 1 e E 1 0 97 O 0 03 0 9215 0 0785 A 1 0 R 0 1 0 95 0 05 0 95 0 05 bh n de fog es que dever o ser substitu dos aor 7 85 Custo com as reposi es para pol tica de 3 anos de garantia 10 000 100 0 1434 143 400 pol tica de 2 anos de garantia 10 000 100 0 0785 78 500 b Impacto monet rio da mudan a de pol tica 8143 400 78 500 64 900 Processos Estoc sticos e Teoria de Filas 130 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 21 O propriet rio de uma barbearia de uma s cadeira est pensando em expandi la devido ao fato de haver muita gente em espera As observa es indicam que durante o per odo de tempo requerido para cortar o cabelo de uma pessoa podem haver 0 12 e 3 novas chegadas com probabilidade 0 3 0 4 0 2 0 1 respectivamente A cada tem capacidade fixa de 6 pessoas incluindo aquela que estiver cortando o cabelo a Desenhe o diagrama de transi o de estado e determine a matriz de probabilidade de transi o b Determine a
78. Gu UT AG EH gt Equa o fundamental da MIG 1 2 5 1 MEDIDAS DE DESEMPENHO Nesta se o ser o apresentadas algumas medidas de desempenho para o modelo MIG 1 Inicialmente notamos que as f rmulas de Little continuam v lidas e as utilizaremos para deduzir alguns resultados e N mero m dio de clientes no sistema em regime estacion rio O valor esperado do n mero de usu rios no sistema L nos instantes imediatamente ap s uma partida pode ser calculado conforme demonstrado a seguir j limg Er Elg lim Elg n gt n 500 Usando a equa o fundamental n gt 0 El Ela Elaq E r Ely Elag Como Elek As ElAg Dag k 4 Plg 0 4 Plg 1 A Plg 2 ElAg Ss k gt Probabilidade sistema ocupado p k 1 Ax p 1 po Processos Estoc sticos e Teoria de Filas 74 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP zj zi 21 p rt e k Comprimento m dio do sistema L Elel p Sabe se que para chegadas Poisson PIN k Poisson A gt V z 3 Ph EE k 0 o k V z servi o x po 4x i k Z H a V z servi o x V z servi o x Be Chegada e servi o independentes V z et blx dx Da defini o da transformada de LaPlace B s f e b x dz Ent o B s B A 2z Sabe se que avo o d V dz jz 1 E v de z Elv Ev dV z dz d v z dz
79. ILAS S O ESTUDADAS As filas s o estudadas porque em toda fila embora nem sempre se perceba existe embutido um problema econ mico e este problema econ mico surge porque em qualquer fila existem dois custos envolvidos o custo da fila e o custo do servi o Para exemplificar o que vem a ser estes dois custos vamos usar o exemplo citado acima sobre o processo de atraca o de navios em um porto Em qualquer porto existem os locais onde os navios podem atracar Estes locais s o chamados ber os Assim o n mero de ber os d o n mero m ximo de navios que podem atracar em um porto Por sua vez a legisla o internacional que regulamenta o tr fego mar timo determina que se ao chegar a um porto obviamente na data certa n o houver ber o para atracar a administra o do porto tem que indenizar a companhia dona do navio pelo tempo que ele ficar ao largo esperando ber o livre para atracar Em resumo quando por qualquer motivo todos os ber os de um porto est o ocupados os navios que chegam formam uma fila l gica aguardando sua vez O custo do servi o o custo de construir e manter em funcionamento os ber os de atraca o Quanto mais ber os oferecidos ou seja quanto maior o n vel de servi o oferecido maior este custo O custo da fila o custo que a administra o do porto tem pelo pagamento das indeniza es aos navios que esperam na fila Este custo inversamente proporcional ao custo do servi o n me
80. Pesquisa Operacional Novaes Ant nio Galv o Pesquisa Operacional e Transportes McGraw Hill USP 1975 Santos M P Pesquisa Operacional Departamento de Matem tica Aplicada Instituto de Matem tica e Estat stica Universidade Estadual do Rio de Janeiro 2003 Wagner Harvey M Pesquisa Operacional Prentice Hall Rio de Janeiro 1986 Livros de Simula o 17 18 19 Chwif L Medina AC Modelagem e Simula o de Eventos Discretos Teoria e Aplica es Ed dos Autores 2006 Law A M Kelton W D Simulation Modeling and Analysis MacGraw Hill 2000 Saliby E Repensando a Simula o Ed Atlas 1989 Processos Estoc sticos e Teoria de Filas 102 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Processos Estoc sticos e Teoria de Filas 103 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 5 LISTA DE EXERCICIOS RESOLVIDOS DE PROCESSOS ESTOCASTICOS 01 Uma floresta constitu da de dois tipos de rvores aquelas com at 3 metros e as maiores do que 3 metros A cada ano 40 das rvores com at 3m morrem 10 s o vendidas por 20 cada 30 permanecem com at 3 metros e 20 crescem para acima de 3m Das rvores maiores do que 3m a cada ano s o vendidas 50 por 50 cada 20 por 30 cada e 30 permanecem na floresta a Qual a probabilidade de que uma rvore com menos de 3m morra antes de se
81. Poisson j adaptadas para sistemas de filas Cabe ressaltar que estas propriedades s o provadas matematicamente Processos Estoc sticos e Teoria de Filas 51 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 O n mero de chegadas ou de servi os completados em uma unidade de tempo especificada independente do numero de chegadas ou t rmino de servi os em qualquer outra unidade 2 O n mero m dio de chegadas ou t rmino de servi os por unidade de tempo proporcional ao tamanho da unidade de tempo 3 A probabilidade de ocorr ncia de 2 chegadas simult neas ou t rmino de 2 servi os em uma unidade de tempo muito pequena At tende a zero 4 A probabilidade de 1 chegada ou t rmino de servi o ocorrer em uma unidade de tempo muito pequena AL sempre a mesma independente do instante At 5 Se a distribui o das chegadas discreta segue a distribui o de Poisson ent o a distribui o do intervalo entre chegadas continua segue a Exponencial Se a distribui o da dura o do servi o continua segue a Exponencial ent o a distribui o dos servi os completados discreta segue a Poisson 2 2 FILAS MARKOVIANAS PROCESSO DE NASCIMENTO E MORTE 2 2 1 SISTEMAS INFINITOS 2 2 1 1 Modelo MIMI Este o modelo de fila mais simples a qual possui as seguintes caracter sticas Tamanho permitido para a fila infinito Chegadas seguindo a
82. Processos Estoc sticos e Teoria de Filas 67 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP D s 0B s 1 JA 5 B s se a chegada obedece a um processo de Poisson a distribui o do tempo entre chegadas A i D Z exponencial com taxa Portanto A E Da mesma forma como o servidor ks A E e exponencial com taxa p ent o pode se escrever B s u s Substituindo se A s e Dis na equa o de D s tem se U a Aili A Como p tem se gg Fe A D s 5 Ate Pode se perceber que as partidas de um sistema MIMI em equil brio s dependem das chegadas 2 4 4 1 IMPLICA ES DO TEOREMA DE BURKE Desde que as chegadas nos estados que caminham para frente formam um processo de Poisson as sa das nos estados que caminham para tr s tamb m formam um processo de Poisson Processos Estoc sticos e Teoria de Filas 68 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP I d Chegada Tempo i sa da Tempo Figura 2 14 Implica es do Teorema de Burke Uma vez que o processo para tr s estatisticamente o mesmo que o processo para frente o processo de sa da Poisson Pelo mesmo argumento o estado deixado por um cliente independente das sa das anteriores 2 4 5 FORMA PRODUTO NA REDE ABERTA Um teorema importante prov
83. TE t cl 24 1 3 4 PROCESSO DE NASCIMENTO E MORTE mms 24 1 3 5 PROCESSO DE POISSON eelere 26 1 3 6 TEMPO ENTRE EVENTOS CONSECUTIVOS mms 28 1 3 7 SUPERPOSI O DE PROCESSOS DE POISGON tee 28 1 3 8 DECOMPOSI O DE PROCESSOS DE POISGON irrst ten 28 1 3 9 TEOREMA DE KEINTHINES 20 6o caros sita ds credita ndo resina Dee 29 1 4 EXERCICIOS PROPOSTOS DE PROCESSOS ESTOC STICOS mmees 30 2 TEORIA DE FILAS iiiaio irao bafo aa as Sia na 39 2 1 INTRODU O E CONCEITOS B SICOS EEN 39 2 1 1 EE 40 2 1 2 PRINCIPAIS CARACTERISTICAS DE UMA FILA assistentes 40 2 1 3 RECETTE 42 2 1 4 TERNINOLOGIMENOTA ES eus ee 43 2 1 5 RESULTADO EENEG 44 2 1 6 EXEMPLOS DE SISTEMAS DE FILAS REAIS ee 45 2 1 7 A DISTRIBUI O EXPONENCIAL NA TEORIA DE FILAS 46 SR PROCESSO DE POISSON cessa a pan Sad n o 51 2 2 FILAS MARKOVIANAS PROCESSO DE NASCIMENTO E MORTE 52 Rodo SISTEMAS INF INDO Shirai caro a na anda ana aan ann 52 2 22 SISTEMAS FINITOS ee 58 23 MODELO DE ERLANG sta a Canas nao T ati enis 60 294 SISTEMA ME 61 2 3 2 ENEE 62 2 4 REDES DE FILAS MARKOVIANAS amassar 63 2 4 1 SISTEMA ABERTO SEM REALIMENTA O 64 2 4 2 SISTEMA FECHADO ege SE 66 2 43 SISTEMAS MISTOS OU ABERTOS COM REALIMENTA O 66 e EE 67 2 4 5 FORMA PRODUTO NA REDE ABERTA eer 69 25 A FILA MJG E 71 2 5 1 MEDIDAS DE DESEMPENHO Eeer 74 2 6 ANEXO E
84. TEMA ESTADO SISTEMA Pela forma produto tem se P K K P K pk lr Kl 208 Xi 2 RA onde p lt l i 1 2 i Considere ainda a rede de filas aberta sem realimenta o mostrada na Figura 2 16 At Wu SAt s Wl atb mm De WI M de mO Figura 2 16 Rede aberta sem realimenta o Au Sejam N4 N2 Ns N4 e Ns os estados em cada n do sistema 1 2 3 4 5 ent o a distribui o de probabilidade conjunta pode ser dada pela equa o abaixo Processos Estoc sticos e Teoria de Filas 70 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP PN N N3 No N BIN JB IN JP INTE IN PINS 2 4 5 1 FORMA PRODUTO NA REDE FECHADA Seja o processo N com distribui o estacion ria dada por Es J para n n n m n K M e bma constante de normaliza o fal No caso de sistemas fechados a constante de normaliza o n o fator vel num produto de constantes associadas a cada esta o Assim n o se tem independ ncia entre o n mero de clientes em cada esta o para cada fixado 2 5 AFILAMIGI A fila M G 1 consiste de um sistema de servidor simples com chegadas Poisson distribui o do tempo de servi o arbitr ria denotada por B x e fun o de distribui o de probabilidade do tempo de servi o denotada por b x A distribui o do tempo entre chegadas dada por 1 e t20 a t 1 e t gt 0 com a taxa m dia de
85. UN O GERADORA DE MOMENTOS Recordemos o desenvolvimento da fun o e em s rie de Maclaurin 2 3 n A Do titt ERR Sabe se que esta s rie converge para todos os valores de x Por isso 10 Ire t e 1 tx n Em seguida Main Ele EQ te C n Para uma soma finita o valor esperado da soma igual soma dos valores esperados No entanto estamos tratando acima com uma s rie infinita e por isso n o pode de imediato aplicar tal resultado Verifica se contudo que sob condi es bastante gerais esta opera o ainda v lida Admitido que as condi es exigidas sejam satisfeitas Como t uma constante tomando os valores esperados podemos escrever Mx t 1 1E X REX ROO 2 n J que Mx uma fun o de vari vel real t podemos tomar a derivada de Mx t em rela o a t isto MI MO SECO MEO EE qu D 2 t s n DI e fazendo t 0 verifica se que somente o primeiro termo permanece e teremos M 0 E X Portanto a derivada primeira da fgm calculada para t 0 fornece o valor esperado da vari vel aleat ria Se calcularmos a derivada segunda de Mx t obteremos MO EX DI HEOO JB n 2 e fazendo t 0 teremos M 0 E X Processos Estoc sticos e Teoria de Filas 81 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Admitido que M n 0 exista e continuando dessa ma
86. Universidade Federal do Rio de Janeiro eo COPPE Programa de Engenharia de Produ o Pa rea de Pesquisa Operacional PO Escola Polit cnica Departamento de Engenharia Industrial PROCESSOS ESTOC STICOS E TEORIA DE FILAS Prof Virg lio Jos Martins Ferreira Filho COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP NDICE 1 PROCESSOS ESTOC ASTICOS iiini iyii aU pd aeia iiaia ani 4 1 1 DESCRI O E DEFINI O DE PROCESSOS ESTOC STICOS mem 4 1 1 1 PROCESSO ESTOC STICOS CONT NUOS DISCRETOS 1111150511111111 4 1 12 DISTRIBUI ES DE PROBABILIDADE si scuisstmesmisanatsisio soy inis sa guias qunseis idas 5 1 1 3 ALGUNS PROCESSOS ESTOC STICOS IMPORTANTES 6 1 2 CADEIAS DE MARKOV EM TEMPO DISCRETO Rn RR RD 7 1 2 1 PROBABILIDADE DE TRANSI O EM V RIOS EST GIOS 8 1 2 2 PROBABILIDADE DE 1 PASSAGEM E PRIMEIRO RETORNO 11 1 2 3 CLASSIFICA O DE E 11 1 2 4 CADEIAS DE MARKOV ERG DICAS PROBABILIDADES LIMITE 12 1 2 5 TEMPO M DIO DE 1 PASSAGEM RECORR NCIA 15 1 2 6 CADEIAS DE MARKOV ABSORVENTES seess eren 17 1 3 CADEIA DE MARKOV EM TEMPO CONTINUO see 19 1 3 1 VISUALIZA O MATRICIAL ca tao ferragem co raid 22 1 3 2 TEMPO AT A PR XIMA TRANSI O asiarsas sreniininasnenig is cien 22 1 3 3 PROBABILIDADE DE REGIME PERMANEN
87. a A probabilidade de indica o de cirurgia para um paciente de 0 15 h 3 salas de opera o no hospital e cada equipe m dica que usa uma sala pode operar at 4 pacientes por dia em m dia Determinar a o tempo total dispendido por um paciente na triagem b a probabilidade de que nenhuma sala de opera o esteja funcionando c o n mero m dio de pacientes a espera de cirurgia 20 Num restaurante pode se escolher entre dois tipos de servi o buffet ou pedido nas mesas Em um certo dia entre 11 30 e 13 00 o regime pode ser considerado estacion rio e se disp e de cozido no servi o de buffet e de omelete no servi o de pedido nas mesas O cozido distribu do em tr s bandejas com uma nica atendente tempo m dio de 8 segundos por bandeja o usu rio deve se dirigir a ela Para a omelete o usu rio se dirige mesa e faz o pedido o tempo m dio de preparo de uma omelete de 3 minutos A cozinha pode processar ao mesmo tempo at 3 omeletes Outros dados venda de tickets m dia de 3 pessoas por minuto chegada de clientes m dia de 170 pessoas por hora probabilidade de um usu rio preferir omelete 0 3 Determinar a n mero m dio de pessoas espera para entrar no restaurante b n mero m dio de pessoas espera de omeletes c n mero m dio de pessoas espera do atendimento no servi o de buffet d o tempo m dio gasto em esperas e atendimentos por uma pessoa que almo a omelete e o tempo m d
88. a Dado que no in cio o po o tinha um desvio ligeiro a probabilidade de ele entrar em curso ser absorvido por E C apLec 0 857 Processos Estoc sticos e Teoria de Filas 136 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Probabilidade de o po o entrar em curso dado que tem chances iguais de come ar com desvio ligeiro ou acentuado 0 5 x 0 857 0 5 x 0 571 0 4285 0 2855 0 714 c di dura o m dia do regime transiente da estado inicial i n m dio de perfis dado estado inicial i do 1 7143 0 5714 2 2857 perfis dba 1 1428 1 7143 2 8571 perfis Como probabilidade de come ar com um desvio ligeiro ou acentuado igual o n mero m dio de perfis 2 2857 2 8571 2 2 57 perfis 25 Na teoria de an lise de cr dito determinados autores verificaram que a estimativa dos valores considerados como devedores duvidosos costuma seguir dois passos b sicos descritos a seguir Classificam se as contas por idade que refletem o estado em que a conta se encontra um m s de atraso dois meses de atraso eic Estima se uma expectativa de perda para cada estado geralmente com base na pol tica da empresa situa o econ mica financeira do cliente e outros fatores relevantes para a an lise do cr dito O segundo t pico merece uma an lise mais detalhada sendo que atualmente diversos m todos principalmente na rea de econometria est o sendo desenvol
89. a de Laplace em processos cont nuos A transformada Z de uma sequ ncia em tempo discreto F n definida por E Ed F 2 Ziele ett 42 n 00 n 00 Processos Estoc sticos e Teoria de Filas 83 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A transformada pode ser unilateral e desta forma transforma se em Kai oo F Z nie DEE n 0 n 0 Esta transformada se chama unilateral e o primeiro caso chamada de transformada Z bilateral Vejamos alguns exemplos a Exemplo 1 Encontre a transformada Z F Z para F n Gin Solu o l se n 0 BEN Define se n 0 0 pela defini o da transformada Z tem se Se Hz F Z 1xZ 1 b Exemplo 2 Seja F t U t e seja F n a sequ ncia obtida ao amostrar se F t a cada T segundos Encontre F Z Solu o Neste caso F n eTu n consequentemente F Z ereto F 2 5 127 Sabendo que m e a a a SG k n l1 a s leeft Jeu Se Liz F Z 1 2 Z og Zi Processos Estoc sticos e Teoria de Filas 84 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Se o per odo de amostra T 1 ent o F Z SES Assim pode se resumir a defini o de transformada Z da seguinte forma Propriedade importante unidade F Z X dA Z lt 1 4linearidade e inuariancia no tempo convolu o logo F 1 x
90. a filas Clientes potenciais de cada classe chegam segundo processos Poisson com taxa m dia de chegada de 10 clientes por hora para a classe 1 e 5 clientes por hora para a classe 2 mas estas chegadas s o perdidas para o sistema se n o puderem entrar imediatamente em servi o Cada cliente da classe 1 que entra no sistema poder receber servi o de qualquer um dos servidores que estiver desocupado os quais tem tempo de servi o com distribui o exponencial com m dia de 5 minutos Cada cliente da classe 2 que entra no sistema requer o uso simult neo dos dois caixas os Processos Estoc sticos e Teoria de Filas 174 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP dois caixas juntos agem como se fossem um nico servidor e o tempo de servi o tem distribui o exponencial com m dia de 5 minutos Assim um cliente desta classe que chega ser perdido para o sistema a menos que ambos os caixas estejam desocupados para come ar o servi o imediatamente a Formule um modelo de filas como um processo de Markov de tempo cont nuo definindo os estados e construindo o diagrama de transi o de estados b Descreva como a formula o obtida em a pode ser ajustada ao formato de um processo nascimento e morte c Use o modelo nascimento e morte para calcular a distribui o de regime permanente do n mero de clientes de cada classe no sistema d Para cada uma das classes de clientes qual
91. a fra o do n mero esperado de clientes que n o s o admitidos no servi o 66 Uma farm cia possui 3 caixas O gerente usa a seguinte estrat gia de opera o pra a abertura das caixas se o n mero de clientes na farm cia for menor ou igual a 2 a farm cia opera com apenas um caixa se o n mero de clientes for igual a 3 ou 4 a farm cia opera com dois caixas se o n mero de clientes for maior ou igual a 5 a farm cia opera com tr s caixas Os clientes chegam na farm cia de acordo com uma distribui o de Poisson com taxa de 10 clientes por hora O tempo de atendimento de um cliente em um caixa segue uma distribui o exponencial com tempo m dio de 12 minutos por cliente a Qual a probabilidade de apenas um caixa se aberto b Quantos caixas ficam em m dia fechados Processos Estoc sticos e Teoria de Filas 175 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Exerc cios de filas respostas D VEVFFVEVVFVFEV 2 3 4 5 6 7 A B N o se alteram 8 9 10 11 12 13 A 2 A 4 Exponencial 14 15 aeb 1 3 min 16 a 4h24min b 49 min c 3h42min 17 a 40 2 b 2 25 e 14 06 carros c 1h 5min 18 a 0 98 cestos b 9 4 carro as c 7 escravos d 27 44 cestos e 9 4 carro as 19 a 2h40 b 7 5 c 1 7 pacientes 20 a 16 1 pessoas b 4 45 pessoas c 3 05 pessoas d 1414 e 756 1 4 21 0 5 horas 22 Manteria a equipe inalterada
92. a lance tenho uma probabilidade p de ganhar 1 e probabilidade q 1 p de perder 1 Meu objetivo aumentar meu capital para 4 e t o logo eu o Processos Estoc sticos e Teoria de Filas 116 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP consiga eu saio do jogo assim como se eu ficar sem nenhum dinheiro a Construa a matriz de probabilidades de transi o e o diagrama de transi o de estados para a cadeia de Markov que modela o jogo b Ap s 2 jogadas qual a probabilidade que eu tenha 2 E 3 c Porque n o razo vel para este jogo falar em probabilidades de regime permanente p p P OS oO o GC 1 Rare Teun Se q q q 12340 1 2 340 1 0 p Ojo q 1 pq 0 Pio q P 2 q0pido pPP 2 0 2pq 0 Ip q 3 0 q0 po ai q o pain 4 00 0 10 4 00 0i O oloo 0 0 1 olo o dd 1 Ap s 2 jogadas probabilidade de ter 2 pa 0 3 pis p As probabilidades de regime permanente descrevem as chances n o nulas do processo estar em cada estado ao longo do tempo Como o processo em quest o apresenta dois estados absorventes segue que as chances do processo estar num estado transiente tender o a zero ao longo do tempo enquanto as chances de estar num dos estados absorventes tender o a 1 11 O livro de did tico PO A Solu o vende 1 milh o de exemplares a cada ano Alguns dos leitores conservam o livro enquanto outros vendem o livro de volta para a livraria Supo
93. aail 2 30 p 2 9 1 9 Io 1 1 p 5 6 p 1 6 2 5 6p CH 1 4 9M p p 5 6p 1 61 p 6l p 12 b C lculo de p P K p P i p i do Teorema da Probabilidade Total i 2 A probabilidade de perder a soma dos produtos da probabilidade de perder dado que tirou ino primeiro lan amento pela probabilidade de tirar no primeiro lan amento p P 2 p 2 1 1 36 p P 3 p 3 1 2 36 D I 4 p 4 p 7 1 07 p 4 p T 11 P 7 P 4 p 7 P 4 o 7 0 4 Lo 7 p 6 2 36 p P 10 p 10 Analogamente PCP S p S Lot o S L p 7 p S 24 360 p P 9 p 9 Processos Estoc sticos e Teoria de Filas 107 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP D I 6 p 6 o 7 p 6 I p 7 p 6 30 396 p P 8 p 8 p P 7 p 7 0 p P 11 o 11 0 p P 12 p 12 1 36 1 1 Mas p P Portanto p 0 7194 GE p 0 23 2 9 1 9 Io 07194 01139 1 6 SE A 10 0 0 0 1 E U O 2276 p o 3 564 0 493 0 507 A ER 0 406 0 594 Probabilidade de vit ria rg 0 493 Probabilidade de derrota mp 0 507 Probabilidade de Ganhar dado que no primeiro lan amento tirou 6 2 n P GI6 5 JS 5 JS 5 GEI 5 f ao TAN A 36 136 36 136 36 36 36 36 11 11 Outra forma de pensar o problema estender o estado continua em seis estados transientes representados pelas pontua es obtidas na primei
94. ada m n matriz de probabilidade de transi o P P Um processo dito homog neo no tempo se a transi o depende de t mas n o depende de t Nesse caso temos FO Xstosty t BL x 0 t Vig O correspondente para estado e tempo discretos pe SE Diagrama de Transi o de Estados o grafo valorado representativo do processo estoc stico onde o conjunto de v rtices est associado ao conjunto de estados e seus valores as respectivas probabilidades de estado O Conjunto de arcos por sua vez est associado as poss veis transi es e valorado pelas probabilidades de transi o 1 2 1 12 3 2 1 3 n gt O De e 1 1 3 ALGUNS PROCESSOS ESTOC STICOS IMPORTANTES Processo de WEINER Movimento Browniano a disposi o de uma part cula suspensa em um fluido sujeita a sucessivas colis es com part culas vizinhas um exemplo cl ssico do processo de Weiner O fen meno f sico foi descoberto pelo bot nico Robert Brown em 1827 A teoria do comportamento desse processo foi desenvolvida por Einstein 1906 e Weiner 19283 Processos Estoc sticos e Teoria de Filas 6 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Processo de Poisson o processo estoc stico Jm tal que e nt ee o denominado processo de Poisson Esse processo modela razoavelmente bem o n mero de chamadas numa cabine telef nica por exemplo Process
95. ada poss vel considerar o tempo de servi o como sendo determin stico ou aleat rio A distribui o do tempo de servi o pode depender do estado do sistema ou at mesmo do tipo de usu rio a ser servido Por m a hip tese mais simples a de independ ncia isto o servi o um processo de renova o Dentre as distribui es mais usadas destacam se a exponencial Erlang e hiperexponencial O n mero de servidores dispon veis para o atendimento a uma mesma fila tamb m deve ser especificado Neste caso comum mencionar os servidores est o em paralelo numa refer ncia a estarem atendendo uma mesma fila c Disciplina de Atendimento A disciplina de atendimento se refere a maneira como os usu rios ser o selecionados para receber servi o No nosso cotidiano os atendimentos em geral se d o pela ordem de chegada A fila no caixa do supermercado a retirada de carros de um estacionamento e a compra de ingressos para o cinema s o exemplos dessa disciplina que ser referida como FCFS do ingl s first come first served Em aplica es outras disciplinas podem aparecer A disciplina LCFS last come first served pode ser usada em modelos de arquivo ou de busca em disco r gidos O servi o em ordem aleat ria independente do tempo de chegada pode servir de modelo para alguns sistemas computacionais Outra disciplina que tem aplica o em computa o a do processamento ou tempo compartilhado processor or time sharing q
96. ado por Jackson afirma que a distribui o estacion ria do n mero de usu rios presentes no sistema pode ser calculada pelo produto de distribui es estacion rias marginais referentes a cada centro O resultado obtido tamb m chamado de solu o na forma produto indica que o sistema se comporta como se cada centro de servi o i e J fosse uma fila com chegadas e servi os exponenciais com taxas y u n respectivamente independente dos demais centros Assim no caso de S servidores id nticos ter amos o sistema comportando se como se fosse uma cole o independente de filas MIMI No entanto importante observar que nem sempre as chegadas internas forma um processo de Poisson Portanto a forma produto deve ser aplicada com cuidado A vantagem da forma produto entre outras a possibilidade de identifica o r pida dos efeitos da mudan a dos par metros de uma esta o sobre o desempenho de toda a rede Para utiliza o como constantes normalizadoras a seguir define se n Vi gt o MO onde o termo correspondente a n O igual a 1 b Sob a condi o de b lt VieJ o processo N te distribui o estacion ria dada por Processos Estoc sticos e Teoria de Filas 69 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP E b n f A com ETC z n Ge A ieJ eo S i Sendo assim considere a rede de filas aberta mostrada na Figura 2 15 ESTADO SIS
97. ais O servidor 1 pode servir com uma taxa exponencial 20 clientes por hora enquanto o servidor 2 pode servir tamb m com uma taxa exponencial 30 clientes por hora Ap s completar o servi o no servidor 1 metade dos clientes deixa o sistema enquanto a outra metade vai para o servidor 2 Ap s completar o servi o no servidor 2 3 4 dos clientes deixa o sistema e 1 4 retorna ao servidor 1 a Qual a fra o do tempo o servidor 1 est ocioso b Qual o n mero m dio de clientes em cada servidor c Qual o tempo m dio que um cliente gasta no sistema d Como se alteram as respostas a at c se o servidor 2 puder atender em m dia a apenas 20 clientes por hora 63 Meu escrit rio usa 2 l mpadas Em m dia uma l mpada dura 22 dias exponencialmente distribu do Quando uma l mpada se queima em demoro em m dia 2 dias exponencialmente distribu do para substitu las a Construa o diagrama de transi o de estados para o problema b Determine qual a fra o do tempo o escrit rio est com luminosidade m xima m dia e m nima 64 O programa de engenharia de produ o aceita a cada ano 20 novos alunos de doutorado Se um aluno de doutorado gasta em m dia 5 anos para concluir seu curso qual o n mero esperado de alunos de doutorado no programa Use o modelo de filas adequado para justificar sua resposta 65 Considere um sistema de filas que tenha duas classes de clientes dois caixas provendo servi o e n o admit
98. al com m dia de 15 minutos a Considere a formula o deste problema de filas onde cada sapato individualmete n o o par de sapatos considerado o cliente Para esta formula o construa o diagrama de transi o de estados e desenvolva as equa es de balan o sem precisar resolver b Considere agora que o par de sapatos o cliente Para esta formula o construa o diagrama de transi o de estados desenvolva as equa es de balan o e obtenha o tempo m dio at que um par de sapatos esteja reparado Processos Estoc sticos e Teoria de Filas 173 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 60 Um posto de gasolina em um local de grande concorr ncia lan ou a seguinte campanha Se o cliente tiver de esperar para abastecer o pre o da gasolina de 1 00 por litro O pre o normal da gasolina de 1 20 litro Com est promo o os clientes chegam ao posto segundo um processo Poisson com taxa m dia d 15 por hora O tempo de servi o na bomba para facilitar considere uma nica bomba exponencialmente distribu do com m dia de 3 minutos Em vista do pre o atrativo todos os clientes que chegam esperam pelo atendimento Determine o pre o esperado da gasolina que vendida 61 Na rodovia do Vai e Vem que d acesso ao Parque Ecol gico do Lobo Guar foi instalada uma nica cabine de ped gio Na poca da instala o foi imaginado que n o haveria tr fego sufic
99. ama de transi o de estado e determine a matriz de probabilidade de transi o b Determine a probabilidade que a casa esteja lotada c Dado que a casa esta lotada quanto tempo demora at que ela esteja completamente vazia Processos Estoc sticos e Teoria de Filas 35 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 22 Suponha que voc conduziu uma s rie de testes sobre um procedimento de treinamento e verificou que a seguinte matriz de probabilidades descreve o conjunto de respostas corretas e incorretas i 1 simo teste Correto Incorreto j simo Correto 0 95 0 05 teste Incorreto 0 01 0 99 a Que propor o de respostas corretas se pode esperar de um estagi rio absolutamente treinado b Que propor o de respostas corretas se pode esperar de um estagi rio ap s quatro repeti es do procedimento caso a resposta inicial seja igualmente poss vel de ser correta ou incorreta c Qual a probabilidade de que se obtenha pela primeira vez uma resposta correta exatamente quatro tentativas ap s uma resposta incorreta d Qual o n mero m dio de tentativas para que se obtenha uma resposta correta ap s ter obtido uma resposta incorreta 23 Um jogador joga um jogo limpo no qual as chances s o 2 contra 1 Em outras palavras ele tem 1 3 de probabilidade de ganhar e 2 3 de perder Se ganhar ganhar 2 Se perder perder
100. an ncia espera atendimento de um cliente idoso na ag ncia E de um cliente n o idoso 47 Uma loja tem dois balconistas cada um capaz de atender fregueses a uma taxa m dia de 60 por hora os tempos de atendimento s o exponencialmente distribu dos A capacidade da loja de 4 fregueses com espera do lado de fora proibida Os fregueses chegam loja de acordo com um processo do tipo Poisson onde a taxa m dia de chegadas depende do n mero de pessoas na loja da forma Determine Clientes na loja 0 1 2 3 4 Taxa m dia de chegadas clientes hora 100 125 150 175 200 a o n mero esperado de fregueses na loja b o valor esperado do tempo que um fregu s deve aguardar por atendimento c a taxa esperada de perda de fregueses devido limita o de capacidade da loja 48 Cada passageiro de um v o e sua bagagem deve ser checada para verificar a exist ncia de armas e explosivos Suponha que no aeroporto de Pol ndia chegue em m dia 10 passageiros por hora com tempos entre chegadas exponenciais Para verificar os passageiros o aeroporto deve ter um posto de checagem constitu do de detector de metais e uma m quina de Raio X para a verifica o de bagagem Quando um posto de checagem est em opera o s o necess rios dois funcion rios Um Processos Estoc sticos e Teoria de Filas 171 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP posto pode verificar em m dia 12 passagei
101. analmente Sejam D4 Ds Di vari veis aleat rias que representam a demanda pelas m quinas durante a semana i Seja X o estoque existente de m quinas e X o n mero de m quina dispon veis ao final da semana i S bado noite a loja faz uma encomenda que ser entregue em tempo para a abertura da loja na 2 feira A pol tica de encomendas da loja s S 1 3 ou seja se no S bado a noite a quantidade de m quinas em estoque for menor que s 1 nenhuma m quina em estoque ent o a loja encomendar at S 3 m quinas caso contr rio nenhuma m quina ser encomendada suposto que haja perdas de vendas quando a demanda exceder o estoque dispon vel As vari veis aleat rias podem ser avaliadas iterativamente pela express o _ maxi 3 D Ojsex lt 1 max X D OlseX gt 1 Considerando que a demanda tem uma distribui o de Poisson com m dia 1 a matriz de transi o de uma etapa dada por 0 080 0 184 0 368 0 368 0 632 0 368 0 0 P 0 264 0 368 0 368 0 0 080 0 184 0 368 0 368 a Descreva como a matriz de transi es pode ter sido obtida b Se o processo iniciou com um estoque de 3 m quinas qual o tempo esperado para que o estoque se esgote c Qual a probabilidade de encontrar o estoque com 0 1 2 3e 4 m quinas d Qual o tempo m dio entre duas encomendas 18 Um naturalista est observando o comportamento de um sapo em um pequeno lago no qual h 4 ninf ias plantas aqu ticas
102. anaus para a base de produ o de Urucu da Petrobr s realizado por dois helic pteros com capacidade para 16 passageiros cada A dura o da viagem tem distri bui o exponencial com m dia 2 horas O procedimento de embarque o seguinte Os passageiros que chegam a uma taxa de 12 por hora s o inscritos nos v os na ordem em que chegam Quando a lota o de um v o est completa ent o os passageiros s o admitidos numa sala de vistoria e espera onde aguardam a prepara o da aeronave para o embarque a Construa o diagrama de transi o de estados para este sistema b Usando o modelo adequado calcule o n mero esperado de pessoas na sala de espera e o tempo m dio entre o instante que o passageiro entra na sala de espera e o instante que o helic ptero pousa na base de Urucu 33 Um projetista de plataforma de produ o de petr leo se deparou com a seguinte situa o A produ o de petr leo estimada em 15 000 m3 dia Cada bomba de transfer ncia tem capacidade para transferir 5 000 m3 dia e em m dia trabalha 20 dias sem dar problemas exponencialmente distribu do O custo de aquisi o de cada uma destas bombas de US 150 000 00 O projetista precisa decidir quantas bombas comprar Os dados adicionais de que ele disp e s o o tempo m dio para reparar uma destas bombas quando elas d o problema de 2 dias exponencialmente distribu dos usualmente existe uma equipe de manuten o embarcada que pode reparar uma b
103. conjunto enumer vel ou finito Estado Cont nuo caso contr rio b Em rela o ao Tempo Tempo Discreto t finito ou enumer vel Tempo Cont nuo caso contr rio Nota o Processo em tempo cont nuo X t t 2 0 Processo em tempo discreto X t t 1 2 3 Processos Estoc sticos e Teoria de Filas 4 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Exemplos Estado Discreto e Tempo Cont nuo n mero de usu rios em uma fila de banco em um determinado instante colis es entre duas part culas no intervalo de 2 minutos Estado Cont nuo e Tempo Cont nuo n vel de uma represa observado em um intervalo de tempo Estado Discreto e Tempo Discreto n mero de m quinas avariadas no fim do dia Quantidade de barris petr leo produzidas ao final do dia por uma determinada multinacional Estado Cont nuo e Tempo Discreto cota o de uma a o no fim do dia 1 1 2 DISTRIBUI ES DE PROBABILIDADE Para um dado valor de t o processo estoc stico X t uma vari vel aleat ria e a obten o de sua distribui o de probabilidade feita como qualquer outra vari vel aleat ria Entretanto quando t varia ao longo do conjunto T a informa o X t n o fornecida por uma simples distribui o para um dado t Para uma informa o completa do processo precisamos da distribui o conjunta X t t e T Com isso podemos prever o comportamen
104. de acomodar somente um n mero finito de usu rios ou seja se um usu rio chega e a fila est cheia ele vai embora sem esperar o atendimento Observe que neste caso a taxa de chegada n o precisa ser menor que a taxa de servi o u pois a fila tem um tamanho fixo finito Neste tipo de modelo aparece uma nova vari vel M que o n mero m ximo de usu rios que podem estar no sistema sendo M 1 o n mero permitido na fila As f rmulas para este modelo s o 1 p P plA M 41 F JoBpiizu C Bp A u L L 1 P A taxa de chegada dos usu rios no sistema No entanto alguns usu rios chegam e encontram a fila cheia ou seja v o embora A taxa de chegada efetiva s d a taxa m dia das unidades que realmente permanecem no sistema Ag u 1 P 4 1 P As demais f rmulas ficam como L L A Ae Ay A 2 2 2 2 Modelo M M s M Fila Finita s gt 1 Processos Estoc sticos e Teoria de Filas 58 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Nesta se o vamos redefinir p e p para simplificar a escrita das f rmulas A P p A HA Temos ent o 1 h i Dis Li E p Bpinze P pls lt n lt M sis 0p n gt M onde s o n mero de esta es de atendimento e M o tamanho da popula o Popula o Finita Em muitos problemas pr ticos a considera o de que a popula o de tamanho infinito leva a
105. de seis faces No primeiro lan amento se tirarmos 7 ou 11 n s ganhamos imediatamente Se tirarmos 2 3 ou 12 perdemos imediatamente Se o resultado do primeiro lan amento for 4 5 6 8 9 10 n s continuamos a lan ar os dados at obtermos um 7 quando perdemos ou at obtermos o mesmo resultado que o primeiro lan amento quando ganhamos Use os seus conhecimentos de Cadeias de Markov para determinar nossa probabilidade de vit ria IO 1 O Perde Wi Do estado inicial antes do primeiro lance de dados o jogador pode ganhar de primeira se tirar 7 6 36 ou 11 2 36 com 2 9 de probabilidade Pode ainda perder de primeira se tirar 2 1 36 3 2 36 ou 12 1 36 com 1 9 de probabilidade Poder ainda continuar jogando caso n o ganhe e nem perca com probabilidade 1 1 9 29 2 8 Os estados P Perde e G Ganha s o absorventes Do estado C Continua perder se obtiver um 7 1 6 Logo pcp 1 6 C lculo de p a Seja p P a probabilidade de perder o jogo Processos Estoc sticos e Teoria de Filas 106 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP pelado l 2 nl p 5 46 SE S SC bat 121 1 1 1 Assim pD gt gt d p p 4 d D gt 4 gt gt p P na A p p S Outra maneira de chegar a este resultado seria construir P 0 2 3 2 9 1 9 p 1 e AE 1 9 pelo p 5 6 p 1 6 A 0 0 R B 29 19 0 0 1 0 0 1 p 5 6 p 1 6 0 0 0 1 Assim
106. deral do Rio de Janeiro Programa de Engenharia de Produ o PEP 4 REFER NCIAS BIBLIOGR FICAS Livros de Processos Estoc sticos Teoria de Filas 1 2 3 4 5 6 De Groot M H Probality and Statistics Addison Wesley 1978 Ross SM Introduction to Probability Models Academic Press Bhat U N Elements of Applied Stochastic Process Weley Feller N An Introduction to Probabilty Models and its Applications Wesley Kleinrock L Queueing Systems Vol 1 Theory Wiley Interscience Publication 1975 Magalh es M N Introdu o Rede de Filas Departamento de Estat stica Instituto de Matem tica e Estat stica Universidade de S o Paulo ABE Associa o Brasileira de Estat stica 1996 Livros de Pesquisa Operacional 7 8 9 10 11 12 13 14 15 16 Willians H P 1984 Model Building in mathematical Programming Ed Wiley Arenales et Al 2007 Pesquisa Operacional Ed Campus Ragsdale N 2001 Speadsheet Modeling and Decision Analysis Ed Southwestern College Publishing Simchi Levi D Kaminsky P amp Simchi Levi E Cadeia de Suprimentos Projeto e Gest o Ed Bookman 2003 Winston W L Operations Research Applications and Algorithms 3rd edition Belmont Duxbury Press 1993 Hillier F S Lieberman G J Introdu o a Pesquisa Operacional Editora Campus RJ 1988 pp 394 444 Philips Ravidran Soeberg
107. dia de dois clientes por minuto chega ao banco O tempo que um caixa demora para atender a um cliente em m dia 2 minutos Cada caixa custa ao banco 9 00 hora Tempos entre chegadas e de atendimento podem ser considerados exponenciais Para minimizar a soma dos custos de servi o e de atraso quantos caixas devem trabalhar Processos Estoc sticos e Teoria de Filas 172 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 54 Uma equipe de projeto disp es de 2 esta es de trabalho cada uma delas com um tempo entre falhas exponencialmente distribu do com m dia de 40 dias O projeto tem um contrato de manuten o com o fornecedor que permite que at as duas esta es sejam reparadas simultaneamente quando da ocorr ncia de defeitos O reparo de cada esta o envolve duas etapas uma visita t cnica seguida pelo reparo propriamente dito Os tempos de cada etapa podem pode ser considerados exponencialmente distribu dos com dura o m dia de 10 dias Desenvolva um modelo de filas para representar o problema e obtenha a diagrama de transi o de estados b as equa es de equil brio e de recorr ncia c n mero m dio de esta es em opera o normal d percentagem do tempo em que todas as esta es est o paradas 55 O Programa de Engenharia de Produ o est procurando determinar se deve arrendar uma copiadora r pida ou lenta O valor da hora de trabalho dos funcion rios q
108. distribui o de Poisson Dura o do servi o seguindo a distribui o Exponencial Fila nica com sele o FIFO primeiro a entrar primeiro a sair 1 esta o de servi o A Figura 2 2 apresenta esquematicamente o funcionamento dessa fila Servi o Exponencial Chegadas Poisson Sala de espera infinita Partidas Figura 2 2 Fila MIMI Processos Estoc sticos e Teoria de Filas 52 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Sejam A t 1 e e B t 1 e as distribui es do intervalo entre chegadas e de dura o do servi o respectivamente Os par metros e u s o referidos como taxas indicando o n mero m dio de usu rios que chegam ou s o servidos por unidade de tempo Denotando por N t o n mero de usu rios no sistema no instante t pode se demonstrar que N t t gt 0 um processo de Markov em tempo cont nuo com o espa o de estados sendo os inteiros n o negativos O tempo de espera para fazer uma transi o s depende do estado presente e se o sistema cont m pelo menos um usu rio ter distribui o exponencial de par metro ul correspondente ao m nimo entre duas exponenciais independentes servi o e chegada No caso de n o haver nenhum usu rio no sistema o tempo para uma transi o ter distribui o exponencial de par metro O processo de Markov NO de fato um processo de nascimento e morte com ta
109. e Um levantamento feito por uma companhia de seguro mostrou que os dois cofres ficam vazios durante 10 do tempo De posse deste dado voc que o gerente teria condi es de dizer por quanto tempo em m dia os valores de um h spede ficam guardados Qual seria o n mero de cofres necess rio para mantendo o mesmo tempo de ocupa o dos cofres atender ao dobro da demanda por cofres garantindo que o tempo desocupado de cada cofre n o ultrapasse 20 do tempo 30 Em uma ag ncia de banco 3 funcion rios ocupam 3 caixas destinados apenas a retiradas cada um pode atender em m dia a 60 pessoas por hora Os clientes que demandam essas caixas chegam a Processos Estoc sticos e Teoria de Filas 167 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP m dia de 150 por hora e entram com igual probabilidade em qualquer das filas que se formam diante delas O sistema se encontra em equil brio estacion rio O gerente da ag ncia resolveu adotar para essas caixas o sistema de fila nica a Qual a probabilidade de uma dada caixa estar ociosa no sistema antigo b Idem no novo sistema c Qual a economia ou perda de tempo obtida por um cliente que vai fazer retirada com a mudan a de sistema 31 Em um supermercado da cidade existem 30 caixas distribu das da seguinte forma 2 caixas se destinam a emiss o de nota fiscal 3 caixas s o caixas r pidas e as demais caixas s o cai
110. e 1 2 e 2 minutos dependendo da velocidade do esmeril Os custos de opera o e manuten o aumentam rapidamente de acordo com a velocidade do esmeril de modo que o custo estimado por minuto para uma m dia de Uu de 10p Os operadores de m quinas chegam para amolar seus instrumentos de acordo com um processo de Poisson a uma taxa m dia de um a cada 2 minutos O custo estimado de um operador estar afastado de sua m quina enquanto ocupado no esmeril de 15 00 minuto Represente num gr fico o custo total esperado por minuto E CT versus u e determine o valor timo deu 41 O propriet rio de uma pequena mas procurada banca de jornais atende a clientes a uma m dia de um a cada 30 segundos sendo a distribui o exponencial Os clientes chegam de acordo com um processo Poisson a uma taxa m dia de tr s por minuto e podem ou n o esperar para serem atendidos se o dono estiver ocupado com outro cliente Um n mero de clientes preferem n o esperar e fazer suas compras em outro lugar A probabilidade de que um cliente desista n 3 onde n o n mero de clientes j na loja Que lucro pode o propriet rio esperar perder dos clientes que ir o fazer suas compras em outro lugar se o lucro m dio por cliente de 0 30 42 Um posto de lavagem de carros tem espa o para somente tr s carros em espera e somente duas plataformas de lavagem Cada plataforma pode acomodar somente um carro de cada vez Os propriet rios chegam de acordo com
111. e 3 1 2 1 2 m 1 27 2 57 m 4 9 gt 2 5 3 5 m 5 9 mtm l d Q S bcadeia absorvente 0 3 0 7 0 0 SH E om estados recorrentes 06 0 4 0 0 O 02 03 0 5 01 0 2 04 0 3 Estados 3 e 4 s o transientes P 04 03 0 3 O 0 1 GS 03 05 0 2 0 2 0 3 rio ve 02 0 99 CC ER e e p 03 07 0 7 037 0 67 m 0 461 106 04 x 0 538 Para os estados 1 e 2 m 7 1 Processos Estoc sticos e Teoria de Filas 121 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 3 0 O 1 3 O 1 5 4 5 0 O 1 4 3 4 0 1 8 O O 7 8 Estados recorrentes 2 3 e 1 4 Para os estados 1 e 4 1 8 7 8 Para os estados 2 e 3 m m 1 o es o T3 RA 1 3 E 2 3m 1 87 D 3 11 gt x 8 11 1 5 4 5 m 1 5m 1 47 x 5 21 gt x 16 21 1 4 3 4 m m 14 Dois jogadores jogam uma moeda honesta Se der cara o jogador I paga R 1 ao jogador ll se der coroa o jogador Il que paga R 1 ao jogador I Considere que a quantidade total de dinheiro em jogo isto a soma das quantias possu das pelos dois jogadores de R 5 Modele o jogo como uma cadeia de Markov Dado que o jogador I come ou o jogo com R 3 calcule o tempo esperado do jogo e a probabilidade de que cada um dos jogadores ven a o jogo isto alcance R 5 1 2 1 2 1 2 E UO AA Go N 1 2 1 2 1 2 Co OO GO 1 2 1 2 1 2 3 4 1 6 1 2 0 8 0
112. e Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Custo m dio do pedido 4000 n m dio de computadores comprados por semana 4000 3 7 2 7 0 7 84000 3 5 2 540 6000 Custo total esperado 116 67 333 33 6000 6450 Logo Pol tica tem o menor custo semanal esperado devido ao menor custo de manuten o de estoque 09 O programa de treinamento de supervisores de produ o de uma determinada companhia consiste de duas fases A fase 1 a qual envolve 3 semanas de aula te rica seguida da fase 2 a qual envolve 3 semanas de aprendizagem pr tica Pelas experi ncias anteriores a companhia espera que somente 60 dos candidatos da fase te rica passem para a fase pr tica com os 40 restantes sendo desligados do programa de treinamento Dos que fazem a parte pr tica 70 s o graduados como supervisores 10 enviados para repeti la e 20 dispensados a Desenhe o diagrama de transi o de estados b Quantos supervisores pode a companhia esperar formar de seu programa normal de treinamento se existem 45 pessoas na fase te rica e 21 na fase pr tica 1 12 D 8 ee To 06 04 O PE 0 E EP EA N D DM A Ce AU Or 06 04 0 1 23 04 ol 8 15 7 15 lo 09 02 0 7 lo 10 9 0 2 OI 2 9 7 9 N esperado de supervisores 45 a 21 a 45 E 21 dr 37 10 No instante 0 eu tenho 1 Nos instantes 1 2 3 eu jogo um jogo no qual eu aposto 1 A cad
113. e O processo estacion rio e A probabilidade de 2 ou mais mudan as de estado acontecerem num certo intervalo de tempo A t pequeno zero e A probabilidade de uma transi o de O para 1 ou de 1 para O em um certo intervalo de tempo A t pequeno proporcional a A t Poa At a At 14 e Pio At B At 15 Assim temos que Processos Estoc sticos e Teoria de Filas 20 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Poot AL Poot Poo At Deal Dat AL Daaf AL Baal po ADIA poo D Pro AL Pool At Po DI ADJ Poo DI BCAL Poolt At Poolt B a B Poot At Poolt At Boa B a B Poo t At lim Daat Pott 5 a Pool Poli B a B Poo t dt dPoo t dt p a B Pool Integrando ambos os lados temos h f a BD Po D a p B a B Pool ce t Como py 0 1 temos 8 a B ce a Logo B O api 1 e 16 EN a b oer Analogamente podemos obter 94 O a Poli e Ka 17 ot ot Ki a p t ga a 8 t 18 ot oer bit ern 19 ot ot Processos Estoc sticos e Teoria de Filas 21 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 3 1 VISUALIZA O MATRICIAL Pool _ AP t Bpoi t dt dp OP volt Ppa t dt IP ap t Bp A dt dp op lt Bolt dt Zo P
114. e limitada pela taxa 43 e Respostas A B e D transparecem inalteradas N o poss vel calcular o n total de clientes na rede com as f rmulas conhecidas pois o teorema de Burke n o mais v lido 5 Seja a rede de filas markovianas esquematizada abaixo Se A 10 clientes hora A 20 clientes hora As 20 clientes hora H 30 clientes hora 4 40 clientes hora a Determine o gargalo do sistema isto a pior fila b Qual a probabilidade de todo o sistema estar ocioso c Qual a probabilidade de existir uma nica pessoa no sistema 4 12941 11 31 1 1 1 f 8 E dr 23 EI 48 36 32 1 1 b B P P P 1 0 1 0 l p 3 4 1 2 O R RP RAR PRE AR eer aa a Fila 3 6 Em um laborat rio de computa o gr fica da universidade existem 4 esta es de trabalho cada uma delas com um tempo entre falhas exponencialmente distribu do com m dia de 40 50 dias O laborat rio tem um contrato com o fornecedor que permite que at duas das esta es sejam reparadas simultaneamente quando da ocorr ncia de defeitos O tempo de reparo de cada esta o pode ser considerado exponencialmente distribu do com dura o m dia de 10 dias Desenvolva um modelo de filas para representar o problema e obtenha a o diagrama de transi o de estados b as equa es de equil brio e de recorr ncia Processos Estoc sticos e Teoria de Filas 143 COPPE Universidade Federal do Rio de Jane
115. e py Mm Di pul m Lat Mi Pj HI4D pa ED kj kzj m 173 pum 10 ki Exemplo Servi o de Transporte de Passageiros por um Helic ptero Consideremos uma cidade com apenas tr s helipontos Barra Shopping 1 Santos Dumont 2 e Gale o 3 e um nico helic ptero que recolhe o passageiro de um dos helipontos e os leva at um outro dos helipontos onde aguardam at que apare a outro passageiro Um nico passageiro um grupo com o mesmo destino atendido de cada vez Processos Estoc sticos e Teoria de Filas 15 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Se o helic ptero est brevemente no Gale o qual a probabilidade de que ele volte ap s 3 viagens Se o helic ptero est brevemente no Santos Dumont quantas viagens em m dia ir o correr at que ele volte ao Santos Dumont Em um longo per odo de tempo qual a fra o de viagem se destinam ao Barra Shopping 1 2 1 1 2 3 2 1 3 Re SM 1 3 ne Figura 1 7 Exemplo Servi o de Transporte de Passageiros por um Helic ptero a matriz de transi o de estados O G lra l rt Lo l t lr O w w N O grafo mostrado na Figura 1 7 um recurso muito usado no estudo dos processos estoc sticos denominado diagrama de transi o de estados Solu o 2 5 13 9 12 36 P 7 7 8 54 18 27 4 19 0 9 54 54 11 Assim a probabilidade de que o helic pt
116. eet Poli Pu Dal 0 D mA Age ds miga Da linha d temos Processos Estoc sticos e Teoria de Filas 26 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP dPo lt GEN APoo t dpo t APoo t AP dt Ou Au APo dt dp t Pail A n AU APon UI Resolvendo o sistema para a linha d temos dpolt Dout In Pt At c Pool ce como Ball zl segue que c 1 Pool e 27 Assim o tempo de perman ncia no estado tem distribui o exponencial em Tell ap Abana Multiplicando ambos os lados da equa o por e temos e Pet An Pon o e Ap AU dr de Pot A SE e APona 1 Para n 1 temos de py t Ae e dt de py t dt e Bail At id Pa t At d e como py 0 O temos Processos Estoc sticos e Teoria de Filas 21 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Pa t Ate At n C Pao O De 28 O n mero de eventos tem distribui o de Poisson com par metro At que o n mero esperado de eventos ocorrendo no per odo t 1 3 6 TEMPO ENTRE EVENTOS CONSECUTIVOS Seja T a vari vel aleat ria correspondente ao tempo entre o n 1 simo e on simo evento Assim T o tempo at que o primeiro evento ocorra Po tb P nenhumeventoocorranotempot Po PIT gt t PIT gt t e PIT
117. efini o de estado peri dico n o garante que o estado ocorra mas se ele acontecer ter que ser naquele tempo Estado Absorvente lim no 1 para cada i j estado absorvente n gt 0 Cadeia Absorvente possui pelo menos um estado absorvente como mostra a Figura 1 5 onde os estados 4 e 5 s o absorventes RH SE Figura 1 5 Exemplo de Cadeia Absorvente 1 2 4 CADEIAS DE MARKOV ERG DICAS PROBABILIDADES LIMITE Uma cadeia dita Erg dica se for irredut vel recorrente n o nula e aperi dica limp Il 9 Processos Estoc sticos e Teoria de Filas 12 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP onde JI j fra o do tempo que o processo passa no estado j medida que o tempo do processo cresce o estado inicial perde import ncia assim como o pr prio tempo H I vetor linha lim P TI m r plicas do vetor 1 n gt 0 Da equa o de Chapman Kolmogorov temos Du Sa PDP lim P limP P limP P HA n gt 500 no I P A equa o acima representa um sistema de equa es lineares com m sistemas independentes e iguais com m equa es lineares cada um Isto m r plicas do sistema abaixo II IIP Xn 1 vi Uma outra abordagem para o problema a ser considerada pela utiliza o da Lei de Conserva o do Fluxo a qual garante que no estado permanente o fluxo que sai do sistema igual ao fluxo que entra
118. egam A demanda m dia pelo escrit rio de 20 pessoas por dia de 8 horas e cada cliente ocupa em m dia 40 minutos do advogado que o atendeu a Quantas horas por semana pode um advogado utilizar no atendimento de clientes b Quanto tempo em m dia gasta um cliente ao se dirigir ao escrit rio 17 Um servi o de lavagem instant nea de carros utiliza uma m quina de escovas rotativas que lava um carro a cada 5 minutos em m dia Num determinado dia a demanda pelo servi o de 10 carros por hora Al m da lavagem h uma nica bomba de gasolina no posto A rea de espera para lavagem suficiente para 33 carros se h 4 carros ou mais espera o congestionamento que resulta faz cair em 20 a taxa de atendimento da bomba que originalmente de 20 carros hora A cada hora 15 carros em m dia procuram o posto para abastecimento a Qual a probabilidade de que o servi o de lavagem prejudique o de abastecimento b Qual o n mero m dio de carros espera do abastecimento com e sem congestionamento na lavagem c Voc vai abastecer seu carro e lav lo depois Quanto tempo espera gastar com isto 18 Na constru o de um pal cio romano sob Tib rio C sar um grande n mero de escravos trabalhava nas escava es necess rias constru o dos alicerces A terra era levada em cestos de m o em m o do local da escava o at uma estrada que passava ao lado onde os cestos eram descarregados em carro as No m
119. eja atendido no mesmo dia com 90 de certeza Qual a capacidade mensal do servi o com este padr o de atendimento 21 Uma loja de autope as tem estacionamento com espa o para 10 carros Os carros chegam segundo um processo Poisson a uma m dia de 10 por hora Sabe se tamb m que o tempo que eles permanecem estacionados tem distribui o exponencial com m dia de 10 min Determine a O n mero m dio de vagas ociosas no estacionamento b A probabilidade de um carro que chegue n o encontre lugar para estacionar n k D Sugest o Para valores de k grandes use ba SA e n 0 M 22 Considere um sistema com um nico atendente tendo uma distribui o de chegadas Poisson com 10 c h Atualmente o atendente trabalha de acordo com uma distribui o exponencial com um tempo m dio de servi o de 5 min A ger ncia tem a sua disposi o um curso de treinamento que ter como resultado uma melhora decr scimo na vari ncia Processos Estoc sticos e Teoria de Filas 92 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP do tempo de servi o por m com um leve aumento da m dia Ap s a execu o do curso estima se que o tempo m dio de servi o aumentar para 5 5 min por m o desvio padr o decrescer de 5 para 4 min Deve a ger ncia mandar o atendente fazer este curso 23 K sucata recebe uma m dia de 15 pedidos por dia de um certo modelo antigo de carro do qual ela pode at
120. encial com par metro a a propriedade 2 implica que P T lt t At T gt t P T lt A PiT lt t Mt T gt t 1 e cs para quaisquer quantidades positivas de t e At Portanto como a expans o de s rie de e para qualquer expoente x d SCH e 1 x n 2 n segue se que PIT lt t At T gt t 1 1 aAt se n 2 n a At para At pequeno porque os termos do somat rio tornam se relativamente negligenci veis para valores suficientemente pequenos de At Note se que o valor de t realmente n o afeta esta estabilidade Como indicado anteriormente T pode representar tanto tempos entre chegadas quanto tempos de servi os nos modelos de filas Por isso esta propriedade oferece uma aproxima o conveniente da probabilidade de que o incidente em quest o chegada ou conclus o de servi os ocorra no intervalo At de tempo pequeno seguinte A propriedade tamb m mostra que esta probabilidade essencialmente proporcional a At para valores pequenos de At 2 1 8 PROCESSO DE POISSON As propriedades do chamado Processo de Poisson se ajustam muito bem aos modelos b sicos de filas Este fato fez com que as solu es anal ticas para modelos de filas pudessem ser obtidas para queles modelos A obten o de solu es anal ticas para modelos que n o seguem o Processo de Poisson s o quando vi veis matematicamente complexas e extremamente trabalhosas A seguir s o apresentadas as propriedades fundamentais do Processo de
121. ender a 20 pedidos por dia Entretanto se menos que 3 carros forem alugados a companhia perde dinheiro da seguinte forma se somente 2 carros s o alugados a perda de 220 dia se somente 1 carro for alugado a perda de 260 dia e se nenhum carro for alugado a perda de 290 dia As perdas s o naturalmente compensadas pelos ganhos quando 3 ou mais carros s o alugados Considerando apenas as perdas qual ser o valor esperado do preju zo por dia Assuma chegadas e servi o Poisson e que n o existe limita o de tamanho nem desist ncias da fila Processos Estoc sticos e Teoria de Filas 93 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 3 MOVIMENTO BROWNIANO 3 1 PASSEIO ALEAT RIO DISCRETO DISCRETE TIME DISCRETE STATE RANDOM WALK O pr ximo passo de um b bado pode ser modelado como sendo aleat rio e dependente somente de onde est o p de apoio para aquele passo que nada mais do que onde parou o passo anterior Supondo claro que o ch o plano n o existem obstru es no entorno que o cara vai estar em p ao final do passo que n o existe nenhum bar por perto entre outros Chamemos de X a posi o inicial do p de apoio E X a posi o do p de apoio no instante t Algumas suposi es para tornar nosso modelo mais amig vel Todos os passos s o do mesmo tamanho 1 pdb passo de b bado Ele est em um corredor apertado e s pode ir pra
122. ento de cerca de 1 quilo por minuto e por tonelada de gelo Qual o custo esperado do gelo que chega a ser embarcado Seja a rede de filas abaixo onde todos os sistemas de filas s o M M 1 Determine a Qual o gargalo do sistema b Qual a m xima taxa de chegadas externas admiss vel c Qual o n mero esperado de clientes em todo o sistema para uma taxa de chegadas externas igual a 75 da taxa calculada em b d Suponha que a taxa calculada em b tenha sido ultrapassada qual o novo gargalo do sistema e Se os sistemas de filas fossem M G 1 o que mudaria nas respostas anteriores a at d Dados 44 w 15 clientes hora yu 20 clientes hora A 25 clientes hora Processos Estoc sticos e Teoria de Filas 88 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 5 Seja a rede de filas markovianas esquematizada abaixo Se 41 10 clientes hora A 20 clientes hora H 20 clientes hora H 30 clientes hora 4 40 clientes hora 6 7 KS 8 a Determine o gargalo do sistema isto a pior fila b Qual a probabilidade de todo o sistema estar ocioso c Qual a probabilidade de existir uma nica pessoa no sistema Em um laborat rio de computa o gr fica da universidade existem 4 esta es de trabalho cada uma delas com um tempo entre falhas exponencialmente distribu do com m dia de 40 dias O laborat rio tem um contrato com o forneced
123. er igual ao fluxo que entra nesse estado Para determinar o fluxo total que sai do estado n n gt 1 notamos que o sistema vai an 1 se uma chegada ocorre e a n 1 se acontece um fim de servi o O fluxo total que entra no estado n vem a partir de n 1 com um fim de servi o ou ent o a partir de n 1 Processos Estoc sticos e Teoria de Filas 53 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP pela ocorr ncia de uma chegada enquanto o fluxo que entra vem do estado 1 devido a um fim de servi o As equa es de balan o s o as seguintes APa u Ph u Panpi APh 1 Eq 2 1 a AP p P1 Eq 2 1 b Esse sistema denominado de equa es de balan o global e ser resolvido por indu o matem tica Resolvendo as equa es 2 1 para n 0 1 2 temos P1 u Po P2 u 2 Po P3 A u 3 Po A express o sugerida seria Pk A u k PO Supomos que seja v lida para K n e vamos verificar que tamb m vale no caso n 1 de 2 1 a vem A An W in Po Han MM Po De onde temos que Prs DM Po Essa equa o equivalente a Pres p Po Utilizando a condi o de que a soma das probabilidades estacion rias deve ser igual a 1 Calcularemos Po A soma acima a da s rie geom trica de raz o p que convergir se e s se p Leg Como e u s o estritamente positivos essa condi o equivale a O lt p lt 1 Note que nessa condi o a ta
124. ero volte ap s 3 viagens sa Da equa o 9 temos lim p II Utilizando por exemplo a calculadora HP podemos obter Processos Estoc sticos e Teoria de Filas 16 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 0 322 0 387 0 29 lim P 0 322 0 387 0 29 0 322 0 387 0 29 Assim em um longo per odo de tempo a fra o de viagens que se destinam ao Barra Shopping de 0 322 Temos que m SE Assim m RE RE que representa o q De 22 m 0 387 gt n mero m dio de viagens que ir o ocorrer at que o helic ptero volte ao Santos Dumont j 1 2 6 CADEIAS DE MARKOV ABSORVENTES a Representa o Matricial R eso b Probabilidade de Absor o A A a para cada i pertencente aos estados transientes e para cada j pertencente aos estados absorventes 00 A Ga SC para cada i pertencente aos estados transientes e para cada j j l pertencente aos estados absorventes A probabilidade de absor o sempre depende do estado inicial A 1 absorvente S pi O po Se ay Py Paay R O ak C Ba k transiente transiente Processos Estoc sticos e Teoria de Filas 17 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A Dot Paay para cada i pertencente aos estados transientes e para cada j keT pertencente aos estados absorventes A Q A R U OJ A R A U Q R 11 c Dura o m
125. f 1 Obs fun o densidade de probabilidade atende a esta condi o n 0 X gt vari vel aleat ria discerta K fee fps de ler dd n 0 logo F Z GE gt K momento de X HN K logo F D 5 fk 1 K Ne EK K F F 5 KIK EI X K KY SEI SEI X X K K K K Na Tabela 2 3 encontram se as transformadas Z das principais sequ ncias discretas Tabela 2 3 Transformada Z principais sequ ncias discretas X n com n 2 0 XIZ Raio de Converg ncia Z gt R sln 1 0 6 n m zm S Z 1 U n di Z 1 N Z 1 GA n2 z z 1 1 G A a Z lal Z a Processos Estoc sticos e Teoria de Filas 85 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP na az lal Gol z lal n n 1 a G a Cos Qn ziz CosQ n 1 Z 2ZCosQ n 1 SenQ n Z Sent in 1 z 2ZCos Qn 1 poan ba ei G A Transformada Z inversa Para que a transformada Z seja til aconselh vel estar familiarizado com os m todos para encontrar a transformada Z inversa A nota o para a transformada Z inversa ser Z A transformada Z inversa de X Z d como resultado a correspondente sequ ncia X n Existem quatro m todos para obtermos a transformada inversa gt M todo da Divis o Direta gt M todo Computacional gt M todo de expans o em fra es parciais gt M todo da Integral de invers o O m todo da divis o direta prov m do fato de que se X Z
126. gasto com um servi o de lavagem n o ultrapasse o tempo m dio de perman ncia na sauna que de 20 minutos A capacidade da sauna de 10 clientes H tr s m quinas de limpeza a seco e 2 lavadeiras especializadas em roupa branca Em ambos os servi os a roupa de cada cliente processada em separado Uma m quina processa um terno em 10 minutos e uma lavadeira gasta em m dia 10 minutos para lavar e outros 10 para passar a ferro a roupa de um cliente Dos clientes 30 usam a lavagem a seco e 20 lavam roupa branca n o sendo habitual que um deles use os dois servi os no mesmo dia a ger ncia gostaria que os clientes n o tivessem de esperar para entrar na sauna Quantos clientes poder o chegar em m dia por hora se a probabilidade de espera deve ser menor que 5 Processos Estoc sticos e Teoria de Filas 166 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Suponha que chegam 25 clientes por hora Ser ent o poss vel dizer que os servi os de lavagem a seco e de roupa branca funcionam a contento Qual a situa o da sauna neste caso em termos de fila de espera 24 Uma dona de casa tem no congelador de sua casa de praia 5 quilos de camar o para o almo o de domingo Na sexta feira o g s engarrafado acabou e noite caiu uma forte chuva que al m de bloquear o acesso de ve culos rea pr xima provocou falta de luz A companhia de eletricidade est neste
127. goria k no tempo i 1 o qual proveniente da categoria j no tempo i Para considerarmos todas as poss veis Processos Estoc sticos e Teoria de Filas 137 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP categorias devemos acrescentar mais uma categoria aquelas descritas anteriormente Trata se da categoria correspondente aos t tulos classificados como pagos que ser o descritos como Pag Valores classificados em qualquer categoria no per odo i podem mover se para a categoria dos t tulos pagos ou para qualquer outra categoria de0 a n no per odo i 1 Iremos adotar os procedimentos recomendados pelo Banco Central do Brasil atrav s da resolu o 2 682 que determina que os cr ditos vencidos h mais de 60 sessenta dias sem garantias sejam transferidos para as contas de Cr ditos em Liquida o Em 1 de mar o foi levantada uma amostra de 1050 contas e em 31 de mar o foi verificado o comportamento dessas contas De 01 03 a 31 03 Integ Pg Em dia Atraso 1 m s Atraso 2 meses Perda Total Emitidas at 28 02 150 100 150 0 0 400 Emitidas at 31 01 120 90 90 150 0 450 Emitidas at 31 12 30 40 40 60 30 200 A primeira linha significa que das faturas emitidas no m s de fevereiro num total de 400 150 foram pagas 100 ainda n o venceram e 150 venceram e n o foram pagas contando o atraso de um m s A segunda linha most
128. gr tis para cada cliente que completar o tanque de combust vel e para clientes que busca apenas o servi o de lavagem cobra uma taxa de 5 00 Experi ncias anteriores mostram que o n mero de clientes que lavam o carro ap s realizar o abastecimento aproximadamente igual ao n mero de clientes que lavam apenas o carro O lucro bruto m dio para os abastecimentos de 7 00 e o custo da lavagem para a Prod leo de 1 00 Os postos Prod leo permanecem abertos 14 horas por dia A Prod leo possui tr s tipos de unidades de lavagem autom tica e os postos devem selecionar a unidade preferida A unidade I pode lavar carros a uma taxa de um carro a cada 5 minutos e alugada por 120 por dia A unidade II pode lavar carros a uma taxa de um carro a cada 4 minutos e alugada por 160 por dia A unidade II pode lavar carros a uma taxa de um carro a cada 3 minutos e alugada por 220 por dia Os postos estimam que os clientes n o ir o esperar na fila mais do que 5 minutos para lavar seus carros Um tempo de espera maior ir causar perdas para a Prod leo tanto em venda de combust vel quanto em lavagens Se a estimativa de chegadas de clientes que resultam em lavagem de 10 por hora qual unidade de lavagem deve ser selecionada 53 O gerente de um banco deve determinar quantos caixas devem trabalhar as sextas feiras Para cada minuto que um cliente passa na fila o gerente imagina que um custo devido ao atraso de 0 05 incorrido Uma m
129. hia faz um esfor o especial no dia seguinte para que o v o saia no hor rio e obt m sucesso em 90 das vezes Se o v o n o saiu atrasado no dia anterior a companhia n o toma provid ncias e o v o sai como escalado em 60 das vezes Que percentual de vezes o v o sai atrasado Qual o tempo m dio entre dois v os no hor rio 08 A baco sistemas de computa o registra a cada semana uma demanda equiprov vel de 1 ou 2 de seu modelo A500 Todos os pedidos devem ser atendidos do estoque existente Duas pol ticas de estoque est o sendo consideradas Pol tica Se o estoque de 2 ou menos unidades coloca se um pedido de forma que o estoque inicial na pr xima semana seja de 4 unidades Pol tica Il Se o estoque de 1 ou menos unidades coloca se um pedido de forma que o estoque inicial na pr xima semana seja de 3 unidades Os seguintes custos s o observados na baco Custo de comprar um computador 4 000 Custo de manter o computador em estoque 100 semana computador Processos Estoc sticos e Teoria de Filas 31 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Custo de efetuar um pedido 500 al m do custo de 4 000 por computador Qual pol tica tem o menor custo semanal esperado 09 O programa de treinamento de supervisores de produ o de uma determinada companhia consiste de duas fases A fase 1 a qual envolve 3 semanas de aula te rica seguida da fase 2
130. iente para justificar mais que uma cabine mas o turismo ecol gico tem aumentado muito recentemente Atualmente nos per odos de pico que s o os que nos interessam h um fluxo de passagem de 210 carros hora enquanto o tempo m dio de servi o de 15 segundos De forma a diminuir os intermin veis engarrafamentos que passaram a ocorrer duas propostas foram feitas A primeira consiste em instalar uma nova cabine id ntica a primeira assuma que o tr fego ir se dividir igualmente por m de forma aleat ria entre as duas cabines A segunda instalar uma cabine autom tica que opera com cart o pr pago Nesta cabine o tempo m dio de servi o ser de somente 5 segundos mas apenas um ter o das chegadas selecionadas aleatoriamente ter o o cart o pr pago A medida de performance o tempo m dio que as pessoas dispendem para passar pelas cabines a Usando o s modelo s apropriado de filas estime os tempos m dios para as duas propostas b Reconhecendo que os tempos de servi o provavelmente n o s o exponenciais mas que certamente tamb m n o s o constantes avalie se e como os resultados de a devem ser modificados c Levando em conta outros fatores que podem ter sido negligenciados qual usa recomenda o 62 Considere dois servidores Uma m dia de 8 clientes por hora chegam do exterior para o servidor 1 e uma m dia de 17 clientes por hora chegam do exterior para o servidor 2 Tempos entre chegadas s o exponenci
131. imento u continuar doente 1 u estar curado 10 u estar morto 30 Qual a melhor alternativa para iniciar o tratamento 18 A fase final da fabrica o de certa pe a de vidro comp e se de duas ou tr s opera es conforme a qualidade da pe a resultante seja B ou A respectivamente Das pe as submetidas opera o 1 10 sofrem defeitos irrecuper veis e s o perdidas 20 precisam ser reprocessadas e as restantes passam para a opera o 2 Das pe as submetidas opera o 2 4 precisam retornar ao in cio do processo isto passar de novo pelas opera es 1 e 2 60 est o em condi es de serem submetidas opera o 3 e as restantes s o consideradas prontas com qualidade B sendo vendidas ao pre o unit rio de 9 Das pe as submetidas opera o 3 9 s o perdidas definitivamente e as restantes com qualidade A vendem se a 16 cada uma Cada opera o leva um dia para ser executada Os custos unit rios m dios das opera es 1 2 e 3 s o respectivamente iguais a 2 1 e 3 Todos os dias entram 70 pe as na fase final de fabrica o O custo de fabrica o unit rio m dio acumulado at a fase final exclusive igual a 3 a Quantas pe as por dia em m dia alcan am as qualidades A e B e quantas s o perdidas A 34 7 B 22 8 perdidas 12 5 Processos Estoc sticos e Teoria de Filas 161 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Qual
132. io gasto em esperas e atendimentos por uma pessoa que almo a cozido a probabilidade de n o haver num dado momento ningu m esperando omelete 21 Voc e seus colegas de turma receberam para resolver um problema de filas que exige a consulta a dois gr ficos de um livro que s existe na biblioteca H dois exemplares iguais do livro e a consulta a cada gr fico exige em m dia 7 5 minutos de cada aluno Um livro somente usado por um aluno quando n o est em uso por outro O trabalho individual e a cada hora chegam em m dia 6 alunos da turma Quanto tempo um deles poder esperar gastar na biblioteca 22 Uma tecelagem tem 250 teares e as estat sticas mostram que em m dia 1 deles apresentam algum defeito ao longo de um dia de trabalho H tr s mec nicos de manuten o cada um podendo consertar em m dia dois teares por dia por um sal rio de 10 h O dia de trabalho tem 8 horas Cada hora parada de um tear representa uma perda de 50 A manuten o pede mais dois mec nicos Voc o gerente da f brica vai atend la vai contratar apenas mais um mec nico ou vai deixar as coisas como est o 23 Uma sauna para executivos oferece a clientela um servi o de lavagem a seco para ternos e de lavagem de roupa branca para que um cliente deixe sua roupa ao chegar e a receba pronta ao sair importante que os clientes n o tenham que esperar por serem pessoas ocupadas e por isto a ger ncia deseja que o tempo m dio
133. irigir para este ltimo cujo caixa consegue atender apenas a 20 clientes por hora em m dia Qual a fra o do tempo ocioso de cada um dos caixas 27 Uma linha autom tica de embalagem de medicamentos enche e fecha 60 frascos de determinado rem dio por minuto Os frascos passam ent o por uma mesa na qual s o colocados em caixas manualmente por 3 embaladoras capazes de embalar cada uma em m dia 22 frascos por minuto Em m dia quantos frascos estar o sobre a mesa a espera de serem embalados 28 No trailer O Lanche situado defronte ao bloco M do CCS trabalham duas mo as Maria no caixa e Beatriz no atendimento aos pedidos Quando existe apenas um cliente esperando por um pedido ele atendido por Beatriz com um tempo de servi o esperado de 1 5 minuto Quando existe mais de um cliente aguardando por pedido Maria d uma m o para Beatriz e o tempo para processar um pedido cai para 1 minuto Em ambos os casos a distribui o do tempo de servi o exponencial a Desenhe o diagrama de transi o de estados para este sistema de filas b Qual a distribui o de probabilidade do estado de equil brio do n mero de clientes no sistema c Como voc obteria L Ly W Wq 29 Um pequeno hotel possui 2 cofres para guarda de valores dos h spedes em regime de exclusividade ou seja n o se quadram valores de dois h spedes em um mesmo cofre Em m dia 3 pessoas por semana procuram o gerente para solicitar o uso de um cofr
134. iro Programa de Engenharia de Produ o PEP c o n mero m dio de esta es em opera o normal d a percentagem do tempo em que todas as esta es est o paradas a 4A Po HP 4A Pa 24 p u p 34 p p SE E ite Ge 2A p 2u p 2U p p b 4A Pi 5 Po u 1 34 A7 A 40 1 P2 oc 6 2 Po Pi et 10 2A ER P3 ER KS gie A A H Er Ke gt S E z 0 4032 1 4p 60 60 3p c L X 4p po 120 py 180 pp 12 4p 120 18p 12p 2 n P 54P Po o Po o Po o Po 1 40 607 gei 30 L 1 8360 resposta 4 1 8360 2 16m quina d Pa 3p Po 0 79 7 Est o sendo feitos planos para a abertura de um posto de lavagem de carros pequeno e tem que ser decidido quanto espa o para carros a espera estimado que os clientes chegariam aleatoriamente i e segundo um processo de chegadas Poisson com uma taxa m dia de um a cada 4 minutos a menos que a rea de carros a espera esteja lotada em cujo caso o cliente levaria seu carro a outro lugar Processos Estoc sticos e Teoria de Filas 144 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP O tempo que pode ser atribu do lavagem de um carro tem uma distribui o exponencial com uma m dia de 3 minutos Compare a fra o de clientes potenciais que seria perdida por causa de espa o de espera inadequado se a zero b dois ou c quatro espa os n o incluindo o carro que est sendo lavado fossem previstos
135. lu o ela considera que a probabilidade de haver mais de um candidato a espera para entregar a prova n o deva exceder 10 Nestas condi es qual o menor n mero de fiscais salas deve ser utilizado 38 Uma UTI especializada em transplantes de medula recebe a visita de uma numerosa turma de estudantes de medicina os quais para poderem entrar devem se submeter a um processo de assepsia que envolve um banho e troca de roupa cada etapa dessas exigindo em m dia 3 5 minutos A turma chega toda de uma vez e aguarda a entrada em uma sala de espera cada estudante indo fazer a assepsia no momento exato em que o anterior a termina e entra na UTI H apenas 2 pacientes internados e junto a cada um est um professor que orienta os alunos no exame do seu paciente Um aluno ao entrar na UTI deve aguardar em uma sala de espera at que algum paciente esteja dispon vel e ent o se dirige ao mesmo saindo da UTI ap s examin lo com isto se evita que mais de uma pessoa entre ao mesmo tempo A discuss o do caso e o exame levam em m dia 10 minutos ao todo Considera se que o regime de tr nsito dos estudantes dentro da UTI seja estacion rio a Desenhe o diagrama de transi o de estados para a situa o descrita b Qual o tempo m dio de espera de um estudante na sala interna antes da visita a um paciente use os gr ficos fornecidos indicando neles as leituras efetuadas Processos Estoc sticos e Teoria de Filas 169 COPPE U
136. m cliente de qualquer tipo chegue A propriedade 3 ent o nos diz que U os tempos entre chegadas para o sistema de fila como um todo tem uma distribui o exponencial com par metro a definido pela equa o acima Como resultado podemos optar por ignorar a distin o feita entre os clientes e ainda termos tempos entre chegadas exponenciais para o modelo de fila Entretanto as implica es s o ainda mais importantes para tempos de servi os nos modelos de filas que tenha mais de um servidor Por exemplo considerando a situa o em que todos os servidores tenham a mesma distribui o exponencial de tempo de servi o com par metro u Para este caso fa amos com que n seja o n mero de servidores prestando servi os atualmente e fa amos com que T seja o tempo de servi o restante para o servidor i i 1 2 n o qual tamb m um distribui o exponencial com par metro o Uu Segue se ent o que o U o tempo at conclus o de servi o seguinte de qualquer destes servidores tenham uma distribui o exponencial com par metro a nu Com efeito o sistema de fila atualmente seria processado exatamente como um sistema de um servidor nico onde os tempos de servi o t m uma distribui o exponencial com par metro nu PROPRIEDADE 4 Rela o com a distribui o de Poisson Suponhamos que o tempo entre ocorr ncias consecutivas de algum tipo de incidente particular por exemplo chegadas ou conclus o de servi os por um
137. m conhecimento matem tico de n vel bem mais elevado do que se prop e nesta apostila No entanto se evitarmos certas dificuldades matem ticas que surgem e aceitarmos que determinadas opera es sejam v lidas poderemos alcan ar uma compreens o suficiente das principais id ias abrangidas a fim de empreg las inteligentemente Suponhamos que X seja uma vari vel aleat ria isto X uma fun o do espa o amostral para os n meros reais Ao calcularmos v rias caracter sticas da vari vel aleat ria X tais como E X ou V X trabalhamos diretamente com a distribui o de probabilidade de X Defini o Seja X uma vari vel aleat ria discreta com distribui o de probabilidade p xi P X xi i 1 2 3 A fun o Mx denominada fun o geratriz de momentos de X definida por Mx t De p x Se X for uma vari vel aleat ria cont nua com fdp f definiremos a fun o geratriz de momentos por Mx t e f x dx Em qualquer dos casos o discreto ou o cont nuo Mx t apenas o valor esperado de e Por isso podemos combinar as express es acima e escrever A seguir ser o mostrados alguns exemplos de fun es geratrizes de momentos Exemplo I Suponha que X seja uniformemente distribu da sobre o intervalo a b Logo a fgm ser dada por a b Mx t E dx dale e t 0 Processos Estoc sticos e Teoria de Filas 19 COPPE Universidade Federal do Rio de Janeiro P
138. m dia 800 000 Contas com atraso de 1 m s 120 000 Contas com atraso de 2 meses 80 000 Valor da carteira 1 000 000 Calcule o valor esperado que ser pago Processos Estoc sticos e Teoria de Filas 38 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 TEORIA DE FILAS 2 1 INTRODU O E CONCEITOS B SICOS A teoria das filas envolve o estudo matem tico das filas ou filas de espera Filas podem existir na forma de pessoas ou objetos esperando algum tipo de servi o ou podem existir num sentido mais abstrato ou seja n o t o vis vel como uma fila de navios esperando para atracar em um porto Um modelo ou sistema de filas pode ser brevemente descrito da seguinte forma usu rios ou fregueses ou clientes chegam para receber um certo servi o e devido indisponibilidade de atendimento imediato formam uma fila de espera A Figura 2 1 ilustra esta id ia Os termos usu rio e servi o s o usados com sentido amplo Podemos estar nos referindo a carros que chegam a um posto de ped gio m quinas que esperam para serem consertadas pe as que seguem uma linha de montagem ou mensagens que s o transmitidas pelos canais de comunica o Uma rede de filas formada por v rias filas que se interconectam entre si de modo que o usu rio ao sair de uma fila pode com uma certa probabilidade dirigir se a outra Nas redes abertas h fluxo de fregueses entrando e sai
139. mis Pi M 1 0 5 m m 2 ma 1 pii ms Piz M 1 0 5 m N ms 2 Ma 1 Dan Dis Ban M 1 0 5 m m 2 Mz 1 Da Mo Pam 1 0 5 m my 2 M22 1 72 2 1 E frequ ncia relativa dado que o estoque est no estado1 esse o n mero m m 12 13 m dio de vezes que o estoque ser reabastecido estando inicialmente no estado 1 Processos Estoc sticos e Teoria de Filas 114 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Custo de efetuar pedido 500 n m dio de pedidos 500 EEN ZE tech T 500 Eiai Mo Mg Moo Mz 2 2 2 2 500 m 75 333 33 Custo m dio do pedido 4000 n m dio de computadores comprados por semana 4000 3 7 2 7 EE 6000 Custo total esperado 216 67 333 33 6000 6550 Pol tica l Estoque m ximo ao fim da semana 2 Estoque m nimo ao fim da semana 0 Ta 1 6 Zeien RE s E Mo Como o DTE id ntico ao da pol tica gt 7 1 2 e M m 1 3 M Custo de manuten o do estoque 100 n m dio de computadores em estoque S100 0 7 1 m 2 8100 0 41 5 2 4 116 67 Os pedidos s s o feitos quando tem as transi es de estado 051 052 151 152 Mi dr 2 Custo de efetuar pedido 500 n m dio de pedidos 500 BEE ZE ER EA 500 iijar Mo Moz M Mo 2 2 2 2 500 no 11 333 33 Processos Estoc sticos e Teoria de Filas 115 COPPE Universidad
140. na igual a zero H Il d para todo i e J A matriz R perde ent o a linha e a coluna J 1 A equa o de tr fego torna se assim Rss as meJ Pelas hip teses j apresentadas no item 2 4 1 que trata de rede de filas aberta a matriz R finita e irredut vel M e a equa o acima ter solu o nica com a imposi o de alguma condi o extra por exemplo fixar o valor de um dos y s ou de sua soma 2 4 3 SISTEMAS MISTOS OU ABERTOS COM REALIMENTA O Considere a rede de filas mostrada na Figura 2 13 Y A A l r TESS Figura 2 13 Sistema Misto ou Aberto com Realimenta o Os clientes saem da esta o a uma taxa retornam a fila com probabilidade r e consequentemente a uma taxa r e saem do sistema com probabilidade 1 r e taxa 1 r A No equil brio sabe se que o n mero de clientes que entra no sistema igual ao n mero de clientes que sai do sistema Portanto pode se determinar a taxa atrav s da seguinte equa o Processos Estoc sticos e Teoria de Filas 66 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP ou seja A f p r Quando a probabilidade de retorno fila r grande cada chegada externa seguida por uma rajada interna de chegada 2 4 4 TEOREMA BURKE Uma propriedade interessante da fila MIM 1 que simplifica bastante a combina o destas filas em uma rede o fato de que a sa da de uma fila MIMI
141. nalise os modelos M D 1 e M M 1 13 Clientes chegam a uma nica fila segundo diferentes processos Poisson com taxas Aa Aq Qual a taxa combinada de chegada Qual a distribui o de probabilidades do tempo entre chegadas A a M Ss A As E eech As Ss Processos Estoc sticos e Teoria de Filas 164 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 14 Clientes chegam a um posto de gasolina com 5 bombas de 5 em 5 minutos mas se o n mero de clientes no posto for superior a 10 20 deles desiste O tempo de atendimento em cada bomba de 12 se houver apenas um cliente na bomba 9 se houverem 2 clientes e 6 se houverem mais de 2 clientes Determine a a taxa m dia de chegada b o tempo m dio de atendimento em cada bomba e c o fator de utiliza o 15 Considere um modelo de filas com uma esta o de servi o a qual as unidades chegam em m dia a uma raz o de 30 por hora O mecanismo de atendimento serve a cada unidade em exatamente 1 5 minutos Suponha que o mecanismo tenha sido substitu do por outro com uma distribui o exponencial de tempo de servi o Qual deve ser o tempo m dio de servi o neste caso a para garantir o mesmo tempo m dio de perman ncia do usu rio no sistema b para garantir o mesmo n mero m dio de unidades no sistema 16 Um escrit rio de advocacia tem 3 s cios que recebem os clientes na ordem em que estes ch
142. nclus es de servi os atingido por um servidor continuamente ocupado no espa o de tempo t onde a u Para os modelos de filas de servidores m ltiplos X t tamb m pode ser definido como o n mero de conclus es de servi os atingido por n servidores continuamente ocupados no espa o de tempo t onde a nu A propriedade particularmente til para descrever o comportamento probabil stico das chegadas quando os tempos entre chegadas t m uma distribui o exponencial com o par metro Neste caso X t seria o n mero de chegadas no espa o de tempo t onde a a taxa m dia de chegada Portanto as chegadas ocorrem de acordo com um processo de chegada de Poisson Tais modelos de filas tamb m s o descritos como uma chegada de Poisson s vezes dito que as chegadas ocorrem aleatoriamente entendendo se por isso que elas ocorrem de acordo com um processo de chegada de Poisson Uma interpreta o intuitiva deste fen meno que cada per odo de tempo de extens o fixa tem a mesma chance de ter uma chegada independentemente de quando tenha ocorrido a chegada precedente como sugerido pela propriedade que se segue PROPRIEDADE 5 Para todos os valores positivos det P T lt t At T gt t At para At pequeno Processos Estoc sticos e Teoria de Filas 50 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Para uma vari vel aleat ria T que tem uma distribui o expon
143. ndo do sistema Por outro lado h redes fechadas nas quais o n mero de usu rios permanece inalterado isto n o h movimenta o de usu rios para dentro ou para fora do sistema Um servi o de manuten o de m quinas pode ser visto como uma rede fechada onde M m quinas se alternam entre os centros de manuten o e de opera o Dessas defini es b sicas ramificam se um sem n mero de outros modelos de filas adequados s varias reas sempre na busca de melhor representar a realidade Client i Client Fonte de ientes Sema de Clientes chegadas El servi o doido Sistema de filas Figura 2 1 O Processo de Fila B sico Em aplica es o estudo dos modelos de filas tem como objetivo a melhoria de desempenho do sistema entendida entre outros aspectos como melhor utiliza o dos recursos de servi o dispon veis menor tempo de espera e mais rapidez no atendimento O pioneiro neste estudo foi A K Erlang que no come o do s culo como engenheiro da companhia dinamarquesa de telefones estudou o problema de congestionamento das linhas A Telefonia permaneceu a principal aplica o de teoria das filas at por volta de 1950 A partir da um grande n mero de reas tem utilizado essa ferramenta e a vasta literatura o melhor indicador dessa expans o Processos Estoc sticos e Teoria de Filas 39 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 1 1 PORQUE F
144. ndo se a m quina principal x ou secund ria y est o operacional no fim do dia d Construa a matriz de probabilidades de transi o e Encontre o tempo de recorr ncia esperado para o estado 1 0 11 Um equipamento utilizado rotineiramente para realizar uma determinada opera o que dura uma semana Ao final de cada opera o o equipamento inspecionado e em 10 dos casos o desgaste verificado de tal ordem que o equipamento precisa ser retirado definitivamente da produ o Nos demais casos o equipamento entra em manuten o e fica totalmente recuperado em uma semana ao custo de 5 mil reais voltando em seguida a ser utilizado na opera o nas mesmas condi es anteriores Quando um equipamento retirado definitivamente de produ o imediatamente substitu do por um novo Como s h espa o para o funcionamento ou manuten o de um equipamento de cada vez a produ o interrompida quando o equipamento est em manuten o Cada equipamento custa 100 mil reais Considere o tempo da inspe o inclu do no tempo de opera o a Defina um processo estoc stico que represente o problema esboce o diagrama de transi es escreva a matriz das probabilidades de transi o e classifique o processo e os seus estados b Quantas opera es em m dia ser o realizadas por um equipamento at ele ser retirado definitivamente da produ o c Quantas semanas dura um equipamento em m dia incluindo os per
145. neira obtemos o seguinte teorema Teorema 1 MO E X Isto a derivada n sima de Mx t avaliada para t 0 fornece E Xn Exemplo V Suponha que X tenha uma distribui o binomial com par metros n e p Consequentemente Mx t pet gJn Por isso Mx t f e ae dx af EP de Logo E x M 0 np o que concorda com nosso resultado anterior Al m disto E X2 M 0 npl n 1 p 1 Da V x M 0 M 0 P np 1 p Os dois teoremas seguintes ser o de not vel import ncia em nossa aplica o da fgm Teorema 2 Suponha que a vari vel aleat ria X tenha fgm Mx Seja Y aX B Ent o My a fgm da vari vel Y ser dada por My t ef Mx ot Teorema 3 Sejam X e Y duas vari veis aleat rias com fgm e Mx t e My t respectivamente Se Mx t My t para todos os valores de t ent o X e Y ter o a mesma distribui o de probabilidade Propriedade Reprodutiva Se duas ou mais vari veis aleat rias que tenham uma determinada distribui o forem adicionadas a vari vel aleat ria resultante ter uma distribui o do mesmo tipo que aquelas das parcelas Esta propriedade denominada Propriedade Reprodutiva ou aditiva Exemplo VI Suponha que X e Y sejam vari veis aleat rias independentes com 2 2 distribui es Nuno e Nu 09 respectivamente Fa amos Z X Y Consequentemente Processos Estoc sticos e Teoria de Filas 82 COPPE Universidade Federal do Rio de Janeiro
146. nha que 90 de todos os estudantes que compram um novo livro o vendam de volta que 80 dos estudantes que compram o livro com um ano de uso o vendam de volta e que 60 dos estudantes que compram um livro com dois anos de uso o vendam de volta Os livros com 4 ou mais anos de uso j est o muito usados e n o s o mais negociados a Em regime permanente quantos novos exemplares do livro pode a editora esperar vender do livro Processos Estoc sticos e Teoria de Filas 117 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP b Suponha que o lucro da livraria com cada tipo de livro seja de 6 por um livro novo 3 por um livro com 1 ano de uso 2 por um livro com 2 anos de uso e de 1 por livro com 3 anos de uso Qual o lucro esperado por livro vendido Estado idade do livro vendido pela editora no come o do est gio Est gio ano letivo Transi o mudan a de ano CARO SC Se EE 0o 1 2 3 of 0 109 0 pn II D D 08 0 2 04 0 D 06 Si 1 0 0 0 Ta 0 1 ma 0 2 m 0 4 T 7 To 0 3277 m 0 9 7 m 0 2949 m 0 8 7 gt 0 2359 m 0 6 7 m 0 1415 Tota T T l a n esperado de exemplares novos a ser vendido propor o de livros novos no mercado q livros vendido ano nO 1 000 000 327 7 mil exemplares b Lucro esperado por livro vendido 6 no 3 m4 2 Tn2 T m3 3 46 12 Tr s bolas s o divididas entre 2 caixas Durante cada per
147. nham de ser peruas e 40 convers veis Determine alguma regra de programa o de probabilidades que assegure esta produ o e que ainda corresponda as implica es 1 2 e 3 deste problema 10 Um industrial tem uma m quina que quando operacional no in cio do dia tem uma probabilidade de 0 1 de quebrar alguma hora durante o dia Quando isto acontece o reparo feito no dia seguinte e est completo no fim do dia a Formule a evolu o do estado da m quina como uma cadeia de Markov identificando os estados poss veis no fim do dia e construindo a matriz de probabilidades de transi o b Calcule o tempo esperado que a m quina ir funcionar at que aconte a uma quebra dado que ela acabou de sofrer um reparo c Suponha agora que a m quina j esteja operando a 20 dias sem quebra desde que o ltimo reparo foi feito Qual o tempo esperado que a m quina ir operar at que aconte a uma quebra Compare com o resultado da letra b Explique Processos Estoc sticos e Teoria de Filas 159 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Suponha agora que o industrial mantenha uma m quina de reserva a qual usada somente quando a m quina principal est sendo reparada Durante o dia de reparo a m quina reserva tem uma probabilidade de 0 1 de quebrar neste caso ela ser reparada no dia seguinte Denote o estado do sistema por x y onde x e y assumem os valores O e 1 depende
148. nharia de Produ o PEP Modelo chegada em grupo gt M Sso 1 12 segundos hora gt u 6 camionete comprar com M D 1 u K oi si 5 6 51 Se 7N gt L ton 1 2K 1 0 100 1 5 6 24 24 6 24 w ZA 5 wedl konpak e E Omie iji ORE i 5 120 mim h 1 000 Kg R 20 74 ton 4 Seja a rede de filas abaixo onde todos os sistemas de filas s o M M 1 Determine a Qual o gargalo do sistema b Quala m xima taxa de chegadas externas admiss vel c Qual o n mero esperado de clientes em todo o sistema para uma taxa de chegadas externas igual a 75 da taxa calculada em b d Suponha que a taxa calculada em b tenha sido ultrapassada qual o novo gargalo do sistema e Se os sistemas de filas fossem M G 1 o que mudaria nas respostas anteriores a at d Dados 4 w 15 clientes hora 20 clientes hora u 25 clientes hora A LE CE E e SE SE JJ o 4 gt 30 20 A SE pl 1 lt 20 EE 47 S a D aao 25 EE ij E e 0 aer a Logo o gargalo do sistema a fila 3 b 4 20 clientes hora Processos Estoc sticos e Teoria de Filas 142 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 c 15 clientes hora gt p p e p4 0 75 p 0 6 30 e filas 1 e 2 E pes L 10 1 5 ET 0 5 0 25 0 4 Logo no sistema todo haver 1 1 3 1 5 6 5 clientes d As filas 1 e 2 pois a taxa de chegada na fila 4 ficar sempr
149. niversidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 39 Uma competi o de triatlon organizada da seguinte forma na primeira etapa uma corrida em pista livre com qualquer n mero de corredores de 20km a segunda etapa consiste de uma prova de nata o na qual os nadadores t m que atravessar ida e volta um lago devido as condi es operacionais apenas dois nadadores podem estar na gua simultaneamente o tempo da travessia do lago ida ou volta pode ser considerado exponencial com m dia de 30 min Finalmente a terceira etapa uma corrida de bicicleta 5 voltas em torno do lago 20km de per metro a organiza o da corrida disp e de apenas 10 bicicletas para uso dos competidores Sabe se ainda que a velocidade m dia de um competidor a p de 40km h e de bicicleta de 80 km h considere que o tempo m dio entre chegadas dos competidores ap s a prova de corrida de 45 min Pede se a Modele o problema como um sistema de filas b Qual o tempo m dio gasto pelo corredor l der c Qual o tempo m dio gasto por um corredor m dio 40 Uma oficina de m quinas cont m um esmeril para amolar os instrumentos de corte das m quinas Tem que ser tomada uma decis o agora quanto a que velocidade ajustar o esmeril O tempo necess rio para que um operador de m quinas amole seu instrumento de corte tem uma distribui o exponencial sendo que a m dia 1 u pode ser ajustada a qualquer ponto entr
150. no per odo i podem mover se para a categoria dos t tulos pagos ou para qualquer outra categoria de O a n no per odo i 1 Iremos adotar os procedimentos recomendados pelo Banco Central do Brasil atrav s da resolu o 2 682 que determina que os cr ditos vencidos h mais de 60 sessenta dias sem garantias sejam transferidos para as contas de Cr ditos em Liquida o Em 1 de mar o foi levantada uma amostra de 1050 contas e em 31 de mar o foi verificado o comportamento dessas contas De 01 03 a 31 03 Integ Pg Em dia Atraso 1 m s Atraso 2 meses Perda Total Emitidas at 28 02 150 100 150 0 0 400 Emitidas at 31 01 120 90 90 150 0 450 Emitidas at 31 12 30 40 40 60 30 200 A primeira linha significa que das faturas emitidas no m s de fevereiro num total de 400 150 foram pagas 100 ainda n o venceram e 150 venceram e n o foram pagas contando o atraso de um m s A segunda linha mostra que de 450 faturas emitidas no m s de janeiro 120 foram pagas 90 ainda n o venceram 90 apresentam atraso de um m s e 150 com atraso de dois meses Finalmente a ltima linha mostra que de 200 faturas emitidas no m s de dezembro al m da sequ ncia de pagamentos e atrasos 30 correspondem perda ou seja atraso superior a 2 meses Seja uma carteira de cr dito total de R 1 000 000 00 conforme mostramos a seguir Situa o da Carteira Valor R Contas e
151. nte de 1a 4 A probabilidade do sapo pular de uma planta para outra inversamente proporcional a dist ncia entre elas isto o sapo prefere pular para uma planta mais perto do que para uma mais longe As dist ncias entre as plantas s o 2 3 4 1 65 2 3 2 2 67 1 2 3 3 4 a Defina a matriz de transi o b Calcule as probabilidades de regime permanente Processos Estoc sticos e Teoria de Filas 127 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP c Interprete estas probabilidades em termos do comportamento do sapo d Explique do ponto de vista do sapo o que significam as hip teses de Markov e de estacionariedade a Tabela com o inverso das dist ncias 1 2 3 4 0 5 6 1 2 2 8 5 6 O 7 6 2 1 2 7 6 0 4 3 2 3 2 4 3 O Si j N ch A soma das linhas da matriz de transi o deve ser igual a 1 portanto De K 1 gt es tese gt Rs 6 2 3 2 2 6 3 3 Se KE sl gt pal Zint i gt pee 6 6 4 3 3 4 Multiplicando cada linha da tabela acima pelas constantes encontradas obt m se a matriz de transi o O 5 12 1 4 1 3 5 24 0 7 24 1 2 ue 7 18 O 4 9 16 1 2 13 0 m 5 24 m 1 6 m 1 6 7 m 0 1538 m 5 12 m 7 18 m 1 2 m 2 7 0 3077 m 1 4 m 7 24 m 1 3 7 m 0 2308 m tT T m l m 0 3077 c As probabilidades de regime permanente indicam a fra o de tempo que o sa
152. o Programa de Engenharia de Produ o PEP 1 KE 2 3 4 EXERCICIOS PROPOSTOS DE TEORIA DAS FILAS Considere a rede de filas aberta com um nico n como mostrada abaixo Chegadas y externas D O n nico uma fila M M com taxa de servi o u Um fregu s retorna ao n com probabilidade p depois de completar seu servi o A disciplina da fila PEPS primeiro a chegar primeiro a ser servido Pergunta se a Quanto vale y taxa total de chegada ao n 1 b Qual o intervalo permitido para varia o de p para que o sistema permane a est vel No bar de um aeroporto uma pessoa pode escolher entre tomar um caf servido no balc o ou ent o usar uma m quina autom tica No balc o s podem ser atendidos em m dia 180 pessoa por hora enquanto a m quina pode atender exatamente 4 pessoas por minuto A cada hora 270 pessoas em m dia procuram o bar para tomar caf a probabilidade de uma pessoa preferir o balc o de 0 6 Qual a demora m dia de uma pessoa que procura o bar desde que entra at ser servida de caf Uma frota de traineiras consome gelo para conservar o peixe durante o tempo passado no mar O gelo vem em camionetas que transportam 1 tonelada cada 50 barras e que no dia da entrega chegam raz o de 5 por hora em m dia O pessoal encarregado da descarga tira 1 barra a cada 12 segundos em m dia O gelo custa 20 a tonelada e no ver o a perda devida ao derretim
153. o os carros est o saindo do t nel raz o de 24 por minuto em m dia Sabendo se que cada carro ocupa 10 metros de sua faixa de tr nsito pergunta se Processos Estoc sticos e Teoria de Filas 153 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP a Qualo tamanho m dio do trecho de pista ocupado pelos carros b O sinal engui ou e a CET colocou provisoriamente um agente de tr nsito que abre o tr nsito em m dia a cada 20 segundos Qual a probabilidade que a fila invada o t nel u 10 carros 20 segundos 30 carros min A 24 carros minuto al L 1W 24 Las SE 4 carros 20m Icarro 10m u A 30 24 bJN de carros na pista 20 A 45 u 60 Ip 1 1 0 1 0 2 0 8 0 9977 19 Uma famosa vidente acostumada a prever o futuro de pol ticos tem sua agenda cheia de entrevistas marcadas raz o de uma por hora dia de 8 horas Ela dedica em m dia 45 minutos a cada cliente e para suavizar a espera da clientela manda servir caf com bolinhos na sala de espera Uma pequena quest o alimentar se cada pessoa toma uma x cara de caf 100 ml a cada meia hora quantos litros de caf dever o ser preparados em m dia por dia A lpessoa hora u l pessoa 45 minutos 60 45 pessoas hora l pessoa 100ml meia hora e o eds RT 0 ER a5 E Zon 2 25 tempom dio de espera de uma pessoana fila ul p 60 15 45 60 L W
154. o que cada unidade permanece na fila A W Se u u 4 Probabilidade de 1 unidade demorar mais de t unidades de tempo no sistema P T gt t e0 Podemos ter ainda as seguintes rela es entre as medidas b sicas L L p 4W Lotto AW 1 L W W u A 1 L W W u A 2 2 1 2 Modelo M M S Neste tipo de modelo considera se que as esta es de servi o s o equivalentes e prestam servi o individualmente a mesma taxa m dia Au Aqui o fator de utiliza o p SH S A H A A A A A A A A m Zu 3u s Duy SH su su su su su su Figura 2 4 Taxas de transi o no processo de Markov Pelo diagrama mostrado na Figura 2 4 temos E eo Processos Estoc sticos e Teoria de Filas 56 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Podemos escrever da seguinte forma H A P ot n P du P isso implica que A Zh sen lt s n P ge pr A J sen gt s lu Logo calcularemos Po Sr E da Sech n 0 n 0 n u slu n gt s o que implica em ch A ge e eso so P no P EE SE E HE SA a so P T sxs 1 Si ol Processos Estoc sticos e Teoria de Filas 57 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP As demais f rmulas para L W W s o iguais ao modelo MIMI 2 2 2 SISTEMAS FINITOS 2 2 2 1 Modelo MI M 1 M Esta a situa o na qual a fila po
155. o de Renova o um exemplo desse processo a vida til de um equipamento onde uma pe a que falha substitu da por uma pe a igual Processo de Markov nesse processo toda hist ria passada resumida no estado atual mem ria de curto prazo 1 2 CADEIAS DE MARKOV EM TEMPO DISCRETO Um processo estoc stico dito ter a propriedade Markoviana se AX X X k X k Xo ko PIX a JIX i 6 para t 0 1 e qualquer sequ ncia LL Ko Ki A express o acima equivale a dizer que a probabilidade condicional de qualquer evento futuro dado qualquer evento passado e o estado presente X i independente do evento passado e depende somente do estado presente do processo Ou seja um processo estoc stico dito ser um processo Markoviano se o estado futuro depende apenas do estado presente e n o dos estados passados Esse tipo de processo estoc stico tamb m denominado de processo sem mem ria Se para cada ie j AX jJIX PMX j71X i para todos t 0 ent o as probabilidades de transi o em um est gio s o ditas serem estacion rias e s o denotadas por p Isso implica que as probabilidades de transi o n o mudam no tempo Um processo estoc stico X t 0 1 dito ser uma cadeia de Markov em tempo discreto se tiver o seguinte 1 Satisfizer a propriedade de Markov 2 Possuir espa o de estados enumer vel No presente curso focaremos nossas aten es em cadeias de Markov que
156. o estacion rio No longo prazo sua vari ncia tende a ser infinito Agora vamos analisar no curt ssimo prazo ou seja a representa o diferencial do processo de Wiener Lim Af 0 dZ Jdt Eldz 0 oz E dZ 0 El dZ dt Logo o processo de Wiener n o tem derivada em rela o ao tempo Isso reflete sua natureza imprevis vel A derivada um indicador de para onde vai uma fun o A resposta no caso de um processo de Wiener n o tenho a menor id ia AZ de AZ gt lim gt At At At gt 0 Af 3 5 GENERALIZA O PROCESSO DE WIENER COM DESVIO dx Normalmente distribu da com dx adt o dZ dx varia o do processox de Weiner com desvio dZ varia o do processo de Weiner normal o par metro do desvio constante o par metro de vari ncia constante Processos Estoc sticos e Teoria de Filas 98 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Eldx Ela dt o dZ Eldx a dt Ow El dx Eldx o Elladt o d od Ow El o d i o Elo a dt o amp dt X Considerando o resultado obtido vemos que o valor esperado desse processo linear com a varia o do tempo mas possui uma incerteza vari ncia que varia com a raiz quadrada dessa varia o de tempo Exemplo Considere o pre o de uma commodity moderada para um Processo de Wiener em 50 anos e intervalo de tempo de 1 m s com os
157. o preventiva que custa 50 por per odo alterando pff para 0 9 e pqq para 0 3 vale a pena Processos Estoc sticos e Teoria de Filas 158 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 7 De forma simplificada classificamos as fam lias de certa regi o em rela o ao seu padr o de vida 8 9 No No mm como alto m dio ou baixo Hoje 2 das fam lias t m padr o alto e 14 t m padr o baixo Suponha que as probabilidades das fam lias mudarem de padr o num per odo de cinco anos s o as seguintes alto para m dio 15 alto para baixo 5 m dio para alto 3 m dio para baixo 5 baixo para m dio 4 baixo para alto 1 a Estime a propor o de fam lias que ter padr o alto daqui a dez anos 5 9 b Que propor o das fam lias ter padr o de vida alto m dio e baixo a longo prazo alto 8 7 m dio 41 3 baixo 50 0 c Daqui a quanto tempo em m dia uma fam lia de padr o baixo alcan ar um padr o alto 300 anos Em certo pa s no qual se realizam elei es de quatro em quatro anos h tr s partidos da Esquerda 1 do Centro 2 e da Direita 3 Suponha que h apenas um partido vencedor em cada elei o que a probabilidade do partido j ganhar uma elei o ap s uma vit ria do partido i na elei o anterior est na linha i e na coluna j da tabela a seguir e que esta probabilidade mant m se constante ao longo do tempo 1
158. o processo estoc stico de dimens o J representando em tempo cont nuo o n mero de usu rios em cada esta o de servi o da rede Este processo Markoviano com espa o de estados dado pelo produto cartesiano dos n meros naturais 0 1 E e Deve se notar que as transi es neste processo s o de tr s tipos chegadas externas fim de servi o com mudan a de n o que acarreta uma chegada interna e fim de servi o com sa da da rede Se a rede n o est vazia o tempo de espera para uma transi o o m nimo entre todos os servi os que est o sendo realizados e as chegadas externas Como todos esses tempos s o exponenciais independentes segue que a espera para uma transi o tamb m ser exponencial com par metro dependendo do estado do sistema antes da transi o Se a rede est vazia ser necess rio esperar pela primeira chegada que ser o m nimo entre os tempos de chegadas externas e portanto com distribui o exponencial Processos Estoc sticos e Teoria de Filas 65 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 2 4 2 SISTEMA FECHADO Nas redes de filas fechadas o n mero de clientes no sistema constante n o h entradas nem sa das externas HI e HI Figura 2 12 Rede de filas fechada Seja M o n mero total de clientes na rede isto para qualquer t preciso ter mM n M Como n o h entradas nem sa das a taxa de chegadas exter
159. o y g Seja A 5 S dt B leg Assim temos CR o 20 dt 1 3 2 TEMPO AT A PR XIMA TRANSI O Dol At Pool Pool At Polt At Po Oll Dat Ai Poo At Pool Poo DaAt Polt AL Pool Poo DAAt Polt At Polt _ ES OPoo t RD E US Polt lim ER OPoo t dPoo t EE E AP t Puate 21 Generalizando Um processo estoc stico cont nuo um processo de Markov se X t t 20 com espa o de estados enumer vel E um processo de Markov se para todo t s2 0e JEE P X s t jl X u u lt s P X s t jI X s 22 Processos Estoc sticos e Teoria de Filas 22 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP O processo ser homog neo se PXC D 1X i p 0 Vs Discretizando e utilizando a equa o de Chapman Kolmogorov temos Pit A gt pr Op At Let P t At P t P At e C lculo de P At Utilizaremos para tal a expans o em s rie de Taylor 1 2 1 DEE 3 E OAN en ONA Pj AD p O pj OMAN E onde amp 0 0 Oi j E ds PO 01 Pi 0 dt A 4 P At I A At 24 Retomando t nhamos anteriormente P t At P P At Eq C K Substituindo o resultado obtido em 24 temos P t At POLU A AS P t At P t At SER P A 25 dt P A Processos Estoc sticos e Teoria de Filas 23 COPPE Universidade Federal do Rio de Janeiro Pr
160. ograma de Engenharia de Produ o PEP A chamado gerador infinitesimal e Propriedades de A A a taxa de transi o ou taxa de sa da isto a velocidade com que se escapa de um estado i para um estado j gt As 0 j 1 3 3 PROBABILIDADE DE REGIME PERMANENTE t s c0 No estudo das cadeias de Markov em tempo continuo interessa conhecer as probabilidades estacionarias t gt o0 de o processo estar em diferentes estados lim Is Sa a lim P DA 1500 ano m pro d JM TIA dt As equa es de regime permanente s o as que seguem 0 TIA 26 1 Ile 1 3 4 PROCESSO DE NASCIMENTO E MORTE Os Processos de Nascimento Morte s o processos estoc sticos muito utilizados na descri o de Sistemas de Filas de Espera dada a sua particular estrutura as transi es de um qualquer estado s s o poss veis para estados vizinhos e de um estado i para os estados i 1 ou i 1 Adotando se um espa o de estados X 0 1 e considerando que cada estado representa um certo n vel de popula o exemplo n mero de clientes numa loja n mero de mensagens num coletor de chamadas n mero de produtos a processar etc tais transi es podem ser facilmente interpretadas A transi o do estado i para o estado i 1 ser um nascimento por exemplo chegada de um cliente uma vez que significa um aumento do n vel da popula o Enquanto que a transi o do estado i para o estado
161. om as seguintes caracter sticas a As chegadas externas a cada esta o i e J ocorrem de acordo com um processo de Poisson de par metro 3 independente das outras chegadas e do servi o nas esta es b Para cada n i e J o atendimento realizado em ordem de chegada segundo uma distribui o exponencial de par metro ui ni ui 0 O A depend ncia da taxa ao n mero de usu rios no centro de servi o permite entre outras op es que v rios servidores em paralelo atendam com a mesma taxa c Ap s o usu rio completar seu servi o na esta o i ele move se para mais servi o SE e F hg EE na esta o j com probabilidade onde i j e J Por outro lado se o usu rio j completou sua demanda de servi o na rede ele deixa o sistema ap s ser atendido na esta o i com J hn l E probabilidade k l onde J 1 um n artificial que representa o exterior da rede Todas as transfer ncias s o assumidas serem instant neas e assim o tempo gasto no sistema proveniente de esperas e atendimentos nas esta es A a Figura 2 11 Sistema aberto sem realimenta o Seja R a matriz quadrada de ordem J 1 formada pelas probabilidades de mudan a das esta es incluindo o n externo e mais a probabilidade para as entradas externas atrav s do n i Processos Estoc sticos e Teoria de Filas 64 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP
162. omba de cada vez se em um determinado instante n o houver capacidade de transfer ncia suficiente para escoar toda a produ o esta restringida e ocorre uma perda por lucros cessantes cujo valor unit rio estimado em US 1 20 m3 a vida til do projeto de 10 anos A luz de seus conhecimentos de teoria das filas quantas bombas dever o projetista especificar Processos Estoc sticos e Teoria de Filas 168 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 34 Para produzir um determinado tipo de tinta colorida uma ind stria realiza em uma m quina 8 opera es de mistura As opera es s o semelhantes consecutivas e a dura o de cada uma delas pode ser considerada exponencialmente distribu da com m dia 1 minuto A mat ria prima da m quina em quest o chamada tinta b sica produzida segundo um processo Poisson com taxa 2 litros hora Sabendo que est o em opera o simult nea 2 m quinas mistura doras determine a Qual o estoque m dio de tinta no sistema tinta b sica tinta em processo b O intervalo de tempo decorrido entre o instante que a tinta b sica produzida e o instante que a tinta colorida obtida c Para produzir um tipo especial de tinta s o necess rias 50 opera es da m quina misturadora Fa a uma estimativa do tempo necess rio para obter est tinta especial 35 Dada a rede de filas M M 1 em s rie abaixo a Estabele a as condi
163. omento que nos interessa o trabalho de escava o estava concentrado na parte mais pr xima da estrada sendo necess rios apenas 5 escravos para fazer o trabalho de passagem de cestos O enchiimento destes se fazia raz o de 126 por hora em m dia cada escravo da fila levava em m dia 4 segundos para receber um cesto e pass lo adiante ou despej lo na carro a Enquanto um escravo passava um cesto os outos descansavam i n o havia dois cestos sendo passados simultaneamente Cada carro a podia carregar o conte do de 30 cestos as carro as chegavam ao local da obra raz o de 4 por hora em m dia a Qual o n mero m dio de cestos a espera de serem carregados b Qual o n mero m dio de carro as vazias a espera de serem enchidas c Suponha que a escava o ao progredir se afaste da estrada quantos escravos podem ser colocados a mais na fila de carregamento sem fazer com que os cestos tenham de esperar indefinidamente d Neste ltimo caso quais seriam as respostas aos itens a e b Processos Estoc sticos e Teoria de Filas 165 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 19 Em um hospital a triagem dos pacientes feita por 4 m dicos que atendem com hora marcada e sem escolha o paciente atendido pelo primeiro m dico dispon vel Os pacientes chegam raz o de 60 por dia de 8 horas Cada m dico atende em m dia a 2 pacientes por hor
164. onencial com m dia de 30 chegadas por hora Voc Processos Estoc sticos e Teoria de Filas 90 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP esta fazendo um levantamento na ag ncia e na presente hora j decorridos 15 min j chegaram 10 clientes Quantos clientes voc espera que ainda cheguem na presente hora Justifique 13 A ocupa o m dia de uma lanchonete de fast food de 50 pessoas Sabe se que chegam a lanchonete 100 pessoas hora e que em m dia uma pessoa demora 20 para fazer sua refei o a Quanto tempo demora um cliente dentro da lanchonete b Qual a percentagem deste tempo gasta na fila 14 Um n mero indeterminado de duplas de alpinistas se dirige a uma montanha com o intuito de escal la Na base do lance inicia da escalada h um plat onde s cabem dois alpinistas e o caminho at este plat estreito e ngreme Um dos guias do grupo esta na entrada deste caminho orientando a subida para o plat De l ele n o pode ver nem ouvir o que se passa em cima mas baseado na experi ncia procura evitar que mais de uma dupla esteja esperando na base do lance dada a falta de espa o Ele sabe que o lance consome em m dia 12 minutos de cada dupla se ela deseja que o plat fique sem superlota o em 84 dos casos quantos alpinistas ele deve encaminhar em m dia por hora para l 15 Um reator nuclear usado para a produ o de radiois to
165. or que permite que at duas das esta es sejam reparadas simultaneamente quando da ocorr ncia de defeitos O tempo de reparo de cada esta o pode ser considerado exponencialmente distribu do com dura o m dia de 10 dias Desenvolva um modelo de filas para representar o problema e obtenha a O diagrama de transi o de estados b as equa es de equil brio e de recorr ncia c o n mero m dio de esta es em opera o normal d a percentagem do tempo em que todas as esta es est o paradas Est o sendo feitos planos para a abertura de um posto de lavagem de carros pequeno e tem que ser decidido quanto espa o para carros a espera estimado que os clientes chegariam aleatoriamente i e segundo um processo de chegadas Poisson com uma taxa m dia de um a cada 4 minutos a menos que a rea de carros a espera esteja lotada em cujo caso o cliente levaria seu carro a outro lugar O tempo que pode ser atribu do lavagem de um carro tem uma distribui o exponencial com uma m dia de 3 minutos Compare a fra o de clientes potenciais que seria perdida por causa de espa o de espera inadequado se a zero b dois ou c quatro espa os n o incluindo o carro que est sendo lavado fossem previstos Obs Desenvolva a partir do diagrama de transi o de estados as express es necess rias para a solu o do problema Uma empresa de nibus envia seus nibus para manuten o de rotina a cada 25 000 Km A garagem
166. os casos quantos alpinistas ele deve encaminhar em m dia por hora para l u o Sduplas hora 12 min Po P 0 84 A p 1 p p 0 84 gt 1 p 0 84 gt p 0 16 gt p 0 40 A 2 p a A 0 4 5 2 duplas hora 4 alpinistas hora u 15 Um reator nuclear usado para a produ o de radiois topos de uso medicinal Um deles de meia vida particularmente curta tem uma demanda de 3 doses por semana em m dia se uma dose for guardada por mais de 2 semanas em m dia ela se tornar fraca demais para ser usada Processos Estoc sticos e Teoria de Filas 151 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP c Qual ser a produ o anual esperada nestas circunst ncias d Qual ser o valor esperado do n mero de unidades em estoque u 3 doses semana a W 2 semanas Ac 1 5 W 2 3 1 1 A gt 2 5 doses semana u 2 b L L W w P 2 5 3 5 si u l p j 31 2 cs 3 Hr u 5 L AW 2 5 4 17doses 3 16 Uma ag ncia de caderneta de poupan a tem k guich s cada um dos quais pode atender em m dia a 180 pessoas por hora Em um certo dia a demanda m dia pelos servi os da ag ncia de 440 pessoas por hora Os guich s est o dispostos em uma linha perpendicular entrada isto faz com que muitas pessoas entrem na primeira fila que encontram sem procurar verificar se existe ou n o outra fila menor Estima se que a p
167. para a maioria dos modelos de fila mesmo para situa es em que na verdade exista um limite superior finito relativamente grande no n mero permiss vel de clientes uma vez que tratar com um limite superior seria um fator de complica o na an lise Entretanto para sistemas de filas em que este limite superior suficientemente pequeno para que seja de fato alcan ado com alguma frequ ncia torna se necess rio supor uma fila finita Variando as caracter sticas a a d acima podemos obter um grande n mero de modelos conforme ser apresentado a seguir 2 1 3 NOTA O DE KENDALL O professor D G Kendall criou em 1953 uma nota o para sistemas de filas que hoje largamente utilizada A nota o consiste na forma A B c K Z onde A descreve a distribui o do tempo entre chegadas B a distribui o do tempo de servi o c o n mero de servidores K a capacidade da fila de espera alguns autores definem K como capacidade total de usu rios no sistema e Z a disciplina de atendimento Algumas escolhas para A e B s o as seguintes M Distribui o Exponencial de memoryless Distribui o de Erlang k Distribui o Determin stica ou degenerada Distribui o Uniforme Distribui o Geral n o especificada A omiss o de K e Z na representa o acima indica que a fila tem capacidade infinita e disciplina FCFS Por exemplo a fila M G 1 tem chegadas exponenciais o servi o com distribui o geral e um servidor
168. po em n pequenos passos de tamanho At t dividido emn passos t At ou t n At n X X tem distribui o binominal para passosindependentes Processos Estoc sticos e Teoria de Filas 100 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Considerando n passos E X X n E Ax n p 4 Ah t p a o X X n 0 Ax n 4pg Ah apa r H Usando Ah 0At gt An 0 At gt DI o E Ax aAt p gAh gt GEZ EA Arel vin Para n passos t finito At 0 n gt infinito Distribui o binominal nomal Ah Ah com m dia t S Ab t d TO o At o At SE ANF com vari ncia 4 pal 0 t Conclus es p q Ah Ar o o 1 Podemos dizer o Movimento Browniano o limite do passeio aleat rio quando o intervalo de tempo e tamanho do passo tendem a zero Se mantida a rela o Ah 0N At 2 A rela o descrita na f rmula acima a nica que faz com que a vari ncia de Xt X0 depende de t e n o do n mero de passos 3 A rela o entre dx e dt n o direta dx depende de Vat 4 Transi es em x em um per odo finito de tempo s o normalmente distribu das porque quando n passos cresce a distribui o binominal tende para a normal 5 Quando At gt 0 a dist ncia total percorrida em um n mero finito de passos tende a infinito Processos Estoc sticos e Teoria de Filas 101 COPPE Universidade Fe
169. po passa em cada planta d As hip teses de Markov do ponto de vista do sapo significam que ele n o tem mem ria Por exemplo ele n o sabe se determinado lugar tem mosca ou n o ou ainda se determinada planta afunda ou n o as chances de ir para a pr xima planta s dependem da planta onde ele est A propriedade de estacionariedade indica que o sapo n o aprende ao longo do tempo O pr ximo salto aleat rio Processos Estoc sticos e Teoria de Filas 128 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 19 Se segura Companhia de Seguras classifica seus clientes de acordo com seu hist rico de acidentes do cliente Um cliente que n o tenha tido nenhum acidente nos ltimos dois anos tem uma anualidade de 100 Clientes que tenham tido acidentes em ambos os anos tem uma anualidade de 400 Clientes que tenham tido acidente em somente um dos ltimos dois anos tem uma anualidade de 300 Um cliente que tenha tido um acidente no ltimo ano tem 10 de chance de ter um acidente no ano corrente Se o cliente n o tiver tido nenhum acidente no ltimo ano ele tem 3 de chance de ter um acidente no ano corrente Para um dado ano qual a anualidade m dia paga por um cliente da Se segura Estado X Y X 1 teve acidente no ano 1 Y 1 teve acidente no ano 2 00 01 10 00 EPA DEN oof 0 97 0 03 0 O P 01 0 0 0 9 0 1 10 0 97 0 08 0 O ES 0 03 0 9 11 0 0 0 9 0 1 0 1
170. pos de uso medicinal Um deles de meia vida particularmente curta tem uma demanda de 3 doses por semana em m dia se uma dose for guardada por mais de 2 semanas em m dia ela se tornar fraca demais para ser usada a Qual ser a produ o anual esperada nestas circunst ncias b Qual ser o valor esperado do n mero de unidades em estoque 16 Uma ag ncia de caderneta de poupan a tem k guich s cada um dos quais pode atender em m dia a 180 pessoas por hora Em um certo dia a demanda m dia pelos servi os da ag ncia de 440 pessoas por hora Os guich s est o dispostos em uma linha perpendicular entrada isto faz com que muitas pessoas entrem na primeira fila que encontram sem procurar verificar se existe ou n o outra fila menor Estima se que a probabilidade de uma pessoa entrar na fila i de 2 k k 1 i k 1 Suponha que k 4 e responda a qual o tempo m dio gasto por uma pessoa que entrou na primeira fila b qual a fra o do tempo desocupado do caixa da fila 4 17 Ae B s o duas m quinas de opera o manual em uma linha de produ o as pe as processadas por A saem dela raz o de 10 por hora em m dia e s o processadas em seguida por B raz o de 12 por hora em m dia Dado o espa o entre A e B haver Processos Estoc sticos e Teoria de Filas 91 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP congestionamento da linha sempre que
171. pram o livro com um ano de uso o vendam de volta e que 60 dos estudantes que compram um livro com dois anos de uso o vendam de volta Os livros com 4 ou mais anos de uso j est o muito usados e n o s o mais negociados a Em regime permanente quantos novos exemplares do livro pode a editora esperar vender do livro b Suponha que o lucro da livraria com cada tipo de livro seja de 6 por um livro novo 3 por um livro com 1 ano de uso 2 por um livro com 2 anos de uso e de 1 por livro com 3 anos de uso Qual o lucro esperado por livro vendido 12 Tr s bolas s o divididas entre 2 caixas Durante cada per odo uma bola escolhida aleatoriamente e trocada para a outra caixa a Calcule a fra o do tempo que uma caixa ir conter 0 1 2 ou 3 bolas b Se a caixa 1 n o cont m bolas em m dia quanto tempo ser decorrido at que ela contenha 1 2 e tr s bolas Processos Estoc sticos e Teoria de Filas 32 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 13 Classifique os diversos estados das cadeias de Markov a seguir dadas por sua matriz de transi o Calcule as probabilidades estacion rias 0 7 03 0 a P 0 08 0 2 0 4 03 0 3 1 6 1 3 1 2 b P 1 6 1 3 1 2 1 6 1 3 1 2 1 4 3 8 3 8 c P 0 0 1 d 1 d 1 2 0 1 2 d P 0 1 0 2 5 0 3 5 2 3 0 O 1 3 O 1 5 4 5 0 O 1 4 3 4 0 1 8 0 O 7 8 14 Dois jogadores jogam uma moeda honesta Se der cara o jogador paga R 1
172. probabilidade que a casa esteja lotada c Dado que a casa esta lotada quanto tempo demora at que ela esteja completamente vazia a 0 3 0 4 0 4 0 4 0 4 0 4 0 7 0 2 Es 0 1 0 1 0 1 Estado n de pessoas na barbearia no in cio do corte de cabelo Est gio per odo de corte do cabelo Transi o pr ximo corte 0 1 2 3 4 5 6 0 03 04 02 01 0 0 O 1 03 0 4 0 2 0 1 0 0 0 P 2 O 03 04 0 2 01 0 0 3 0 03 0 4 0 2 01 0 4 0 0 O 03 04 0 2 0 1 5 0 0 0 O 03 04 0 3 6 0 0 0 0 D 0 3 0 7 b 70 D 71 m 0 0307 7 0 4 7 7 037 z 0 0716 m 0 27 7 0 47 0 37 7 0 1023 m 0 l 7 7 0 27 0 47 0 37 gt m 0 1364 m 0 1z 0 27 0 47 0 37 m 0 1704 m 0lm 0 27 0 47 0 37 m 0 2159 Mo tA T T ta A A l Ts 0 2727 Processos Estoc sticos e Teoria de Filas 131 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Probabilidade da casa estar lotada ae 27 27 c Meo 1 Doo Peso Posso Peso Posso Poseo Meo 94 07 Mso 1 Pao PsM Ps3Mzo Pao PssMso PsoMso iaa 90 74 Mo 1 Palio Paso Passo Passo Passo Pa o ER M 84 07 Mo 1 Dao P323M Passo Paso Passo Passo mo 12 96 Moo 1 Pamo Posso Posso Posso Posso Po o M 56 29 Mio 1 Pi Mio Pi2M Piso Piso PisMso Piso Mo 32 59 Tempo m dio para que a casa passe de lotada a vazia Mso 94 07 cortes de cabelo 22
173. quinas Processos Estoc sticos e Teoria de Filas 126 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP d Qual o tempo m dio entre duas encomendas a A matriz foi obtida usando a tabela da distribui o de Poisson Onde P D 0 P D 1 0 368 P D 1 2 0 184 e P D 4 3 0 0613 Ex Se X 0 o estoque reposto e fica com 3 m quinas Logo a probabilidade de que X 1 3 D 1 0 ou Rus D 1 1 de 0 368 A probabilidade de que X1 1 D 1 2 de 0 184 Se D 123 ent o s nesse caso a probabilidade de 1 0 368 0 368 0 184 0 08 b Tempo esperado para que o estoque se esgote dado que iniciou com 3 m quinas mao Mio 1 Pao Paso Passo Mo 3 5 Moo 1 Dao PaM P23M30 gt Mo 2 5 Mo 1 Pio Pi2M Di sf mo 1 6 c Probabilidade de encontrar o estoque com 0 1 2 e 3 m quinas dada pelo vetor n ma 0 08 m 0 632 7 0 264 7 0 08 7 Ta 0 2857 m 0 368 m 0 368 m 0 368 7 m 0 2848 m 0 368 m 0 368 7 T 0 2632 myta tar m l m 0 1663 A probabilidade de encontrar 4 m quinas no estoque 0 d Tempo m dio entre duas encomendas tempo m dio de retorno para o estado O Moo 1 ro 3 5 semanas 18 Um naturalista est observando o comportamento de um sapo em um pequeno lago no qual h 4 ninf ias plantas aqu ticas O sapo circula entre estas 4 plantas pulando de uma para outra as quais s o numeradas arbitrariame
174. r o de respostas corretas ap s 4 repeti es pi 42 69 c 3 ee pu ES be fic Hp k l fe EE Pro 0 01 Le pr fic Pec 0 0194 0 01 0 95 0 0099 fem Duo E Pec 0 0282 0 01 0 903 0 0099 0 85 0 009765 ua Pe fr Deo fo Pro RE ne Pee 0 0365 0 01 0 858 0 0099 0 903 0 009765 0 95 0 009703 0 97 Probabilidade de se obter uma resposta correta exatamente 4 tentativas ap s uma resposta incorreta fic 0 97 d mic 1 Bu iw 1 0 99 mp mMc 100 n m dio de tentativas para que se obtenha uma resposta correta ap s ter obtido uma resposta incorreta mic 100 tentativas 23 Um jogador joga um jogo limpo no qual as chances s o 2 contra 1 Em outras palavras ele tem 1 3 de probabilidade de ganhar e 2 3 de perder Se ganhar ganhar 2 Se perder perder 1 Suponha que os recursos totais do jogador e do seu oponente sejam N Se o capital de qualquer um dos jogadores cair abaixo do ponto em que eles pudessem pagar caso perdessem o jogo seguinte o jogo termina a Desenhe o diagrama de transi o de estados e determine a matriz de transi o b Suponha que os dois jogadores concordem em que se o capital de qualquer dos dois cair para 1 eles far o o pr ximo jogo com chances iguais ganhar o ou Processos Estoc sticos e Teoria de Filas 133 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP perder o 1 com igual
175. r vendida b Se uma rvore com menos de 3m plantada qual o seu valor esperado de venda M V20 V30 e V50 s o estados absorventes 3 3 M V20 V30 V50 3 03 02 04 01 0 O 3 0 03 10 0 02 05 P M 0 o de OO SO EE vo o o0o 0 1 0 0 Sg o c dO 4 0 V nl o Dip 0 0 1 1 428 0 408 0 571 0 142 0 082 0 204 E 1 0 nee 0 1428 0 0 0 285 0 714 c Probabilidade de que uma rvore com menos de 3m morra antes de ser vendida a 3m 0 571 57 d Valor esperado de venda se uma rvore com menos de 3m plantada Vesp 20 0 142 30 0 082 50 0 204 15 50 Processos Estoc sticos e Teoria de Filas 104 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 02 Com a chegada da civiliza o os ndios da Aldeia Taipan resolveram instituir um sistema de previd ncia social para o que contaram com a ajuda de um consultor Mestre em Engenharia de Produ o A primeira etapa do estudo do consultor consistiu em classificar os ndios em tr s grupos crian as trabalhadores e aposentados Logo em seguida utilizando a excelente mem ria dos ndios ele inferiu os seguintes dados durante um per odo de um ano 959 1000 de todas as crian as permanecem crian as 40 1000 se tornam adultos trabalhadores e 1 1000 delas morrem al m disto ainda durante um dado ano 960 1000 de todos os adultos trabalhadores permanecem adultos trabalhadores 30 1000 se apo
176. ra jogada que implicam em continua o do jogo a saber 4 5 6 8 9 e 10 As probabilidades de transi o se encontram na matriz abaixo Por simplicidade dispensamo nos de esbo ar o D T E correspondente Processos Estoc sticos e Teoria de Filas 108 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 4 5 6 89 10 G P I O 336 4 36 5 36 5 36 4 36 3 36 8 36 4 4 36 5 0 27 36 0 0 0 0 0 3 36 6 6 36 P 8 0 O 26 36 0 0 0 0 4 36 9 6 36 10 O 0 O 25 36 0 0 0 5 36 G 6 36 P o0 0 0 O 25 36 0 0 5 36 6 36 0 0 0 0 O 26 36 0 4 36 6 36 0 0 0 0 0 O 27 36 3 36 6 36 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 O 336 4 36 5 36 5 36 4 36 3 36 O 27 36 0 0 0 0 0 0 O 26 36 0 0 0 0 Q 0 0 O 25 36 0 0 0 0 0 0 O 25 36 0 0 0 0 0 0 O 26 36 0 0 0 0 0 0 O 27 36 1 3 36 4 36 5 36 5 36 4 36 3 36 O 9 36 0 0 0 0 0 0 O 10 36 0 0 0 0 HQ 0 0 O 11 36 0 0 0 0 0 0 O 11 36 O 0 0 0 0 0 O 10 36 0 0 0 0 0 0 O 9 36 1 1 3 2 5 511 541 2 5 1 3 0 4 0 0 0 0 0 0 o 185 0 0 0 0 l Q 0 0 O 36 11 0 0 0 0 0 0 o 36 11 0 0 0 0 0 0 o 185 0 0 0 0 0 0 0 4 O tempo m dio de jogo ser 3 376 obtido por 1 1 3 2 5 5 11 5 11 2 5 1 8 Processos Estoc sticos e Teoria de Filas 109 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP G 35 72 1 3 2 5 5 11 5 11 2 5 1 3 o A A Il Q R O O On P 37
177. ra que de 450 faturas emitidas no m s de janeiro 120 foram pagas 90 ainda n o venceram 90 apresentam atraso de um m s e 150 com atraso de dois meses Finalmente a ltima linha mostra que de 200 faturas emitidas no m s de dezembro al m da segii ncia de pagamentos e atrasos 30 correspondem perda ou seja atraso superior a 2 meses Seja uma carteira de cr dito total de R 1 000 000 00 conforme mostramos a seguir Situa o da Carteira Valor R Contas em dia 800 000 Contas com atraso de 1 m s 120 000 Contas com atraso de 2 meses 80 000 Valor da carteira 1 000 000 Calcule o valor esperado que ser pago Ajustando as quantidades para vetores de probabilidades considerando as faturas pagas Pag e perdas A como estados absorventes e transpondo a coluna de faturas pagas podemos gerar a seguinte matriz de transi o Ao A A2 An Pag Ao 100 400 150 400 o 2 o0 150 400 P Al 90 450 90 450 150 450 O 120 450 A gt 40 200 40 200 60 200 7 30 200 30 200 Anh SA KE o De RO Oo Pag 0 0 Or 0 1 Processos Estoc sticos e Teoria de Filas 138 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Ao A A2 An Pag Ao 0 25 0 375 O 0 0 375 P A 02 02 0333 0 0 267 A 02 02 D 0 15 0 15 a ape a de eU Aa A NES UA AR ES RAS E ESA E SE DS An 0 0 Da 0 Pag 0 0 0 i o0 1 Ao A Ap Ao A A2 Ao 0 75 0 375 0 A 1 6
178. racter sticas de um processo de Wiener O Processo de Wiener lembra bastante o b bado no corredor que vimos at agora 3 4 PROCESSO DE WIENER Seja Z um processo de Wiener e AZ a mudan a em Z transi o correspondente a um intervalo de tempo At A rela o entre AZ e At dada por defini o AZ e At onde uma v a normalmente distribu da com m dia zero e desvio padr o 1 Sendo que a vari vel aleat ria s n o tem correla o serial no tempo isto COV Lex e 0 vtzs Podemos dizer que AZ uma vari vel aleat ria com distribui o normal de m dia zero e vari ncia igual a At Assim os valores de AZ para diferentes intervalos de tempo s o independentes Como consequ ncia Z um processo de Markov Propriedade 1 com incrementos independentes Propriedade 2 Analisando uma transi o num intervalo de tempo T constitu do de n subintervalos At isto Processos Estoc sticos e Teoria de Filas 97 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP AZ Z s T Z s z E JA com independente AZ De A logo ei Elei Al ALXI Atn T AZ normalmente distribu da com m dia zero e vari ncia n At T Isto a vari ncia de uma transi o no processo de Wiener cresce linearmente com o horizonte de tempo Isso quer dizer que quanto mais pra frente se olha o processo maior a incerteza do mesmo Propriedade 3 O processo de Wiener n
179. rado ii se ontem esteve chuvoso e hoje ensolarado ent o com 70 de chance amanh ser ensolarado iii se ontem estava ensolarado e hoje est chuvoso ent o amanh ser um dia chuvoso com 60 de chance iv se os dois ltimos dias foram chuvosos ent o amanha ser um dia chuvoso com 80 de chance poss vel modelar o tempo em Pedra Azul como uma cadeia de Markov Explique porque e construa o diagrama de transi o de estados Sim poss vel modelar como uma cadeia de Markov se o estado trouxer a informa o dos 2 ltimos dias assim toda informa o que preciso para o pr ximo estado est contida no estado anterior hoje amanh E E E C E E C CC 0 95 0 0 05 O e Se Le 0 7 0 03 0 E 0 0 4 o 06 Ge 0 0 2 o 08 hoje ontem 06 Suponha que no mercado existem apenas duas marcas de cerveja Mharba e rtica Dado que a ltima compra de uma pessoa foi uma de Mharba existe 90 de chance de que sua pr xima compra seja de Mharba Dado que a ltima compra de uma pessoa foi de rtica existe uma probabilidade de 80 de que sua pr xima compra seja de rtica o Xo tn 2 oo a Represente o problema por uma cadeia de Markov apresentando a matriz de probabilidades de transi o e o diagrama de transi o de estados b Dado que uma pessoa acabou de comprar Mharba quanto tempo ser necess rio para que outra compra de Mharba seja realizada E de tica Como voc interpreta o tempo neste ca
180. resultados distorcidos visto que na verdade a popula o pequena para ser considerada de tamanho infinito Quando isto ocorre a presen a de um ou mais usu rios no sistema tem um forte efeito na distribui o das chegadas futuras e o uso de um modelo com popula o infinita conduz a resultados errados Alguns exemplos t picos s o um pequeno grupo de m quinas que quebram de tempos em tempos necessitando conserto um pequeno grupo de mec nicos que v o a determinado balc o pegar pe as ou ferramentas Num caso extremo do primeiro exemplo se todas as m quinas est o quebradas nenhuma chegada pode ocorrer Processos Estoc sticos e Teoria de Filas 59 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Isto contrasta com os modelos de popula o infinita nos quais a taxa de chegada independente do n mero de usu rios que j est o no sistema Neste tipo de modelo a taxa de chegada a taxa de chegada de cada unidade ou seja 1 1 o tempo m dio entre chegadas de cada unidade No caso das m quinas por exemplo seria o tempo m dio entre quebra de cada m quina A taxa de chegada efetiva Ae d a taxa m dia de chegada considerando se todos os usu rios As f rmulas para este tipo de modelo s o bastante complexas e n o ser o apresentadas aqui 2 3 MODELO DE ERLANG Se uma vari vel aleat ria t regida por uma distribui o de Erlang de ordem k ela pode
181. rmanecem na floresta a Qual a probabilidade de que uma rvore com menos de 3m morra antes de ser vendida b Se uma rvore com menos de 3m plantada qual o seu valor esperado de venda 02 Com a chegada da civiliza o os ndios da Aldeia Taipan resolveram instituir um sistema de previd ncia social para o que contaram com a ajuda de um consultor Mestre em Engenharia de Produ o A primeira etapa do estudo do consultor consistiu em classificar os ndios em tr s grupos crian as trabalhadores e aposentados Logo em seguida utilizando a excelente mem ria dos ndios ele inferiu os seguintes dados durante um per odo de um ano 959 1000 de todas as crian as permanecem crian as 40 1000 se tornam adultos trabalhadores e 1 1000 delas morrem al m disto ainda durante um dado ano 960 1000 de todos os adultos trabalhadores permanecem adultos trabalhadores 30 1000 se aposentam e 10 1000 falecem A taxa de mortalidade dos aposentados de 50 1000 a cada ano O n mero de nascimentos de 1000 crian as por ano a Supondo que a popula o da Aldeia est em regime permanente determine a sua popula o bem como sua estrutura et ria nos tr s grupos mencionados b Cada aposentado recebe uma pens o de 5 000 por ano O fundo de pens o custeado pelos pagamentos dos adultos trabalhadores Com quanto cada adulto trabalhador deve contribuir por ano para o fundo de pens o 03 No jogo de Craps n s jogamos um par de
182. ro de ber os Se existem poucos ber os o custo da fila ser grande mas o custo do servi o ser pequeno J se existirem muitos ber os o custo do servi o ser grande mas em compensa o como a fila ser pequena o custo da fila ser pequeno 2 1 2 PRINCIPAIS CARACTERISTICAS DE UMA FILA Algumas das caracter sticas b sicas de uma fila como chegadas servi o de disciplina de atendimento e capacidade de espera ser o descritas a seguir a Chegadas O processo de chegada arrival process a descri o de como os usu rios procuram o servi o Se eles chegam a intervalos fixos de tempo o processo de chegadas dito constante ou determin stico Por outro lado se as chegadas s o aleat rias no tempo elas formam um processo estoc stico e necess rio descrever suas propriedades probabil sticas A suposi o mais comum de que as chegadas formam um processo de renova o isto os intervalos entre chegadas s o independentes e identicamente distribu dos Em geral tamb m assumida a independ ncia em rela o ao servi o mas poss vel aplicar um processo de renova o para as chegadas condicionado situa o do servi o O processo de Poisson um processo de renova o com distribui o exponencial e um dos Processos Estoc sticos e Teoria de Filas 40 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP mais utilizados para modelar as chegadas
183. robabilidade de uma pessoa entrar na fila i de 2 k k 1 i k 1 Suponha que k 4 e responda a qual o tempo m dio gasto por uma pessoa que entrou na primeira fila b qual a fra o do tempo desocupado do caixa da fila 4 Processos Estoc sticos e Teoria de Filas 152 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP u 180 pessoas hora 440 pessoas hora _2 k 1 i Ppi onde k 4 k k 1 _2 5 i Pa a W ET 440 2 176 1 1 W u 180 176 0 25 hora 15 minutos b ociosidade 1 p 1 0 756 75 6 1 See 4 P 10 E SE E 17 A e B s o duas m quinas de opera o manual em uma linha de produ o as pe as processadas por A saem dela raz o de 10 por hora em m dia e s o processadas em seguida por B raz o de 12 por hora em m dia Dado o espa o entre A e B haver congestionamento da linha sempre que existam mais de 2 pe as espera do processamento Qual a fra o esperada do tempo de funcionamento da linha relativa a ocorr ncia de congestionamento Es Liia UA 2 Congestionamento 1 p p p p3 4 1 l p p pP P P p p SI 0 4822 lh 100 x 48 22 x 48 22 18 A sa da de um t nel uma pista com 2 faixas de tr nsito em m o nica 100 metros mais adiante h um sinal luminoso que abre o tr nsito a cada 20 segundos deixando passar de cada vez 10 carros Em um dado moment
184. robabilidade do tempo restante at o incidente chegada ou conclus o do servi o que ocorre sempre a mesma independente de quanto tempo At j tenha se passado Com efeito o processo esquece sua hist ria Este fen meno surpreendente ocorre com a distribui o exponencial porque PT gt ALT gt t At PT gt At PT gt t At PT gt At P T gt t At T gt At e7204 at e ot e Para tempos entre chegadas esta propriedade descreve a situa o comum onde o tempo at a chegada seguinte completamente n o influenciado por quando tenha ocorrido a ultima chegada Para tempos de servi o a propriedade mais dif cil de ser interpretada N o dever amos esperar que ela se mantivesse numa situa o onde o servidor tivesse que realizar a mesma sequ ncia fixa de opera es para cada cliente porque ent o um servi o logo implicaria que provavelmente pouco restaria a ser feito Por outro lado no tipo de situa o onde as opera es de servi o requeridas diferem de cliente para cliente a defini o matem tica da propriedade pode ser bastante real stica Para este caso se j tiver sido feito um servi o consider vel para um cliente a nica implica o pode ser que este cliente em particular requeira mais servi os que a maioria PROPRIEDADE 3 O m nimo de diversas vari veis aleat rias independentes exponenciais tem uma distribui o exponencial Para definirmos esta propriedade matema
185. rograma de Engenharia de Produ o PEP Exemplo Il Suponha que X seja binomialmente distribu da com par metros n e p Neste caso n Mx t Sel k 0 n pea py ER pe pf ora pr K A ltima igualdade decorre de uma aplica o direta do teorema binomial Exemplo III Suponha que X tenha uma distribui o de Poisson com par metro Por conseguinte oo oo k eta A Zei 1 Mn gt e LT e 3 E k 0 k 0 A de Ale 1 E e EC A terceira igualdade decorre do desenvolvimento de et em 1 0 Esta foi empregada com y et Exemplo IV Suponha que X tenha uma distribui o exponencial com par metro a Logo Mx t f e ae dx af e2 dx Esta integral converge somente se t lt a Por isso a fgm existe somente para estes valores de t Admitido que essa condi o seja satisfeita temos Mx t Lero 0 LIt lt a a t Visto que a fgm apenas um valor esperado de X podemos obter a fgm de uma fun o de uma vari vel aleat ria sem primeiro obtermos sua distribui o de probabilidade Por exemplo se X tiver distribui o N 0 1 e desejarmos achar a fgm de Y X podemos prosseguir sem obtermos a fgm de Y bastando para isso escrevermos Processos Estoc sticos e Teoria de Filas 80 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 1 Main Ele E e f exp Ami 4 dx 1 20 27 2 6 2 PROPRIEDADES DA F
186. ros por hora tempos de verifica o exponenciais Se o aeroporto tem apenas um posto responda a qual a probabilidade que um passageiro tenha de esperar pela verifica o b em m dia quantos passageiros estar o esperando pela verifica o c em m dia quanto tempo o passageiro gastar no processo de verifica o d Suponha agora que a administra o do aeroporto queira determinar quantos postos deve operar de modo a minimizar custos operacionais e de atraso por um per odo de 10 anos Assuma que o custo de 1 hora de atraso de um passageiro 10 e que o aeroporto funciona 16 h por dia O custo de aquisi o opera o e manuten o de um posto pode ser estimado em 1 milh o em um per odo de 10 anos Finalmente assuma que cada passageiro escolhe entre os postos com igual probabilidade 49 Duas barbearias est o situadas lado a lado em um shopping Cada uma delas comporta at 4 clientes 1 cortando o cabelo e os demais esperando e qualquer cliente potencial que encontre a barbearia cheia n o espera e desiste de cortar o cabelo ali A barbearia 1 cobra 11 por um corte de cabelo que demora em m dia 12 minutos A barbearia 2 cobra 5 por corte que dura em m dia 6 minutos Os clientes potenciais procuram cada uma das barbearias a uma taxa m dia de 10 clientes hora Assumindo tempos entre chegadas e de corte como exponenciais qual barbearia ter maior receita 50 A partir da moderniza o dos pontos de venda a opera
187. rutura topol gica da rede importante uma vez que ela descreve as transi es poss veis entre os n s Os caminhos feitos por cada cliente tamb m devem ser descritos A natureza do fluxo estoc stico em termos do processo estoc stico b sico que descreve este fluxo tem grande signific ncia Considere a rede com dois n s mostrada na Figura 2 10 Rede de filas Markovianas com 2 esta es Figura 2 10 Rede de filas Markovianas com 2 esta es Assumindo se que as chegadas ao sistema obedecem ao processo de Poisson a uma taxa e que o servidor 1 atende com distribui o exponencial a uma taxa u4 Ent o o n 1 representa um sistema de filas MIMI Da mesma forma o n 2 isoladamente representa um sistema de filas MIMI A quest o b sica encontrar a distribui o do tempo entre chegadas no n 2 que ser equivalente a distribui o do tempo entre partidas do n 1 Pode se dizer que em m dia o valor da taxa de chegada ao n 2 Jai A SE A lt 4 a A se zi Processos Estoc sticos e Teoria de Filas 63 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Ou seja quando Ly significa que o servidor 1 um limitador e deve se passar a analisar apenas as filas seguintes a este servidor 2 4 1 SISTEMA ABERTO SEM REALIMENTA O Uma rede aberta tamb m denominada rede aberta de Jackson exemplificada na Figura 2 11 consiste de um conjunto de J n s c
188. s poss vel como tamb m relativamente prov vel que T assuma um valor pequeno pr ximo a zero De fato 11 PO lt T lt 0 393 Jo enquanto PI lt T lt gt 0 383 N Es I o o DO de modo que mais prov vel que o valor de T assuma seja pequeno isto menor que a metade de E T e n o pr ximo ao seu valor esperado isto n o muito longe de metade de E T mesmo que o segundo intervalo seja duas vezes maior que o primeiro O questionamento a ser feito se esta propriedade para T realmente razo vel num modelo de fila Se T representar tempos de servi o a resposta depender da natureza geral do servi o envolvido conforme discutido a seguir Se o servi o requerido for essencialmente id ntico para cada cliente com o servidor realizando sempre a mesma sequ ncia de opera es de servi o ent o os tempos de servi o reais tenderiam a estar pr ximos ao tempo de servi o esperado Podem ocorrer pequenos desvios da m dia por m usualmente isso se daria apenas por causa das pequenas varia es na efici ncia do servidor Um tempo de servi o pequeno muito abaixo da m dia seria essencialmente imposs vel porque necess ria uma certa quantidade de tempo m nimo para realizar as opera es de servi o requeridas mesmo que o servidor esteja trabalhando a toda velocidade Esta claro que a distribui o exponencial n o forneceria uma aproxima o precisa para a distribui o de
189. s de supermercado e uma fila de lanchonete onde cada um se serve canais de servi o em s rie Entretanto em muitas outras organiza es isto n o ocorre tais como servi os de assist ncia t cnica a domicilio o t cnico de manuten o vai at o cliente m quina de venda autom tica onde o vendedor uma m quina e um posto de gasolina onde os carros podem ser vistos como os clientes Outra classe importante a dos sistemas de servi o de transporte Para alguns destes sistemas os ve culos s o os clientes tais como os carros esperando num posto de ped gio ou sinaleira de tr nsito um caminh o ou navio esperando para ser carregado ou descarregado por carregadores ou servidores e avi es esperando para aterrisar ou decolar de uma pista o servidor Em anos recentes a teoria de filas provavelmente tem sido mais aplicada a sistemas de servi o internos empresa ind stria onde os clientes que recebem servi os s o internos organiza o Exemplos disto s o sistemas de manuseio de materiais onde unidades de manuseio de materiais ou servidores movem as cargas os clientes Al m disso as m quinas podem ser vistas como servidores cujos clientes s o os trabalhos que est o sendo processados Um exemplo correlato de grande import ncia uma instala o de computador onde o computador visto como servidor Ultimamente tem havido um reconhecimento crescente de que a teoria das filas tamb m seja aplic vel a sis
190. sentam e 10 1000 falecem A taxa de mortalidade dos aposentados de 50 1000 a cada ano O n mero de nascimentos de 1000 crian as por ano a Supondo que a popula o da Aldeia est em regime permanente determine a sua popula o bem como sua estrutura et ria nos tr s grupos mencionados b Cada aposentado recebe uma pens o de 5 000 por ano O fundo de pens o custeado pelos pagamentos dos adultos trabalhadores Com quanto cada adulto trabalhador deve contribuir por ano para o fundo de pens o Como a popula o da Aldeia est em regime permanente o n mero de nascimentos igual ao n mero de mortes isto est representado pela transi o M gt C Usando a Lei da Conserva o de Fluxo e o fato de que o n mero de mortes igual ao n mero de nascimentos temos o sistema 0 04C 0 03 0 01 T 0 037 0 05A4P 0 05 AP 0 017 0 001C IM IM 0 04 0 001 C M 1000 Logo Processos Estoc sticos e Teoria de Filas 105 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP a Popula o da Aldeia e sua estrutura et ria Crian as C 24 390 1000 25390 1000 nascimentos por ano Trabalhadores T 24 390 Aposentados AP 14 634 Popula o total 64 414 ndios b Valor a pagar aos aposentados 14 634 5 000 Ent o cada trabalhador deve contribuir com 14 634 5 000 3000 ano 24 390 03 No jogo de Craps n s jogamos um par de dados
191. servi o tenha ca do para 3 1 2 minutos Como o p nico afeta L e W 10 Mec nicos que trabalham no Centro Automotivo Classe A devem retirar as ferramentas e pe as que necessitam de uma ferramentaria Uma m dia de 10 mec nicos por hora chegam procurando por pe as Atualmente a ferramentaria possui um ferramenteiro que recebe 6 00 por hora e que leva em m dia 5 minutos para atender a cada pedido estimado que cada mec nico produz 10 00 de servi os por hora cada hora que o mec nico gasta na ferramentaria custa a oficina 10 00 A oficina est analisando a possibilidade de contratar um ajudante de ferramenteiro a 4 00 por hora Se este ajudante for contratado o ferramenteiro ter possibilidade de atender a uma requisi o em 4 minutos em m dia Assuma que os tempos entre chegadas e de servi o s o exponenciais Deve o ajudante ser contratado 11 Modele usando teoria de filas um sistema em que o servi o tomar sol na praia Considere que as chegadas a praia seguem um processo Poisson de taxa 4 e que o tempo que cada pessoa passa na praia aleat rio podendo ser aproximado por uma distribui o exponencial com m dia 1 4 a Desenhe o diagrama de transi o de estados b Obtenha as equa es de recorr ncia n m S X A c Calcule Pn sugest o 2 e n 0 HI d Obtenha L Lq W Wq 12 An lises anteriores indicam que a chegada de clientes em uma dada ag ncia dos correios segue uma distribui o exp
192. servi os id nticos ou seja um servi o de Erlang pode ser decomposto em k subservi os Subservi os Exponenciais Figura 2 6 Servidor Erlang 2 3 1 SISTEMA MIE S No sistema M M S os estados correspondem ao n mero de clientes no sistema No caso de um sistema MIEVS os estados correspondem ao n mero de subservi os a ser executado e cada cliente traz k subservi os Atrav s da Figura 2 7 Diagrama de estados da fila M Ek 1 pode se verificar o que foi dito anteriormente em filas com servidor Erlang um novo cliente s entra no sistema ap s o cliente que est sendo atendido ter passado por todos os k est gios de servi o E EE QD AD EM Figura 2 7 Diagrama de estados da fila M E 1 Processos Estoc sticos e Teoria de Filas 61 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP O n mero m dio de clientes na fila para este tipo de sistema dado por ol k oi L E Dk p e o n mero m dio de clientes no sistema L AW A tempo m dio de um cliente na fila dada por L feet W ES o E 1 e o tempo m dio de um cliente no sistema W W u SE O fator de utiliza o do sistema dado por p u oi Verifica se mais uma vez que se k 1 L p que o resultado do sistema p oi MIMI Enquanto que se k L a el que o resultado do sistema determin stico p MIDI 23 2 SISTEMA E M 1 Neste tipo de
193. servidores e os trabalhos a efetuar formam uma fila nica com uma disciplina FCFS para avaliar qual se for o caso das alternativas prefer vel de forma a manter a fila de tarefas a realizar no m nimo 58 Um posto de servi o est analisando duas formas de processamento de pedidos de clientes Op o 1 Tr s atendentes em paralelo atendendo a uma nica fila Cada atendente preenche completamente todos os formul rios na presen a do solicitante O tempo de processamento exponencial com m dia de 15 minutos Op o 2 Cada solicitante primeiramente preenche um formul rio sem a ajuda do atendente O tempo para este preenchimento exponencialmente distribu do com m dia de 65 minutos Quando o solicitante completa o preenchimento ele se dirige a uma fila nica onde aguardar que um dos tr s atendentes confira o formul rio Isto demora em m dia 4 minutos exponencialmente distribu do Os tempos entre chegadas s o exponencialmente distribu dos e em m dia 4 8 clientes chegam a cada hora Qual das op es permitir que o solicitante saia mais rapidamente do posto de servi o 59 A Sapataria Caroline funciona com um nico empregado A sapataria recebe normalmente pares de sapatos para serem reparados em uma base primeiro a chegar o primeiro a ser atendido que chegam segundo um processo Poisson com uma taxa m dia de 1 par por hora O tempo para reparar cada p de sapato individualmente tem uma distribui o exponenci
194. sistema n mero de clientes no sistema ser grandemente afetado pelo estado inicial e pelo tempo decorrido desde ent o O sistema dito ent o estar em condi o transiente Entretanto depois de j ter passado tempo suficiente o estado do sistema se torna essencialmente independente do estado inicial e do tempo decorrido exceto sob circunst ncias pouco usuais O sistema ent o alcan ou essencialmente uma condi o de estado de equil brio A nota o mostrada na Tabela 2 2 sup e que o sistema esteja numa condi o de estado de equil brio Tabela 2 2 Nota o utilizada no estado de equil brio N N mero de clientes no sistema de fila P Probabilidade de que exatamente n clientes estejam no sistema no sistema de fila L N mero de clientes esperado no sistema de fila Ly Comprimento de fila esperado om Tempo de espera no sistema inclui tempo de servi o para cada cliente em particular W E o q Tempo de espera na fila exclui o tempo de servi o para cada cliente em particular Wa E ed 2 1 5 RESULTADO DE LITTLE As rela es entre as medidas de desempenho do sistema s o conhecidas como f rmulas de Little Estas rela es relacionam o n mero m dio de usu rios L ou L com o tempo m dio de espera W ou Wa e tiveram a sua primeira demonstra o formal no trabalho de Little 1961 Desde ent o provas alternativas e extens es t m sido apresentadas e sua validade extrapolou os modelos
195. sistema as distribui es do tempo entre chegadas e de servi o s o invertidas em rela o se o 2 3 1 SISTEMA MIEKJ S O sistema E M S opera da seguinte maneira dado que um cliente acabou de chegar no sistema ent o uma nova chegada de cliente imediatamente introduzida Quando esta chegada inserida ela deve passar atrav s de k est gios exponenciais cada um com par metro ki como mostra a Figura 2 8 Sistema EkIM 1 gt GDO Gr imp Figura 2 8 Sistema EVIMI Para este tipo de sistema o diagrama de estados est mostrado na Figura 2 9 Diagrama de estados para o sistema Ek M 1 Processos Estoc sticos e Teoria de Filas 62 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP SST ESTO EX CESTO O a a a H H Figura 2 9 Diagrama de estados para o sistema E M 1 2 4 REDES DE FILAS MARKOVIANAS Uma rede de filas ou sistema de m ltiplos n s formada por v rias filas interconectadas entre si com usu rios deslocando se entre elas para receber servi o A rede pode ser aberta ou fechada dependendo de poder enviar e receber usu rios de fora da rede Isto em uma rede fechada o n mero total de usu rios n o se altera havendo apenas uma permuta o nas suas posi es J nas redes abertas a presen a total varia pela chegada ou sa da externa de usu rios Algumas considera es devem ser feitas no estudo de rede de filas Por exemplo a est
196. so c Suponha ainda que cada consumidor fa a uma compra de cerveja por semana 1 ano 52 semanas e que existam 100 milh es de consumidores de cerveja Uma unidade de cerveja vendida por 2 e custa cervejaria 1 Por 500 milh es por ano uma firma de propaganda garante diminuir de 10 para 5 a fra o dos clientes de Mharba que mudam para rtica depois de uma compra Deve a cervejaria Mharba contratar a empresa de propaganda Processos Estoc sticos e Teoria de Filas 111 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP a 0 1 M A o AE P M 0 9 071 Ton spa 0 2 01 7 0 2 7 z 1 3 gt Ty L l Ty 2 3 Dado que uma pessoa acabou de comprar Mharba o tempo necess rio para realizar e outra compra de Mharba tempo m dio de 1 retorno mym e uma compra de tica tempo m dio de 12 passagem Mma 1 3 Mmm 1 5 Ty 2 Mma 1 Pumm Mma gt mma 1 0 9 mma gt mma 10 O tempo interpretado como o n mero de compras de cerveja realizadas c Quantidade de cerveja comprada por ano N 52 100 milh es 5 2 bilh es e Sem contratar a empresa de propaganda Quantidade de Mharba comprada por ano Ny N my 3 47 bilh es Lucro obtido Lu Ny 2 1 3 47 bilh es e Contratando a empresa de propaganda A matriz de probabilidades de transi o se altera para M A P MI 0 95 0 05 0 05 zy 0 2 7 e z 1 5 A 02
197. temas de servi o social Por exemplo um sistema judicial uma rede de filas onde os tribunais s o instala es de servi os os ju zes ou pain is de ju zes s o os servidores e os casos esperando para serem julgados s o os clientes Um Processos Estoc sticos e Teoria de Filas 45 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP sistema legislativo uma rede de filas similar onde os clientes agora s o os projetos de lei esperando para serem processados Embora essas sejam quatro grandes classes dos sistemas de filas elas ainda n o esgotam a lista De fato a teoria das filas teve inicio no principio deste s culo com aplica es na engenharia telef nica e ainda permanece como uma importante rea de aplica o Al m disso todos n s temos as nossas filas pessoais trabalhos de casa livros para ler e assim por diante 2 1 7 A DISTRIBUI O EXPONENCIAL NA TEORIA DE FILAS As caracter sticas de opera o dos sistemas de filas s o grandemente determinadas por duas propriedades estat sticas isto a distribui o de probabilidade dos tempos entre chegadas e a distribui o de probabilidades dos tempos de servi o Para sistemas de filas reais estas distribui es podem assumir praticamente qualquer forma a nica restri o que n o podem ocorrer valores negativos Entretanto para a formula o de um modelo de teoria de filas como uma representa o
198. ticamente fa amos com que T4 T2 Tn sejam vari veis aleat rias independentes exponenciais com par metros oi a On respectivamente Fa amos tamb m com que U seja a vari vel aleat ria que assuma o valor igual ao m nimo dos valores realmente assumidos por T4 T2 Th isto U min T4 To Th Processos Estoc sticos e Teoria de Filas 48 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Portanto se T representar o tempo at que um tipo particular de incidente ocorra ent o U representar o tempo at que o primeiro dos n incidentes diferentes ocorra Note se agora que para qualquer t gt 0 P U gt t P T gt t T2 gt t Tas HU HIT gt t P T2 gt t P Th gt t e alt e a2t e ant exp E Sos i l de modo que U de fato tem uma distribui o exponencial com par metro n e Ze i 1 Esta propriedade tem algumas implica es para os tempos entre chegadas nos modelos de filas Especificamente vamos supor que existam diversos n tipos diferentes de clientes por m os tempos entre chegadas para cada tipo tipo i tenham uma distribui o exponencial com par metro a i 1 2 n Pela propriedade 2 o tempo restante a qualquer instante especifico at cnegada seguinte de um cliente do tipo i teria esta mesma distribui o Portanto fazendo com que T seja este tempo restante medido a partir do instante em que u
199. to do processo no futuro conhecendo o comportamento no passado Quando t cont nuo obter essa distribui o conjunta imposs vel j que o conjunto t n o enumer vel Sob essas circunst ncias v lido assumir que o comportamento do processo pode ser obtido estudando o em um conjunto discreto de pontos assim a distribui o conjunta definida nesse conjunto de pontos apropriada Seja t1 t2 tn com t1 lt t2 lt lt tn um conjunto discreto de pontos de T A distribui o conjunta do processo X t nesses pontos pode ser definida como segue PIX Sx SX X lt Sx OU A probabilidade do processo estoc stico estar no tempo t no estado a chamada probabilidade de estado P e definida por P PiX a 2 Ovetorp p Pp pP chamado vetor de probabilidade de estado A probabilidade do processo estoc stico com tempo e estado discretos estar no m n estado j dado que estava no estado i chamada probabilidade de transi o P P ij PIX jIX im lt n 3 Processos Estoc sticos e Teoria de Filas 5 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Para o caso cont nuo a probabilidade condicional de transi o e a probabilidade de estado s o definidas respectivamente como segue Flo Xto t PIX Sxl Xt x 4 F x t PIX lt x 5 A matriz que armazena todas as probabilidades de transi o pom cham
200. tras palavras ele tem 1 3 de probabilidade de ganhar e 2 3 de perder Se ganhar ganhar 2 Se perder perder 1 Suponha que os recursos totais do jogador e do seu oponente sejam N Se o capital de qualquer um dos jogadores cair abaixo do ponto em que eles pudessem pagar caso perdessem o jogo seguinte o jogo termina a Desenhe o diagrama de transi o de estados e determine a matriz de transi o b Suponha que os dois jogadores concordem em que se o capital de qualquer dos dois cair para 1 eles far o o pr ximo jogo com chances iguais ganhar o ou perder o 1 com igual probabilidade Desenhe o diagrama de transi o de estados e determine a matriz de transi o para este caso c No caso descrito na letra b suponha que o jogador 1 tem 3 e o jogador 2 tem 2 qual a probabilidade do jogador 1 ganhar o jogo d Quantas jogadas durar o jogo 15 Considere o jogo de dados que segue O jogador lan a um dado de seis faces Se o resultado for 5 ou 6 no primeiro lan amento ele ganha imediatamente Se o resultado for 1 perde imediatamente Em qualquer outro caso o jogador continua a lan ar o dado at obter 5 ou 6 quando perde ou at obter o mesmo resultado do primeiro lan amento quando ganha O dado n o equilibrado e as probabilidades dos resultados 1 2 3 4 5 e 6 s o respectivamente 10 15 20 20 E 20 a Defina um processo estoc stico que represente o problema esboce o diagrama de transi es escre
201. u A E R 2 04 06 com 3 ax 60 3 0 6 04 Ai 0 8 0 2 d d3 dura o m dia do jogo regime transiente dado estado inicial 3 d j e3j 0 8 1 2 1 2 0 4 3 6 jogadas Processos Estoc sticos e Teoria de Filas 135 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP 24 Perfura se um po o e medida que a perfura o avan a uma s rie de perfis s o realizados Suponha que o po o possa ser classificado em quatro estados rotulados como se segue Em curso Com desvio ligeiro Com desvio acentuado Abandonado por estar t o fora de curso que n o se consegue mais atingir o alvo Suponha ainda que X represente o estado do sistema ap s a n sima corre o de curso e que o comportamento do po o possa ser modelado por uma cadeia de Markov com a seguinte matriz de probabilidade de transi o 1 0 0 0 P 1 2 1 4 1 4 0 0 1 2 1 4 1 4 0 0 0 1 a Se o po o come ou com um desvio ligeiro qual a probabilidade de que ele eventualmente entre em curso b Se o po o tem chances iguais de come ar com desvio ligeiro e acentuado qual a probabilidade de que ele eventualmente entre em curso D L D A EC Ab DL 14 14 12 0 192 pi P DA 12 14 0 1 4 1 4 c Qual o n mero m dio de perfis se poder obter deste po o D L D A E C Ab E l Q D L 1 7143 0 5714 A ER D L 0 857 0 143 D A 1 1428 1 7143 D A 0 571 0 429
202. u com 0 zero meses de atraso A valores a serem recebidos que est o com 1 m s de atraso A valores a serem recebidos que est o com n meses de atraso Essa disposi o corresponde a uma classifica o da idade das contas a receber sendo o estado Ao a conta que est em dia A a conta com um m s de atraso e assim por diante An a situa o dos considerados incobr veis Na pr tica o n mero de idades das contas pode variar de institui o para institui o ou por categorias de cr dito tais como cr dito imobili rio leasing financiamentos diretos ao consumidor e qualquer outro tipo de opera o de cr dito Se considerarmos um levantamento de contas a receber provenientes do per odo i para o per odo seguinte i 1 que denominaremos de j a conta poder ser classificada com rela o a esses dois ndices o per odo anterior e o per odo em que se encontra no momento atual De forma geral teremos Ajk igual ao levantamento da categoria k no tempo i 1 o qual proveniente da categoria j no tempo i Para considerarmos todas as poss veis categorias devemos acrescentar mais uma categoria quelas descritas anteriormente Trata se da categoria correspondente aos t tulos classificados como pagos que ser o descritos Processos Estoc sticos e Teoria de Filas 37 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP como Pag Valores classificados em qualquer categoria
203. ualidade m dia paga por um cliente da Se segura 20 DOFOGO uma companhia produtora de fog es famosos pela sua qualidade A companhia tem uma pol tica de 2 anos de garantia onde ela garante a substitui o de qualquer fog o que falhe durante este per odo A companhia est planejando fazer uma campanha promocional onde pretende estender a garantia para tr s anos Como forma de avaliar o impacto desta nova pol tica foram coletados os seguintes dados 3 dos fog es novos falham durante o primeiro ano de opera o 5 dos fog es com mais de um ano de uso falham durante o segundo ano de opera o 7 dos fog es com mais de dois anos de uso falham durante o terceiro ano de opera o Observe que um fog o substitu do n o coberto pela garantia a Use cadeias de Markov para predizer quantos fog es dever o ser repostos com a nova pol tica b Supondo que o custo de repor um fog o seja de 100 e que a DOFOGO venda 10 000 fog es por ano qual o impacto monet rio da mudan a de pol tica de garantia 21 O propriet rio de uma barbearia de uma s cadeira est pensando em expandi la devido ao fato de haver muita gente em espera As observa es indicam que durante o per odo de tempo requerido para cortar o cabelo de uma pessoa podem haver 0 1 2 e 3 novas chegadas com probabilidade 0 3 0 4 0 2 0 1 respectivamente A cada tem capacidade fixa de 6 pessoas incluindo aquela que estiver cortando o cabelo a Desenhe o diagr
204. ue definida pela dedica o a todos os usu rios presentes no sistema de uma pequena quantidade de servi o de cada vez Assim em rodadas sucessivas o usu rio vai recebendo sua dose de atendimento at que sua requisi o total de Processos Estoc sticos e Teoria de Filas 41 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP servi o seja completada A disciplina de atendimento pode ainda estabelecer prioridades entre usu rios de modo a atender primeiro os de alta prioridade Em alguns modelos o servi o pode at ser interrompido para dar lugar a um usu rio de prioridade mais alta Quando modelos com prioridade s o adotados necess rio especificar como se dar a ordem de atendimento dentro da mesma classe de prioridade e em geral FCFS utilizada nestes casos d Capacidade do Sistema muito comum haver uma limita o f sica no numero de usu rios que podem esperar Se a capacidade total estiver ocupada o usu rio n o poder entrar no sistema e ser perdido ou desviado para outro centro de servi o Essa limita o se relaciona com a chegada mas a decis o de n o se juntar fila n o do usu rio e sim do sistema de servi o Uma fila caracterizada pelo m ximo n mero permiss vel de clientes que ela possa conter As filas s o cnamadas de infinitas ou finitas de acordo com esse n mero ser infinito ou finito A suposi o de uma fila infinita o padr o
205. ue dentre outras tarefas ir o fazer as c pias de 15 A copiadora lenta alugada por 4 hora e toma em m dia 10 minutos do funcion rio para efetuar as c pias exponencialmente distribu dos A copiadora r pida custa 15 hora e ocupa o funcion rio por 6 minutos em m dia tamb m exponencialmente distribu dos Uma m dia de 4 funcion rios por hora necessitam usar a copiadora tempos entre chegadas exponencialmente distribu dos Qual copiadora deve o programa alugar 56 Sandu ches Bitoca est querendo determinar quantos atendentes deve disponibilizar durante o hor rio do almo o Durante este per odo uma m dia de 100 clientes por hora chega ao restaurante Cada atendente pode servir uma m dia de 50 clientes por hora Um atendente custa 5 hora e o custo de um cliente esperando pode ser avaliado em 20 hora Assumindo que um modelo M M S aplic vel qual o n mero de atendentes minimiza a soma dos custos de atendente e de atrasos 57 Um empreiteiro est definindo sua equipe de trabalho Ele tem alocado dinheiro suficiente para contratar ou dois pedreiros Tipo A ou tr s pedreiros Tipo B A classifica o e o pagamento dos pedreiros feita de acordo com sua efici ncia no trabalho Um mesmo trabalho realizado por um pedreiro Tipo AT em 2 3 do tempo gasto por um pedreiro Tipo B Assim em uma primeira impress o as duas alternativas parecem iguais Desenvolva um modelo de filas Markovianas onde os pedreiros s o os
206. va a matriz das probabilidades de transi o e classifique o processo e os seus estados b Calcule a probabilidade do jogador ao final ganhar o jogo c Quantas vezes em m dia o dado ser lan ado at o jogo terminar 16 Um curso comp e se de tr s fases Em cada uma delas o aluno pode ser reprovado definitivamente no curso com probabilidade igual a 6 obrigado a repetir a fase com probabilidade igual a 30 ou passar para a fase seguinte Na terceira fase passar para a fase seguinte representa a aprova o final no curso Cada fase dura um m s Qual a probabilidade de um aluno que passou para a segunda fase concluir o curso com aprova o 83 6 a Quanto tempo em m dia um aluno fica no curso 3 9 meses b Qual a propor o de alunos matriculados no in cio do curso que s o reprovados 23 6 17 Um centro de tratamento m dico de forma extremamente simplificada pode ser modelado por uma cadeia de Markov de quatro estados conforme demonstra a tabela abaixo T medicamentos T cir rgico Curado Morto T medicamentos 0 3 0 3 0 3 0 1 T cir rgico 0 1 0 1 0 6 0 2 Curado 0 0 1 0 Morto 0 0 0 1 a Para um paciente inicialmente em tratamento medicamentoso calcule as probabilidades dele ficar curado e de vir a falecer Repita para o caso do paciente que inicialmente recebeu o tratamento cir rgico c Um paciente possui as seguintes utilidades subjetivas em fun o de seu sofr
207. vidos Entretanto poss vel desenvolver um m todo para estimar a probabilidade de devedores duvidosos com base nas Cadeias de Markov atrav s do atraso e da inadimpl ncia existente para uma determinada carteira de cr dito de uma institui o financeira Se em uma determinada data fizermos um levantamento de uma carteira de cr dito poderemos facilmente verificar os seguintes estados das contas em carteira A valores a serem recebidos que ainda n o venceram ou seja est o em dia ou com 0 zero meses de atraso A valores a serem recebidos que est o com 1 m s de atraso A valores a serem recebidos que est o com n meses de atraso Essa disposi o corresponde a uma classifica o da idade das contas a receber sendo o estado A a conta que est em dia A a conta com um m s de atraso e assim por diante A a situa o dos considerados incobr veis Na pr tica o n mero de idades das contas pode variar de institui o para institui o ou por categorias de cr dito tais como cr dito imobili rio leasing financiamentos diretos ao consumidor e qualquer outro tipo de opera o de cr dito Se considerarmos um levantamento de contas a receber provenientes do per odo i para o per odo seguinte i 1 que denominaremos de j a conta poder ser classificada com rela o a esses dois ndices o per odo anterior e o per odo em que se encontra no momento atual De forma geral teremos A igual ao levantamento da cate
208. xa m dia de servi o por unidade de tempo ui maior do que a taxa m dia com que os fregueses est o chegando A Portanto independente do quanto crescer a fila se esvaziar de tempos em tempos e o processo de Markov ser recorrente positivo com uma nica distribui o de equil brio Efetuando a soma da s rie acima obtemos Po 1 p e ent o Pa p 1 p n gt 0 0 lt p lt 1 Processos Estoc sticos e Teoria de Filas 54 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP A partir da distribui o estacion ria vamos calcular o n mero m dio de usu rios na fila e no sistema Seja N o n mero total de usu rios no sistema em regime estacion rio e L sua m dia Temos L E N Zap X nli p 1 05 np n 0 n 0 Este ltimo somat rio pode ser reescrito como Ka Snp p 2p 3p pl 2p 95 np n 0 n 1 A derivada de o em rela o a p dada por ao Assim admitindo satisfeitas as condi es para inverter os sinais de somat rio e derivada obtemos Seja N4 o n mero de usu rios na fila e Ly seu valor esperado Temos L E N 08 5 n 1 P Sab Y P n 1 n 1 n 1 Outras f rmulas para o modelo M M 1 Tempo m dio esperado que cada unidade permanece no sistema Processos Estoc sticos e Teoria de Filas 55 COPPE Universidade Federal do Rio de Janeiro Programa de Engenharia de Produ o PEP Tempo m dio esperad
209. xas independentes do estado do sistema Para n gt 0 a transi o do estado n a n 1 se d com taxa e entre n e n 1 com taxa u Quando n 0 s pode haver chegadas Dessa forma chegadas correspondem a nascimentos e o fim de servi o a uma morte A Figura 2 3 apresenta um diagrama com taxas de mudan a de processo An Au Aa Ani An Ant GDL E lt Li Hz u Un Un 1 u Figura 2 3 Taxas de transi o no processo de Markov A condi o b sica para que um sistema de fila seja est vel que a taxa de chegada seja menor do que a taxa de servi o ou seja u tem que ser menor do que 1 Essa fra o o fator de utiliza o da fila e ser denotado por p para facilitar a visualiza o das f rmulas Seja Pn t P N t n a distribui o de probabilidade do n mero no sistema no instante t sua respectiva distribui o estacion ria ser Pn Vamos escrever as equa es de equil brio do sistema usando o procedimento conhecido como balan o de fluxo e a partir delas obter a distribui o estacion ria Definimos o fluxo como o produto da probabilidade estacion ria pela taxa de transi o Vamos admitir que em regime estacion rio o sistema permanece uma fra o do tempo Pn no estado n Dessa forma se chegam usu rios por unidade de tempo a taxa de fluxo m dio que entra em n 1 proveniente do estado n APn Se condi es de equil brio existem ent o para cada estado o fluxo que sai deve s
210. xas normais Os tempos m dios de atendimento em cada um destes tipos de caixa s o de respectivamente 15 min 5 min e 10 min Al m destas caixas existem ainda 5 postos de recebimento com cart es de cr dito cujo tempo m dio de atendimento de 2 min Sabe se que dos 60 clientes que se destinam aos caixas por hora 10 se destinam aos caixas que emitem notas 30 se destinam aos caixas r pidos e os 60 restantes se destinam aos caixas normais Sabe se ainda que 60 dos clientes deste supermercado efetuam seus pagamentos com cart o de cr dito Observa o Os cliente que pagam com cheque ou dinheiro dirigem se a um dos caixas e ap s serem atendidos se retiram do estabelecimento Os clientes que pagam com cart o de cr dito dirigem se a um dos caixas e ap s o registro de suas compras dirigem se a um dos postos de recebimento com cart o para assinarem o recibo de d bito ap s o que retiram se a Represente esquematicamente o modelo de filas correspondente ao problema b Qual o valor esperado do tempo que um cliente demora para pagar suas compras desde o instante que ele se destina ao caixa at o instante que ele sai do supermercado c O que aconteceria ao tempo obtido no item b se o n mero de clientes que chegam ao supermercado por hora dobrasse Por que d Na sa da dos caixas para os postos de recebimento de cart o necess rio supor que 2 clientes n o saem simultaneamente por que 32 O transporte de passageiros de M

PROCESSOS ESTOCÁSTICOS E TEORIA DE FILAS

Contents

Download Pdf Manuals

Related Search

Related Contents

PROCESSOS ESTOC&Aacute;STICOS E TEORIA DE FILAS

Contents

Download Pdf Manuals

Related Search

Related Contents

PROCESSOS ESTOCÁSTICOS E TEORIA DE FILAS