• Author / Uploaded
• Caroline Oliveira

Citation preview

UNIVERSIDADE SÃO FRANCISCO

DISCIPLINA

PESQUISA OPERACIONAIOL Parte II

Adalberto Nobiato Crespo

2015

Versão 4.0

1

Sumário PROCESSOS ESTOCÁSTICOS ......................................................................................................... 3 1 – Processos Estocásticos ................................................................................................................... 3 1.1 – Classificação de Processos Estocásticos ................................................................................. 3 Questões para Estudo ........................................................................................................................... 4 2 – Processos Markovianos .................................................................................................................. 5 3 – Conceitos Fundamentais .............................................................................................................. 11 3.1 – Cadeias de Markov................................................................................................................ 11 3.2 – Probabilidade de Transição ................................................................................................... 12 3.3 – Probabilidade de Transição de Passo 1 ................................................................................. 12 3.4 – Probabilidade de Transição de Passo n ................................................................................. 12 3.5 – Distribuição Inicial de Probabilidades .................................................................................. 14 3.6 – Distribuição de Probabilidades após “n” Passos ................................................................... 16 3.7 – Classificação dos Estados de Uma Cadeia de Markov ......................................................... 20 3.8 – Classificação de Matrizes Estocásticas ................................................................................. 26 Primeira Lista de Exercícios - Cadeias de Markov ......................................................................... 28 4 – Aspectos Fundamentais sobre Filas ............................................................................................. 34 4.1 – Conceito de Fila .................................................................................................................... 34 4.2 – Dimensionamento de Filas .................................................................................................... 35 4.3 – Aspectos Históricos............................................................................................................... 36 5 – Fundamentos Básicos de Filas ..................................................................................................... 37 5.1 - Elementos de Uma Fila .......................................................................................................... 37 5.2 – Características de Uma Fila .................................................................................................. 38 5.3 – Distribuição do Tempo de Atendimento ............................................................................... 41 5.4 – Dinâmica de uma Fila ........................................................................................................... 42 5.5 – Conceitos Básicos de Fila .................................................................................................... 47 5.5.1 – Variáveis Aleatórias Fundamentais ....................................................................................... 48 5.5.2 - Postulados Básicos.................................................................................................................. 53 Segunda Lista de Exercícios ............................................................................................................ 54 6 – O Sistema de uma Fila e um Atendente ....................................................................................... 55 6.1 – Equações do Modelo ................................................................................................................. 55 Terceira Lista de Exercícios ............................................................................................................ 57 Quarta Lista de Exercícios .............................................................................................................. 59

2

PROCESSOS ESTOCÁSTICOS 1 – Processos Estocásticos Um Processo Estocástico é definido como uma coleção de variáveis aleatórias Xt indexadas por um parâmetro t pertencente a um conjunto T. Normalmente, T é um conjunto de números inteiros não negativos e Xt representa uma característica qualquer mensurável de interesse e que varia com o tempo t. Exemplo 1: Xt: Nível de estoque de um produto no fim de cada semana t. t = 1, 2, 3... X1 = 20 – significa que na semana 1 o estoque era de 20 unidades. X2 = 13 – significa que na semana 2 o estoque era de 13 unidades. X5 = 28 – significa que na semana 5 o estoque era de 20 unidades. Processos Estocásticos são de interesse para descrever o procedimento de um sistema operando em algum período de tempo. Com isso, a variável aleatória Xt representa o estado do sistema no parâmetro t. O parâmetro t representa o estado e o valor da variável Xt representa o comportamento do sistema no estado t. Por exemplo, é interessante para uma empresa observar o comportamento do estoque de um determinado produto, durante 6 meses. Esta observação serve para a programação dos estoques nos próximos períodos. Portanto, a variável Xt é definida em um conjunto de estados denominado Espaço de Estados. 1.1 – Classificação de Processos Estocásticos Os Processos Estocásticos podem ser classificados como: a) Em relação ao Estado  Estado Discreto: Xt é definida sobre um conjunto enumerável finito.  Estado Contínuo: Xt caso contrário b) Em relação ao Tempo t (parâmetro)  Tempo Discreto: t é finito e enumerável  Tempo Contínuo: t caso contrário

3

Exemplos: 1 – Número de usuários em uma fila de banco em um determinado instante t. Estado discreto e Tempo contínuo 2 – Índice pluviométrico diário. Estado contínuo e Tempo discreto 3 – Número de dias chuvosos. Estado Discreto e Tempo discreto Questões para Estudo 1 – Suponha que Xt representa o nível de estoque de um produto e t representa a semana de observação do estoque. Qual é a probabilidade do estoque ser zero no final desta semana, dado que na semana anterior o estoque era de 10 unidades? Matematicamente temos a equação: PX atual  0 | X anterior  10  ? Fazendo: semana atual =1 semana anterior = 0 Então teremos a seguinte equação: PX 1  0 | X 0  10  ? Pode se também estar interessado na seguinte questão: PX 10  0 | X 9  11, X 8  12, X 7  15... X 1  6, X 0  3  ?

Onde: 10=semana atual; 9 = semana anterior; e assim por diante. O valor desta probabilidade serve para tomada de decisões sobre o estoque do produto em questão. 2 – Suponha que Xt representa o comportamento do tempo numa cidade de praia durante o verão. Qual é a probabilidade do tempo estar com sol nesta semana, dado que na semana anterior o tempo esteve com chuva. Matematicamente temos a equação: PX atual  sol | X anterior  chuva  ? Fazendo: semana atual =1 semana anterior = 0 Então teremos a seguinte equação: PX 1  sol | X 0  chuva  ? Pode se também estar interessado na seguinte questão: PX 4  sol | X 3  chuva, X 2  chuva, X 1  sol  ?

Onde: 4 = semana atual; 3 = semana anterior; e assim por diante. O valor desta probabilidade serve para tomada de decisões sobre os eventos que poderão ser promovidos na cidade de praia, no período em questão.

4

Existem vários "tipos" de Processos Estocásticos, porém neste curso será abordado apenas um tipo de Processo Estocástico denominado Processo Markoviano. 2 – Processos Markovianos Um Processo Estocástico é dito ser um Processo Markoviano se: PX k 1  yk 1 | X k  yk , X k 1  yk 1 , X k 2  yk 2 ... X 1  y1 , X 0  y0   PX k 1  yk 1 | X k  yk 

Onde k = 0, 1, 2, 3 ... Essa expressão pode ser traduzida como: a probabilidade condicional de qualquer evento futuro, dado qualquer evento passado e o estado presente Xk = yk, é independente do evento passado e depende somente do estado presente. Em termos mais resumidos: Um processo Estocástico é dito ser um Processo Markoviano se o estado futuro depende apenas do estado presente e não depende dos estados passados. Este tipo de Processo Estocástico é também denominado de processo sem Memória, uma vez que o passado é desprezado. As probabilidades condicionais PX k 1  yk 1 | X k  yk são denominadas Probabilidades de Transição e representam a probabilidade do estado Xk+1 ser yk+1 no instante k+1 dado que no instante k o estado Xk é yk. Exemplo 2: No ano de 1993, o estado do uso da terra em uma cidade de 50 quilômetros quadrados de área éra: Tabela 1 – Estado do uso da Terra em 1993 I

Uso Residencial

30%

II

Uso Comercial

20%

III

Uso Industrial

50%

Os valores da tabela 1 podem ser dispostos em um vetor T, denominado Vetor de Estados: T = [ I II III ]. As probabilidades de cada Estado podem também serem dispostas em um vetor , denominado Vetor de Probabilidades de Estado:  = [0,30 0,20 0,50]. Supondo que as probabilidades de transição para intervalos de 5 anos são dadas pela Tabela 2:

5

Tabela 2 – Probabilidades de Transição em 5 anos Para I

Para II

Para III

de I

0,8

0,1

0,1

de II

0,1

0,7

0,2

de III

0

0,1

0,9

As probabilidades condicionais na Tabela 2 podem ser interpretadas como: de I para I: a probabilidade da cidade estar no estado I após 5 anos, dado que atualmente está no estado I é 0,8, ou seja PX t 5  I | X t  I   0,8 . Para t = 1993, tem-se: PX (1998)  I | X (1993)  I   0,8 de I para II: a probabilidade da cidade estar no estado II após 5 anos, dado que atualmente está no estado I é 0,1, ou seja PX t 5  II | X t  I   0,1 . Para t = 1993, tem-se: PX (1998)  II | X (1993)  I   0,1 de I para III: a probabilidade da cidade estar no estado III após 5 anos, dado que atualmente está no estado I é 0,1, ou seja PX t 5  III | X t  I   0,1 . Para t = 1993, tem-se: PX (1998)  III | X (1993)  I   0,1 O mesmo raciocínio para os demais estados. Os valores da Tabela 2 podem ser dispostos numa matriz denominada Matriz de Transição. I 0,8 0,1 0,1 P  II  0,1 0,7 0,2 III  0 0,1 0,9

Assim, a partir da matriz de transição P e do vetor de probabilidade de estado  para 1993, denominado (0), pode-se calcular o vetor de probabilidades de estado  para o ano de 1998 da seguinte forma, denominado (1). 0,8 0,1 0,1 π1  π 0 P  [0,30 0,20 0,50]0,1 0,7 0,2  [0,26 0,22 0,52]  0 0,1 0,9

6

Este resultado pode ser interpretado como: Em 1998, o estado de uso da terra na cidade será dado pela Tabela 3: Tabela 3 – Estado do uso da Terra em 1998 I

Uso Residencial

26%

II

Uso Comercial

22%

III

Uso Industrial

52%

Exemplo 3: Um cliente pode adquirir uma das seguintes marcas de carro: Fiat, Ford e Chevrolet. A próxima compra do cliente é controlada pela marca do carro que ele possui atualmente. Toda vez que um novo carro é comprado, ocorre um passo no processo de compra. Neste processo há, portanto, apenas 3 Estados possíveis (m=3): a compra de um Ford, a compra de um chevrolet e a compra de um Fiat. Isto pode ser representado como: Estados do Processo

Descrição

S1

O cliente compra um Ford

S2

O cliente compra um Chevrolet

S3

O cliente compra um Fiat

No presente momento (t = 0), os Estados S1, S2, S3 representam o estado atual do processo, isto é, a marca do carro que o cliente possui atualmente. No passo seguinte, (t = 1) os Estados S1, S2, S3 representam todos os resultados possíveis da próxima compra do cliente. Assim, o Espaço de estado é { S1, S2, S3}. Uma pessoa de mercado revela a seguinte situação: Próxima Compra (t = 1) Marca do Carro Atual (t=0)

% que compra

% que compra

% que compra

Ford

Chevrolet

Fiat

Ford

40

30

30

Chevrolet

20

50

30

Fiat

25

25

50

7

Essa mesma informação pode ser representada numa matriz de probabilidades chamada Matriz de Transição. 0,40 0,30 0,30 P  0,20 0,50 0,30 0,25 0,25 0,50

Cada elemento dessa tabela representa uma probabilidade de se passar de um Estado para outro em um passo. Isto é, representa a probabilidade de compra de uma marca de carro. Ex: 0,20 representa a probabilidade de um cliente comprar um carro Ford dado que atualmente ele possui um carro da marca Chevrolet. Graficamente tem-se a seguinte situação: 0,50

0,40

S2

0,30

S1

Chevrolet

0,20

Ford 0,25

0,25 0,30

Fiat

0,30

S3 0,50

Exemplo 4: A situação de uma máquina poderia ser descrita por um Processo de Markov. Neste caso, o Estado pode descrever a condição da máquina: em funcionamento; esperando reparo; sendo reparada. O espaço de Estado é discreto e pelo menos em alguns casos a probabilidade da situação da máquina na próxima observação depende de sua situação presente. Estados do Processo

Descrição

S1

Máquina funcionando

S2

Máquina ociosa, esperando reparo

S3

Máquina ociosa, sendo reparada

8

Exemplo 5: Um grupo de 4 crianças joga um jogo que consiste em passar uma bola de um lado para outro. Em cada estágio do jogo, a criança que está com a bola tem idêntica chance de passar a bola para qualquer uma das outras 3 crianças. Seja X0 a criança que está com a bola no início do jogo e Xn a criança que está com a bola depois que a mesma foi lançada exatamente n vezes. Este jogo consiste de um Processo de Markov com a seguinte Matriz de Transição:  0 1  P  3 1 3 1  3

1 3 0 1 3 1 3

1 3 1 3 0 1 3

1 3 1  3 1 3  0 

A matriz P chama-se Matriz de Transição ou Matriz de probabilidades. Para que uma criança receba a bola em um dado momento, depende apenas de quem está com a bola naquele momento e não depende das demais crianças. Com esta propriedade este jogo constitui-se numa cadeia de Markov. O conjunto S = { 1, 2, 3, 4} chama-se espaço de estados. Algebricamente tem-se: Seja k = 1 se a criança está com a bola num dado momento. k = 0 se a criança não está com a bola num dado momento. Logo, PX 1  1 | X 0  0 

1 e ainda 3

PX 1  1 | X 0  1  0

Constitui-se numa Cadeia de Markov porque tem a propriedade que: PX n  y | X n1  y, X n2  k ,... X 0  1  PX n  k | X n1  k 

Isto é, o fato de Xn = k (uma criança estar ou não com bola depois de n lançamentos) depende somente de Xn-1 = k e independe da trajetória percorrida. Isto é, independe de Xn-2, Xn-3, Xn-4, ... X0.

9

Exemplo 6: Jogo da Moeda Um jogador paga R$ 10,00 ao banqueiro para lançar uma moeda e ganha R$ 80,00 quando a diferença entre o número de Caras e Coroas for igual a 3. Qual deve ser a situação do jogador depois de n lançamentos da moeda? Situação: O jogador paga R$10,00 por um lançamento e recebe R$80,00 quando Z = | #Caras - #Coroas | = 3. Onde: #Caras: número de caras e #Coroas: número de Coroas Analisando tem-se: Numero de Lançamentos

Resultados #Caras #Coroas

Z

0

0

0

0

0

1

Ca

1

0

1

2

Ca

2

0

2

3

Co

2

1

1

4

Ca

3

1

2

5

Co

3

2

1

6

Ca

4

2

2

7

Ca

5

2

3

Graficamente, a probabilidade da função Z assumir os valores 0, 1, 2, 3, são: 1

1/2

0

1

1/2 2

1/2

1/2

1 3

1/2

Matricialmente tem-se a seguinte Matriz de Transição: 0 1  P  2 0   0

1 0 1 2 0

0 1 2 0 0

0  0 1  2 1 

10

Logo, tem-se: Seja Zn a variável aleatória que pode assumir os valores 0, 1, 2, 3 no tempo t = n. Espaço de Estados: S = {0, 1, 2, 3} Isto é, antes do início do jogo, tem-se: Tempo t = 0

Tempo t = 1

P[Z0 = 0] = 1;

P[Z1 = 0] = 1/2;

P[Z0 = 1] = 0;

P[Z1 = 1] = 0;

P[Z0 = 2] = 0;

P[Z1 = 2] = 1/2;

P[Z0 = 3] = 0.

P[Z1 = 3] = 0.

Para saber a situação do jogador no tempo t = n, ou seja, depois de n lançamentos, deve-se calcular: Pn = P.P.P.P...P Isto é, multiplica-se a matriz P n vezes. 3 – Conceitos Fundamentais 3.1 – Cadeias de Markov Um Processo Markoviano é dito ser uma Cadeia de Markov quando as variáveis aleatórias Xt estão definidas em um espaço de Estados discreto. De acordo com a forma de representação dos estados e do tempo, os Processos Markovianos podem ser: Estados

Tempo

Classificação

Contínuo

Contínuo

Processo Markoviano em tempo contínuo

Contínuo

Discreto

Processo Markoviano em tempo discreto

Discreto

Contínuo

Cadeia de Markov em tempo contínuo

Discreto

Discreto

Cadeia de Markov em tempo discreto

Desta forma, uma cadeia de Markov é um Processo Markoviano onde o espaço de estados é um conjunto discreto. Quando o tempo t é discreto, a Cadeia de Markov é dita ser uma Cadeia de Markov em Tempo Discreto. Note também que existem cadeias de Makov de tempo contínuo.

11

No caso de tempo discreto, tem-se: PX k 1  yk 1 | X k  yk , X k 1  yk 1 , X k 2  yk 2 ... X 1  y1 , X 0  y0   PX k 1  yk 1 | X k  yk 

Uma maneira simples de visualizar um tipo especifico de cadeia de Markov é através de uma máquina de estados finitos. Se você está no estado “y” no tempo “n”, então a probabilidade de que você se mova para o estado “x” no tempo “n+1”, não depende de “n”, e somente depende do estado atual “y” em que você está. 3.2 – Probabilidade de Transição Numa Cadeia de Markov, chamam-se Probabilidades de Transição a probabilidade do Estado Xk+1 ser yk+1 no tempo k+1 dado que o Estado Xk é yk no tempo k. Isto é: PX k 1  yk 1 | X k  yk . Se para cada xk+1 e xk, tem-se: PX k 1  yk 1 | X k  yk   PX 1  y1 | X 0  y0 . Então, as Probabilidades de Transição são ditas Estacionárias. Se as Probabilidades de Transição são Estacionárias, então isto significa que as Probabilidades de Transição não mudam em relação ao tempo. 3.3 – Probabilidade de Transição de Passo 1 As Probabilidades de Transição são denominadas Probabilidades de Transição de Passo 1 se: PX k 1  yk 1 | X k  yk   PX 1  y1 | X 0  y0 .

3.4 – Probabilidade de Transição de Passo n Se a Probabilidades de Transição de Passo 1 for Estacionário (não muda com o tempo) implica que para cada xk+n e yk e n (n=0,1, 2, ...), tem-se: PX k n  yk n | X k  yk   PX n  yn | X 0  y0 

Essas probabilidades condicionais são chamadas Probabilidades de Transição de Passo n. Notação: Para facilitar a notação será adotada a seguinte alteração: yk+1 = j; ou yk+n = j e yk =i Logo, se tem: pij  PX k 1  j | X k  i

e

pij( n )  PX k  n  j | X k  i 

12

Propriedades: Como os valores pij(n ) são probabilidades, então precisam satisfazer as seguintes propriedades: a) p ij( n )  0 M

b)

p j 0

(n) ij

 (i, j); n = 0, 1, 2,...

 1  i: n = 0, 1, 2, ...

Uma maneira de mostrar todas as Probabilidades de Transição de Passo n é: Estados

0

1

...

M

0

(n) p00

(n) p01

...

p 0( nM)

M

p

(n) 0j

1

(n) 1j

1

j 0

p10( n )

1

p11( n)

...

p1(Mn)

M

p j 0

.

.

.

...

.

M

p M( n )0

pM( n1)

...

(n ) pMM

M

p j 0

(n) Mj

1

Ou através de uma matriz de probabilidades:

P (n)

(n)  p 00  (n) p   10  ...  (n)  p M 0

(n) p 01 p11( n ) ... p M( n1)

... ... ... ...

p 0( nM)   p1(Mn )  ...  (n)  p MM 

A matriz P(n) é denominada Matriz de Transição de Passo n. Quando n = 1 é denominada apenas Matriz de Transição. Exemplo 7: Supõe uma máquina que em um determinado momento pode estar funcionando ou parada. Seja Xn a variável aleatória que denota o estado da máquina no tempo “n” (ou tempo t). Espaço de Estados: S = { parada, funcionando} = {0, 1} O tempo “n” pode representar um dia (por exemplo).

13

Graficamente tem-se: 1-p 0

q

0 p

1

1

1-q

Tempo n

Tempo n+1

Assim tem-se: P[Xn+1 =1 | Xn = 0] = p

e

P[Xn+1 =0 | Xn = 1] = q

e

P[Xn+1 = 1 | Xn = 1] = 1 - q

Consequentemente tem-se: P[Xn+1 =0 | Xn = 0] = 1 - p

A Matriz de Transição de Passo 1 é dada por: 0 1 0 1  p p  P  1 q 1  q 

3.5 – Distribuição Inicial de Probabilidades Seja S um espaço de Estados. Chama-se distribuição inicial ao vetor das probabilidades no início do processo. Isto é, são as probabilidades associadas a cada estado do sistema no início do processo (no tempo t =0). Notação: 0(x) = P[X0 = x] é a probabilidade de o sistema iniciar no Estado x. n(x) = P[Xn = x] é a probabilidade de o sistema estar no Estado x, no tempo n (ou seja, após “n” passos). A distribuição inicial 0(x) = P[X0 = x] é tal que: a) 0(x) ≥ 0  xS. b)

 xS

0

( x)  1

14

Exemplo 8: Se no exemplo 2, 0 = [0,30 0,20 0,50] significa que no ano de 1993 o uso da terra pode estar no estado I, II, ou III, respectivamente com as probabilidades 0,30; 0,20; e 0,50. 0(I) = P[X0 = I] = 0,30  probabilidade da cidade usar a terra para uso residencial. 0(II) = P[X0 = II] = 0,20  probabilidade da cidade usar a terra para uso comercial. 0(III) = P[X0 = III] = 0,50  probabilidade da cidade usar a terra para uso industrial. Exemplo 9: Se no exemplo 3, 0 = [0 0 1], significa que o sistema inicia no Estado S3, ou seja no início o cliente possui um automóvel Fiat. 0(1) = P[X0 = 1] = 0  probabilidade de o cliente ter um carro Ford. 0(2) = P[X0 = 2] = 0  probabilidade de o cliente ter um carro Chevrolet. 0(3) = P[X0 = 3] = 1  probabilidade de o cliente ter um carro Fiat. Exemplo 10: Se no exemplo 4, 0 = [0 1 0], significa que o sistema inicia no Estado S2, ou seja, a maquina está ociosa esperando reparo. 0(1) = P[X0 = 1] = 0  probabilidade de a máquina estar funcionando 0(2) = P[X0 = 2] = 1  probabilidade de a máquina estar ociosa esperando reparo. 0(3) = P[X0 = 3] = 0  probabilidade de a máquina estar ociosa sendo reparada.

Exemplo 11: Se no exemplo 5, 0 = [0 1/3 0 2/3], significa que no inicio do jogo a bola pode estar com a criança no. 2 ou com a criança no. 4, respectivamente com probabilidades 1/3 e 2/3 (no tempo 0). 0(1) = P[X0 = 1] = 0  probabilidade de a criança 1 estar com a bola. 0(2) = P[X0 = 2] = 1/3  probabilidade de a criança 2 estar com a bola. 0(3) = P[X0 = 3] = 0  probabilidade de a criança 3 estar com a bola. 0(4) = P[X0 = 4] = 2/3  probabilidade de a criança 4 estar com a bola.

15

3.6 – Distribuição de Probabilidades após “n” Passos - Distribuição Estacionária Sejam: 0(x) a distribuição inicial de probabilidades de um processo, isto é, no início do processo. n(x) a distribuição de probabilidades do processo após “n” passos. P a Matriz de Transição de Passo 1, ou simplesmente Matriz de transição. Pn = P.P.P....P (multiplicação da matriz P n vezes) Então a distribuição de probabilidades após “n” passos pode ser obtida como: n(x) = 0(x)Pn Isto é:

0(x) = 0(x) 1(x) = 0(x)P 2(x) = 0(x).P.P = 0(x).P2 3(x) = 0(x).P.P.P = 0(x).P3 ... n(x) = 0(x).P.P...P = 0(x).Pn

Exemplo 12: No exemplo 2 da cidade que utiliza a terra tem-se: 0,8 0,1 0,1 P   0,1 0,7 0,2  0 0,1 0,9

Assim, a partir da matriz de transição P e do vetor de probabilidade de estado  para 1993, denominado (0), pode-se calcular o vetor de probabilidades de estado  para o ano de 1998, denominado (1). 0,8 0,1 0,1 π1  π 0 P  [0,30 0,20 0,50]0,1 0,7 0,2  [0,26 0,22 0,52]  0 0,1 0,9

Este resultado pode ser interpretado como: Em 1998, o estado de uso da terra na cidade será dado pela Tabela 3: Tabela 3 – Estado do uso da Terra em 1998 I

Uso Residencial

26%

II

Uso Comercial

22%

III

Uso Industrial

52%

16

Exemplo 13: No exemplo 7 da utilização das maquinas, tem-se: 0 1 0 1  p p  P  1 q 1  q 

Supondo que (0) = [ 0 1], ou seja que a máquina está funcionando, então pode-se calcular a distribuição de probabilidades da máquina no próximo dia como: 1 = 0.P = 0

p  1  p 1  =[q 1  q   q

1-q ]

A distribuição de probabilidades da máquina no segundo dia pode se calculada como: 2 = 0.P2 = 0

(1  p) 2  pq 2 p  p 2  pq 1  = 2 pq  (1  q) 2   2q  pq  q

[2q – pq - q2

pq + (1 - q)2]

Lembrando que: 0: representa o estado “maquina parada” 1: representa o estado “maquina funcionando” Logo: 2(0) = 2q - pq - q2 e a probabilidade da máquina estar parada no segundo dia. 2(1) = pq + (1- q2)

e a probabilidade da máquina estar funcionando no segundo dia.

Observação: Pode ser demonstrado que, num tempo “n” infinitamente grande tem-se:

 ( n ) (0)  lim P[ X n  0]  n

 ( n ) (1)  lim P[ X n  1]  n



Logo:

q

 n    pq

q p  q é a probabilidade da máquina estar parada. p p  q é a probabilidade da máquina estar funcionando.

p   pq

é a distribuição de probabilidades no tempo “n”, ou seja, após n passos.

17

Exemplo 14: Se no exemplo 5, (crianças com a bola) a distribuição inicial for 0 = [0 1/3 0 2/3] e a matriz de transição de probabilidades dada pela matriz P,  0 1  P  3 1 3 1  3

1 3 0 1 3 1 3

1 3 1 3 0 1 3

1 3 1  3 1 3  0 

Então, a distribuição de probabilidades depois de 2 lançamentos da bola (n = 2) será calculada como: 2(x) = 0(x).P.P = 0(x).P2 , Ou seja,



 2 ( x)   0 ( x).P 2  0 

Ou seja,

1 3

0

 6

3 9 2  2  9 3   2 9 2  9

 2 ( x)    27

7 27

2 9 3 9 2 9 2 9

2 9 2 9 3 9 2 9

2 9 2  9   6 2   27 9 3  9

6 27

8  27 

7 27

6 27

8  27 

Exercício de Fixação: O problema do Rato e o Labirinto Um rato é colocado num labirinto conforme a figura abaixo:

1

2

3

4

5

6

7

8

9

O rato se movimenta através dos compartimentos aleatoriamente, isto é, se existem k meios de sair de um compartimento ele escolhe cada um deles com probabilidade 1/k. O rato faz uma mudança de compartimento a cada minuto. Seja X0 a posição inicial do rato e para n ≥ 1, seja Xn o compartimento onde se encontra o rato no n-ésimo minuto (ou após n minutos).

18

Pede-se: a) Descreva o espaço de estados do sistema b) Calcule a matriz de probabilidades de transição para cadeia de Markov {Xn; n = 0, 1, 2, 3,...}. c) Calcule a Matriz P2. d) Supondo que o rato seja colocado inicialmente no box no. 9, ou seja, 0(x) = [0 0 0 0 0 0 0 0 1], calcule (2), isto é a Distribuição de Probabilidade do Passo 2. Solução: a) Espaço de Estados: S = { 1, 2, 3, 4, 5, 6, 7, 8, 9} 1 0 1 0 0 0 0 0 0 0   2 1 / 2 0 1 / 2 0 0 0 0 0 0  3  0 1/ 2 0 0 0 1/ 2 0 0 0    4 0 0 0 0 0 0 1 0 0  b) P  5  0 0 0 0 0 0 0 1 0    6 0 0 1 0 0 0 0 0 0  7 0 0 0 1/ 2 0 0 0 1/ 2 0    8 0 0 0 0 1 / 3 0 1 / 3 0 1 / 3 9  0 0 0 0 0 0 0 1 0  1 1 / 2 2 1 / 4 3 1 / 4  4 0 c) P 2  P.P  5  0  6 0 7 0  8 0 9  0

1/ 2 0 0 3/ 4 0 0 1/ 4 1/ 2 0 0 0 1/ 2 0 0 0 1/ 2 0 0 0 0 0 0 0 1/ 6 0 0 0

0 0 0 0 1/ 3 0 1/ 6 0 1/ 3

0 0 0 0 0 1/ 2 0 0 0

0 0 0  0 0 0  0 0 0   0 1/ 2 0  1/ 3 0 1/ 3   0 0 0  4 / 6 0 1/ 6   0 5/6 0  1/ 3 0 1 / 3 

d) 2 = 0.P2 = [0 0 0 0 1/3 0 1/3 0 1/3]

19

3.7 – Classificação dos Estados de Uma Cadeia de Markov Seja S = {s1, s2, s3, ...} o Espaço de Estados de uma cadeia de Markov. a) Estado Alcançável (Acessível) Seja si e sj dois estado de S. O estado sj é dito ser alcançável a partir do estado si se existe n ≥ 0 tal que p ij( n )  0 . Isto implica que é possível o sistema entrar no estado sj eventualmente quando o sistema começa no estado si. Notação: si  sj Exemplo 15: No exercício do rato e o labirinto tem-se s1  s3 uma vez que p31( 2)  0 . Exemplo 16: Um jogador tem R$ 1,00 e a cada vez que joga ganha R$ 1,00 com probabilidade p > 0 ou perde R$ 1,00 com probabilidade 1 – p. O jogo termina quando o jogador acumula R$ 3,00 ou R$ 0,00. Este jogo é uma Cadeia de Markov cujos estados representam a quantia esperada de dinheiro que o jogador possui a cada vez que joga. O Espaço de estados é S = { 0, 1, 2, 3} e a matriz de transição é dada por: 0 1 0  1 1 p 0 P  2 0 1 p  3 0 0

0 p 0 0

0 0  p  1

Nesta Cadeia de Markov, o estado 2 não é alcançável a partir do estado 3. Isto pode ser observado a partir do contexto, uma vez que se o jogador alcançar o estado 3, ele nunca deixará este estado, o que implica que p32( n)  0 para qualquer n ≥ 0. Entretanto o estado 3 é alcançável a partir do estado 2, uma vez que p 23(1)  0 . b) Estados Comunicantes Um estado sj é dito comunicante com o estado si se o estado sj é alcançável a partir de si e o estado si é alcançável a partir de sj. Notação: si  sj Obs.: si  sj

então si  sj e sj  si.

20

Relação de Equivalência i)

si  si

ii)

si  sj

iii)

Se si  sj e sj  sk então si  sk

 sj  si

Nota: Se dois estados se comunicam entre si, diz-se que eles pertencem à mesma classe de estados. Se todos os estados são comunicantes então os estados pertencem a uma única classe. Neste caso tem-se uma Cadeia de Markov Irredutível. c) Estado Transiente Um estado é dito ser transiente (transitório) se, entrando neste estado, o processo pode nunca retornar novamente para este estado. Portanto, o estado si é transiente se e somente se existe um estado sj (i  j) que é alcançável a partir de si mas não vice versa, isto é o estado si não é alcançável a partir de sj. Assim, se o estado si é transiente e o processo visita este estado, há uma probabilidade positiva que o processo irá mover para o estado s j e assim nunca irá retornar para o estado si. Consequentemente, um estado transiente será visitado somente um número finito de vezes. Definições i) Seja f ii = a probabilidade condicional de que o processo iniciando em s i, retorne alguma vez em si. ii) Seja f ij = a probabilidade condicional de que o processo iniciando em si, visite alguma vez o estado sj. iii) Seja f ijn = a probabilidade condicional de que o processo iniciando em s i visite sj pela primeira vez no tempo n (no n-ésimo passo). f ijn = P[Xn= sj, Xn-1 ≠ sj, Xn-2 ≠ sj, ....., X1 ≠ sj / X0=si ]

Nota: Um estado si é transiente se e somente se f ii < 1.

21

d) Estado Recorrente Um estado é dito ser recorrente se, entrando neste estado, o processo definitivamente irá retornar para este estado. Portanto, um estado é recorrente, se e somente se não é transiente. Nota: Um estado si é recorrente se e somente se f ii = 1. e) Estado Absorvente Um estado é dito absorvente se o sistema após ter entrado nele não pode mais sair dele. Isto é, se um estado k é absorvente então pkk  1 . Uma vez que o processo visita o estado k não mais sai deste estado. f) Estado Periódico e Aperiódico Um estado i é Periódico com período t se um retorno a este estado é possível somente em t, 2t, 3t, ......passos para t > 1 e t é o maio número inteiro com esta propriedade (Máximo Divisor Comum). Isto significa que pii( n )  0 sempre que n não é divisível por t. Se um estado i de uma classe tem período t então todos os estados desta classe também têm período t. Exemplo 17:

0,5

1 S6

S1

1

1 S3

Todos os Estados são Periódicos.

0,5

0,5

S1

S6

0,5

0,5 S3

0,5

Todos os Estados são Aperiódicos

Exemplo 18: Começando no estado 1 da matriz P é possível retornar ao estado 1 somente nos tempos 2, 4, 6, ..... Logo o estado 1 tem período t = 2. Isto pode ser verificado calculando pii(n ) para todo n e observar que pii( n )  0 quando "n" é impar.

22

0 1 0  1 1 p 0 P  2 0 1 p  3 0 0

0 p 0 0

0 0  p  1

Se t = 1 então o estado i é chamado Aperiódico. Isto é, existem dois números consecutivos s e s+1 tal que o processo pode estar no estado i nos tempos s e s+1. g) Estado Ergódico Em uma Cadeia de Markov de estados finitos, os estados recorrentes que são aperiódicos são chamados de estados Ergódicos. Uma Cadeia de Markov é dita ser Ergódica se todos os estados são Ergódicos, S3 ou seja todos os estados são recorrentes e aperiódicos. h) Classes de Comunicação ou Conjunto Fechado Seja S um Espaço de Estados. Seja C = {sk tal que sk  sj}, diz-se que C é uma classe de comunicação (ou um conjunto fechado) do estado sj. Isto é, um conjunto C é dito ser uma classe de comunicação se o processo ao entrar em um desses estados de C, este irá permanecer nos estados de C indefinidamente, ou seja, C é um conjunto tal que nenhum estado fora de C é alcançável a partir de qualquer estado de C. Pode-se afirmar que C é um conjunto formado por estados recorrentes. Se dois estado se comunicam entre si então pertencem à mesma classe. Observação: Se C1 e C2 são duas classes de comunicação, então C1 = C2 ou C1  C2 = . Se todos os estados são comunicantes, isto é, todos os estados pertencem a uma única classes, então a cadeia de Markov é dita ser Irredutível.

23

Exemplo 19: Classes de Comunicação da matriz de transição do problema do rato e o labirinto. As classes são C1 e C2. C1 s2

s1

s6

s3

C2

s8

s4

s7

s9

s5

C1 ={s1, s2, s3, s6} é uma classe recorrente, ou seja formada por estados recorrentes C2 ={s4, s5, s7, s8, s9} é uma classe recorrente, ou seja formada por estados recorrentes. Nenhum estado de C1 consegue alcançar qualquer estado de C2. Exemplo 20: Classifique os estados e decomponha em classes a Cadeia de Markov representada pela seguinte Matriz de Transição. 0 1 / 4 3 / 4 0 1 / 2 1 / 2 0 0  P 0 0 1 0  0 1/ 3 2 / 3  0  1 0 0 0

0 0 0  0 0 S5 C3 S1

S2

S4 C1 S3

C2

24

C1 ={s1, s2} é uma classe recorrente, ou seja, formada por estados recorrentes C2 ={s3}

é uma classe absorvente, ou seja, formada por estados absorventes

C3 ={s4, s5} é uma classe transiente Exemplo 21: Classifique os estados e decomponha em classes a Cadeia de Markov representada pela seguinte Matriz de Transição. S1 S2 S3 S4 S5 S6 S7 S1 0,8 0 0 0 0 0,2 0   S2 0 0 0 0 1 0 0   S3  0,1 0 0,9 0 0 0 0   P  S4  0 0 0 0,5 0 0 0,5 S5  0 0,3 0 0 0,7 0 0   S6 0 0 1 0 0 0 0  S7  0 0,5 0 0 0 0,5 0  S5 S2 S6

S1

C3

S4 S3

S7 C1 C2

C1 ={s1, s2, s6} é uma classe recorrente, ou seja formada por estados recorrentes C2 ={s4, s7}

é uma classe transiente

C3 ={s2, s5}

é uma classe recorrente, ou seja formada por estados recorrentes

i) Estados Estáveis Se existir πj = lim πj(k) onde πj(k) = P[Xk = j], para um dado estado j, então j é um estado estável ( ou de equilíbrio estacionário). Se πj existe para todos os estados j, então π = [π0, π1, π2, ......] é o vetor de probabilidade de estados estacionários. Nota: Quando a cadeia de Markov for irredutível e não periódica então o valor de π é obtido resolvendo-se o sistema de equações π = πP, onde π0 + π1 + π2 + .... = 1.

25

3.8 – Classificação de Matrizes Estocásticas a) Matrizes Ergódicas

P existe, isto é, Uma matriz estocástica P é Ergódica se a matriz L  lim n n

se cada pij(n ) tem limite quando n. Isto é, todos os estados são aperiódicos. No limite, a Matriz L tem todas as linhas iguais. A matriz L é a matriz com as distribuições limites e independe da distribuição inicial 0. b) Matrizes Regulares Uma das mais importantes características exibidas por muitas cadeias de Markov é um comportamento de equilíbrio em longo prazo. Em outras palavras, “depois de um longo tempo”, a distribuição da cadeia de Markov permanece aproximadamente a mesma de período em período de tempo. Isso significa que, em longo prazo, as probabilidades de o sistema estar em cada um dos vários estados pouco ou nada variam à medida que o tempo passa. Uma matriz estocástica é Regular se uma das suas potências contém apenas elementos positivos (não contém elementos nulos). Exemplo 21: 0,6 0,3 0,1 P   0,1 0,8 0,1    0,1 0,2 0,7

A matriz P contém somente valores positivos. Logo P é uma matriz Regular. 0,2   0 P   0,15 0,85

A matriz P contém um valor nulo. Entretanto a segunda potência de P somente valores positivos. Logo P é uma matriz Regular.

tem

0 0,2 0,8 P  0 1 0   0 0,7 0,3

A matriz P contém valores nulos e suas potencias continuarão com valores nulos. Logo P não é uma matriz Regular.

26

A propriedade fundamental das matrizes Regulares é a de possuírem uma distribuição de equilíbrio. Isso significa que, a longo prazo, as probabilidades de o sistema estar em cada um dos vários estados estabilizam-se em determinados valores positivos. Em particular, então, após um período de tempo suficientemente longo, haverá uma probabilidade positiva de estar em qualquer um dos estados da cadeia de Markov. Teorema: Uma matriz Regular é também uma matriz Ergódica. Observações: a) Se P é uma matriz Regular com matriz L, então as linhas de L são todas idênticas, tendo a soma de seus componentes igual a 1. b) Se P é uma matriz Regular então P é uma matriz Ergódica e assim existe a matriz limite L. c) A Matriz L é obtida resolvendo-se o sistema L = LP, com a condição de que  pij(n ) =1. Exemplo 22: Seja a matriz estocástica P, determine a matriz L com as distribuições limites. 0,88 0,12 P    0,15 0,85

Solução: Como a matriz P contém todos os elementos positivos então P é uma matriz regular e por isso é uma matriz Ergódica. Logo existe a matriz L. Cálculo da matriz L: Seja L1 a primeira linha da matriz L onde L1 = [x1 x2]. Então L1 = L1P. Isto é: [x1 x2] = [x1

0,88x1  0,15x2  x1 0,88 0,12 x2].   0,12x1  0,85x2  x2    0,15 0,85 x  x  1  1 2

 0,12x1  0,15x2  0  0,12x1  0,15x2  0 x  x  1 2  1

Eliminando uma das redundâncias teremos: 0,12 x1  0,15x2  0   x1  x2  1

Resolvendo o sistema em x1 e x2, teremos a seguinte solução: x1 = 0,55 e x2 = 0,45 Logo L1= [0,55

0,45] 0,55 0,45

Com isso a matriz com os valores limite L será: L   . 0,55 0,45 27

Exemplo 23: Seja a matriz estocástica P, determine a matriz L com as distribuições limites. 0 0 1 P  1 1 0

Se o processo começa no estado 0 no tempo 0, o processo retornará ao estado 0 nos tempos 2, 4, 6, .... e entrará no estado 1 nos tempos 1, 3, 5, .... n

P não existe. Esta matriz não é Ergódica. Portanto, o nlim  c) Matrizes Absorventes Diz-se que uma matriz é absorvente se ela tem um estado absorvente e se de cada estado não absorvente é possível ir para algum estado absorvente. Esta última condição significa que para cada estado i não absorvente existe um estado absorvente j tal que, para algum n, pij( n )  0 . Numa matriz absorvente, qualquer que seja a distribuição inicial, após um número finito de passos, o sistema estará em um dos estados absorventes.

28

Primeira Lista de Exercícios - Cadeias de Markov 1. O fabricante da pasta dental HIGLO controla atualmente 60% o mercado de uma determinada cidade. Dados do ano anterior mostram que 88% dos consumidores de HIGLO permaneceram leais à marca, enquanto 12% mudaram para outras marcas. Além disso, 85% dos consumidores das marcas da concorrência permaneceram leais à concorrência, enquanto que os outros 15% mudaram para HIGLO. Assumindo que essa tendência se mantém, resolva: a) Formule o processo seguinte como uma cadeia de Markov, e determine a Matriz de Probabilidades de transição. b) Determine a quota de mercado de HIGLO daqui a 5 anos. c) Determine a quota de mercado de HIGLO a longo prazo. 2. O programa de formação de supervisores de produção de uma determinada companhia consiste em duas fases. A fase 1, a qual envolve 3 semanas de aulas, é seguida da fase 2, que envolve 3 semanas nas de aprendizagem prática sob a direção de supervisores experimentados. Da experiência anterior, a companhia espera que apenas 60% dos candidatos que começam as aulas venham a passar à fase seguinte, verificando-se a desistência dos restantes 40%. Dos que passam à fase prática, 70% serão graduados como supervisores, 10% terão de repetir esta fase e 20% abandonarão o programa. Quantos supervisores pode a companhia esperar formar no seu programa de formação atual, sabendo que há 45 pessoas na primeira fase e 21 na fase prática. Formule o processo seguinte como uma cadeia de Markov, identificando a matriz de probabilidades de transição. 3. Resolva os itens b) e c) do problema formulado no exercício 1, assumindo que a quota atual de mercado da HIGLO é igual a 90%. 4. Construa o diagrama de transição de estados da cadeia de Markov do exercício 2. 5. Os dados de um recenseamento familiar dividem as famílias em populações economicamente estáveis e economicamente deprimidas. Num período de 10 anos, a probabilidade de que uma família estável assim permaneça é de 0,92, enquanto a probabilidade de ela ficar em depressão é de 0,08. A probabilidade de que uma família em depressão se torne estável é de 0,03, enquanto a probabilidade de que ela assim permaneça é de 0,97. Se designarmos a estabilidade econômica como o estado 1 e a depressão econômica como o estado 2, então podemos representar este processo por uma cadeia de Markov com dois estados. a) Determine a matriz de probabilidades de transição do processo de Markov.

29

p ij2

b) Faça uma interpretação física dos elementos da matriz P2 encontrada, que representa a probabilidade de passagem do estado i para o estado j em dois períodos de tempo. 6. Assumindo que os dados do exercício 5 permanecem válidos a longo prazo, determine a proporção de famílias que, a longo prazo, serão classificadas como economicamente estáveis. 7. A ala geriátrica de um hospital classifica os seus pacientes como acamados ou ambulatórios. Dados históricos indicam que durante o período de uma semana, 30% de todos os pacientes em ambulatórios têm alta, 40% permanecem em regime ambulatório e 30% têm de ser acamados para repouso completo. Durante o mesmo período, 50% dos pacientes acamados vão para o ambulatório, 20% permanecem acamados e 30% morrem. Atualmente, o hospital tem 100 pacientes na sua ala geriátrica, com 30% dos pacientes acamados e 70% em ambulatórios. a) Formule o sistema como uma cadeia de Markov, e determine a matriz de probabilidades de transição. b) Determine o estado dos pacientes atuais após 2 semanas. c) Determine o estado dos pacientes atuais a longo prazo. (O estado de um paciente com alta não muda se o paciente morrer). 8. Numa cadeia de Markov, um estado é dito ser absorvente se o sistema após ter entrado nele não pode mais sair dele. Determine todos os estados absorventes para as cadeias de Markov definidas pelas seguintes matrizes: 0   1 0,21 0,79  a) 

c)

1 0 0 0,5  0 0  0 0,3

0 0 0 0,5 1 0  0 0,7 

e)

0 0   1 0,21 0,79 0    0,17 0,35 0,48

0 1 0 0,5 0,3 0,2    1 0 0  b)

 0,1 0,8 0,1 0,9 0 0,1   0,2 0,2 0,6 d)

30

9. Num país, existem 4 principais fabricantes de automóveis : FD, VW, GM, FT. Os “market shares” destes fabricantes são, respectivamente : 10%, 35% , 25 % e 30 %. A matriz de transição que representa a probabilidade de mudança de marca é dada a seguir:  PFD , FD  PVW , FD P   P  GM,FD PFT,FD

PFD,VW

PFD,GM

PVW,VW

PVW,GM

PGM,VW

PGM,GM

PFT,VW

PFT,GM

PFD,FT  0.6 0.1 0.2  PVW,FT  0.1 0.7 0.1  PGM,FT  0.15 0.05 0.75   PFT,FT  0.05 0.35 0.25

0.1  0.1  0.05  0.35

Supondo que o instante inicial é t =0 calcule: a) Os market shares nos instantes t = 1 e t = 2. b) A matriz de transição de 2, 3, 10, 20 e 30 estágios. c) Baseado nos resultados de b, você consegue fazer alguma conjectura a respeito da existência de um limite para Pn ? 10. O tempo num dia qualquer pode ser classificado como sol ou chuva. Suponha que o tempo hoje depende das condições dos últimos 2 dias. Mostre como este sistema pode ser analisado como uma cadeia de Markov. Quantos estados são necessários para esta representação? 11.Um fabricante de disquetes usa cadeias de Markov para ter uma idéia da lealdade dos consumidores a diversas marcas. Dados de uma pesquisa foram usados para estimar a seguinte matriz de transição que representa a probabilidade de mudança de marcas a cada mês. Suponha que existem 3 marcas principais, A, B e C.  PAA P   PBA  PCA

PAB PBB PCB

PAC  0.80 0.10 0.10  PBC   0.03 0.95 0.02 PCC  0.20 0.05 0.75

A divisão de mercado das marcas A, B e C no instante inicial t = 0 são 45%, 25% e 30%, respectivamente. a) Qual será a divisão de mercado das marcas A, B e C após 2 meses (isto é, em t = 2)? b) Qual a previsão para o equilíbrio de mercado das marcas A, B e C, isto é, após um grande número de transições? 12.Classifique todas as classes de estados da matriz de transição P do problema do Rato e o Labirinto. 13.Classifique todas as classes de estados da matriz de transição P 2 do problema do Rato e o Labirinto.

31

14.Seja P uma matriz de transição, calcule a matriz P(). 0 1 0  P  0,5 0,3 0,2   0 0   1

15.Classifique os estados das Cadeias de Markov abaixo, de acordo com as suas respectivas Matrizes de Transição. 0  0 1 / 2 1 / 2 a) P  1 1 / 2 0 1 / 2 2 1 / 2 1 / 2 0  0 0 1 / 2 1 / 2 0 0 0   1 0 0 0 1 / 3 1 / 3 1 / 3   2 0 0 0 1 / 3 1 / 3 1 / 3 b) P    3 1 0 0 0 0 0  4 1 0 0 0 0 0    5 1 0 0 0 0 0 

0 0 1 0 c) P  1 0 0 1 2 1 0 0

16.Um treinador de futebol na moda acredita na polivalência dos seus jogadores. Considera três tipos de jogadores na sua equipe: Atacantes, Defesas, e Goleiro. Após cada jogo reavalia os jogadores de forma a que no jogo seguinte possa usálos de acordo com as suas tácticas para o ataque/defesa. Além disso, sempre que um jogador incorre numa falta disciplinar coloca-o, de castigo, como goleiro no jogo seguinte. Depois de ter experimentado este sistema uma época observou que a probabilidade que, de um jogo para o outro:  um atacante continue atacante é 1/2;  um atacante passe a defesa é zero;  um defesa passe a atacante é zero;  um defesa fique defesa é 1/2;  um goleiro passe a atacante é 3/4;  um goleiro passe a defesa é zero. No ınicio do campeonato classificou o seu plantel da seguinte forma: doze atacantes, onze defesas e dois goleiros. Depois pensou num modelo de cadeia de Markov para a evolução da sua equipa. Os alunos de USF vão ajudá-lo a entender o que lhe vai acontecer com este esquema, estudando a cadeia de Markov subjacente ao modelo.

32

1 - Identifique os seguintes itens. a) O espaço de estados S. b) Um grafo dirigido correspondente às transições. c) A matriz de transição de estados P. d) A distribuição inicial . 2 - Determine, para este modelo, os seguintes resultados. e) A matriz de transições de ordem superior Pn para n ≥ 1, Ex. n = 2 e n = 3. f) As classes de estados comunicantes. g) As classes fechadas e os estados absorventes. 3 - Diga o que vai acontecer no fim do campeonato, isto é, ao fim de 35 jogos. Se não puder efetuar o cálculo exatamente proponha um resultado que ache plausível. 4 - Determine os estados transientes, recorrentes e os estados periódicos. 5 - Determine a distribuição estacionária, se esta existir.

33

TEORIA DAS FILAS 4 – Aspectos Fundamentais sobre Filas 4.1 – Conceito de Fila O que são filas? Qualquer pessoa sabe exatamente o que são filas em decorrência das experiências que o dia-a-dia nos coloca. Todos nos conhecemos o que são filas pela vivência do dia-adia. Nós entramos em uma fila para descontar um cheque em um banco, pagar pelas compras em um supermercado, comprar um ingresso em um cinema, pagar o pedágio em uma estrada e tantas outras situações. Filas existem também em ambientes de produção. Algumas vezes as filas são algo abstrato, tais como uma lista no computador referente a pedidos de manufatura em uma fábrica de geladeiras, ou uma pilha de papéis referentes a solicitações de reparos em máquinas estragadas dentro de uma fábrica, que devem aguardar a disponibilidade do reparador. Outras vezes a fila não é vista enfileirada, mas sim, dispersa, como, por exemplo, pessoas em uma barbearia, esperando pela vez de cortar o cabelo, aviões sobrevoando um aeroporto, esperando pela vez para aterrissar, ou navios parados no mar, esperando pela vez de atracar no porto para descarregar. Exemplos de Problemas de Filas:  Chamadas Telefônicas  Salão de Barbeiro  Caixas de Supermercados  Pedágios  Posto de Gasolina  Atracação de Navios em um Porto  Consultório Médico  Hospitais  Bancos  Aeroportos  Banheiros  Computador, etc.

34

Filas não são Simpáticas Certamente não é agradável entrar em uma fila e esperar pelo serviço e quando a espera é longa, ficamos aborrecidos. Se estivermos em uma fila, passamos a comparar o desempenho da nossa fila com o desempenho das outras filas e, geralmente, somos levados a pensar como uma das leis de Murphy.

Lei de Murphy: “A fila que anda é a outra, mas não adianta trocar de fila, pois a fila que anda é a outra.”

Filas são Dispendiosas Além de não serem simpáticas, as filas têm ainda o lado desfavorável do custo. Isto é válido em qualquer ambiente, indo de fábricas a um supermercado. Por exemplo, nas fábricas a existência de fila em um determinado equipamento pode ocasionar um aumento nos tempos do ciclo de produção. As conseqüências disto podem ser aumento nos custos, e atrasos no atendimento aos pedidos dos clientes. Medidas de Efetividade de um Sistema de Filas 1. Percentual de tempo ocioso ou ocupado 2. Tempo médio que cada cliente gasta na fila de espera 3. Tempo médio gasto pelo cliente no sistema 4. Número médio de clientes na fila 5. Número médio de clientes no sistema 6. Probabilidade de existir um número n de clientes no sistema.

4.2 – Dimensionamento de Filas Do ponto de vista do cliente, o ideal seria dimensionar sistemas para a não existência de filas e, se isto realmente fosse possível, certamente não teríamos clientes aborrecidos. Em muitas situações na vida real, apesar de não serem simpáticas e de causarem prejuízos, temos que conviver com as filas na vida real, visto ser antieconômico superdimensionar um sistema para que nunca existam filas. O que se tenta obter é um balanceamento adequado que permita um atendimento aceitável pelo melhor custo e melhor benefício.

35

O melhor dimensionamento de um sistema de filas pode estar fundamentado nos seguintes itens: - Na demanda histórica média; - Na expectativa de qualidade de atendimento por parte dos clientes; - Na necessidade de oferecer uma melhor renda aos funcionários; - Na percepção, pelo proprietário, da fidelidade dos clientes; - Na percepção, pelo proprietário, de que não existe nenhuma ameaça de surgimento de um novo concorrente na vizinhança. O dimensionamento de sistemas pode ser feito por duas abordagens inteiramente diferentes entre si: - Teoria das Filas; - Simulação de Funcionamento dos Sistemas. A Teoria das Filas é um método analítico que aborda o assunto por meio de fórmulas matemáticas. A Simulação é uma técnica que, utilizando um computador, procura montar um modelo que melhor represente o sistema em estudo. A simulação é uma técnica que permite imitar o funcionamento de um sistema real. Pode-se visualizar o funcionamento de um Banco, uma Fábrica, um Pedágio, etc. 4.3 – Aspectos Históricos Teoria das Filas A abordagem matemática de filas se iniciou no princípio do século XX (1908) em Copenhague, Dinamarca, com A. K. Erlang, considerado o pai da Teoria das Filas, quando trabalhava em uma companhia telefônica estudando o problema de redimensionamento de centrais telefônicas. Foi somente a partir da segunda guerra mundial que a teoria foi aplicada a outros problemas de filas. Apesar do enorme progresso alcançado pela teoria, inúmeros problemas ainda não são adequadamente resolvidos devido a complexidades matemáticas.

36

Simulação Com surgimento do computador na década de 50, a modelagem de filas pode ser analisada pelo ângulo da simulação, em que não mais se usam fórmulas matemáticas, mas apenas tenta-se imitar o funcionamento do sistema real. As linguagens de simulação apareceram na década de 60 e hoje, graças aos microcomputadores, podem ser facilmente usadas. A técnica de simulação visual, cujo uso se deu a partir da década de 80, por causa de sua maior capacidade de comunicação, teve uma aceitação surpreendente. Por causa do seu menor nível de complexidade, seu uso cresceu enormemente.

5 – Fundamentos Básicos de Filas 5.1 - Elementos de Uma Fila

Clientes

Servidor

Servidor Fila População

Servidor Atendimento

Figura 1: Elementos de uma fila

A Figura 1 ilustra os elementos que compõem uma fila. Num sistema de filas tem-se que, de certa população, surgem os clientes que formam uma fila e que aguardam por algum serviço. O termo cliente é usado de uma forma genérica e pode representar tanto uma pessoa, um navio, ou um produto numa linha de produção. O atendimento é constituído de um ou mais servidores (que podem ser chamados de atendentes ou canais de serviço) e tanto podem representar um barbeiro, um cais de atração ou uma máquina numa linha de produção.

37

5.2 – Características de Uma Fila 5.2.1 - Clientes e Tamanho da População

Um cliente é proveniente de uma população. Quando a população é muito grande dizemos que a população é infinita para efeitos práticos. Em população muito grande a chegada de um novo cliente numa fila não afeta a taxa de chegada dos clientes subseqüentes e, assim, concluímos dizendo que as chegadas são independentes. Como exemplo, a chegada de um novo passageiro numa fila de um metrô não afetará a taxa de chegada dos demais clientes. Quando a população é pequena isto não acontece, como exemplo, se numa população de 3 caminhões para serem carregados por uma carregadeira, se os 3 caminhões já estão na fila, a partir deste momento a taxa de chegada será zero, porque não há mais caminhões para chegar na fila. 5.2.2 - Processo de Chegada

Consideremos um posto de pedágio com 5 atendentes. Podemos constatar, por exemplo, que o processo de chegada de veículos entre 7 e 8 horas da manhã pode ser definido por 20 veículos por minuto, ou 1 veículo a cada 3 segundos. Trata-se de um valor médio, pois não significa que em todo intervalo de 1 minuto chegarão 20 veículos. Em alguns intervalos de 1 minuto pode-se constatar a chegada de 10, 15, 25 ou até mesmo 30 veículos. Igualmente, o intervalo de 3 segundos entre chegadas não é rígido e podemos constatar valores desde zero segundo (2 veículos chegando juntos) até 20 segundos. O número 3 segundos representa o intervalo médio entre chegadas no período de 7 às 8 horas da manhã. Resumindo: Podemos quantificar o processo de chegada dizendo que: - A taxa média de chegadas é de 20 veículos por minuto, ou que - O intervalo médio entre chegadas é de 3 segundos. No entanto existem variações em torno da média e, portanto, para caracterizar corretamente um processo de chegada devemos lançar mão de uma distribuição de probabilidades, tal como a distribuição normal, a distribuição de Poisson, ou a Distribuição Exponencial. Quando se estudam filas, o ritmo de chegada é uma importante variável aleatória e a seguinte notação será adotada: A letra grega λ será adotada para representar o ritmo de chegada. A sigla IC será adotada para representar os intervalos de chegada dos clientes. Assim, no exemplo anterior temos:

38

Ritmo de chegada (ou taxa de chegada): λ = 20 clientes/minuto Intervalo entre chegadas: IC = 3 segundos

5.2.3 - Processo de Atendimento

Continuando com o exemplo do pedágio e observando um atendente em serviço, podemos constatar, por exemplo, que ele atende 6 veículos por minuto ou que gasta 10 segundos para atender um veículo. Estes valores são médios e, para descrevê-los corretamente devemos também utilizar uma distribuição de probabilidades. Resumindo: Podemos quantificar o processo de atendimento dizendo que: - A taxa média de atendimento é de 6 veículos por minuto, ou que - O Tempo médio de atendimento é de 10 segundos. O processo de atendimento é também quantificado por uma importante variável aleatória e a seguinte notação será adotada: A letra grega  será adotada para representar o ritmo de atendimento. A sigla TA será adotada para representar os tempos de atendimento dos clientes. Assim, no exemplo anterior temos: Ritmo de atendimento (ou taxa de atendimento):  = 6 clientes/minuto Tempo de Atendimento: TA = 10 segundos

5.2.4 - Número de Servidores

O mais simples sistema de filas é aquele de um único servidor que pode atender um único cliente de cada vez. Conforme aumenta o ritmo de chegada dos clientes, podemos manter a qualidade do serviço aumentando convenientemente o número de servidores. A figura 1 representa um sistema de filas com 3 servidores. 5.2.5 - Disciplina da Fila

Trata-se da regra que define o próximo cliente a ser atendido e o processo comum de atendimento é aquele em que o primeiro da fila é atendido ou, de uma maneira mais ampla, “o primeiro a chegar é o primeiro a ser atendido” (FIFO: first In First Out). Outras disciplinas podem existir tais como “ultimo a chegar é o primeiro a ser atendido” (LIFO: Last In First Out), ou então atendimento por ordem de prioridade, ou atendimento aleatório.

39

5.2.6 - Tamanho Médio da Fila

O tamanho médio da fila é a característica que mais se considera ao se defrontar com a opção de se escolher uma fila. Considera a situação de um cliente em um supermercado procurando efetuar o pagamento no caixa de menor fila: o ideal é chegar ao caixa e será logo atendido, ou seja, fila zero. Quando a fila é de tamanho razoável (por exemplo 10 clientes) intuitivamente sabemos que o tempo de espera na fila será longo. Assim, o supermercado dimensiona a quantidade de caixas de modo que, a qualquer momento, os clientes não sintam um grande desconforto ao pegar uma fila. Situações atípicas certamente ocorrerão, mas não devem afetar a credibilidade da instituição.

5.2.7 - Tamanho Máximo da Fila

Quando os clientes devem esperar, alguma área de espera deve existir (por exemplo: as cadeiras de uma barbearia). Observa-se, na vida real,que os sistemas existentes são dimensionados para certa quantidade máxima de clientes em espera. Esse dimensionamento geralmente é feito com base em experiência real. Quando existe um crescimento da demanda, se faz uma ampliação também baseada na experiência com o manuseio do referido sistema. Há casos em que um novo cliente que chega pode ser recusado, devendo tentar novamente em outro instante. Exemplo: tentativa de conseguir uma linha telefônica, recebendo o sinal de “ocupado” ou de que não há linha disponível. Essas condições referem-se ao que se chama de “tamanho máximo” da fila, que é uma importante variável de estudo em um sistema de filas.

5.2.8 - Tempo Médio de Espera na Fila

O tempo médio de espera na fila é outra característica capaz de causar irritações nos clientes. O ideal é que não haja tempo de espera na fila, mas nem sempre é a melhor situação do ponto de vista econômico. Se entrarmos numa fila com 10 pessoas à nossa frente, o tempo de espera será igual ao somatório dos tempos de atendimento de cada uma dos clientes na nossa frente ou, possivelmente, será igual a 10 vezes a duração média de atendimento dos clientes. Tal como o tamanho médio da fila, o tempo médio de espera na fila depende do processo de chegada e do processo de atendimento.

40

5.3 – Distribuição do Tempo de Atendimento Quando nos referimos a filas, precisamos recorrer às variáveis aleatórias. Assim para as principais variáveis existe um valor médio e uma distribuição de freqüências que mostra as chances de ocorrências dos valores. Quando se diz que a duração média de atendimento é de 10 segundos, não se está afirmando que todo atendimento é de 10 segundos. Em diferentes momentos de observação podem-se ter valores maiores ou menores que 10 segundos. Para exemplificar a variável “tempo de atendimento”, se fosse coletada uma grande quantidade de dados sobre o atendimento poder-se-ia concluir que existe um padrão de atendimento expresso por uma distribuição de freqüências, tal como mostrado na Figura 2. 18

Frequencia Relativa (%)

16 14 12 10 8 6 4 2 0 2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Figura 2: Tempo de Atendimento (segundos)

Pela Figura 2 pode-se concluir que:  É nula a probabilidade de atender um cliente em menos de 5 segundos  A probabilidade de atender um cliente em 10 segundos é 18% ou 0,18.  A probabilidade de atender um cliente em 25 segundos é 0,5% ou 0,05. A mesma observação pode ser feita para outras variáveis tais como “tamanho médio da fila”, etc.

41

5.4 – Dinâmica de uma Fila

Imagine um observador fazendo anotações num sistema de filas num banco durante 30 minutos, anotando o intervalo entre chegadas dos clientes no caixa eletrônico e anotando também o tempo de atendimento do cliente. Imagine que o observador obteve os seguintes resultados em minutos: Processo de Chegada Cliente

1

2

3

4

5

6

7

8

9

10

11

12

Intervalo

2

3

3

3

5

0

1

5

1

4

1

2

Momento

3

6

9

12

17

17

18

23

24

28

29

31

No período de meia hora chegaram 12 pessoas em intervalos de minutos: Momento: significa o instante da chegada do novo cliente Intervalo: significa o tempo que levou para chegar um novo cliente Exemplo: O 1º cliente demorou 2 minutos para chegar, chegou no 3º minuto. O 5º e o 6º clientes chegaram juntos no 17º. minuto. Neste sistema, as seguintes perguntas podem ser feitas: - Qual é a média dos intervalos de chegada? - Qual é a taxa de chegada dos clientes? IC = Intervalo de Chegada A soma de todos os intervalos é igual a 30, logo, pode-se concluir que: Em média: IC =

soma dos intervalos 30   2,5 minutos total de clientes 12

Ou seja, pode-se concluir que em média a cada 2,5 minutos chega um cliente. Desta forma, pode-se concluir que a taxa de chegada de clientes por hora é: 

60 minutos  24 clientespor hora 2,5 minutos

Graficamente temos: Minutos

1º. 2º. 3º.

6º.

9º.

12º.

17º.18º.

23º.

31º.

Clientes

1º.

2º.

3º.

4º.

5º. 7º. 6º.

8º.

12º.

42

Conclusão: IC = 2,5 minutos ou λ = 24 clientes por hora ou λ = 0,4 clientes por minuto Processo de Atendimento O observador anotou o tempo de atendimento dos clientes no caixa eletrônico e obteve os seguintes resultados em minutos: Cliente

1

2

3

4

5

6

7

8

9

10

11

12

Tempo de Atendimento

1

2

1

1

3

2

1

4

2

3

1

3

O tempo total de atendimento de todos os clientes foi de 24 minutos. O tempo médio de atendimento dos clientes é: TA 

1  2  1  1  3  2  1  4  2  3  1  3 24   2 minuntos 12 12

Ou seja, TA = 2 minutos por cliente Ou seja, o sistema tem capacidade de atender 30 clientes por hora. Logo, a taxa de atendimento é µ=30. Conclusão: µ = 30 clientes por hora TA = 2 minutos

Parâmetros do Sistema Taxa de Chegada dos Clientes: λ = 24 clientes por hora IC = 2,5 minutos Taxa de Atendimento dos Clientes: µ = 30 clientes por hora TA = 2 minutos Nota: Todos esses parâmetros representam médias.

43

Dinâmica do Funcionamento de uma Fila

1

2

3

4

8

5 6

9 10

Tempo de Atendimento

7 11 12

5

15

10

20

35

30

25

Tempo de Espera na Fila

12

7 11 10 9

6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Figura 3: Dinâmica do Funcionamento de uma Fila

Pela Figura 3, observa-se que: - O primeiro cliente chegou ao caixa eletrônico no início do 3º minuto e seu atendimento durou 1 minuto, portanto se encerrou no final do 3º minuto. - O quinto cliente chegou ao caixa eletrônico no início do 17º minuto e seu atendimento durou 3 minutos, portanto se encerrou no final do 19º minuto. - O 6º cliente chegou ao caixa eletrônico junto com o 5º cliente. Então no início do 20º minuto foi iniciado o atendimento do 6º ciente que se estendeu até o final do 21º minuto. - O 12º cliente saiu do atendimento no final do 35º minuto. De acordo com a Figura 3, os tempos fila foram: Cliente

1

2

3

4

5

6

7

8

9

10

11

12

Tempo de

0

0

0

0

0

3

4

0

3

1

3

2

fila

44

Portanto, os seguintes parâmetros podem ser calculados: Total de clientes atendidos: 12 Tempo Médio de Fila: TMF 

tempo total de fila 0  0  0  0  0  3  4  0  3  1  3  2 16    1,33 minutos total de clientes 12 12

Tamanho Médio da Fila TaMF 

tempo total de fila 3  4  3  1  3  2 16    0,4 clientes tempo gasto no atendimento 35 35

Observação: Revendo os dados do sistema do banco, pode-se concluir que: λ = 24 clientes por hora (ou IC = 2,5 minutos) µ = 30 clientes por hora (ou TA = 2minutos) Observe que a capacidade de atendimento do sistema (µ) é superior ao ritmo de chegada dos clientes (λ), mas mesmo assim houve a formação de filas. Sistemas Estáveis A abordagem matemática de filas pelo uso da Teoria das Filas exige que exista estabilidade no fluxo de chegada e no processo de atendimento, ou seja, os valores λ e µ devem se manter constantes no tempo. Do contrário deve ser utilizada a técnica de simulação de sistemas. Por exemplo, observando-se o funcionamento de um banco, poderíamos verificar que o fluxo de chegada de clientes varia durante o dia na seguinte forma: Período Fluxo

10 às 12 horas

12 às 14 horas

14 às 16 horas

Médio

Alto

Médio

Ou seja, não existe uma estabilidade para o ritmo de chegada dos clientes e neste caso o uso da Teoria das Filas só pode ser aplicado se o período global de chegada for retalhado em períodos parciais estáveis.

45

Condições para sistemas Estáveis:  O fluxo médio de chegada é constante (λ constante).  O fluxo médio de atendimento é constante (µ constante).  O ritmo de atendimento é maior que o ritmo de chegada (λ TF  0,3  0,04 ==>

TF  0,26horas

NF  .TF

==> NF  20.0,26

NF  5,2 clientes por hora

==>

50

Exercício: Em uma mineração cada caminhão efetua um ciclo onde é carregado de minério por uma das carregadeiras, desloca-se para o britador para o descarregamento e retorna as carregadeiras. Verificar se que o tempo médio (TS) dos caminhões percorrerem o sistema é de 12 minutos. Sabe-se que em média existem 6 caminhões no britador (NS). Qual é a taxa de chegada dos caminhões?

Sistema de Filas

Caminhões

Carregadeiras

Britador

Fórmula de Little NF  .TF NS  .TS



NS 6   0,5 caminhão por minuto TS 12

Ciclo Chama-se ciclo o tempo que um caminhão gasta, partindo de um ponto e chegando ao mesmo ponto. Duração do ciclo =  população /  Suponha que a população seja de 30 caminhões, calcule a duração do ciclo. ciclo 

30





30  60 minutos 0,5

Pode-se calcular o ciclo como: Ciclo = TS + TFS (tempo no sistema + tempo fora do sistema) Neste exemplo: TS = 12 minutos

Ciclo = 60 minutos

Ciclo = TS + TFS ===> TFS = Ciclo - TS TFS = 60 – 12

===> TFS = 48 minutos 51

Resumo das fórmulas Taxa de Chegada

λ

Taxa de Atendimento

µ

Intervalo Ente Chegadas

IC = 1/λ

Tempo de Atendimento

TA = 1/µ

Taxa de Utilização dos Atendentes

ρ = λ/(c.µ)

Número Mínimo de Atendentes

  i   

Relação Entre Fila, Sistema e Atendimento

NS = NF + NA NA = λ/µ NS = NF + λ/µ = NF + TA/IC TS = TF + TA

Formulas de Little

NF = λTF NS = λTS

Ciclo

Ciclo = TS + TFS Ciclo = (População)/λ

52

5.5.2 - Postulados Básicos

A. Em qualquer sistema estável, o fluxo que entra é igual ao fluxo que sai. λ =>

=> λ

B. Em qualquer sistema estável, o fluxo de entrada se mantém nas diversas seções do sistema, desde que não haja junção ou desdobramento. λ

λ

λ

λ

B

A

C

C. Em qualquer sistema estável a junção de fluxos equivale às suas somas aritméticas, λ3 = λ1 + λ2. λ1

A λ3

λ2

λ3

C

B

D. Num sistema estável, o desdobramento percentual de um fluxo é igual ao desdobramento aritmético do mesmo fluxo. Assim se após a estação A 80% do fluxo se deslocou para a estação B, então o ritmo de chegada em B é de 0,8x20 =16 clientes por minuto. λ1=20

80%

A

B

λ3=16

λ2=16 20% λ3=4

C λ3=4

53

Segunda Lista de Exercícios 1) Em uma pizzaria que faz entregas em casa, chegam a média 4 entregadores por minuto para pegar o produto a ser entregue. Sabe-se ainda que o número médio de entregadores dentro da pizzaria é de 6 (NS). Qual é o tempo médio no sistema? 2) No mesmo sistema anterior, existem 40 entregadores. Qual o tempo médio da entrega (TFS)? 3) Em um sistema de computação tem-se: Tempo médio para calcular e fornecer dados (TFS) = 15 seg. Número de terminais ativos é igual a 40. A taxa de chegada de transações é λ = 2 por segundo. Pede-se o tempo de resposta do computador. 4) Em uma mineração tem-se 12 caminhões efetuando um ciclo no qual consomem 4 minutos entre fila e carregamento pela escavadeira (TS) e a seguir, gastam 8 minutos para levar a carga até o britador e voltar (TFS). Calcular λ, o ritmo de chegada dos caminhões e NS, o número de caminhões no sistema. 5) Em um sistema de computação tem-se 21 terminais. O tempo médio de resposta do computador (TS) é de 2 segundos e existem em média 6 transações (NS) dentro do sistema. Pede-se: a) Qual é a taxa de chegada das transações? b) Qual a duração de um ciclo? c) Qual o tempo médio de calcular e fornecer dados (TFS)? 6) Na figura seguinte, representativo do fluxo de peças de um setor de uma fábrica, calcule o fluxo de chegada de peças em cada equipamento. λ=10

A

E

C 30%

λ=20

B

F

D 70%

54

6 – O Sistema de uma Fila e um Atendente Pode ser mostrado que a distribuição de probabilidades de Poisson se ajusta bem para o processo de chegada de muitos sistemas na vida prática. Assim, no processo de chegada de clientes em sistemas de filas a distribuição de probabilidades de Poisson se ajusta perfeitamente. Quando o processo de chegada de clientes segue uma distribuição de probabilidades de Poisson, pode ser mostrado que os intervalos entre as chegadas dos clientes seguem uma distribuição de probabilidades Exponencial Negativa. Com a utilização destas distribuições de probabilidades pode-se calcular uma série de dados que caracterizam um sistema de filas. Consideremos um sistema de filas com uma única fila e um único atendente com os seguintes parâmetros do sistema: λ = taxa de chegada dos clientes µ = taxa de atendimento dos clientes n = número de clientes no sistema Desta forma, os seguintes resultados podem ser estabelecidos: 6.1 – Equações do Modelo

a) Probabilidade de haver n clientes no sistema: λ PX  n     μ 

n

 λ 1  μ   

b) Probabilidade de que o número de clientes no sistema seja superior a um certo número k. λ PX  K     μ 

K 1

c) Probabilidade de que o sistema esteja ocioso (parado).  λ PX  0  1    μ

d) Probabilidade de que o sistema esteja ocupado. PX  0  ρ 

λ μ

55

e) Número médio de clientes no sistema NS 

λ μλ

f) Número médio de clientes na fila. NF 

λ2 μμ  λ 

g) Tempo médio de espera na fila. TF 

λ μμ  λ 

h) Tempo médio gasto no sistema TS 

1 μλ

56

Terceira Lista de Exercícios 1 - Clientes chegam a uma barbearia em um ritmo de 3 por hora e o serviço demora, em média, 16 minutos. Qual é o tempo médio de espera na recepção?. Qual é o tempo médio no sistema? 2 – Pessoas chegam a uma bilheteria de um teatro a um ritmo de 25 por hora. O tempo médio de atendimento da bilheteria é de 2 minutos. Calcule o tamanho da fila, o tempo médio de espera e a fração de tempo em que a bilheteria não trabalha. 3 – Em um sistema no qual λ=4 clientes/hora e µ=6 clientes/hora, qual a probabilidade de existir no sistema: a) nenhum cliente b) um cliente c) 3 ou 4 clientes d) 5 ou mais clientes 4 – No mesmo sistema anterior, admitindo-se que o custo do cliente parado seja de R$ 10,00 por hora, pede-se o custo por hora de clientes no sistema. 5 – Uma empresa deseja comprar um equipamento para efetuar manutenção em suas máquinas, que estragam a um ritmo de 12 falhas por semana. A empresa possui duas opções: o equipamento A custa R$ 20.000,00 e é capaz de efetuar 15 consertos por semana; o equipamento B custa R$ 80.000,00 e é capaz de efetuar 50 consertos por semana. Sabe-se que o custo semanal de uma máquina parada é de R$ 550,00 e que o tempo útil de vida de ambos os equipamentos é de 5 anos. Pergunta-se: Qual equipamento deve ser adquirido de modo que o custo total anual (52 semanas) seja mínimo? Observações: - Para calcular o custo total do valor do equipamento, efetue a operação: (Custo Anual)=(custo do equipamento)x(fator de recuperação do capital) - Considere uma taxa de juros de 15% ao ano. Assim, temos que o fator de recuperação de capital é de 0,2984. 6 – Em um sistema de filas seqüenciais, conforme figura, no qual as peças fluem pela linha de produção, temos: λ1=10; λ2= 5; µ1=15; µ2=30 e µ3=20. Calcule: a) NF, TF,NS e TS para cada um dos servidores. b) NS e TS para o sistema como um todo. λ1 A

λ3 λ2

C

λ3

B

57

7 – Em um setor de uma fábrica, o produto que está sendo fabricado chega para receber componentes adicionais, trabalho este realizado por um operário. Após instalados os componentes, o produto é inspecionado por um profissional qualificado. Os produtos que passam na inspeção vão para outro setor da fábrica e os que são rejeitados (20%) vão para uma área de reparo existente no próprio setor. Atualmente os dados são os seguintes: - A cada 40 minutos chega um novo produto ao setor; - O instalador gasta 25 minutos para instalar os componentes; - O inspetor gasta 5 minutos para inspecionar o trabalho realizado; - O reparador gasta 10 minutos para efetuar os reparos necessários; - Os tempos de deslocamentos do produto entre as estações de trabalho são iguais a 1 minuto. Pede-se: a) NF, NS, TF e TS para cada servidor. b) NS e TS para o sistema como um todo.

58

Quarta Lista de Exercícios 1) Os clientes chegam a uma loja de conveniência de um posto de gasolina a uma taxa de λ = 40 clientes/hora, segundo uma distribuição de Poisson. O único caixa da loja pode atendê-los a uma taxa de μ = 60 clientes/hora, segundo uma distribuição exponencial. Pede-se: 1. A taxa de ocupação do funcionário; 2. P comprimento médio da fila; 3. O número médio de clientes no sistema; 4. O tempo médio despendido esperando na fila; 5. tempo médio no sistema. 2) Existe apenas uma máquina copiadora na sala dos alunos da faculdade. Os alunos chegam a uma taxa de λ = 40 alunos/hora, segundo uma distribuição de Poisson. Uma cópia leva um tempo médio de 40 segundos, ou μ = 90 alunos/hora, segundo uma distribuição exponencial. Pede-se: 1. A taxa de ocupação da máquina; 2. O comprimento médio da fila; 3. O número médio de alunos no sistema; 4. O tempo médio despendido esperando na fila; 5. Tempo médio no sistema. 3) Devido a um recente aumento de negócios, o secretário de uma firma de advocacia agora precisa digitar com um editor de textos uma média de 20 cartas por dia, segundo uma distribuição de Poisson. Ele leva aproximadamente 20 minutos para digitar cada carta, segundo uma distribuição exponencial. Supondo que o secretário trabalha 8 horas por dia. Pede-se: 1. A taxa de utilização do secretário; 2. O tempo médio de espera para que o secretário digite uma carta; 3. O número médio de cartas no sistema; 4. O número médio de cartas esperando digitação; 5. A probabilidade de que o secretário tenha mais de 5 cartas para digitar. 4) Numa clínica veterinária, vacina-se um cão a cada 3 minutos. Os cães chegam a uma taxa de 1 cão a cada 6 minutos, de acordo com uma distribuição de Poisson. Pede-se: 1. A taxa de utilização da clínica; 2. A taxa de ociosidade da clínica; 3. O tempo médio de espera para um cão ser vacinado; 4. O número médio de cães na clínica; 5. O número médio de cães esperando para serem vacinados; 59

6. A probabilidade de que a clínica possua mais de 3 cães para vacinar. 5) Uma empresa de elevadores mantêm uma equipe de atendimento para consertar elevadores defeituosos que ocorrem uma média de λ = 3 elevadores por dia. A equipe pode atender a uma média de μ = 8 máquinas por dia. Pede-se: 1. A taxa de utilização da equipe; 2. O tempo médio de espera de um elevador defeituoso; 3. O número de elevadores aguardando reparo num dado momento qualquer; 4. Qual é a probabilidade de que mais de 1 elevador esteja esperando por reparo; 5. Qual a probabilidade de que mais de 3 elevadores estejam esperando por reparo; 6) Num complexo de 4 salas de cinemas, cada uma das salas com um filme diferente e com horários de início dos filmes alternados para evitar tumulto, existe apenas uma bilheteria capaz de atender 280 clientes por hora. Clientes chegam a uma taxa de 210 clientes por hora. Para determinar a eficiência da atual operação de venda de ingressos, deseja-se examinar algumas características de operação da fila. Pede-se: 1. O numero médio de espectadores esperando na fila para comprar um ingresso; 2. A taxa de ocupação da bilheteria; 3. Tempo médio de fila de um espectador; 4. Qual é a probabilidade de mais de 15 pessoas estejam esperando na fila; 7) A estação de colheita no centro-oeste é curta, e os fazendeiros entregam suas cargas de caminhão fechado de soja a um gigantesco silo de armazenagem central em um período de tempo de 2 semanas. Por causa disso, os caminhões carregados com soja, que esperam para descarregar e retornar ao campo, tem de estacionar a uma quadra do silo de armazenagem. O silo central pertence à cooperativa e é do interesse de todos os fazendeiros tornar o processo o mais eficiente possível. O custo da deterioração dos grãos provocada pelos atrasos na descarga e o custo do aluguel dos caminhões e do tempo ocioso dos motoristas são preocupações significativas para os membros da cooperativa. Embora os fazendeiros tenham dificuldade em quantificar o prejuízo em grãos, é fácil estabelecer que o custo da espera e da descarga para caminhões e motoristas é de R$18, 00 a hora. Durante a temporada de 2 semanas, o silo de armazenagem permanece aberto e funciona 16 horas por dia, 7 dias por semana, podendo descarregar 35 caminhões por hora. Os caminhões carregados chegam durante todo o dia a uma taxa de 30 caminhões por hora. Para ajudar a cooperativa a tratar o problema de perda de tempo enquanto os caminhões esperam na fila ou descarregam no silo, encontre: 1. O número médio de caminhões no sistema; 2. O tempo médio por caminhão no sistema; 3. A taxa de utilização da área do silo; 4. A probabilidade de que mais de 3 caminhões estejam esperando na fila;

60

5. O custo diário total de os fazendeiros terem seus caminhões presos por causa do processo de descarga; 6. A cooperativa s utiliza intensamente o silo durante 2 semanas por ano. Os fazendeiros estimam que o aumento do silo reduziria os custos de descarga em 50% no ano seguinte. Custaria R$ 9.000,00 para fazer isso fora da temporada da colheita. Vale a pena efetuar a despesa para aumentar a área de armazenagem? 8) Uma loja mantém um bem-sucedido callcenter no qual um funcionário recebe os pedidos por telefone. Se o funcionário estiver ocupado em um linha, as demais chamadas são transferidas para um atendimento automático que solicita o cliente a esperar. Assim que o funcionário se desocupa, a chamada que estiver esperando ha mais tempo é transferida e atendida em primeiro lugar. As chamadas chegam a uma taxa de 12 por hora. O funcionário pode atender um pedido a cada 4 minutos. O funcionário recebe R$ 5,00 por hora. A perda de boa vontade e de vendas devido à espera do cliente por um atendimento é de R$ 25,00 por hora. Pede-se: 1. Qual é o tempo médio que os clientes de catálogo devem esperar para que suas chamadas sejam transferidas para o funcionário? 2. Qual é o número médio de chamadas aguardando a anotação de um pedido? 3. A loja está cogitando a contratação de um segundo funcionário para atender chamadas. A loja pagaria a esse funcionário os mesmos R$ 5,00 por hora. A loja deve fazer essa contratação? Explique. 9) Numa clínica de beleza, sabe-se que cada cliente esperando custa R$ 60,00 em vendas perdidas, e que cada atendimento custa R$ 2,50. Um levantamento estatístico constatou que o número médio de clientes no sistema é de 5 por hora. Pede-se: 1. O custo total do sistema por mês, 22 dias úteis de 8 horas cada; 2. Se melhorar a taxa de atendimento em 1 unidade a um custo de R$ 30.000,00, é vantajoso promovê-lo? 3. A taxa de ocupação. 10) Numa loja de troca de óleo mediu-se 2 parâmetros para estudar a sua performance: i) o número médio de clientes na fila igual a 2; ii) tempo médio gasto por atendimento igual a 12 minutos. São conhecidos os seguintes dados adicionais: (iii) custo unitário por atendimento de R$ 10,00; (iv) custo unitário de permanência no sistema de R$ 60,00. Sabe-se que o custo de ampliação do serviço é de R$ 900,00 por mês (melhorar o atendimento em uma unidade). A empresa considera a ampliação desde que haja uma economia mensal de 10% superior ao custo de fazer a ampliação. Considere 22 dias por mês, 8 horas por dia. Nestas condições, a ampliação deve ser feita?

61

11) Um banco está tentando determinar qual das opções alugar para o processamento de cheques. Opção 1 possui uma máquina que processa 1.000 cheques por hora e tem um aluguel de R$ 10.000,00 por ano. A opção 2 processa 1.600 cheques por hora e tem um aluguel de R$ 15.000,00 por ano. A jornada de trabalho é de 8 horas por dia, 5 dias por semana, 50 semanas no ano. O banco deve processar atualmente 800 cheques por hora, sendo que o valor médio de um cheque processado é de R$ 100,00. Assumindo uma taxa de juros de 220% ao ano, determine o custo total do banco, considerando a desvalorização por cheque parado. Qual das opções o banco deve escolher? 12) Num sistema de 1 fila e 1 atendente, foram medidos os seguintes dados: Tempo Gasto no Sistema por Cliente (h) 0,5 0,6 0,7 0,8 0,9 1

Probabilidade (%) 15 20 35 15 10 5

No. de Atendimentos por Hora 10 11 12 13 14 15

Freqüência 5 15 30 30 15 5

Pergunta-se: 1. Qual é a probabilidade de que o número de clientes no sistema seja igual a 2? 2. Qual é taxa de ociosidade? 3. Qual é o número de clientes no sistema?

62

Trabalho Prático Este trabalho deve ser elaborado em grupo de no máximo x alunos. Escolha um lugar onde ocorra um processo de filas, tal com: bancos, Xerox, cantinas, salão de barbeiro, posto de gasolina, etc. De posse de um cronômetro, meça o tempo entre chegadas dos clientes e o tempo de atendimento dos clientes. Observe que duas medidas deverão ser coletadas: o tempo entre chegadas dos clientes e o tempo de atendimento dos clientes. Colete dados até o ponto em que se observe uma estabilidade no sistema. Com posse dos dados coletados, resolva os seguintes itens: 1. Faça uma tabela para os intervalos de chegadas dos clientes e uma tabela para os tempos de atendimentos dos clientes; 2. Calcule a taxa de chegada dos clientes e a taxa de atendimento dos clientes; 3. Calcule a taxa de ocupação e a taxa de ociosidade do sistema; 4. Calcule o número médio de clientes no sistema 5. Calcule o número médio de clientes na fila 6. Calcule o tempo médio dos clientes na fila 7. Calcule o tempo médio dos clientes no sistema 8. Calcule a probabilidade de haver mais de 4 clientes na fila 9. Calcule a probabilidade de que o sistema esteja ocioso; 10.Elabore um relatório fazendo uma análise e tecendo comentários sobre o sistema em estudo. A avaliação do trabalho estará baseada no relatório apresentado, onde deve constar o nome do sistema avaliado e os componentes do grupo.

63

Respostas de Alguns Exercícios Primeira Lista de Exercícios: a) P 

1-

0,88 0,12 ;  0  0,6 0,4 0,15 0,85

  0,5648 0,4352

b) π5 = π0P5, ou seja, 5 . Cota de mercado: 56,48% c) Cota de mercado em longo prazo: 55,56% para o fabricando da HIGLO 44,44% para o concorrente 1 0,4 2- P  0,2 0

0 0 0 0 0,6 0 . 0  0 0 0,1 0,7 0 0 1

45 66

21 0. 66

π1 = π0P = [0,34 0 0,44 0,22]

Formatura: 0,22 x 66 = 14,5 aproximadamente 15 alunos vão se formar. 3- b)  5  0,6370 0,3730 ; Aproximadamente 63% do mercado. c) L1 

5 9

4 9

45- a) P2 

0,92x0,92  0,08x0,03 0,92x0,08  0,08x0,97 0,03x0,92  0,97 x0,03 0,3x0,08  0,97 x0,97

6- Resolver o sistema L1=L1xP, onde L1  x1 x 2 78- a) O estado 1 é absorvente b) Nenhum estado é absorvente c) Os estados 1 e 2 são absorventes d) Nenhum estado é absorvente e) O estado 1 é absorvente 9101112C1 = {S1, S2, S3, S6 } é uma classe recorrente. C2 = { S4, S5, S7, S8, S9} é uma classe recorrente. S2 S1

S3

C2 S4

S5

C1 S9 S6 S8

S7

13-

64

14-

P

()

1 / 3 1 / 3 1 / 3  1 / 3 1 / 3 1 / 3   1 / 3 1 / 3 1 / 3

15- a) Todos os estados são Ergódicos b) Todos os estados são recorrentes, periódicos (período m = 3) e não nulos c)Todos os estados são comunicantes. A cadeia é Irredutível.

Segunda Lista de Exercícios: 1- TS = 1,5 minutos 2- TFS = 8,5 minutos 3- TS = 5 segundos 4- λ = 1; NS = 4 5- λ = 3; Ciclo = 7; TFS = 5 6- A = 10; B = 20; C = 10; D = 30; E = 9; F=21. Terceira Lista de Exercícios: 1- λ = 3; µ = 3,75; TF = 1,07h; TS = 1,33h 2- λ = 25; µ = 30; NF = 4,16; TF = 0,167h ; Tempo Ocioso: 17% 3- P[X=0] = 0,33; P[X=1] = 0,22; P[X=3] + P[X=4] = 0,15; P[X≥5] = 0,1307 4- NF x TF x R$10,00 = R$4,44 5- Custo anual de A: R$ 101.968,00 Custo anual de B: R$ 32.036,00 6Servidor λ µ NF TF TS NS 1 10 15 1,33 0,13 0,20 2 2 5 30 0,03 0,007 0,04 0,2 3 15 20 2,25 0,15 0,20 3 Para o sistema como um todo, temos NS = 2 + 0,2 + 3 = 5,2 Para o TS temos: a) Para quem entra pelo servidor 1: TS=TS(1) + TS(3) = 0,20 + 0,20 = 0,40 b) Para quem entra pelo servidor 2: TS=TS(2) + TS(3) = 0,04 + 0,20 = 0,24 7- Os cálculos foram feitos tomando a hora como unidade de tempo. Servidor λ µ NF TF NS TS(hora) TS(minuto) Instalador 1,5 2,4 1,04 0,69 1,67 1,1 66 Inspetor 1,5 12 0,02 0,01 0,14 0,09 5,4 Reparador 0,3 6 0,002 0,009 0,05 0,18 10,9 Para o sistema como um todo, temos: - NS = 1,67 + 0,14 + 0,05 = 1,86 - Para quem não passa pelo reparo: TS = 66 + 5,4 + 1+1 = 73,4 - Para quem passa pelo reparo: TS = 66 + 5,4 + 10,8 +1+1 = 85,2 - Efetuando a média ponderada, temos: TS = 0,8x73,8 + 0,2x85,2 = 75,76

65

Quarta Lista de Exercícios: 1- 1) ρ = 0,66 ou 66% 2) NF = 1,33 clientes 3) NS = 2 clientes 4) TF = 1,8 minutos 5) TS = 3 minutos 2- 1) 2) 3) 4) 5)

ρ = 0,44 ou 44% NF = 0,355 NS = 0,8 TF = 0,008h TS = 0,02h

3- 1) 2) 3) 4) 5)

ρ = 0,837 ou 83,7% TF = 1,667h NS = 5 cartas NF = 4,17 cartas P[X > 5] = 0,335

4- 1) 2) 3) 4) 5) 6)

ρ = 0,50 ou 50% P[X = 0] = 0,50 ou 50% TF = 3,22 minutos ou 0,053h NS = 1 cão TF = 0,5 cães P[X > 3] = 0,063

5- 1) 2) 3) 4) 5)

ρ = 0,375 ou 37,5% TF = 0,075 dias P[X = 1] = 0,23 P[X > 1] = 0,14 P[X > 3] = 0,019

6- 1) 2) 3) 4)

NF = 2,25 clientes ρ = 0,75 TF = 0,0107h P[X > k] = [/k]K+1 = 0,01

7-

66

8- 1) TF = 0,27h 2) NF = 3,2 chamadas 3) A contratação do funcionário aumenta o custo para R$ 10,00 por hora, porém a perda de vendas devido a espera dos clientes por atendimento diminuirá, pois se um funcionário atende 15 chamadas por hora, com 2 funcionários a capacidade aumentará para 30 chamadas por hora no atendimento, diminuindo a espera de atendimento dos clientes. 9-

67