Марков обработва примери. Елементи на теорията на опашките

Еволюцията на която след дадена стойност на параметъра за време t (\displaystyle t) не зависиот еволюцията, която предхожда t (\displaystyle t), при условие че стойността на процеса в този момент е фиксирана („бъдещето“ на процеса не зависи от „миналото“ с известното „настояще“; друга интерпретация (Венцел): „бъдещето“ на процеса зависи върху „миналото“ само чрез „настоящето“).

Енциклопедичен YouTube

1 / 3

✪ Лекция 15: Стохастични процеси на Марков

✪ Произход на веригите Марков

✪ Обобщен модел на процес на Марков

Субтитри

История

Свойството, което дефинира процес на Марков, обикновено се нарича свойство на Марков; за първи път е формулиран от А. А. Марков, който в трудовете от 1907 г. положи основите за изследване на последователностите от зависими опити и сумите от произволни променливи, свързани с тях. Тази линия на изследване е известна като теория на веригите на Марков.

Основите на общата теория на процесите на Марков с непрекъснато време са положени от Колмогоров.

Марков имот

Общ случай

Нека бъде (Ω, F, P) (\displaystyle (\Omega,(\mathcal (F)),\mathbb (P)))- вероятностно пространство с филтриране (F t , t ∈ T) (\displaystyle ((\mathcal (F))_(t),\ t\in T))над някакъв (частично подреден) комплект T (\displaystyle T); остави (S , S) (\displaystyle (S,(\mathcal (S))))- измеримо пространство. произволен процес X = (X t , t ∈ T) (\displaystyle X=(X_(t),\ t\in T)), дефиниран върху филтрираното вероятностно пространство, се счита за удовлетворяващ Марков имотако за всеки A ∈ S (\displaystyle A\in (\mathcal (S)))и 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)\in A|(\mathcal (F))_(s))=\mathbb (P) (X_(t)\in A|X_(s)). )

Марков процесе случаен процес, който удовлетворява Марков имотс естествена филтрация.

За марковски вериги с дискретно време

Ако S (\displaystyle S)е дискретно множество и T = N (\displaystyle T=\mathbb (N) ), определението може да бъде преформулирано:

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),\) точки , X_(0)=x_(0))=\mathbb (P) (X_(n)=x_(n)|X_(n-1)=x_(n-1))).

Пример за процес на Марков

Помислете за прост пример за стохастичен процес на Марков. Една точка се движи произволно по оста x. В момент нула точката е в началото и остава там за една секунда. Секунда по-късно се хвърля монета - ако гербът е паднал, тогава точката X премества една единица дължина надясно, ако числото - наляво. Секунда по-късно монетата се хвърля отново и се прави същото произволно движение и т.н. Процесът на промяна на позицията на точката („лутане“) е случаен процес с дискретно време (t=0, 1, 2, ...) и изброим набор от състояния. Такъв случаен процес се нарича марковски, тъй като следващото състояние на точката зависи само от настоящото (текущо) състояние и не зависи от минали състояния (няма значение по кой път и за колко време точката е стигнала до текущата координата) .

Случайните процеси на Марков са кръстени на изключителния руски математик А.А. Марков (1856-1922), който първи започва изучаването на вероятностната връзка на случайните променливи и създава теория, която може да се нарече "вероятностна динамика". В бъдеще основите на тази теория станаха първоначалната основа за общата теория на случайните процеси, както и за такива важни приложни науки като теорията на дифузионните процеси, теорията на надеждността, теорията на опашките и др. В момента теорията на марковските процеси и нейните приложения намират широко приложение в различни области на науките като механика, физика, химия и др.

Поради сравнителната простота и яснота на математическия апарат, високата надеждност и точност на получените решения, процесите на Марков са получили специално внимание от специалисти, занимаващи се с изследване на операциите и теорията за вземане на оптимални решения.

Въпреки горната простота и яснота, практическото приложение на теорията на марковските вериги изисква познаване на някои термини и основни положения, които трябва да бъдат обсъдени преди представянето на примери.

Както бе споменато, стохастичните процеси на Марков са специални случаи на стохастични процеси (SP). От своя страна произволните процеси се основават на концепцията за случайна функция (SF).

Случайна функция е функция, чиято стойност за произволна стойност на аргумента е произволна променлива (CV). С други думи, SF може да се нарече функция, която при всеки тест приема някаква по-рано неизвестна форма.

Такива примери за SF са: колебания на напрежението в електрическата верига, скоростта на автомобил на участък от пътя с ограничение на скоростта, грапавостта на повърхността на част в определен участък и др.

Като правило се смята, че ако аргументът SF е време, тогава такъв процес се нарича случаен. Има и друго, по-близко до теорията за вземане на решения, дефиниция на случайните процеси. В същото време под случаен процес се разбира процес на произволна промяна в състоянията на всяка физическа или техническа система във времето или по някакъв друг аргумент.

Лесно е да се види, че ако обозначим състояние и изобразим зависимост, тогава такава зависимост ще бъде произволна функция.

Случайните процеси се класифицират според видовете състояния и аргумента t. В този случай произволните процеси могат да бъдат с дискретни или непрекъснати състояния или време.

В допълнение към горните примери за класификацията на случайните процеси има още едно важно свойство. Това свойство описва вероятностната връзка между състоянията на случайни процеси. Така например, ако при произволен процес вероятността за преход на системата към всяко следващо състояние зависи само от предишното състояние, тогава такъв процес се нарича процес без последващо въздействие.

Забележете, първо, че произволен процес с дискретни състояния и време се нарича произволна последователност.

Ако произволна последователност има свойството на Марков, тогава тя се нарича верига на Марков.

От друга страна, ако в случаен процес състоянията са дискретни, времето е непрекъснато и свойството след ефект е запазено, тогава такъв случаен процес се нарича процес на Марков с непрекъснато време.

Стохастичен процес на Марков се нарича хомогенен, ако вероятностите за преход остават постоянни по време на процеса.

Марковска верига се счита за дадена, ако са дадени две условия.

1. Има набор от вероятности за преход под формата на матрица:

2. Има вектор на началните вероятности

описващи първоначалното състояние на системата.

В допълнение към матричната форма, моделът на веригата на Марков може да бъде представен като насочена претеглена графика (фиг. 1).

Ориз. един

Наборът от състояния на веригата на Марков се класифицира по определен начин, като се вземе предвид по-нататъшното поведение на системата.

1. Необратим комплект (фиг. 2).

Фиг.2.

В случай на невъзвръщаем набор са възможни всякакви преходи в този набор. Системата може да напусне този набор, но не може да се върне към него.

2. Повтарящ се набор (фиг. 3).

Ориз. 3.

В този случай са възможни и всякакви преходи в рамките на набора. Системата може да влезе в този набор, но не може да го напусне.

3. Ергодичен комплект (фиг. 4).

Ориз. 4.

В случай на ергодичен набор са възможни всякакви преходи в рамките на множеството, но преходите от и към множеството са изключени.

4. Абсорбиращ комплект (фиг. 5)

Ориз. 5.

Когато системата влезе в този набор, процесът приключва.

В някои случаи, въпреки случайността на процеса, е възможно до известна степен да се контролират законите на разпределение или параметрите на вероятностите за преход. Такива вериги на Марков се наричат ​​контролирани. Очевидно с помощта на контролирани марковски вериги (MCC) процесът на вземане на решения става особено ефективен, което ще бъде разгледано по-късно.

Основната характеристика на дискретната марковска верига (DMC) е детерминираността на интервалите от време между отделните стъпки (етапи) на процеса. Това свойство обаче често не се наблюдава в реални процеси и интервалите се оказват случайни с някакъв закон на разпределението, въпреки че процесът остава марковски. Такива произволни последователности се наричат ​​полумаркови.

Освен това, като се има предвид наличието и отсъствието на определени набори от състояния, споменати по-горе, веригите на Марков могат да бъдат поглъщащи, ако има поне едно поглъщащо състояние, или ергодични, ако вероятностите за преход образуват ергодичен набор. От своя страна ергодичните вериги могат да бъдат редовни или циклични. Цикличните вериги се различават от обикновените по това, че в процеса на преходи през определен брой стъпки (цикли) има връщане в някакво състояние. Редовните вериги нямат това свойство.

Структура и класификация на системите за масови опашки

Системи за опашка

Често има нужда от решаване на вероятностни проблеми, свързани със системите за опашка (QS), примери за които могат да бъдат:

Билетни каси;

Ремонтни работилници;

Търговия, транспорт, енергийни системи;

Комуникационни системи;

Общността на такива системи се разкрива в единството на математическите методи и модели, използвани при изследването на тяхната дейност.

Ориз. 4.1. Основните области на приложение на TMT

Входът към QS получава поток от заявки за услуга. Например клиенти или пациенти, повреди на оборудване, телефонни обаждания. Заявките пристигат нередовно, в произволно време. Продължителността на услугата също е произволна. Това създава нередности в работата на QS, причинява претоварвания и недонатоварвания.

Системите за опашка имат различна структура, но обикновено могат да бъдат разграничени четири основни елемента:

1. Входящ поток на търсене.

2. Акумулатор (опашка).

3. Устройства (сервизни канали).

4. Изходен поток.

Ориз. 4.2. Обща схема на системите за опашка

Ориз. 4.3. Модел на работа на системата

(стрелките показват моментите на пристигане на изискванията в

система, правоъгълници - време за обслужване)

Фигура 4.3а показва модел на системата с редовен поток от изисквания. Тъй като интервалът между пристиганията на рекламации е известен, времето за обслужване се избира така, че да зареди напълно системата. За система със стохастичен поток от изисквания ситуацията е съвсем различна – изискванията идват в различни моменти от време и времето за обслужване също е случайна величина, която може да се опише с определен закон за разпределение (фиг. 4.3 б).

В зависимост от правилата за формиране на опашката се разграничават следните QS:

1) системи с повреди , при който, когато всички канали за обслужване са заети, заявката оставя системата необслужена;

2) системи с неограничена опашка , в който заявката влиза в опашката, ако към момента на пристигането й всички канали за обслужване са били заети;

3) системи с изчакване и ограничена опашка , при което времето за изчакване е ограничено от някои условия или има ограничения за броя на заявленията, стоящи на опашката.

Помислете за характеристиките на входящия поток от изисквания.

Потокът от заявки се нарича стационарен , ако вероятността един или друг брой събития да попаднат във времеви сегмент с определена дължина зависи само от дължината на този сегмент.

Потокът от събития се нарича протича без последствия , ако броят на събитията, попадащи в определен интервал от време, не зависи от броя на събитията, попадащи върху други.

Потокът от събития се нарича обикновени ако две или повече събития не могат да се случат едновременно.

Потокът от заявки се нарича Поасон (или най-простата), ако има три свойства: стационарна, обикновена и няма последствия. Името се дължи на факта, че при посочените условия броят на събитията, попадащи на всеки фиксиран интервал от време, ще бъде разпределен съгласно закона на Поасон.

интензивностпоток от приложения λ е средният брой приложения, идващи от потока за единица време.

За стационарен поток интензитетът е постоянен. Ако τ е средната стойност на интервала от време между две съседни заявки, тогава в случай на поток на Поасон, вероятността за влизане в услугата мискания за определен период от време тсе определя от закона на Поасон:

Времето между съседни заявки се разпределя експоненциално с плътност на вероятността

Времето за обслужване е произволна променлива и се подчинява на експоненциален закон за разпределение с плътност на вероятността, където μ е интензитетът на потока на услугата, т.е. средният брой обслужени заявки за единица време,

Съотношението на интензитета на входящия поток към интензитета на потока от услуги се нарича зареждане на системата

Системата за опашка е система от дискретен тип с краен или изброим набор от състояния и преходът на системата от едно състояние в друго става рязко, когато настъпи някакво събитие.

Процесът се нарича процес на дискретно състояние , ако възможните му състояния могат да бъдат преномерирани предварително и преходът на системата от състояние в състояние става почти мигновено.

Такива процеси са два вида: с дискретно или непрекъснато време.

В случай на дискретно време, преходите от състояние в състояние могат да се случват в строго определени моменти от време. Процесите с непрекъснато време се различават по това, че преминаването на системата в ново състояние е възможно по всяко време.

Случаен процес е съответствие, при което на всяка стойност на аргумента (в този случай момент от времевия интервал на експеримента) се приписва произволна променлива (в този случай състоянието на QS). Случайна величина се нарича величина, която в резултат на опит може да вземе една, но неизвестна предварително коя числена стойност от дадено числово множество.

Следователно, за да се решат проблемите на теорията на опашките, е необходимо да се проучи този случаен процес, т.е. да изгради и анализира своя математически модел.

произволен процесНаречен Марковски , ако за всеки момент от време вероятностните характеристики на процеса в бъдеще зависят само от състоянието му в момента и не зависят от това кога и как системата е дошла до това състояние.

Преходите на системата от състояние в състояние се случват под влияние на някои потоци (поток от приложения, поток от откази). Ако всички потоци от събития, които довеждат системата до ново състояние, са най-простият Поасон, тогава процесът, протичащ в системата, ще бъде марковски, тъй като най-простият поток няма следствие: в него бъдещето не зависи от миналото. - група шахматни фигури. Състоянието на системата се характеризира с броя на фигурите на противника, оставащи на дъската в момента. Вероятността в момента материалното предимство да бъде на страната на един от опонентите зависи преди всичко от състоянието на системата в момента, а не от това кога и в каква последователност фигурите са изчезнали от дъската до момента.

Лекция 9

Марковски процеси
Лекция 9
Марковски процеси



1

Марковски процеси

Марковски процеси
Случайният процес в системата се нарича
Марковски, ако няма последствия. Тези.
ако разгледаме текущото състояние на процеса (t 0) - като
настоящ, набор от възможни състояния ((s),s t) - като
минало, набор от възможни състояния ( (u),u t) - като
бъдеще, след това за Марков процес с фиксиран
настояще, бъдещето не зависи от миналото, а се определя
само присъства и не зависи от това кога и как системата
стигна до това състояние.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
2

Марковски процеси

Марковски процеси
Случайните процеси на Марков са кръстени на изключителния руски математик А. А. Марков, който първи започва изучаването на вероятностната връзка на случайните променливи
и създаде теория, която може да се нарече „динамика
вероятности." В бъдеще основите на тази теория бяха
първоначалната основа на общата теория на случайните процеси, както и на такива важни приложни науки като теорията на дифузионните процеси, теорията на надеждността, теорията на опашките и др.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
3

Марков Андрей Андреевич Марков Андрей Андреевич Марков Андрей Андреевич

Марковски процеси
Марков Андрей Андреевич
1856-1922
руски математик.
Написа около 70 доклада
теории
числа,
теории
приближения на функции, теории
вероятности. Значително разширен обхватът на закона
големи числа и централно
гранична теорема. Е
основател на теорията за случайните процеси.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
4

Марковски процеси

Марковски процеси
На практика обикновено са чисти марковски процеси
не се срещат. Но има процеси, за които влиянието на "праисторията" може да се пренебрегне и при изучаване
такива процеси могат да се прилагат модели на Марков. AT
В момента теорията на марковските процеси и нейните приложения се използват широко в различни области.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
5

Марковски процеси

Марковски процеси
Биология: процеси на раждане и смърт - популации, мутации,
епидемии.
Физика:
радиоактивен
разпада,
теория
броячи
елементарни частици, дифузионни процеси.
Химия:
теория
следи
в
ядрен
фотографски емулсии,
вероятностни модели на химическата кинетика.
Изображения.jpg
Астрономия: теория на флуктуациите
яркостта на млечния път.
Теория на опашките: телефонни централи,
сервизи, билетни каси, информационни гишета,
металорежещи машини и други технологични системи, системи за управление
гъвкави производствени системи, обработка на информация от сървъри.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
6

Марковски процеси

Марковски процеси
Нека в настоящия момент t0 системата е в
определено състояние S0. Знаем характеристиките
състояние на системата в настоящето и всичко, което беше при t< t0
(история на процеса). Можем ли да предвидим бъдещето
тези. какво се случва, когато t > t0?
Не точно, но някои вероятностни характеристики
процес в бъдеще може да бъде намерен. Например вероятността, че
че след известно време
система S ще бъде в състоянието
S1 или престой в състояние S0 и т.н.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
7

Марковски процеси. Пример.

Марковски процеси
Марковски процеси. Пример.
Система S - група самолети, участващи във въздушен бой. Нека x е числото
"червени" самолети, y е броят на "сините" самолети. До момента t0, броят на оцелелите (несвалени) самолети
съответно – x0, y0.
Интересуваме се от вероятността, че във времето
t 0 численото превъзходство ще бъде на страната на „червените“. Тази вероятност зависи от това в какво състояние е била системата.
в момент t0, а не от това кога и в каква последователност са загинали самолетите, свалени до момента t0.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
8

Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Марков процес с крайно или изброимо число
състояния и моменти от време се нарича дискретно
Марковска верига. Преходите от състояние в състояние са възможни само в цели числа.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
9

10. Дискретни марковски вериги. Пример

Марковски процеси

Да предположим
Какво
реч
отива
относно
последователни хвърляния на монети
игра "хвърляне"; монетата е хвърлена
условни моменти от време t =0, 1, ... и нататък
всяка стъпка играчът може да спечели ±1 s
същото
вероятност
1/2,
така
Така в момента t неговата обща печалба е произволна променлива ξ(t) с възможни стойности j = 0, ±1, ... .
При условие, че ξ(t) = k, на следващата стъпка печалбата ще бъде
вече е равно на ξ(t+1) = k ± 1, като приема стойностите j = k ± 1 със същата вероятност 1/2. Можем да кажем, че тук с подходяща вероятност има преход от състояние ξ(t) = k към състояние ξ(t + 1) = k ± 1.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
10

11. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Обобщавайки този пример, може да си представим система с
изброим брой възможни състояния, които с течение на времето
дискретното време t = 0, 1, ... преминава произволно от състояние в състояние.
Нека ξ(t) е неговата позиция в момент t в резултат на верига от произволни преходи
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
11

12. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
При анализиране на случайни процеси с дискретни състояния е удобно да се използва геометрична схема - графика
държави. Върховете на графа са състоянията на системата. Граф Аркс
– възможни преходи от състояние в състояние.
Играта "хвърляне".
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
12

13. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Означете всички възможни състояния с цели числа i = 0, ±1, ...
Да приемем, че при известно състояние ξ(t) =i, на следващата стъпка системата преминава в състояние ξ(t+1) = j с условна вероятност
P( (t 1) j (t) i)
независимо от нейното поведение в миналото, по-точно независимо от
от веригата от преходи до момента t:
P( (t 1) j (t) i; (t 1) it 1;...; (0) i0 )
P( (t 1) j (t) i)
Този имот се нарича Марковски.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
13

14. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
номер
pij P( (t 1) j (t) i)
наречена вероятност
преход на системата от състояние i в състояние j с една стъпка
момент от време t1.
Ако вероятността за преход не зависи от t, тогава веригата
Марков се нарича хомогенен.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
14

15. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Матрица P , чиито елементи са вероятности
преход pij , се нарича преходна матрица:
p11 ... p1n
P p 21 ... p 2n
стр
n1 ... pnn
Тя е стохастична, т.е.
pij 1 ;
и
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
p ij 0 .
15

16. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
Преходната матрица за играта "хвърляне"
...
k2
k2
0
k 1
1/ 2
к
0
k 1
к
k 1
k2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
Градинарят в резултат на химичен анализ на почвата оценява
състоянието й с едно от трите числа - добро (1), справедливо (2) или лошо (3). В резултат на наблюдения през годините градинарят забеляза
че продуктивността на почвата в ток
година зависи само от състоянието му в
предходната година. Следователно, вероятностите
преход на почвата от едно състояние в
друг може да бъде представен от следното
Марковска верига с матрица P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
17

18. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
Въпреки това, в резултат на агротехнически мерки, градинарят може да промени вероятностите за преход в матрицата P1.
Тогава матрицата P1 ще бъде заменена
към матрица P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
18

19. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Помислете как състоянията на процеса се променят с течение на времето. Ще разглеждаме процеса в последователни моменти от време, започвайки от момент 0. Нека зададем първоначалното разпределение на вероятностите p(0) ( p1 (0),..., pm (0)) , където m е броят на процеса състояния, pi (0) е вероятността за намиране
процес в състояние i в първоначалния момент. Вероятността pi (n) се нарича безусловна вероятност на състоянието
аз в момент n 1.
Компонентите на вектора p(n) показват кои от възможните състояния на веригата в момент n са най-много
вероятно.
м
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
pk (n) 1
k 1
19

20. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Познаването на последователността ( p (n)) за n 1,... ви позволява да получите представа за поведението на системата във времето.
В система с 3 състояния
п11 п12 п13
P стр21
стр
31
стр. 22
стр.32
стр23
стр.33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
Общо взето:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
к
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
к
p(n 1) p(n) P
20

21. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
Матрица
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Стъпка
(p(n))
н
0
1, 0, 0
н
1
0.2 , 0.5 , 0.3
н
2
0.04 , 0.35 , 0.61
н
3
0.008 , 0.195 , 0.797
н
4
0.0016 , 0.1015 , 0.8969
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
21

22. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
н
Преходна матрица в n стъпки 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
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
22

23. Дискретни марковски вериги

Марковски процеси
Дискретни марковски вериги
Как се държат веригите на Марков за n?
За хомогенна марковска верига при определени условия е валидно следното свойство: p (n) за n.
Вероятностите 0 не зависят от първоначалното разпределение
p(0) , но се определят само от матрицата P . В този случай се нарича стационарно разпределение, а самата верига се нарича ергодична. Свойството на ергодичност означава, че с нарастване на n
вероятността от състояния практически престава да се променя и системата преминава в стабилен режим на работа.
и
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
23

24. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
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
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
p()(0,0,1)
24

25. Дискретни марковски вериги. Пример

Марковски процеси
Дискретни марковски вериги. Пример
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)
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
25

26. Марковски процеси с непрекъснато време

Марковски процеси

Процесът се нарича непрекъснат времеви процес, ако
моментите на възможни преходи от състояние в състояние не са фиксирани предварително, а са несигурни, произволни и могат да възникнат
в някакъв момент.
Пример. Технологичната система S се състои от две устройства,
всеки от които в произволен момент от време може да излезе от
сграда, след което незабавно започва ремонтът на възела, също продължаващ за неизвестно, произволно време.
Възможни са следните състояния на системата:
S0 - и двете устройства работят;
S1 - първото устройство е в ремонт, второто работи правилно;
S2 - второто устройство е в ремонт, първото работи правилно;
S3 - и двете устройства са в ремонт.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
26

27. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
Настъпват преходи на системата S от състояние в състояние
почти мигновено, в случайни моменти на провал
всяко устройство или
край на ремонта.
Вероятността за едновременно
повреда на двете устройства
може да се пренебрегне.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
27

28. Потоци от събития

Марковски процеси
Потоци от събития
Поток от събития е последователност от хомогенни събития, следващи едно след друго в произволен момент.
е средният брой събития
Интензивността на потока от събития
за единица време.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
28

29. Потоци от събития

Марковски процеси
Потоци от събития
Поток от събития се нарича стационарен, ако неговите вероятностни характеристики не зависят от времето.
По-специално, интензивността
стационарният поток е постоянен. Потокът от събития неизбежно има концентрации или разреждане, но те не са от редовно естество, а средният брой събития за единица време е постоянен и не зависи от времето.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
29

30. Потоци от събития

Марковски процеси
Потоци от събития
Поток от събития се нарича поток без последствия, ако за
всякакви два неприпокриващи се времеви сегмента и броят на събитията, попадащи в единия от тях, не зависи от това колко събития са паднали върху другия. С други думи, това означава, че събитията, които образуват потока, се появяват в определени моменти.
време независимо един от друг и всеки породен от собствените си причини.
Поток от събития се нарича обикновен, ако вероятността за възникване на две или повече събития в елементарен интервал t е пренебрежимо малка в сравнение с вероятността за настъпване на едно
събития, т.е. събитията в него се появяват едно по едно, а не в групи от няколко наведнъж
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
30

31. Потоци от събития

Марковски процеси
Потоци от събития
Поток от събития се нарича най-прост (или стационарен Поасон), ако има три свойства наведнъж: 1) е стационарен, 2) е обикновен, 3) няма последствия.
Най-простият поток има най-простото математическо описание. Той свири сред потоците същия специален
роля, подобно на закона за нормалното разпределение между другите
закони за разпределение. А именно, когато има достатъчно голям брой независими, стационарни и обикновени
потоци (съпоставими един с друг по интензитет), се получава поток, близък до най-простия.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
31

32. Потоци от събития

Марковски процеси
Потоци от събития
За най-простия поток с интензивност
интервал
времето T между съседни събития има експоненциално
разпределение с плътност
p(x) e x , x 0 .
За произволна променлива T с експоненциално разпределение, математическото очакване е реципрочна стойност на параметъра.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
32

33. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
Като се имат предвид процеси с дискретни състояния и непрекъснато време, можем да приемем, че всички преходи на системата S от състояние в състояние се извършват под действието на
най-простите потоци на събития (потоци от повиквания, потоци за отказ, потоци за възстановяване и т.н.).
Ако всички потоци от събития, които прехвърлят система S от състояние в състояние, са най-простите, тогава процесът, протичащ в
система, ще бъде марковска.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
33

34. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
Нека системата в държавата бъде засегната от
най-простият поток от събития. Веднага щом се появи първото събитие от този поток, системата „скача“ от състоянието
в състояние.
- интензивността на потока от събития, превеждащ системата
извън държавата
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
в
.
34

35. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
Нека разглежданата система S има
възможни състояния
. Вероятността p ij (t) е вероятността за преминаване от състояние i в състояние j за време t.
Вероятност за i-то състояние
е вероятността, че
че в момент t системата ще бъде в състояние
. Очевидно е, че за всеки момент от време сумата
от всички вероятности за състояние е равно на едно:
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
35

36. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
Да се ​​намерят всички вероятности за състояния
като
функции на времето се съставят и решават диференциални уравнения на Колмогоров - специален вид уравнение, в което неизвестните функции са вероятностите на състоянията.
За вероятностите за преход:
p ij (t) p ik (t) kj
к
За безусловни вероятности:
p j (t) p k (t) kj
к
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
36

37. Колмогоров Андрей Николаевич

Марковски процеси
Колмогоров Андрей Николаевич
1903-1987
Страхотен руснак
математик.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
37

38. Марковски процеси с непрекъснато време

Марковски процеси
Марковски процеси с непрекъснато време
- процент на неуспех;
- интензивността на възстановителния поток.
Нека системата е в състояние
S0. Той се прехвърля в състояние S1 от потока
повреда на първото устройство. Интензивността му е
където
- Средно време на безотказна работа на устройството.
От състояние S1 към S0 системата се прехвърля от потока от възстановявания
първо устройство. Интензивността му е
където
- средно време за ремонт на първата машина.
По същия начин се изчисляват интензитетите на потоците от събития, които пренасят системата по всички дъги на графика.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
38

39. Системи за опашка

Марковски процеси

Примери за системи за опашка (QS): телефонни централи, сервизи,
билет
каси,
справка
бюрото,
машинни инструменти и други технологични системи,
системи
управление
гъвкав
производствени системи,
обработка на информация от сървъри и др.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
39

40. Системи за опашка

Марковски процеси
Системи за опашка
QS се състои от определен брой порции
единици, които се наричат ​​обслужващи канали (това са
машини, роботи, комуникационни линии, касиери и др.). Всяка CMO
е проектиран да обслужва потока от приложения (изисквания), пристигащи в произволно време.
Обслужването на заявката продължава за произволно време, след което каналът се освобождава и е готов за получаване на следващия.
приложения.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
40

41. Системи за опашка

Марковски процеси
Системи за опашка
Процесът на работа на QS е произволен процес с дискретен
състояния и непрекъснато време. Състоянието на QS се променя рязко в моментите на появата на някои събития
(пристигане на ново приложение, край на услугата, момент,
когато приложението, което е уморено от чакане, напусне опашката).
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
41

42. Системи за опашка

Марковски процеси
Системи за опашка
Класификация на системите за опашка
1. QS с откази;
2. CMO с опашка.
В QS с откази, иск, който пристига в момента, когато всички канали са заети, получава отказ, напуска QS и вече не е
обслужен.
В QS с опашка заявка, която пристига в момента, когато всички канали са заети, не напуска, а влиза в опашката и чака възможността да бъде обслужена.
QS с опашки са разделени на различни типове в зависимост от
за това как е организирана опашката - ограничена или неограничена. Ограниченията могат да се прилагат както за дължината на опашката, така и за времето
очаквания, "дисциплина на обслужването".
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
42

43. Системи за опашка

Марковски процеси
Системи за опашка
Предмет на теорията на опашките е конструкцията
математически модели, свързващи дадени условия
QS работа (брой канали, тяхната производителност, правила
работа, естеството на потока от приложения) с характеристиките, които ни интересуват - показатели за ефективността на QS. Тези индикатори описват способността на QS да се справя с потока
приложения. Те могат да бъдат: средният брой приложения, обслужвани от QS за единица време; среден брой заети канали; средният брой заявления в опашката; средно време на изчакване за обслужване и др.
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"
43

44.

БЛАГОДАРЯ ТИ
ЗА ВНИМАНИЕ!!!
44

45. Изградете графика на прехода

Марковски процеси
Изградете графика на прехода
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
ХНУРЕ, катедра. PM, преподавател Кириченко Л.О.
„Теория на вероятностите, математическа
статистика и случайни процеси"

Под произволен процесразбират промяната във времето на състоянията на някаква физическа система по неизвестен преди това случаен начин. При което под физическа система имаме предвидвсяко техническо средство, група устройства, предприятие, индустрия, биологична система и др.

произволен процеспротичащи в системата се наричат Марковски – ако за даден момент от време, вероятностните характеристики на процеса в бъдеще (t > ) зависи само от състоянието му в даден момент ( присъстват ) и не зависят от това кога и как системата е стигнала до това състояние в минало .(Например брояч на Гайгер, който регистрира броя на космическите частици).

Процесите на Марков обикновено се разделят на 3 типа:

1. Марковска верига – процес, чиито състояния са дискретни (т.е. могат да бъдат преномерирани), а времето, за което се разглежда, също е дискретно (т.е. процесът може да променя състоянията си само в определени моменти от време). Такъв процес протича (променя) на стъпки (с други думи, на цикли).

2. Дискретен марков процес - множеството от състояния е дискретно (може да се изброява), а времето е непрекъснато (преход от едно състояние в друго - по всяко време).

3. Непрекъснат процес на Марков – множеството състояния и времето са непрекъснати.

На практика процесите на Марков в чист вид не се срещат често. Често обаче се налага да се справяме с процеси, за които влиянието на праисторията може да бъде пренебрегнато. Освен това, ако всички параметри от "миналото", от които зависи "бъдещето", се включват в състоянието на системата в "настоящето", тогава тя също може да се счита за марковска. Това обаче често води до значително увеличаване на броя на взетите под внимание променливи и невъзможност за получаване на решение на проблема.

При оперативните изследвания т.нар Стохастични процеси на Марков с дискретни състояния и непрекъснато време.

Процесът се нарича процес на дискретно състояние, ако всичките му възможни състояния , ,... могат да бъдат изброени (преномерирани) предварително. Преходът на системата от състояние в състояние преминава почти мигновено - скок.

Процесът се нарича непрекъснат времеви процес, ако моментите на преход от състояние в състояние могат да приемат произволни стойности по оста на времето.

например : Техническо устройство S се състои от два възела , всеки от които в произволен момент от време може да се провали ( отказвам). След това ремонтът на възел започва незабавно ( възстановяване), което продължава произволно време.

Възможни са следните състояния на системата:

И двата възела са ОК;

Първият възел се ремонтира, вторият работи.

- вторият възел се ремонтира, първият работи

И двата възела се ремонтират.

Преходът на системата от състояние в състояние се случва в произволни моменти почти мигновено. Удобно е да се показват състоянията на системата и връзката между тях с помощта на графика на състоянието .

държави

Преходи

Преходи и отсъстват т.к повредите и възстановяването на елементите се случват независимо и произволно, а вероятността за едновременен отказ (възстановяване) на два елемента е безкрайно малка и може да се пренебрегне.

Ако всички потоци от събития превеждат системата Сот държава в държава протозои, тогава процес,протичащи в такава система ще бъде Марковски. Това се дължи на факта, че най-простият поток няма последващо действие, т.е. в него "бъдещето" не зависи от "миналото" и освен това има свойството на обикновеност - вероятността за едновременно възникване на две или повече събития е безкрайно малка, т.е. невъзможно е да се премине от състояние за състояние без преминаване на няколко междинни състояния.

За по-голяма яснота на графиката на състоянието е удобно да се запише интензитета на потока от събития, който прехвърля системата от състояние в състояние по дадената стрелка при всяка стрелка за преход ( - интензивността на потока от събития, който прехвърля системата от държавата в. Такава графика се нарича маркирани.

Използвайки обозначената графика на състоянията на системата, може да се изгради математически модел на този процес.

Помислете за преходите на системата от някакво състояние към предишното или следващото. Фрагмент от графиката на състоянието в този случай ще изглежда така:

Нека системата в момента те в състояние на.

Означете (t)- вероятност за i-то състояние на систематае вероятността системата в даден момент те в състояние на. За всеки момент от време t =1 е вярно.

Нека определим вероятността, че в момента t+∆t системата ще бъде в състояние. Това може да бъде в следните случаи:

1) и не го е напуснал през времето ∆ t. Това означава, че през времето ∆t не възникнасъбитие, което привежда системата в състояние (поток с интензитет) или събитие, което я привежда в състояние (поток с интензитет). Нека определим вероятността за това за малко ∆t.

Съгласно експоненциалния закон за разпределение на времето между две съседни изисквания, съответстващи на най-простия поток от събития, вероятността в интервала от време ∆t няма да възникнат изисквания в потока с интензитет λ1ще бъде равно на

Разширявайки функцията f(t) в ред на Тейлър (t>0), получаваме (за t=∆t)

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

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

По същия начин, за поток с интензитет λ 2 получаваме .

Вероятността на интервала от време ∆t (за ∆t®0) никое изискване няма да бъде равно на

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

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

По този начин вероятността системата да не е напуснала състоянието през времето ∆t, за малко ∆t ще бъде равна на

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

2) Системата беше в състояние S i -1 и за времето премина в състояние S i . Тоест, поне едно събитие се е случило в потока с интензитет. Вероятността за това е равна на най-простия поток с интензитет λ ще

В нашия случай вероятността за такъв преход ще бъде равна на

3)Системата беше в състояние и през времето ∆t преминава в състоянието . Вероятността за това ще бъде

Тогава вероятността системата в момент (t+∆t) да бъде в състояние S i е равна на

Извадете P i (t) от двете части, разделете на ∆t и, преминавайки до предела, с ∆t→0, получаваме

Замествайки съответните стойности на интензитетите на преходите от състояния към състояния, получаваме система от диференциални уравнения, описващи промяната в вероятностите на състоянията на системата като функции на времето.

Тези уравнения се наричат ​​уравнения Колмогоров-Чапман за дискретен марков процес.

След като зададем началните условия (например P 0 (t=0)=1,P i (t=0)=0 i≠0) и ги решим, получаваме изрази за вероятностите на състоянието на системата като функции от времето . Аналитични решения се получават сравнително лесно, ако броят на уравненията ≤ 2.3. Ако има повече от тях, тогава уравненията обикновено се решават числено на компютър (например по метода Runge-Kutta).

В теорията на случайните процеси доказано , Какво ако номер n състояния на системата със сигурност и от всеки от тях е възможно (в краен брой стъпки) да се премине към всеки друг, тогава има граница , към което клонят вероятностите кога t→ . Такива вероятности се наричат крайни вероятности състояния, а стационарното състояние - стационарен режим функциониране на системата.

Тъй като в стационарен режим всичко следователно всички =0. Приравнявайки левите части на системата от уравнения с 0 и допълвайки ги с уравнението =1, получаваме система от линейни алгебрични уравнения, решавайки които намираме стойностите на крайните вероятности.

Пример. Нека в нашата система степента на отказ и възстановяване на елементите е следната

Неуспехи 1ел:

2ел:

Ремонт 1ел:

2ел:

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

Решавайки тази система, получаваме

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

Тези. в неподвижно състояние системата средно

40% е в състояние S 0 (и двата възела са здрави),

20% - в състояние S 1 (1-ви елемент е в ремонт, 2-ри е в добро състояние),

27% - в състояние S 2 (2-ра електрическа е в ремонт, 1 е в добро състояние),

13% - в състояние S 3 - и двата елемента са в ремонт.

Познаването на крайните вероятности позволява Оценете средната производителност на системата и натоварването на ремонтните услуги.

Нека системата в състояние S 0 носи доход от 8 единици. за единица време; в държавата S 1 - доход 3 sr.u.; в състояние S 2 - доход 5; в състояние S 3 - доход \u003d 0

Цена ремонт за единица време за el-ta 1- 1 (S 1, S 3) арб. единици, el-ta 2- (S 2, S 3) 2 арб. След това в стационарен режим:

Системен доходза единица време ще бъде:

W max =8P 0 +3P 1 +5P 2 +0P 3 =8 0.4+3 0.2+5 0.27+0 0.13=5.15 c.u.

Разход за ремонтв единици време:

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 c.u.

печалбаза единица време

W \u003d W doh -W rem \u003d 5,15-1,39 = 3,76 единици

След като изразходвате определени разходи, е възможно да промените интензитета λ и μ и съответно ефективността на системата. Осъществимостта на такива разходи може да се оцени чрез преизчисляване на P i . и показатели за ефективност на системата.