Przykłady procesów Markowa. Elementy teorii kolejkowania

których ewolucja po dowolnej wartości parametru czasu t (\displaystyle t) nie zależy z ewolucji, która poprzedziła t (\displaystyle t), pod warunkiem, że wartość procesu w tej chwili jest stała („przyszłość” procesu nie zależy od „przeszłości” ze znaną „teraźniejszością”; inna interpretacja (Wentzel): „przyszłość” procesu zależy na „przeszłość” tylko poprzez „teraźniejszość”).

Encyklopedyczny YouTube

1 / 3

✪ Wykład 15: Procesy stochastyczne Markowa

✪ Pochodzenie łańcuchów Markowa

✪ Uogólniony model procesu Markowa

Napisy na filmie obcojęzycznym

Fabuła

Własność definiująca proces Markowa jest zwykle nazywana własnością Markowa; po raz pierwszy sformułował ją A. A. Markov, który w pracach z 1907 r. położył podwaliny pod badanie sekwencji prób zależnych i związanych z nimi sum zmiennych losowych. Ten kierunek badań jest znany jako teoria łańcuchów Markowa.

Podstawy ogólnej teorii procesów Markowa z czasem ciągłym położył Kołmogorow.

Własność Markowa

Sprawa ogólna

Zostawiać (Ω , F , P) (\displaystyle (\Omega,(\mathcal (F)),\mathbb (P)))- przestrzeń prawdopodobieństwa z filtrowaniem (F t , t ∈ T) (\displaystyle ((\mathcal (F))_(t),\t\wT)) nad niektórymi (częściowo zamówionymi) zestawami T (\displaystyle T); Odpuść sobie (S , S) (\displaystyle (S,(\mathcal (S))))- mierzalna przestrzeń. losowy proces X = (X t , t ∈ T) (\ Displaystyle X = (X_ (t), \ t \ w T)), zdefiniowane na filtrowanej przestrzeni prawdopodobieństwa, uważa się za spełniające Własność Markowa jeśli dla każdego A ∈ S (\displaystyle A\in (\mathcal (S))) oraz s , t ∈ T: s< t {\displaystyle s,t\in T:s,

P (X t ∈ A | F s) = P (X t ∈ A | X s) . (\displaystyle \mathbb (P) (X_(t)\w A|(\mathcal (F))_(s))=\mathbb (P) (X_(t)\w A|X_(s)). )

Proces Markowa to losowy proces, który spełnia Własność Markowa z naturalną filtracją.

Do łańcuchów Markowa z czasem dyskretnym

Jeśli S (\displaystyle S) jest dyskretnym zestawem i T = N (\displaystyle T=\mathbb (N) ) definicję można przeformułować:

P (X n = x n | X n - 1 = x n - 1 , X n - 2 = x n - 2 , ... , X 0 = x 0) = P (X n = x n | X n - 1 = x n - 1) (\displaystyle \mathbb (P) (X_(n)=x_(n)|X_(n-1)=x_(n-1),X_(n-2)=x_(n-2),\ kropki , X_(0)=x_(0))=\mathbb (P) (X_(n)=x_(n)|X_(n-1)=x_(n-1))).

Przykład procesu Markowa

Rozważ prosty przykład procesu stochastycznego Markowa. Punkt porusza się losowo wzdłuż osi X. W czasie zero punkt znajduje się w punkcie początkowym i pozostaje tam przez jedną sekundę. Sekundę później rzuca się monetą - jeśli herb wypadł, to punkt X przesuwa się o jednostkę długości w prawo, jeśli cyfra - w lewo. Sekundę później moneta jest ponownie rzucana i wykonywany jest ten sam losowy ruch, i tak dalej. Proces zmiany położenia punktu ("wędrówka") jest procesem losowym o dyskretnym czasie (t=0, 1, 2, ...) i przeliczalnym zbiorze stanów. Taki losowy proces nazywamy Markowskiem, ponieważ następny stan punktu zależy tylko od stanu obecnego (bieżącego), a nie od stanów przeszłych (nie ma znaczenia, w którą stronę i na jaki czas punkt dotarł do aktualnej współrzędnej) .

Procesy losowe Markowa noszą imię wybitnego rosyjskiego matematyka A.A. Markov (1856-1922), który jako pierwszy rozpoczął badanie probabilistycznego związku zmiennych losowych i stworzył teorię, którą można nazwać „dynamiką prawdopodobieństwa”. W przyszłości fundamenty tej teorii stały się wyjściową podstawą dla ogólnej teorii procesów losowych, a także tak ważnych nauk stosowanych, jak teoria procesów dyfuzji, teoria niezawodności, teoria kolejek itp. Obecnie teoria procesów Markowa i jej zastosowania znajdują szerokie zastosowanie w różnych dziedzinach nauk, takich jak mechanika, fizyka, chemia itp.

Ze względu na porównawczą prostotę i klarowność aparatu matematycznego, wysoką niezawodność i dokładność otrzymanych rozwiązań, procesy Markowa zyskały szczególną uwagę specjalistów zajmujących się badaniami operacyjnymi i teorią optymalnego podejmowania decyzji.

Mimo powyższej prostoty i jasności, praktyczne zastosowanie teorii łańcuchów Markowa wymaga znajomości niektórych terminów i podstawowych postanowień, które należy omówić przed przedstawieniem przykładów.

Jak wspomniano, procesy stochastyczne Markowa są szczególnymi przypadkami procesów stochastycznych (SP). Z kolei procesy losowe opierają się na koncepcji funkcji losowej (SF).

Funkcja losowa to funkcja, której wartość dla dowolnej wartości argumentu jest zmienną losową (CV). Innymi słowy, SF można nazwać funkcją, która w każdym teście przybiera jakąś nieznaną wcześniej formę.

Takimi przykładami SF są: wahania napięcia w obwodzie elektrycznym, prędkość samochodu na odcinku drogi z ograniczeniem prędkości, chropowatość powierzchni części na określonym odcinku itp.

Z reguły uważa się, że jeśli argumentem SF jest czas, to taki proces nazywa się losowym. Istnieje inna, bliższa teorii podejmowania decyzji, definicja procesów losowych. Jednocześnie proces losowy jest rozumiany jako proces losowej zmiany stanów dowolnego układu fizycznego lub technicznego w czasie lub innego argumentu.

Łatwo zauważyć, że jeśli wyznaczymy stan i zobrazujemy zależność, to taka zależność będzie funkcją losową.

Procesy losowe są klasyfikowane według typów stanów i argumentu t. W takim przypadku procesy losowe mogą mieć dyskretne lub ciągłe stany lub czas.

Oprócz powyższych przykładów klasyfikacji procesów losowych istnieje jeszcze jedna ważna właściwość. Właściwość ta opisuje probabilistyczną zależność między stanami procesów losowych. Czyli np. jeśli w procesie losowym prawdopodobieństwo przejścia systemu do każdego kolejnego stanu zależy tylko od stanu poprzedniego, to taki proces nazywamy procesem bez następstw.

Zauważ, że po pierwsze losowy proces ze stanami dyskretnymi i czasem nazywany jest ciągiem losowym.

Jeśli ciąg losowy ma właściwość Markowa, nazywa się go łańcuchem Markowa.

Z drugiej strony, jeśli w procesie losowym stany są dyskretne, czas jest ciągły, a własność aftereffect jest zachowana, to taki losowy proces nazywamy procesem Markowa z ciągłym czasem.

Proces stochastyczny Markowa nazywany jest jednorodnym, jeśli prawdopodobieństwa przejścia pozostają stałe podczas procesu.

Łańcuch Markowa jest uważany za podany, jeśli spełnione są dwa warunki.

1. Istnieje zbiór prawdopodobieństw przejścia w postaci macierzy:

2. Istnieje wektor prawdopodobieństw początkowych

opisujący stan początkowy systemu.

Oprócz postaci macierzowej model łańcucha Markowa można przedstawić jako ukierunkowany wykres ważony (ryc. 1).

Ryż. jeden

Zbiór stanów układu łańcuchowego Markowa jest klasyfikowany w określony sposób, biorąc pod uwagę dalsze zachowanie układu.

1. Zestaw nieodwracalny (rys. 2).

Rys.2.

W przypadku zestawu bezzwrotnego możliwe są dowolne przejścia w ramach tego zestawu. System może opuścić ten zestaw, ale nie może do niego wrócić.

2. Zbiór rekurencyjny (rys. 3).

Ryż. 3.

W takim przypadku możliwe są również dowolne przejścia w ramach zestawu. System może wejść do tego zestawu, ale nie może go opuścić.

3. Zestaw ergodyczny (rys. 4).

Ryż. 4.

W przypadku zbioru ergodycznego możliwe są wszelkie przejścia w zbiorze, ale przejścia zi do zbioru są wykluczone.

4. Zestaw absorbujący (rys. 5)

Ryż. 5.

Gdy system wejdzie w ten zestaw, proces się kończy.

W niektórych przypadkach, pomimo losowości procesu, można w pewnym stopniu sterować prawami rozkładu lub parametrami prawdopodobieństw przejścia. Takie łańcuchy Markowa nazywane są kontrolowanymi. Oczywiście przy pomocy kontrolowanych łańcuchów Markowa (MCC) proces decyzyjny staje się szczególnie efektywny, co zostanie omówione później.

Główną cechą dyskretnego łańcucha Markowa (DMC) jest determinizm odstępów czasowych pomiędzy poszczególnymi etapami (etapami) procesu. Właściwość ta jednak często nie jest obserwowana w rzeczywistych procesach, a przedziały okazują się losowe z pewnymi prawami rozkładu, chociaż proces pozostaje Markowski. Takie losowe sekwencje nazywane są semi-Markowa.

Ponadto, biorąc pod uwagę obecność i brak pewnych zbiorów stanów wymienionych powyżej, łańcuchy Markowa mogą być absorbujące, jeśli istnieje co najmniej jeden stan absorbujący, lub ergodyczne, jeśli prawdopodobieństwa przejścia tworzą zbiór ergodyczny. Z kolei łańcuchy ergodyczne mogą być regularne lub cykliczne. Łańcuchy cykliczne różnią się od zwykłych łańcuchów tym, że w procesie przechodzenia przez określoną liczbę etapów (cykli) następuje powrót do pewnego stanu. Zwykłe łańcuchy nie mają tej właściwości.

Struktura i klasyfikacja systemów kolejkowych

Systemy kolejkowe

Często istnieje potrzeba rozwiązania problemów probabilistycznych związanych z systemami kolejkowania (QS), których przykładami mogą być:

Kasy biletowe;

Warsztaty naprawcze;

Handel, transport, systemy energetyczne;

Systemy komunikacji;

Wspólność takich systemów ujawnia się w jedności metod matematycznych i modeli wykorzystywanych w badaniu ich działań.

Ryż. 4.1. Główne obszary zastosowania TMT

Dane wejściowe do QS odbierają strumień zgłoszeń serwisowych. Na przykład klienci lub pacjenci, awarie sprzętu, rozmowy telefoniczne. Prośby docierają nieregularnie, w losowych momentach. Czas trwania usługi również jest losowy. Stwarza to nieprawidłowości w pracy QS, powoduje jego przeciążenia i niedociążenia.

Systemy kolejkowe mają inną strukturę, ale zazwyczaj można je rozróżnić cztery główne elementy:

1. Przychodzący przepływ popytu.

2. Akumulator (kolejka).

3. Urządzenia (kanały serwisowe).

4. Przepływ wyjściowy.

Ryż. 4.2. Ogólny schemat systemów kolejkowych

Ryż. 4.3. Model działania systemu

(strzałki pokazują momenty nadejścia wymagań w

system, prostokąty - czas obsługi)

Rysunek 4.3a przedstawia model systemu z regularnym przepływem wymagań. Ponieważ znany jest odstęp czasu między zgłoszeniami reklamacji, czas obsługi dobierany jest tak, aby w pełni obciążyć system. Dla systemu ze stochastycznym przepływem wymagań sytuacja jest zupełnie inna – wymagania przychodzą w różnych momentach, a czas obsługi jest również zmienną losową, którą można opisać pewnym prawem dystrybucji (rys. 4.3 b).

W zależności od zasad tworzenia kolejki rozróżnia się następujące QS:

1) systemy z awariami , w którym, gdy wszystkie kanały obsługi są zajęte, żądanie pozostawia system bez obsługi;

2) systemy z nieograniczoną kolejką , w którym żądanie trafia do kolejki, jeśli w momencie jego nadejścia wszystkie kanały obsługi były zajęte;

3) systemy z oczekiwaniem i limitowaną kolejką , w którym czas oczekiwania jest ograniczony pewnymi warunkami lub występują ograniczenia dotyczące liczby wniosków stojących w kolejce.

Rozważ charakterystykę napływającego strumienia wymagań.

Przepływ próśb nazywa się stacjonarny , jeśli prawdopodobieństwo, że jedna lub inna liczba zdarzeń wpadnie w odcinek czasu o określonej długości, zależy tylko od długości tego odcinka.

Strumień wydarzeń nazywa się przepływ bez konsekwencji , jeśli liczba zdarzeń przypadających na określony przedział czasu nie zależy od liczby zdarzeń przypadających na inne.

Strumień wydarzeń nazywa się zwyczajny jeśli dwa lub więcej wydarzeń nie może wystąpić jednocześnie.

Przepływ próśb nazywa się Poissona (lub najprostsze), jeśli ma trzy właściwości: stacjonarną, zwyczajną i nie ma konsekwencji. Nazwa wynika z faktu, że w określonych warunkach liczba zdarzeń przypadających na dowolny ustalony przedział czasowy zostanie rozłożona zgodnie z prawem Poissona.

intensywność przepływ aplikacji λ to średnia liczba aplikacji pochodzących z przepływu w jednostce czasu.

W przypadku przepływu stacjonarnego intensywność jest stała. Jeżeli τ jest średnią wartością odstępu czasu między dwoma sąsiednimi żądaniami, to w przypadku przepływu Poissona prawdopodobieństwo wejścia do usługi m prośby na określony czas t określa prawo Poissona:

Czas między sąsiednimi żądaniami rozkłada się wykładniczo z gęstością prawdopodobieństwa

Czas obsługi jest zmienną losową i jest zgodny z rozkładem wykładniczym z gęstością prawdopodobieństwa, gdzie μ jest natężeniem przepływu usługi, tj. średnia liczba żądań obsługiwanych w jednostce czasu,

Stosunek natężenia przepływu przychodzącego do natężenia przepływu usługi nazywamy rozruch systemu

System kolejkowy to system typu dyskretnego ze skończonym lub przeliczalnym zbiorem stanów, a przejście systemu z jednego stanu do drugiego następuje nagle, gdy wystąpi jakieś zdarzenie.

Proces nazywa się proces stanu dyskretnego , jeśli jego możliwe stany można z góry przenumerować, a przejście systemu ze stanu do stanu następuje niemal natychmiast.

Takie procesy są dwojakiego rodzaju: z czasem dyskretnym lub ciągłym.

W przypadku czasu dyskretnego przejścia ze stanu do stanu mogą zachodzić w ściśle określonych momentach czasu. Procesy o czasie ciągłym różnią się tym, że przejście systemu do nowego stanu jest możliwe w każdej chwili.

Proces losowy to korespondencja, w której każdej wartości argumentu (w tym przypadku momentowi z przedziału czasu eksperymentu) przypisana jest zmienna losowa (w tym przypadku stan QS). Zmienna losowa ilość nazywana jest wielkością, która w wyniku doświadczenia może przyjąć jedną, ale z góry niewiadomą jaką, wartość liczbową z danego zbioru liczbowego.

Dlatego, aby rozwiązać problemy teorii kolejek, konieczne jest zbadanie tego losowego procesu, tj. zbudować i przeanalizować jego model matematyczny.

losowy proces nazywa Markowian , jeśli w jakimkolwiek momencie probabilistyczna charakterystyka procesu w przyszłości zależy tylko od jego aktualnego stanu, a nie od tego, kiedy i jak układ doszedł do tego stanu.

Przejścia systemu ze stanu do stanu zachodzą pod wpływem pewnych przepływów (przepływ wniosków, przepływ awarii). Jeżeli wszystkie przepływy zdarzeń, które doprowadzają system do nowego stanu, są najprostszym Poissonem, to proces zachodzący w systemie będzie procesem markowskim, gdyż najprostszy przepływ nie ma konsekwencji: w nim przyszłość nie zależy od przeszłości. - grupa figur szachowych. Stan układu charakteryzuje się liczbą pionków przeciwnika pozostających w danej chwili na planszy. Prawdopodobieństwo, że w danym momencie przewaga materialna będzie po stronie któregoś z przeciwników, zależy przede wszystkim od stanu układu w danym momencie, a nie od tego, kiedy iw jakiej kolejności pionki zniknęły z planszy do chwili.

Wykład 9

Procesy Markowa
Wykład 9
Procesy Markowa



1

Procesy Markowa

Procesy Markowa
Proces losowy w systemie nazywa się
Markowskiego, jeśli nie ma to żadnych konsekwencji. Tych.
jeśli weźmiemy pod uwagę aktualny stan procesu (t 0) - as
obecny, zbiór możliwych stanów ((s),s t) - as
przeszłość, zbiór możliwych stanów ( (u),u t) - as
przyszłości, a następnie dla procesu Markowa z ustaloną
teraźniejszość, przyszłość nie zależy od przeszłości, ale jest zdeterminowana
tylko obecny i nie zależy od tego, kiedy i w jaki sposób system
doszedł do tego stanu.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
2

Procesy Markowa

Procesy Markowa
Procesy losowe Markowa zostały nazwane na cześć wybitnego rosyjskiego matematyka A.A. Markowa, który jako pierwszy zaczął badać probabilistyczne połączenie zmiennych losowych
i stworzył teorię, którą można nazwać „dynamiką
prawdopodobieństwa”. W przyszłości podstawą tej teorii były:
podstawa wyjściowa ogólnej teorii procesów losowych, a także tak ważnych nauk stosowanych, jak teoria procesów dyfuzji, teoria niezawodności, teoria kolejek itp.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
3

Markow Andriej Andriejewicz Markow Andriej Andriejewicz Markow Andriej Andriejewicz

Procesy Markowa
Markow Andriej Andriejewicz
1856-1922
Rosyjski matematyk.
Napisał około 70 artykułów na
teorie
liczby,
teorie
przybliżenia funkcji, teorie
prawdopodobieństwa. Znacząco rozszerzył zakres prawa
duże liczby i centralne
twierdzenie graniczne. jest
twórca teorii procesów losowych.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
4

Procesy Markowa

Procesy Markowa
W praktyce czyste procesy Markowa są zwykle
nie spotykają się. Ale są procesy, dla których wpływ „prehistorii” można pominąć, a podczas nauki
w takich procesach można zastosować modele Markowa. W
Obecnie teoria procesów Markowa i jej zastosowania znajdują szerokie zastosowanie w różnych dziedzinach.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
5

Procesy Markowa

Procesy Markowa
Biologia: procesy narodzin i śmierci – populacje, mutacje,
epidemie.
Fizyka:
radioaktywny
rozpady,
teoria
liczniki
cząstki elementarne, procesy dyfuzji.
Chemia:
teoria
ślady
w
jądrowy
emulsje fotograficzne,
probabilistyczne modele kinetyki chemicznej.
Obrazy.jpg
Astronomia: teoria fluktuacji
jasność Drogi Mlecznej.
Teoria kolejkowania: centrale telefoniczne,
warsztaty naprawcze, kasy biletowe, punkty informacyjne,
obrabiarki i inne układy technologiczne, układy sterowania
elastyczne systemy produkcyjne, przetwarzanie informacji przez serwery.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
6

Procesy Markowa

Procesy Markowa
Niech w chwili obecnej t0 układ będzie w
pewien stan S0. Znamy cechy charakterystyczne
stan systemu w teraźniejszości i wszystko, co było w t< t0
(historia procesu). Czy możemy przewidzieć przyszłość?
tych. co się dzieje, gdy t > t0?
Niezupełnie, ale pewne cechy probabilistyczne
proces w przyszłości można znaleźć. Na przykład prawdopodobieństwo, że
że po chwili
system S będzie w stanie
S1 lub pozostań w stanie S0 itd.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
7

Procesy Markowa. Przykład.

Procesy Markowa
Procesy Markowa. Przykład.
System S - grupa samolotów biorących udział w walce powietrznej. Niech x będzie liczbą
"czerwone" samoloty, y to liczba "niebieskich" samolotów. Do czasu t0 liczba ocalałych (nie zestrzelonych) samolotów
odpowiednio – x0, y0.
Interesuje nas prawdopodobieństwo, że w danym momencie
t 0 przewaga liczebna będzie po stronie „czerwonych”. Prawdopodobieństwo to zależy od stanu, w jakim znajdował się system.
w chwili t0, a nie od kiedy i w jakiej kolejności samoloty zostały zestrzelone do czasu t0 zostały zabite.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
8

Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Proces Markowa ze skończoną lub przeliczalną liczbą
stany i momenty czasu nazywane są dyskretnymi
Łańcuch Markowa. Przejścia ze stanu do stanu są możliwe tylko w czasach całkowitych.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
9

10. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa

Przypuszczać
Co
przemówienie
idzie
o
kolejne rzuty monetą
gra „rzucać”; moneta jest wrzucana do
warunkowe momenty czasu t =0, 1, ... i on
na każdym kroku gracz może wygrać ±1 s
to samo
prawdopodobieństwo
1/2,
więc
Zatem w chwili t jego całkowity zysk jest zmienną losową ξ(t) o możliwych wartościach j = 0, ±1, ... .
Zakładając, że ξ(t) = k, w następnym kroku wypłata będzie
jest już równe ξ(t+1) = k ± 1, przyjmując wartości j = k ± 1 z takim samym prawdopodobieństwem 1/2. Można powiedzieć, że tutaj z odpowiednim prawdopodobieństwem następuje przejście ze stanu ξ(t) = k do stanu ξ(t + 1) = k ± 1.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
10

11. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Uogólniając ten przykład, można sobie wyobrazić system z
policzalna liczba możliwych stanów, które z biegiem czasu
dyskretny czas t = 0, 1, ... losowo przechodzi ze stanu do stanu.
Niech ξ(t) będzie jego pozycją w czasie t w wyniku łańcucha losowych przejść
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
11

12. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Przy analizie procesów losowych ze stanami dyskretnymi wygodnie jest posłużyć się schematem geometrycznym – grafem
państw. Wierzchołki grafu to stany układu. Policz łuki
– możliwe przejścia ze stanu do stanu.
Gra „rzucać”.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
12

13. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Oznacz wszystkie możliwe stany liczbami całkowitymi i = 0, ±1, ...
Załóżmy, że przy znanym stanie ξ(t) =i, w kolejnym kroku układ przechodzi w stan ξ(t+1) = j z prawdopodobieństwem warunkowym
P((t1) j(t)i)
niezależnie od jej zachowania w przeszłości, a dokładniej niezależnie od
od łańcucha przejść do momentu t:
P( (t 1) j (t) i; (t 1) to 1;...; (0) i0 )
P((t1) j(t)i)
Ta nieruchomość nazywa się markowskimi.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
13

14. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Numer
pij P( (t 1) j (t) i)
zwany prawdopodobieństwem
przejście układu ze stanu i do stanu j w jednym kroku w
punkt w czasie t1.
Jeżeli prawdopodobieństwo przejścia nie zależy od t, to łańcuch
Markowa nazywa się jednorodnym.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
14

15. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Macierz P , której elementami są prawdopodobieństwa
przejście pij , nazywa się macierzą przejścia:
p11 ... p1n
P p 21 ... p 2n
p
n1 ... pnn
Jest stochastyczny, tj.
pij 1 ;
i
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
p ij 0 .
15

16. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
Matryca przejścia do gry „rzucać”
...
k2
k2
0
k 1
1/ 2
k
0
k 1
k
k 1
k2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
Ogrodnik w wyniku analizy chemicznej gleby ocenia
jej stan z jedną z trzech liczb - dobra (1), dobra (2) lub zła (3). W wyniku obserwacji na przestrzeni lat zauważył ogrodnik
że produktywność gleby w nurcie
rok zależy tylko od jego stanu w
Poprzedni rok. Dlatego prawdopodobieństwa…
przejście gleby z jednego stanu do
inny może być reprezentowany przez:
Łańcuch Markowa z matrycą P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
17

18. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
Jednak w wyniku zabiegów agrotechnicznych ogrodnik może zmienić prawdopodobieństwa przejścia w macierzy P1.
Wtedy matryca P1 zostanie wymieniona
do macierzy P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
18

19. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Zastanów się, jak stany procesu zmieniają się w czasie. Rozpatrzymy proces w kolejnych momentach czasu, zaczynając od momentu 0. Ustalmy początkowy rozkład prawdopodobieństwa p(0) ( p1 (0),..., pm (0)) , gdzie m jest numerem procesu stany, pi (0) jest prawdopodobieństwem znalezienia
proces w stanie i w momencie początkowym. Prawdopodobieństwo pi(n) nazywamy bezwarunkowym prawdopodobieństwem stanu
ja w czasie n 1.
Składowe wektora p(n) pokazują, które z możliwych stanów obwodu w czasie n są najbardziej
prawdopodobny.
m
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
pk (n) 1
k 1
19

20. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Znajomość ciągu ( p (n)) dla n 1,... pozwala uzyskać wyobrażenie o zachowaniu się systemu w czasie.
W systemie 3-stanowym
p11 p12 p13
P p21
p
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
Ogólnie:
pj (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
k
p(n 1) p(n) P
20

21. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
Matryca
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Krok
(p(n))
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
21

22. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
n
Macierz przejść w n krokach P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p(2)
P(2) P2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
22

23. Dyskretne łańcuchy Markowa

Procesy Markowa
Dyskretne łańcuchy Markowa
Jak zachowują się łańcuchy Markowa dla n ?
Dla jednorodnego łańcucha Markowa, pod pewnymi warunkami, zachodzi następująca własność: p (n) dla n.
Prawdopodobieństwo 0 nie zależy od rozkładu początkowego
p(0) , ale są określone tylko przez macierz P . W tym przypadku nazywa się to dystrybucją stacjonarną, a sam łańcuch nazywa się ergodycznym. Własność ergodyczności oznacza, że ​​wraz ze wzrostem n
prawdopodobieństwo stanów praktycznie przestaje się zmieniać, a system przechodzi w stabilny tryb pracy.
i
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
23

24. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
p()(0,0,1)
24

25. Dyskretne łańcuchy Markowa. Przykład

Procesy Markowa
Dyskretne łańcuchy Markowa. Przykład
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0,1017 0,5254 0,3729
0.1017 0.5254 0.3729
p()(0,1017,0,5254,0,3729)
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
25

26. Procesy Markowa z czasem ciągłym

Procesy Markowa

Proces nazywa się procesem ciągłym, jeśli
momenty możliwych przejść ze stanu do stanu nie są z góry ustalone, ale są niepewne, losowe i mogą wystąpić
w pewnym momencie.
Przykład. Układ technologiczny S składa się z dwóch urządzeń,
z których każdy w losowym momencie może wyjść z
budynku, po którym natychmiast rozpoczyna się naprawa węzła, również trwająca przez nieznany, losowy czas.
Możliwe są następujące stany systemu:
S0 - oba urządzenia działają;
S1 - pierwsze urządzenie jest naprawiane, drugie działa poprawnie;
S2 - drugie urządzenie jest naprawiane, pierwsze działa poprawnie;
S3 - oba urządzenia są naprawiane.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
26

27. Procesy Markowa z czasem ciągłym

Procesy Markowa
Procesy Markowa z czasem ciągłym
Występują przejścia systemu S ze stanu do stanu
niemal natychmiast, w przypadkowych momentach awarii
dowolne urządzenie lub
koniec naprawy.
Prawdopodobieństwo jednoczesnego
awaria obu urządzeń
można zaniedbać.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
27

28. Strumienie wydarzeń

Procesy Markowa
Strumienie wydarzeń
Strumień zdarzeń to sekwencja jednorodnych zdarzeń następujących po sobie w losowym czasie.
to średnia liczba zdarzeń
Intensywność przepływu wydarzeń
na jednostkę czasu.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
28

29. Strumienie wydarzeń

Procesy Markowa
Strumienie wydarzeń
Strumień zdarzeń nazywamy stacjonarnymi, jeśli jego probabilistyczne cechy nie zależą od czasu.
W szczególności intensywność
przepływ stacjonarny jest stały. Przebieg zdarzeń nieuchronnie ma koncentrację lub rozrzedzenie, ale nie mają one charakteru regularnego, a średnia liczba zdarzeń w jednostce czasu jest stała i nie zależy od czasu.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
29

30. Strumienie wydarzeń

Procesy Markowa
Strumienie wydarzeń
Strumień zdarzeń nazywany jest strumieniem bez konsekwencji, jeśli for
dowolne dwa nienakładające się segmenty czasu, a liczba zdarzeń przypadających na jeden z nich nie zależy od tego, ile zdarzeń przypadło na drugi. Innymi słowy, oznacza to, że wydarzenia, które tworzą strumień, pojawiają się w określonych momentach.
czas niezależnie od siebie i każdy spowodowany własnymi przyczynami.
Strumień zdarzeń nazywamy zwykłymi, jeśli prawdopodobieństwo wystąpienia dwóch lub więcej zdarzeń w elementarnym przedziale t jest pomijalnie małe w porównaniu z prawdopodobieństwem wystąpienia jednego
wydarzenia, tj. wydarzenia w nim pojawiają się jedno po drugim, a nie w grupach po kilka na raz
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
30

31. Strumienie wydarzeń

Procesy Markowa
Strumienie wydarzeń
Strumień zdarzeń nazywany jest najprostszym (lub stacjonarnym Poissonem), jeśli ma jednocześnie trzy właściwości: 1) jest stacjonarny, 2) jest zwyczajny, 3) nie ma konsekwencji.
Najprostszy przepływ ma najprostszy opis matematyczny. Gra wśród strumieni ten sam specjalny
rolę, jak m.in. prawo rozkładu normalnego
prawa dystrybucji. Mianowicie, gdy wystarczająco duża liczba samodzielnych, stacjonarnych i zwykłych
przepływy (porównywalne ze sobą pod względem intensywności), uzyskuje się przepływ bliski najprostszemu.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
31

32. Strumienie zdarzeń

Procesy Markowa
Strumienie wydarzeń
Dla najprostszego przepływu z intensywnością
interwał
czas T między sąsiadującymi zdarzeniami ma wykładnik
rozkład z gęstością
p(x) e x , x 0 .
W przypadku zmiennej losowej T o rozkładzie wykładniczym oczekiwanie matematyczne jest odwrotnością parametru.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
32

33. Procesy Markowa z czasem ciągłym

Procesy Markowa
Procesy Markowa z czasem ciągłym
Rozpatrując procesy o stanach dyskretnych i czasie ciągłym, można przyjąć, że wszystkie przejścia układu S ze stanu do stanu zachodzą pod działaniem
najprostsze przepływy zdarzeń (przepływy połączeń, przepływy awarii, przepływy odzyskiwania itp.).
Jeżeli wszystkie przepływy zdarzeń przenoszących system S ze stanu do stanu są najprostsze, to proces zachodzący w
system, będzie markowski.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
33

34. Procesy Markowa z czasem ciągłym

Procesy Markowa
Procesy Markowa z czasem ciągłym
Niech na system w stanie wpłynie
najprostszy przepływ wydarzeń. Gdy tylko pojawi się pierwsze zdarzenie tego przepływu, system „przeskakuje” ze stanu
w stan.
- intensywność przepływu zdarzeń, tłumacząc system
poza stanem
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
w
.
34

35. Procesy Markowa z ciągłym czasem

Procesy Markowa
Procesy Markowa z czasem ciągłym
Niech rozważany system S będzie miał
możliwe stany
. Prawdopodobieństwo p ij (t) to prawdopodobieństwo przejścia ze stanu i do stanu j w czasie t.
Prawdopodobieństwo i -tego stanu
jest prawdopodobieństwo, że
że w czasie t system będzie w stanie
. Oczywiste jest, że przez każdą chwilę suma
wszystkich prawdopodobieństw stanów jest równe jednemu:
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
35

36. Procesy Markowa z ciągłym czasem

Procesy Markowa
Procesy Markowa z czasem ciągłym
Aby znaleźć wszystkie prawdopodobieństwa stanu
jak
funkcje czasu, równania różniczkowe Kołmogorowa są kompilowane i rozwiązywane - specjalny rodzaj równania, w którym nieznane funkcje są prawdopodobieństwami stanów.
Dla prawdopodobieństw przejścia:
p ij (t) p ik (t) kj
k
Dla prawdopodobieństw bezwarunkowych:
p j (t) p k (t) kj
k
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
36

37. Kołmogorow Andriej Nikołajewicz

Procesy Markowa
Kołmogorow Andriej Nikołajewicz
1903-1987
Wielki rosyjski
matematyk.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
37

38. Procesy Markowa z ciągłym czasem

Procesy Markowa
Procesy Markowa z czasem ciągłym
- współczynnik awaryjności;
- intensywność przepływu regeneracyjnego.
Niech system będzie w stanie
S0. Jest przenoszony do stanu S1 przez przepływ
awaria pierwszego urządzenia. Jego intensywność to
gdzie
- Średni czas bezawaryjnej pracy urządzenia.
Ze stanu S1 do S0 system jest przenoszony przez przepływ uzupełnień
pierwsze urządzenie. Jego intensywność to
gdzie
- średni czas naprawy pierwszej maszyny.
Podobnie obliczane są natężenia przepływów zdarzeń, które przenoszą układ wzdłuż wszystkich łuków wykresu.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
38

39. Systemy kolejkowe

Procesy Markowa

Przykłady systemów kolejkowych (QS): centrale telefoniczne, warsztaty naprawcze,
bilet
kasy,
odniesienie
Biuro,
obrabiarki i inne układy technologiczne,
systemy
kierownictwo
elastyczny
systemy produkcyjne,
przetwarzanie informacji przez serwery itp.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
39

40. Systemy kolejkowe

Procesy Markowa
Systemy kolejkowe
QS składa się z określonej liczby porcji
jednostki, które nazywane są kanałami usług (są to
maszyny, roboty, linie komunikacyjne, kasjerzy itp.). Dowolna CMO
jest przeznaczony do obsługi przepływu aplikacji (wymagań) przychodzących w losowych momentach.
Obsługa żądania trwa przez losowy czas, po którym kanał zostaje zwolniony i jest gotowy do odbioru następnego.
Aplikacje.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
40

41. Systemy kolejkowe

Procesy Markowa
Systemy kolejkowe
Proces działania QS jest procesem losowym z dyskretnym
stany i czas ciągły. Stan QS zmienia się gwałtownie w momentach pojawienia się niektórych zdarzeń
(przybycie nowej aplikacji, koniec usługi, moment,
gdy zmęczona czekaniem aplikacja opuści kolejkę).
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
41

42. Systemy kolejkowe

Procesy Markowa
Systemy kolejkowe
Klasyfikacja systemów kolejkowych
1. QS z awariami;
2. CMO z kolejką.
W QS z odmową, roszczenie, które pojawia się w momencie, gdy wszystkie kanały są zajęte, otrzymuje odmowę, opuszcza QS i już nie
serwisowany.
W QS z kolejką roszczenie, które przychodzi w momencie, gdy wszystkie kanały są zajęte, nie odchodzi, ale wchodzi do kolejki i czeka na możliwość obsłużenia.
QS z kolejkami są podzielone na różne typy w zależności od
o tym, jak zorganizowana jest kolejka - ograniczona lub nieograniczona. Ograniczenia mogą dotyczyć zarówno długości kolejki, jak i czasu
oczekiwania, „dyscyplina usług”.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
42

43. Systemy kolejkowe

Procesy Markowa
Systemy kolejkowe
Przedmiotem teorii kolejek jest konstrukcja
modele matematyczne łączące dane warunki
Działanie QS (liczba kanałów, ich wydajność, zasady)
pracy, charakter przepływu aplikacji) o interesujących nas cechach - wskaźniki skuteczności QS. Wskaźniki te opisują zdolność systemu QS do radzenia sobie z przepływem
Aplikacje. Mogą to być: średnia liczba aplikacji obsługiwanych przez QS w jednostce czasu; średnia liczba zajętych kanałów; średnia liczba wniosków w kolejce; średni czas oczekiwania na usługę itp.
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"
43

44.

DZIĘKUJĘ CI
UWAGA!!!
44

45. Zbuduj wykres przejścia

Procesy Markowa
Zbuduj wykres przejścia
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
KHNURE, wydział. PM, wykładowca Kirichenko L.O.
„Teoria prawdopodobieństwa, matematyczna
statystyki i procesy losowe"

Pod losowy proces zrozumieć zmianę w czasie stanów jakiegoś układu fizycznego w nieznany wcześniej losowy sposób. W której przez fizyczny system mamy na myśli dowolne urządzenie techniczne, grupa urządzeń, przedsiębiorstwo, przemysł, system biologiczny itp.

losowy proces przepływający w systemie nazywa się Markowski – jeśli na jakiś czas, probabilistyczna charakterystyka procesu w przyszłości (t > ) zależy tylko od jego stanu w danym momencie ( obecny ) i nie zależy od tego, kiedy i jak system doszedł do tego stanu w przeszłości (Na przykład licznik Geigera, który rejestruje liczbę cząstek kosmicznych).

Procesy Markowa są zwykle podzielone na 3 typy:

1. Łańcuch Markowa – proces, którego stany są dyskretne (tzn. mogą być przenumerowane), a czas, w którym jest rozpatrywany, jest również dyskretny (tzn. proces może zmieniać swoje stany tylko w określonych momentach). Taki proces przebiega (zmiany) etapami (czyli cyklami).

2. Dyskretny proces Markowa - zbiór stanów jest dyskretny (można go wyliczyć), a czas jest ciągły (przejście z jednego stanu do drugiego - w dowolnym momencie).

3. Ciągły proces Markowa – zbiór stanów i czas są ciągłe.

W praktyce procesy Markowa w czystej postaci nie są często spotykane. Często jednak mamy do czynienia z procesami, dla których można pominąć wpływ prehistorii. Ponadto, jeśli wszystkie parametry z „przeszłości”, od których zależy „przyszłość”, są uwzględnione w stanie systemu w „teraźniejszości”, to można go również uznać za markowskie. Prowadzi to jednak często do znacznego wzrostu liczby zmiennych branych pod uwagę i niemożności uzyskania rozwiązania problemu.

W badaniach operacyjnych tzw Procesy stochastyczne Markowa ze stanami dyskretnymi i czasem ciągłym.

Proces nazywa się proces stanu dyskretnego, jeśli wszystkie jego możliwe stany , ,... można z góry wyliczyć (przenumerować). Przejście systemu ze stanu do stanu przechodzi niemal natychmiast - skok.

Proces nazywa się ciągły proces czasu, jeśli momenty przejścia ze stanu do stanu mogą przyjmować dowolne wartości losowe na osi czasu.

na przykład : Urządzenie techniczne S składa się z dwóch węzłów , z których każdy w losowym momencie może zawieść ( odmawiać). Następnie naprawa węzła rozpoczyna się natychmiast ( powrót do zdrowia), który trwa przez losowy czas.

Możliwe są następujące stany systemu:

Oba węzły są w porządku;

Pierwszy węzeł jest naprawiany, drugi działa.

- drugi węzeł jest naprawiany, pierwszy działa

Oba węzły są naprawiane.

Przejście systemu ze stanu do stanu następuje w losowych momentach niemal natychmiast. Wygodne jest wyświetlanie stanów systemu i relacji między nimi za pomocą wykres stanu .

stany

Przejścia

Przejścia i są nieobecne, ponieważ awarie i naprawa elementów występują niezależnie i losowo, a prawdopodobieństwo jednoczesnej awarii (naprawy) dwóch elementów jest nieskończenie małe i można je pominąć.

Jeśli wszystkie strumienie zdarzeń tłumaczą system S od stanu do stanu pierwotniaki, następnie proces, płynące w takim systemie będzie Markowski. Wynika to z faktu, że najprostszy przepływ nie ma następstw, tj. w nim „przyszłość” nie zależy od „przeszłości”, a dodatkowo ma właściwość zwyczajności – prawdopodobieństwo jednoczesnego wystąpienia dwóch lub więcej zdarzeń jest nieskończenie małe, tj. nie można przejść ze stanu do stanu bez przechodzenia kilku stanów pośrednich.

Dla jasności na wykresie stanu wygodnie jest odłożyć intensywność przepływu zdarzeń przenoszących układ ze stanu do stanu wzdłuż danej strzałki przy każdej strzałce przejścia ( - natężenie przepływu zdarzeń przenoszących układ ze stanu w. Taki wykres nazywa się oznaczony.

Wykorzystując znakowany wykres stanów systemu można zbudować matematyczny model tego procesu.

Rozważ przejścia systemu z jakiegoś stanu do poprzedniego lub następnego. Fragment wykresu stanu w tym przypadku będzie wyglądał tak:

Niech system na czas t jest w stanie .

Oznacz (t)- prawdopodobieństwo i-tego stanu układu jest prawdopodobieństwo, że system w czasie t jest w stanie . Dla dowolnego momentu czasu t =1 jest prawdziwe.

Określmy prawdopodobieństwo, że w danej chwili t+∆t system będzie w stanie. Może to mieć miejsce w następujących przypadkach:

1) i nie opuścił go w tym czasie ∆ t. Oznacza to, że w czasie ∆t nie powstał zdarzenie, które wprowadza system w stan (przepływ z natężeniem) lub zdarzenie, które wprowadza go w stan (przepływ z natężeniem). Określmy prawdopodobieństwo tego dla małego ∆t.

Zgodnie z wykładniczym prawem rozkładu czasu między dwoma sąsiednimi wymaganiami, odpowiadającymi najprostszemu przepływowi zdarzeń, prawdopodobieństwo, że w przedziale czasu ∆t nie pojawią się wymagania w przepływie o natężeniu λ1 będzie równy

Rozszerzając funkcję f(t) w szereg Taylora (t>0) otrzymujemy (dla t=∆t)

f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…” 1-l*∆t dla ∆t®0

Podobnie dla przepływu o natężeniu λ 2 otrzymujemy .

Prawdopodobieństwo, że w przedziale czasu ∆t (dla ∆t®0) żadne wymaganie nie będzie równe

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

1 - - *∆t + 1 - ( + )*∆t + b.m.

Zatem prawdopodobieństwo, że układ nie wyjdzie ze stanu w czasie ∆t, dla małego ∆t będzie równe

P( / )=1 – ( + )* ∆t

2) System był w stanie S i -1 i na czas przeszedł do stanu S i . Oznacza to, że co najmniej jedno zdarzenie miało miejsce w strumieniu z intensywnością. Prawdopodobieństwo tego jest równe najprostszemu przepływowi o intensywności λ Wola

W naszym przypadku prawdopodobieństwo takiego przejścia będzie równe

3)System był w stanie i w tym czasie „przeszedł do stanu” . Prawdopodobieństwo tego będzie

Wtedy prawdopodobieństwo, że układ w czasie (t+∆t) będzie w stanie S i jest równe

Odejmij P i (t) od obu części, podziel przez ∆t i przechodząc do granicy, przy ∆t→0, otrzymujemy

Podstawiając odpowiednie wartości intensywności przejść ze stanów do stanów, otrzymujemy układ równań różniczkowych opisujących zmianę prawdopodobieństw stanów układu w funkcji czasu.

Te równania nazywają się równaniami Kołmogorowa-Chapman dla dyskretnego procesu Markowa.

Po ustaleniu warunków początkowych (np. P 0 (t=0)=1,P i (t=0)=0 i≠0) i ich rozwiązaniu otrzymujemy wyrażenia na prawdopodobieństwa stanu systemu w funkcji czasu . Rozwiązania analityczne są dość łatwe do uzyskania, jeśli liczba równań ≤ 2,3. Jeśli jest ich więcej, równania są zwykle rozwiązywane numerycznie na komputerze (na przykład metodą Runge-Kutty).

W teorii procesów losowych udowodniony , Co jeśli liczba n stany systemu na pewno a z każdego z nich można (w skończonej liczbie kroków) przejść do dowolnego innego, to jest granica , do którego zmierzają prawdopodobieństwa, gdy t→ . Takie prawdopodobieństwa nazywają się ostateczne prawdopodobieństwa stany i stan ustalony - tryb stacjonarny funkcjonowanie systemu.

Ponieważ w trybie stacjonarnym wszystko , zatem wszystkie =0. Przyrównując lewe części układu równań przez 0 i uzupełniając je równaniem =1, otrzymujemy układ liniowych równań algebraicznych, rozwiązując, przy których znajdujemy wartości ostatecznych prawdopodobieństw.

Przykład. Niech w naszym systemie wskaźniki awarii i odtworzenia elementów są następujące

Awarie 1el:

2el:

Naprawa 1el:

2el:

P 0 + P 1 + P 2 + P 3 \u003d 1

0=-(1+2)P 0 +2P 1 +3 P 2

0=-(2+2)P 1 +1P 0 +3P 3

0=-(1+3)P 2 +2P 0 +2P 3

0=-(2+3)P 3 +2P 1 +1P 2

Rozwiązując ten system, otrzymujemy

P0 =6/15=0,4; P1 =3/15=0,2; P2=4/15=0,27; P3=2/15≈0,13.

Tych. w stanie stacjonarnym system średnio

40% jest w stanie S 0 (oba węzły są zdrowe),

20% - w stanie S 1 (pierwszy element w naprawie, drugi w dobrym stanie),

27% - w stanie S 2 (druga elektryka w naprawie, 1 w dobrym stanie),

13% - w stanie S 3 - oba elementy są w naprawie.

Znajomość ostatecznych prawdopodobieństw pozwala Oceń średnią wydajność systemu i obciążenie usług naprawczych.

Niech system w stanie S 0 przyniesie dochód 8 jednostek. na jednostkę czasu; w stanie S 1 - dochód 3 sr.u.; w stanie S 2 - dochód 5, w stanie S 3 - dochód \u003d 0

Cena £ naprawa na jednostkę czasu dla el-ta 1- 1 (S 1, S 3) arb. unit, el-ta 2- (S 2, S 3) 2 arb. Następnie w trybie stacjonarnym:

Dochód z systemu na jednostkę czasu będzie:

W max =8P 0 +3P 1 +5P 2 +0P 3 =8 0,4+3 0,2+5 0,27+0 0,13=5,15 j.m.

Koszty naprawy w jednostkach czas:

W rem =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0 0,4+1 0,2+2 0,27+3 0,13=1,39 j.m.

Zysk na jednostkę czasu

W \u003d W doh -W rem \u003d 5,15-1,39 \u003d 3,76 jednostki

Po wydaniu pewnych wydatków można zmienić intensywność λ i μ, a tym samym wydajność systemu. Wykonalność takich wydatków można ocenić, przeliczając P i . oraz wskaźniki wydajności systemu.