Proces Markowa – podstawowe wiadomości

Łańcuch Markowa

Proces Markowa

1

}

N

n

,

X

{

0

n



}

0

t

),

t

(

X

{



2

}

r

,...,

2

,

1

{

S



}

r

,...,

2

,

1

{

S



3

j

X

n



j

)

t

(

X



4

,..

i

X

,

i

X

j

X

{

P

2

n

2

n

1

n

n













}

i

X

j

X

{

P

}

i

X

...,

1

n

n

0

0











,..

i

)

t

(

X

,

i

)

t

(

X

j

)

t

(

X

{

P

2

n

2

n

1

n

n













}

i

)

t

(

X

j

)

t

(

X

{

P

}

i

)

0

(

X

...,

1

n

n

0











5

ij

ij

1

n

n

p

)

n

(

p

}

i

X

j

X

{

P











)

t

(

p

)

t

t

(

p

}

i

)

t

(

X

j

)

t

(

X

{

P

ij

n

n

ij

n

n















1

1

6

)

,

(

0

d

P

))

0

(

,

(

d

A

7

]

p

[

ij



P

– macierz stochastyczna,

w wierszu suma elementów = 1

]

a

[

ij



A

– macierz quasi-stochastyczna:























j

i

dla

a

a

j

i

dla

0

a

i

j

ij

ii

ij



w wierszu suma elementów = 0

8

P – macierz prawdopodobieństw
przejścia

A – macierz intensywności przejścia

9

ij

p

- prawdopodobieństwo przejścia ze

stanu i do stanu j

ij

a

, dla

j

i



- intensywność przejścia ze stanu i

do stanu j; interpretacja: średnia liczba przejść
ze stanu i do stanu j w jednostce czasu

ii

a - intensywność wyjścia ze stanu i

10

n

n

n

n

,

P

d

d

d

P

d

d

0

0

1









???

)

(

,

)

t

(

)

t

(

'





0

d

A

d

d

11

P regularna

e

d









n

n

lim

(łańcuch ergodyczny)

A nierozkładalna, jeśli

0

1





jest pojedynczą

wartością własną

e

d









)

t

(

lim

t

(proces ergodyczny)

12 e :











1

e1

e

eP

e :











1

e1

0

eA

2

Podstawy teorii kolejek

Erlang A.K. (1918), Kendall D.G. (1951)

System kolejkowy (system masowej obsługi):

klient – zgłoszenie – customer
aparat obsługi – server
kolejka – poczekalnia – queue

Kryteria klasyfikacji systemów kolejkowych:

- z oczekiwaniem – bez oczekiwania
- zgłoszenia pojedyncze – grupowe
- obsługa pojedynczych zgłoszeń – obsługa grupowa (stała lub zmienna wielkość

grupy)

- FIFO, LIFO, SIRO, priorytety
- jeden rodzaj obsługi – sieć obsług

Model systemu (wg powyższej klasyfikacji warianty pierwsze)

▪ Parametry:

s – liczba aparatów obsługi

R – liczność obsługiwanej populacji

p – maksymalna długość kolejki

▪ Zmienne losowe:

1



- odstęp czasu między przybyciem dwóch kolejnych zgłoszeń

2



- czas obsługi jednego zgłoszenia

Oznaczenia typu rozkładu

1



,

2



:

M – wykładniczy,

0







t

,

ae

)

t

(

f

at

,

a

/

)

(

E

1





,

2

1 a

/

)

(

Var





▪ dla

1



parametr a =



(arrival rate),

▪ dla

2



parametr a =



(service rate)

Uwaga: jeśli odstępy między przybywającymi zgłoszeniami mają
rozkład wykładniczy, proces ich napływu jest procesem Poissona

G – nieustalony
D – deterministyczny

zgłoszenia

wchodzące

aparaty
obsługi

zgłoszenia

wychodzące

kolejka

3

▪ Założenia:

– niezależność zmiennych losowych ...
– w jednostce czasu może wystąpić co najwyżej jedno zdarzenie ustalonego typu tzn.

nadejście lub zakończenie obsługi zgłoszenia (jednostka czasu b. krótka,

0





t

)

▪ Notacja Kendalla:

typ rozkładu

1



/ typ rozkładu

2



/s : (R, p)

np.

M/M/1 : (





,

)

M/D/2 : (

0

,



)

▪ Modelem systemu kolejkowego jest proces stochastyczny

}

t

),

t

(

N

{

0



o zbiorze

stanów

}

p

s

,...,

,

{

S





1

0

, gdzie N(t) oznacza liczbę zgłoszeń znajdujących się w

systemie.

▪ W przypadku M/M – proces

}

t

),

t

(

N

{

0



jest procesem Markowa.

Przykład 1 – mała myjnia samochodowa

☺ 1 stanowisko do mycia samochodów (s = 1)
☺ 1 miejsce na oczekiwanie (p = 1)
☺ czas obsługi i odstęp między zgłoszeniami są zmiennymi losowymi o rozkładzie

wykładniczym

☺ czas mycia samochodu – średnio 3,75 minuty
☺ napływ zgłoszeń – średnio jeden samochód co 2,5 minuty



M/M/1 :

)

,

( 1





}

t

),

t

(

N

{

0



jest procesem Markowa, S = {0, 1, 2}

Niech jednostką czasu będzie kwadrans



☺

6





,

4





0 1 2

☺ A =

2

1

0





















4

4

0

6

10

4

0

6

6

1) sprawdź, że macierz A jest nierozkładalna
2) wyznacz rozkład stacjonarny e
3) wyznacz



,



oraz A dla jednostki czasu = 15 sekund i sprawdź, czy ma to

wpływ na nierozkładalność macierzy A oraz postać rozkładu e