seminarium
O
T
O
T
naukowe
AJD Częstochowa
AJD Częstochowa
2007
2007
M
M
TEORIA OBSA
UGI
TEORIA OBSA
UGI
MASOWEJ
MASOWEJ
Markowowskie systemy obsługi
Markowowskie systemy obsługi
A
AC
CUCHY MARKOWA
A
AC
CUCHY MARKOWA
Niech T będzie podzbiorem zbioru liczb rzeczywistych
Niech T będzie podzbiorem zbioru liczb rzeczywistych
nieujemnych oraz niech X będzie zbiorem skończonym
nieujemnych oraz niech X będzie zbiorem skończonym
lub przeliczalnym.
lub przeliczalnym.
Definicja 1. Proces stochastyczny x (t) przyjmujący
Definicja 1. Proces stochastyczny x (t) przyjmujący
wartości ze zbioru X nazywamy łańcuchem Markowa, je\
eli
wartości ze zbioru X nazywamy łańcuchem Markowa, je\
eli
dla dowolnej liczby naturalnej n=1,2,..., dowolnych
dla dowolnej liczby naturalnej n=1,2,..., dowolnych
t_1,t_2,...,t_nR
T, takich, \
e t_1< t_2< ...< t_n i dowolnych
t_1,t_2,...,t_nR
T, takich, \
e t_1< t_2< ...< t_n i dowolnych
x_0,x_1,...,x_n R
X zachodzi równość
x_0,x_1,...,x_n R
X zachodzi równość
P{� (tn ) = xn � (t0 ) = x0 ,...,� (tn-1) = xn-1} =P{� (tn ) = xn � (tn-1) = xn-1}
(1)
(1)
Elementy zbioru X nazywać będziemy od tej pory stanami
Elementy zbioru X nazywać będziemy od tej pory stanami
procesu x (t).
procesu x (t).
Własność (1) oznacza, \
e przy ustalonym stanie x_n-1 procesu
Własność (1) oznacza, \
e przy ustalonym stanie x_n-1 procesu
x (t) w chwili czasu t_n-1 jego dalsze zachowanie nie zale\
y od
x (t) w chwili czasu t_n-1 jego dalsze zachowanie nie zale\
y od
tego, w jaki sposób proces trafił do stanu x_n-1 (przyszłość
tego, w jaki sposób proces trafił do stanu x_n-1 (przyszłość
przy ustalonej teraz
niejszości nie zale\
y od przeszłości) .
przy ustalonej teraz
niejszości nie zale\
y od przeszłości) .
W dalszym ciągu będziemy zakładać, \
e X={i}, i=0,1,...(na
W dalszym ciągu będziemy zakładać, \
e X={i}, i=0,1,...(na
przykład wszystkie stany procesu x (t) są ponumerowane).
przykład wszystkie stany procesu x (t) są ponumerowane).
Typowym przykładem takiego procesu jest u\
ywany w
Typowym przykładem takiego procesu jest u\
ywany w
teorii obsługi masowej proces h (t), gdzie h (t) jest liczbą
teorii obsługi masowej proces h (t), gdzie h (t) jest liczbą
zgłoszeń znajdujących się w systemie w chwili t.
zgłoszeń znajdujących się w systemie w chwili t.
A
ańcuch Markowa nazywa się jednorodnym, gdy
A
ańcuch Markowa nazywa się jednorodnym, gdy
P{� (t + t0) = j � (t0) = i}
prawdopodobieństwo warunkowe dla
prawdopodobieństwo warunkowe dla
i, j " X
t0
ustalonych oraz dowolnych nie zale\
y od .
ustalonych oraz dowolnych nie zale\
y od .
t,t0 e" 0
Nadal analizować będziemy tylko jednorodne łańcuchy
Nadal analizować będziemy tylko jednorodne łańcuchy
Markowa.
Markowa.
A
ańcuch Markowa, dla którego T={0,1,2,...} nazywa się
A
ańcuch Markowa, dla którego T={0,1,2,...} nazywa się
łańcuchem Markowa z czasem dyskretnym, natomiast, gdy
łańcuchem Markowa z czasem dyskretnym, natomiast, gdy
T=[0," ) odpowiadający łańcuch Markowa nazywa się
T=[0," ) odpowiadający łańcuch Markowa nazywa się
łańcuchem Markowa z czasem ciągłym.
łańcuchem Markowa z czasem ciągłym.
Wprowadz
my następujące oznaczenia:
Wprowadz
my następujące oznaczenia:
Pij (t) = P{� (t) = j �0 = i}
Pj (t) = P{� (t) = j}
Wielkości te są odpowiednio nazywane
Wielkości te są odpowiednio nazywane
prawdopodobieństwem przejścia ze stanu i do stanu j w
prawdopodobieństwem przejścia ze stanu i do stanu j w
ciągu czasu t oraz prawdopodobieństwem zdarzenia
ciągu czasu t oraz prawdopodobieństwem zdarzenia
polegającego na tym, \
e proces w chwili czasu t znajduje się
polegającego na tym, \
e proces w chwili czasu t znajduje się
w stanie j.
w stanie j.
W przypadku łańcuchów Markowa z czasem dyskretnym
W przypadku łańcuchów Markowa z czasem dyskretnym
wielkości nazywamy prawdopodobieństwami
wielkości Pij
(n ) nazywamy prawdopodobieństwami
przejścia ze stanu i do stanu j w n krokach,
przejścia ze stanu i do stanu j w n krokach,
prawdopodobieństwa przejścia w jednym kroku nazywamy
prawdopodobieństwa przejścia w jednym kroku nazywamy
krótko prawdopodobieństwami przejścia.
krótko prawdopodobieństwami przejścia.
{Pj (0), j " X}
Zespół prawdopodobieństw
Zespół prawdopodobieństw
nazywamy rozkładem początkowym łańcucha Markowa.
nazywamy rozkładem początkowym łańcucha Markowa.
A
ańcuch Markowa nazywa się ergodycznym, je\
eli dla
A
ańcuch Markowa nazywa się ergodycznym, je\
eli dla
wszystkich jego stanów istnieją granice j .
wszystkich jego stanów istnieją granice P ( t ) Ą .
j
Granice te nazywamy prawdopodobieństwami końcowymi
Granice te nazywamy prawdopodobieństwami końcowymi
łańcucha Markowa.
łańcucha Markowa.
A
AC
CUCHY MARKOWA Z CZASEM
A
AC
CUCHY MARKOWA Z CZASEM
CI
GA
YM, PROCESY NARODZIN I ŚMIERCI
CI
GA
YM, PROCESY NARODZIN I ŚMIERCI
Rozpatrzmy ciągłe stochastycznie łańcuchy Markowa z czasem
Rozpatrzmy ciągłe stochastycznie łańcuchy Markowa z czasem
ciągłym tzn. takie łańcuchy Markowa, dla których praktycznie
ciągłym tzn. takie łańcuchy Markowa, dla których praktycznie
niemo\
liwe jest przejście ze stanu i do stanu j w ciągu krótkiego
niemo\
liwe jest przejście ze stanu i do stanu j w ciągu krótkiego
okresu czasu t (tĆ0).
okresu czasu t (tĆ0).
Dla takich łańcuchów mo\
na dowieść, \
e istnieją następujące
Dla takich łańcuchów mo\
na dowieść, \
e istnieją następujące
granice:
granice:
1 - Pii ( " t )
 = lim
i
" t 0
" t
Pij ( " t )
 = lim
ij
" t 0
" t
Granice te nazywamy odpowiednio intensywnością wyjścia ze
Granice te nazywamy odpowiednio intensywnością wyjścia ze
stanu i oraz intensywnością przejścia ze stanu i do stanu j.
stanu i oraz intensywnością przejścia ze stanu i do stanu j.
Dla łańcuchów Markowa z czasem ciągłym mo\
na wyprowadzić
Dla łańcuchów Markowa z czasem ciągłym mo\
na wyprowadzić
równania, za pomocą których mo\
na wyznaczyć
równania, za pomocą których mo\
na wyznaczyć
prawdopodobieństwa bezwarunkowe tego, \
e łańcuch Markowa
prawdopodobieństwa bezwarunkowe tego, \
e łańcuch Markowa
w chwili czasu t znajduje się w stanie j czyli funkcje .
w chwili czasu t znajduje się w stanie j czyli funkcje .
Pj (t)
Równania te mają postać:
Równania te mają postać:
2
P (t ) = -  P (t ) +  Pk (t )
"
j j j kj
k `" j
Równania te są spełnione zawsze w przypadku skończonego
Równania te są spełnione zawsze w przypadku skończonego
zbioru stanów, w przypadku, gdy zbiór stanów jest
zbioru stanów, w przypadku, gdy zbiór stanów jest
nieskończony potrzeba dodatkowo, aby wszystkie
nieskończony potrzeba dodatkowo, aby wszystkie
intensywności wyjścia były skończone.
intensywności wyjścia były skończone.
Dokonując odpowiednich przejść granicznych mo\
emy
Dokonując odpowiednich przejść granicznych mo\
emy
uzyskać równania dla prawdopodobieństw końcowych
uzyskać równania dla prawdopodobieństw końcowych
zwane równaniami równowagi:
zwane równaniami równowagi:
Równania te mają postać:
Równania te mają postać:
-  p +  p = 0
"
j j kj k
k `" j
Wprowadzone równania dla prawdopodobieństw
Wprowadzone równania dla prawdopodobieństw
bezwarunkowych oraz równania równowagi w dość łatwy
bezwarunkowych oraz równania równowagi w dość łatwy
sposób mo\
na wypisywać korzystając z interpretacji
sposób mo\
na wypisywać korzystając z interpretacji
łańcuchów Markowa w postaci grafów stochastycznych.
łańcuchów Markowa w postaci grafów stochastycznych.
Rozpatrzmy następujący przykład.
Rozpatrzmy następujący przykład.
Przykład 1. Rozpatrzmy następujący łańcuch Markowa
Przykład 1. Rozpatrzmy następujący łańcuch Markowa
przedstawiony w postaci poni\
szego grafu stochastycznego.
przedstawiony w postaci poni\
szego grafu stochastycznego.
0
0
1
�0
�2
�1
2 1
2
W analizowanym łańcuchu Markowa intensywność
W analizowanym łańcuchu Markowa intensywność
wyjścia z dowolnego stanu jest sumą intensywności
wyjścia z dowolnego stanu jest sumą intensywności
przejścia z tego stanu do innych stanów (tak jest w
przejścia z tego stanu do innych stanów (tak jest w
przypadku łańcuchów Markowa ze skończonym
przypadku łańcuchów Markowa ze skończonym
zbiorem stanów oraz w wielu innych analizowanych w
zbiorem stanów oraz w wielu innych analizowanych w
teorii obsługi masowej łańcuchach Markowa). Zatem
teorii obsługi masowej łańcuchach Markowa). Zatem
otrzymujemy następujące równania na funkcje :
otrzymujemy następujące równania na funkcje :
Pj (t)
P02 (t) = -(0 + �2)P0(t) + �0P1(t) + 2P2(t)
P12 (t) = -(1 + �0)P1(t) + 0P0(t) + �1P2(t)
P22 (t) = -(2 + �1)P2(t) + �2P0(t) + 1P1(t)
Patrząc na postać tych równań zauwa\
amy, \
e wypisuje się je
Patrząc na postać tych równań zauwa\
amy, \
e wypisuje się je
automatycznie korzystając z grafu.
automatycznie korzystając z grafu.
Dokonując odpowiednich przejść granicznych otrzymujemy
Dokonując odpowiednich przejść granicznych otrzymujemy
natomiast następujące równania równowagi:
natomiast następujące równania równowagi:
(0 + �2) p0 = �0 p1 + 2 p2
(1 + �0) p1 = 0 p0 + �1 p2
(2 + �1) p2 = �2 p0 + 1 p1
Równania równowagi wypisuje się więc korzystając z zasady
Równania równowagi wypisuje się więc korzystając z zasady
 to co wchodzi do danego stanu jest równe temu co
 to co wchodzi do danego stanu jest równe temu co
wychodzi . A dokładniej suma wszystkich iloczynów
wychodzi . A dokładniej suma wszystkich iloczynów
intensywności przejścia do danego stanu oraz odpowiednich
intensywności przejścia do danego stanu oraz odpowiednich
prawdopodobieństw końcowych jest równa iloczynowi
prawdopodobieństw końcowych jest równa iloczynowi
intensywności wyjścia z danego stanu oraz
intensywności wyjścia z danego stanu oraz
prawdopodobieństwa tego stanu.
prawdopodobieństwa tego stanu.
Oczywiście zarówno równania dla prawdopodobieństw
Oczywiście zarówno równania dla prawdopodobieństw
bezwarunkowych, jak i równania równowagi mogą być
bezwarunkowych, jak i równania równowagi mogą być
rozwiązane w oparciu o pewne algebraiczne metody
rozwiązane w oparciu o pewne algebraiczne metody
rozwiązywania odpowiednio układów równań ró\
niczkowych
rozwiązywania odpowiednio układów równań ró\
niczkowych
(np. w oparciu o przekształcenia Laplace a) oraz układów
(np. w oparciu o przekształcenia Laplace a) oraz układów
równań algebraicznych (tu oczywiście dokładamy warunek
równań algebraicznych (tu oczywiście dokładamy warunek
normalizacyjny  suma wszystkich prawdopodobieństw
normalizacyjny  suma wszystkich prawdopodobieństw
końcowych jest równa jeden).
końcowych jest równa jeden).
PROCESY NARODZIN I ŚMIERCI
PROCESY NARODZIN I ŚMIERCI
Procesy narodzin i śmierci są pewnym szczególnym
Procesy narodzin i śmierci są pewnym szczególnym
przypadkiem łańcuchów Markowa z czasem ciągłym i
przypadkiem łańcuchów Markowa z czasem ciągłym i
nieskończonym zbiorem stanów, w którym mo\
liwe są tylko
nieskończonym zbiorem stanów, w którym mo\
liwe są tylko
przejścia ze stanu n do stanów n+1 oraz n-1 (n>0), a ze stanu 0
przejścia ze stanu n do stanów n+1 oraz n-1 (n>0), a ze stanu 0
tylko do stanu 1. Zatem w procesach narodzin i śmierci
tylko do stanu 1. Zatem w procesach narodzin i śmierci
mo\
liwa jest tylko zmiana numeru stanu  o jeden . Stąd te\

mo\
liwa jest tylko zmiana numeru stanu  o jeden . Stąd te\

wynika ich nazwa, przejście n -> n+1 mo\
na interpretować
wynika ich nazwa, przejście n -> n+1 mo\
na interpretować
jako narodziny, a przejście n -> n-1 jako śmierć osobnika w
jako narodziny, a przejście n -> n-1 jako śmierć osobnika w
populacji zło\
onej z n osobników.
populacji zło\
onej z n osobników.
Procesy narodzin i śmierci odgrywają ogromną rolę w teorii
Procesy narodzin i śmierci odgrywają ogromną rolę w teorii
obsługi masowej, gdy\
opisują klasę procesów, w których
obsługi masowej, gdy\
opisują klasę procesów, w których
strumień wejściowy jest pojedynczy oraz w których niemo\
liwe
strumień wejściowy jest pojedynczy oraz w których niemo\
liwe
jest obsłu\
enie więcej ni\
jednego zgłoszenia w czasie t -> 0.
jest obsłu\
enie więcej ni\
jednego zgłoszenia w czasie t -> 0.
W przypadku procesu narodzin i śmierci wypisywanie
W przypadku procesu narodzin i śmierci wypisywanie
omawianych równań jest automatyczne z uwagi na proste
omawianych równań jest automatyczne z uwagi na proste
grafy, które interpretują te procesy.
grafy, które interpretują te procesy.
4
3
0 1 2
.......
Powy\
ej przedstawiono typowy graf procesu narodzin i
Powy\
ej przedstawiono typowy graf procesu narodzin i
śmierci, górne połączenia symbolizują  przejścia procesu o
śmierci, górne połączenia symbolizują  przejścia procesu o
jeden stan do przodu , dolne  o jeden stan do tyłu .
jeden stan do przodu , dolne  o jeden stan do tyłu .
W przypadku procesów narodzin i śmierci wypisywanie
W przypadku procesów narodzin i śmierci wypisywanie
równań równowagi upraszcza się do następującej metody
równań równowagi upraszcza się do następującej metody
zwanej metodą przekrojów. Między dowolnymi dwoma
zwanej metodą przekrojów. Między dowolnymi dwoma
stanami rysujemy przerywaną linię. W procesach narodzin i
stanami rysujemy przerywaną linię. W procesach narodzin i
śmierci oraz w innych procesach, w których mo\
liwa jest
śmierci oraz w innych procesach, w których mo\
liwa jest
zmiana stanu tylko o jeden iloczyn prawdopodobieństwa oraz
zmiana stanu tylko o jeden iloczyn prawdopodobieństwa oraz
intensywności z lewej strony tej linii (przekroju) jest równy
intensywności z lewej strony tej linii (przekroju) jest równy
analogicznemu iloczynowi z prawej strony przekroju.
analogicznemu iloczynowi z prawej strony przekroju.
Poznane metody będziemy stosować dalej przy analizie tzw.
Poznane metody będziemy stosować dalej przy analizie tzw.
markowowskich systemów obsługi.
markowowskich systemów obsługi.
MARKOWOWSKIE
MARKOWOWSKIE
SYTEMY OBSA
UGI
SYTEMY OBSA
UGI
Niech h(t) oznacza liczbę zgłoszeń znajdujących się w systemie
Niech h(t) oznacza liczbę zgłoszeń znajdujących się w systemie
obsługi w chwili t. Je\
eli h(t) jest łańcuchem Markowa, to
obsługi w chwili t. Je\
eli h(t) jest łańcuchem Markowa, to
odpowiadający system nazywa się markowowskim systemem
odpowiadający system nazywa się markowowskim systemem
obsługi.
obsługi.
Mo\
na wykazać, \
e markowowskie są wszystkie systemy
Mo\
na wykazać, \
e markowowskie są wszystkie systemy
obsługi typu M/M/n/m, gdzie 1ŁnŁ" , 0ŁmŁ" .
obsługi typu M/M/n/m, gdzie 1ŁnŁ" , 0ŁmŁ" .
Systemy takie będziemy więc badać w oparciu o
Systemy takie będziemy więc badać w oparciu o
poznane metody analizy łańcuchów Markowa z czasem
poznane metody analizy łańcuchów Markowa z czasem
ciągłym.
ciągłym.
Przejdz
my do analizy kilku typów systemów tego typu.
Przejdz
my do analizy kilku typów systemów tego typu.
W kolejnych rozwa\
aniach przyjmiemy następujące
W kolejnych rozwa\
aniach przyjmiemy następujące
oznaczenia:
oznaczenia:
a jest intensywnością wejściowego najprostszego strumienia
a jest intensywnością wejściowego najprostszego strumienia
zgłoszeń;
zgłoszeń;
m jest parametrem rozkładu wykładniczego czasu obsługi
m jest parametrem rozkładu wykładniczego czasu obsługi
zgłoszenia;
zgłoszenia;
r=a/(nm) jest ładowaniem systemowym.
r=a/(nm) jest ładowaniem systemowym.
Dodatkowo dla systemów o nieskończonej liczbie urządzeń
Dodatkowo dla systemów o nieskończonej liczbie urządzeń
wprowadzimy oznaczenie y=a/m.
wprowadzimy oznaczenie y=a/m.
W kolejnych rozwa\
aniach skupimy się na przedstawieniu
W kolejnych rozwa\
aniach skupimy się na przedstawieniu
grafów oraz wyprowadzeniu równań dla prawdopodobieństw
grafów oraz wyprowadzeniu równań dla prawdopodobieństw
stacjonarnych kilku szczególnych przypadków systemów
stacjonarnych kilku szczególnych przypadków systemów
M/M/n/m. Oczywiście korzystając z poznanej metody
M/M/n/m. Oczywiście korzystając z poznanej metody
mo\
emy równie\
wypisywać równania dla
mo\
emy równie\
wypisywać równania dla
prawdopodobieństw bezwarunkowych w trybie
prawdopodobieństw bezwarunkowych w trybie
niestacjonarnym.
niestacjonarnym.
1. SYSTEM OBSA
UGI M/M/n/m, 1Ł n<" , 0Ł m<" .
1. SYSTEM OBSA
UGI M/M/n/m 1Ł n<" , 0Ł m<" .
Dla systemów tego typu zbiór stanów jest skończony, je\
eli
Dla systemów tego typu zbiór stanów jest skończony, je\
eli
tylko r=a/(nm) < " , to wówczas istnieją warunki stacjonarne
tylko r=a/(nm) < " , to wówczas istnieją warunki stacjonarne
działania tych systemów i mo\
emy w oparciu o metodę
działania tych systemów i mo\
emy w oparciu o metodę
przekrojów wypisać równania równowagi i znalez
ć
przekrojów wypisać równania równowagi i znalez
ć
pi = lim Pi (t)
prawdopodobieństwa stacjonarne . Aby to zrobić
prawdopodobieństwa stacjonarne . Aby to zrobić
t"
narysujmy graf przejść dla tego systemu.
narysujmy graf przejść dla tego systemu.
a a a
a a a
n+1
0 1 ... n ... n+m-1 n+m
m nm nm
m nm nm
Korzystając z metody przekrojów otrzymujemy
Korzystając z metody przekrojów otrzymujemy
następujące równania równowagi:
następujące równania równowagi:
apk -1 = k�pk , gdy 1 d" k d" n
ńł
�łap = n�pk , gdy n d" k d" n + m
ół k -1
Rozwiązując powy\
szy układ otrzymujemy następujące
Rozwiązując powy\
szy układ otrzymujemy następujące
wyra\
enia pozwalające obliczyć prawdopodobieństwa
wyra\
enia pozwalające obliczyć prawdopodobieństwa
stacjonarne obecności k zgłoszeń w systemie.
stacjonarne obecności k zgłoszeń w systemie.
ńł
(n�)k
p0, gdy 1 d" k d" n
�ł
�ł
k!
pk =
�ł
n k
�łn � p0, gdy n < k d" n + m
�ł
ół n!
gdzie
n+1 m
n
(n�)k nn� (1- � )
p0 = [ + ]-1
"
k! n!(1- �)
k =0
Przykład 1. Rozwa\
my system obsługi M/M/3/1, w którym a=2,
Przykład 1. Rozwa\
my system obsługi M/M/3/1, w którym a=2,
m=3. Narysować graf przejść dla tego systemu oraz znalez
ć
m=3. Narysować graf przejść dla tego systemu oraz znalez
ć
rozkład stacjonarny liczby zgłoszeń w systemie.
rozkład stacjonarny liczby zgłoszeń w systemie.
2 2 2 2
0 1 2 3 4
3 6 9 9
Korzystając z metody przekrojów otrzymujemy następujący
Korzystając z metody przekrojów otrzymujemy następujący
układ równań:
układ równań:
2 p0 = 3p1
ńł
�ł2 p1 = 6 p2
�ł
�ł2 p2 = 9 p3
�ł
�ł2 p3 = 9 p4
�ł
�ł
p0 + p1 + p2 + p3 + p4 = 1
ół
Rozwiązanie układu jest następujące:
Rozwiązanie układu jest następujące:
729
ńł
p0 =
�ł
1421
�ł
486
�ł
p1 =
�ł
1421
�ł
162
�ł
p2 =
�ł
1421
�ł
36
�ł
p3 =
�ł
1421
�ł
8
�ł
p4 =
�ł
1421
ół
Zauwa\
my, \
e ostatnie z prawdopodobieństw odgrywa
Zauwa\
my, \
e ostatnie z prawdopodobieństw odgrywa
rolę prawdopodobieństwa utraty zgłoszenia.
rolę prawdopodobieństwa utraty zgłoszenia.
Korzystając z rozkładu liczby zgłoszeń mo\
emy np.
Korzystając z rozkładu liczby zgłoszeń mo\
emy np.
wyznaczyć wartość oczekiwaną liczby zgłoszeń w
wyznaczyć wartość oczekiwaną liczby zgłoszeń w
n+m
warunkach stacjonarnych ( ).
warunkach stacjonarnych ( ).
E� =
"kp
k
k =0
2. SYSTEM OBSA
UGI M/M/n/" .
2. SYSTEM OBSA
UGI M/M/n/" .
Dla tego systemu graf będzie bardzo podobny do grafu z
Dla tego systemu graf będzie bardzo podobny do grafu z
poprzedniego systemu, z tym, \
e tutaj zbiór stanów jest
poprzedniego systemu, z tym, \
e tutaj zbiór stanów jest
nieskończony. W tym przypadku proces h(t) jest więc
nieskończony. W tym przypadku proces h(t) jest więc
procesem narodzin i śmierci. Warunki stacjonarne istnieją,
procesem narodzin i śmierci. Warunki stacjonarne istnieją,
gdy r <1. Równania równowagi uzyskujemy w sposób
gdy r <1. Równania równowagi uzyskujemy w sposób
analogiczny:
analogiczny:
apk -1 = k�pk , gdy 1d" k d" n
ńł
�łap = n�pk , gdy k e" n +1
ół k -1
Ich rozwiązania sa równie\
bardzo podobne :
Ich rozwiązania sa równie\
bardzo podobne :
ńł
(n�)k
p0, gdy 1 d" k d" n
�ł
�ł
k!
pk =
�ł
n k
�łn � p0, gdy k e" n +1
�ł
ół n!
System ten jest jednak w odró\
nieniu od poprzedniego
System ten jest jednak w odró\
nieniu od poprzedniego
systemem z oczekiwaniem. Jest więc dla niego sens
systemem z oczekiwaniem. Jest więc dla niego sens
wyznaczania charakterystyk czasu oczekiwania i czasu
wyznaczania charakterystyk czasu oczekiwania i czasu
przebywania. Jeśli chodzi o charakterystyki stacjonarnego
przebywania. Jeśli chodzi o charakterystyki stacjonarnego
czasu oczekiwania i stacjonarnego czasu przebywania to
czasu oczekiwania i stacjonarnego czasu przebywania to
wzory na pierwsze momenty tych zmiennych
wzory na pierwsze momenty tych zmiennych
przedstawiają się następująco:
przedstawiają się następująco:
n
nn-2� p0
w1 =
�(1- �)2(n -1)!
v1 = w1 + �
Przykład 2. Rozwa\
my system obsługi M/M/2/" , dla
Przykład 2 Rozwa\
my system obsługi M/M/2/" , dla
którego a=2, m=3.
którego a=2, m=3.
Graf takiego systemu wygląda następująco:
Graf takiego systemu wygląda następująco:
2 2 2 2
0 1 2 3 4 ...
3 6 6 6
Natomiast równania równowagi mają postać: (r <1)
Natomiast równania równowagi mają postać: (r <1)
2 p0 = 3p1
ńł
�ł2 p1 = 6 p2
�ł
�ł2 p2 = 6 p3
�ł
�ł...........
�ł
�ł p0 + p1 +.... =1
ół
Ten nieskończony układ równań mo\
na rozwiązać w oparciu o
Ten nieskończony układ równań mo\
na rozwiązać w oparciu o
pojęcie szeregu geometrycznego.
pojęcie szeregu geometrycznego.
3. SYSTEM M/M/ " .
3. SYSTEM M/M/ " .
W systemie tym jest nieskończona liczba urządzeń obsługi,
W systemie tym jest nieskończona liczba urządzeń obsługi,
zatem wszystkie przybywające zgłoszenia są obsługiwane od
zatem wszystkie przybywające zgłoszenia są obsługiwane od
razu po przybyciu (nie oczekują w kolejkach). Graf takiego
razu po przybyciu (nie oczekują w kolejkach). Graf takiego
systemu wygląda następująco:
systemu wygląda następująco:
a a a
a a a
a
a
k-1 k
0 1 ... ... k+1
m km (k+1)m
m km (k+1)m
Równania równowagi dla tego systemu mają postać:
Równania równowagi dla tego systemu mają postać:
apk -1 = k�pk , k =1,2,...
Uwzględniając warunki normalizacyjne otrzymujemy
Uwzględniając warunki normalizacyjne otrzymujemy
ostatecznie wzór na prawdopodobieństwo obecności k
ostatecznie wzór na prawdopodobieństwo obecności k
zgłoszeń w systemie w warunkach stacjonarnych
zgłoszeń w systemie w warunkach stacjonarnych
yk
pk = e- y,
k!
gdzie y=a/m.
gdzie y=a/m.
Podane metody mo\
na równie\
stosować do analizy
Podane metody mo\
na równie\
stosować do analizy
prostych systemów w których odstępy czasu między
prostych systemów w których odstępy czasu między
sąsiednimi chwilami przybycia zgłoszeń lub czas obsługi
sąsiednimi chwilami przybycia zgłoszeń lub czas obsługi
mają rozkład Erlanga. Korzystając z faktu, \
e rozkład
mają rozkład Erlanga. Korzystając z faktu, \
e rozkład
Erlanga jest sumą niezale\
nych rozkładów wykładniczych,
Erlanga jest sumą niezale\
nych rozkładów wykładniczych,
traktujemy przedział czasowy o rozkładzie Erlanga jako
traktujemy przedział czasowy o rozkładzie Erlanga jako
sumę przedziałów o rozkładzie wykładniczym i mo\
emy
sumę przedziałów o rozkładzie wykładniczym i mo\
emy
znów analizować takie systemy za pomocą grafów. Ta
znów analizować takie systemy za pomocą grafów. Ta
metoda nazywa się metodą faz Erlanga. Metodę tą mo\
na
metoda nazywa się metodą faz Erlanga. Metodę tą mo\
na
M / Ek / n / m Ek/ M / n /
stosować więc w systemach typu , m
stosować więc w systemach typu ,
Ek / El / n / m
oraz .
oraz .