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