Proces_Markowa,_system_kolejkowy.pdf

(331 KB) Pobierz
Proces Markowa – podstawowe wiadomości
Proces Markowa – podstawowe wiadomości
Łańcuch Markowa
Proces Markowa
1 }
X{ 0
n }0
,
n
N
(X{ 
t
),
t
2 }r
S
,1{
2
,...,
}r
S
,1{
2
,...,
3 j
X n j
X
(
t
)
X{P
n 
j
X
n
1
,i
X
n
2
i
n
2
,..
(X{P
t
n 
)
j
(X
t
n
1
)
,i
(X
t
n
2
)
i
n
2
,..
4
...,
)0(X
i
}
(X{P
t
)
j
(X
t
)
}i
...,
X
0
i
0
}
X{P
n
j
X
n
1
}i
0
n
n
1
5
X{P 
n
j
X
n
1
}i
p
ij
(
n
)
p
ij
)
(X{P
t
n
)
j
X
(
t
n
 1
1
)
}i
p
ij
(
t
n
t
n
)
p
ij
(
t
6 )
P ))
,
d
A
,
0(
A – macierz quasi-stochastyczna:
[ ij
a
]
P – macierz stochastyczna,
w wierszu suma elementów = 1
[ ij
p
]
a
ij
0
dla
i
j
7
a
a
dla
i
j
ii
ij
j
i
 w wierszu suma elementów = 0
8
P – macierz prawdopodobieństw
przejścia
A – macierz intensywności przejścia
i - intensywność przejścia ze stanu i
do stanu j; interpretacja : średnia liczba przejść
ze stanu i do stanu j w jednostce czasu
p - prawdopodobieństwo przejścia ze
stanu i do stanu j
9
ij
a - intensywność wyjścia ze stanu i
10
d
n , P
d
n
1
P
d
0
d
n
d
0
n
???
' 
(
t
)
 0
d
(
t
)
A
,
d
(
)
P regularna
A nierozkładalna, jeśli 0
 jest pojedynczą
1
wartością własną
e
11
lim (łańcuch ergodyczny)
n
d
e
lim
d
(
t
)
(proces ergodyczny)
n
t
12 e :
eP
e
e :
eA
0
e1
1
e1
1
( d
( 0
a, dla j
ij
ii
406575790.019.png 406575790.020.png 406575790.021.png 406575790.022.png 406575790.001.png 406575790.002.png 406575790.003.png 406575790.004.png 406575790.005.png 406575790.006.png 406575790.007.png 406575790.008.png 406575790.009.png 406575790.010.png 406575790.011.png 406575790.012.png 406575790.013.png 406575790.014.png 406575790.015.png 406575790.016.png 406575790.017.png
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
kolejka
zgłoszenia
wchodzące
aparaty
obsługi
zgłoszenia
wychodzące
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
(f at
)
ae
t
,
, a
 ,
/
Var 
(
)
1a
2
▪ 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
2
t
E1
(
)
/
406575790.018.png
▪ 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/D/2 : ( 0, )
▪ Modelem systemu kolejkowego jest proces stochastyczny }
(N{ 0
),
t
o zbiorze
stanów }p
S 
 1
0 , gdzie N(t) oznacza liczbę zgłoszeń znajdujących się w
,
,...,
s
systemie.
▪ W przypadku M/M – proces }
(N{ 0
t
),
t
 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
  }
,
(N{ 0
t
),
t
 jest procesem Markowa, S = {0, 1, 2}
Niech jednostką czasu będzie kwadrans 
☺ 6
 , 4
0 1 2
0
6
6
0
☺ A =
1
4
10
6
2
0
4
4
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
3
M/M/1 : ( 
t
{

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin