Основные понятия марковских процессов

Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:

Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позицийполной определенности в настоящем и будущем.

Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.

Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .

Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».

Понятие случайного процесса

Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.

Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системеS протекаетслучайный процесс , если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.

Примеры: 1. СистемаS – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.

Марковский случайный процесс

Случайный процесс, протекающий в системе, называется Марковским , если для любого момента времениt 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный моментt 0 и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t 0 система находится в определенном состоянииS 0 . Мы знаем характеристики состояния системы в настоящеми все, что было приt <t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет приt >t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое времясистемаS окажется в состоянииS 1 или останется в состоянииS 0 и т.д.

Пример . СистемаS – группа самолетов, участвующих в воздушном бою. Пустьx – количество «красных» самолетов,y – количество «синих» самолетов. К моменту времениt 0 количество сохранившихся (не сбитых) самолетов соответственно –x 0 ,y 0 . Нас интересует вероятность того, что в момент временичисленный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времениt 0 , а не от того, когда и в какой последовательности погибали сбитые до моментаt 0 самолеты.

На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием «предистории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели (в теории массового обслуживания рассматриваются и не Марковские системы массового обслуживания, но математический аппарат, их описывающий, гораздо сложнее).

В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.

Процесс называется процессом с дискретным состоянием , если его возможные состоянияS 1 ,S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

Пример . Технологическая система (участок)S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:

S 0 - оба станка исправны;

S 1 - первый станок ремонтируется, второй исправен;

S 2 - второй станок ремонтируется, первый исправен;

S 3 - оба станка ремонтируются.

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

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом состояний . Вершины графа – состояния системы. Дуги графа – возможные переходы из состояния в

Рис.1. Граф состояний системы

состояние. Для нашего примера граф состояний приведен на рис.1.

Примечание. Переход из состояния S 0 вS 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.

Многие операции, которые приходится анализировать при выборе оптимального решения, развиваются как случайные процессы, зависящие от ряда случайных факторов.

Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применен математический аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов.

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

Пусть имеется некоторая система S, состояние которой меняется с течением времени (под системой S может пониматься все что угодно: промышленное предприятие, техническое устройство, ремонтная мастерская и т. д.). Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, говорят, что в системе S протекает случайный процесс.

Примеры случайных процессов:

флуктуации цен на фондовом рынке;

обслуживание клиентов в парикмахерской или ремонтной мастерской;

выполнение плана снабжения группы предприятий и т. д.

Конкретное протекание каждого из этих процессов зависит от ряда случайных, заранее непредсказуемых факторов, таких как:

поступление на фондовый рынок непредсказуемых известий о политических изменениях;

случайный характер потока заявок (требований), поступающих со стороны клиентов;

случайные перебои в выполнении плана снабжения и т. д.

ОПРЕДЕЛЕНИЕ. Случайный процесс, протекающий в системе, называется марковским (или процессом без последствия ), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом).

Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от “предыстории” процесса.

Рассмотрим пример. Пусть система S представляет собой фондовый рынок, который уже существует какое-то время. Нас интересует, как будет работать система в будущем. Ясно, по крайней мере в первом приближении, что характеристики работы в будущем (вероятности падения цен конкретных акций через неделю) зависят от состояния системы в настоящий момент (здесь могут вмешаться самые различные факторы типа решений правительства или результатов выборов) и не зависят от того, когда и как система достигла своего настоящего состояния (не зависят от характера движения цен на эти акции в прошлом).

На практике часто встречаются случайные процессы, которые, с той или другой степенью приближения можно считать марковскими.

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

Марковские случайные процессы подразделяются на классы в зависимости от того, как и в какие моменты времени система S" может менять свои состояния.

ОПРЕДЕЛЕНИЕ. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы s x , s 2 , s v ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Например, разработку проекта S осуществляют совместно два отдела, каждый из которых может совершить ошибку. Возможны следующие состояния системы:

5, - оба отдела работают нормально;

s 2 - первый отдел совершил ошибку, второй работает нормально;

s 3 - второй отдел совершил ошибку, первый работает нормально;

s 4 - оба отдела совершили ошибку.

Процесс, протекающий в системе, состоит в том, что она случайным образом в какие-то моменты времени переходит («перескакивает») из состояния в состояние. Всего у системы четыре возможных состояния. Перед нами - процесс с дискретными состояниями.

Кроме процессов с дискретными состояниями существуют случайные процессы с непрерывными состояниями : для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями.

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

При анализе случайных процессов с дискретными состояниями очень удобно пользоваться геометрической схемой - так называемым графом состояний. Граф состояний геометрически изображает возможные состояния системы и ее возможные переходы из состояния в состояние.

Пусть имеется система S с дискретными состояниями:

Каждое состояние будем изображать прямоугольником, а возможные переходы (“перескоки”) из состояния в состояние - стрелками, соединяющими эти прямоугольники. Пример графа состояния приведен на рис. 4.1.

Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния s 2 в 5 3 только через s y то стрелками отмечаются только переходы s 2 -> и л, 1 -> 5 3 , но не s 2 -» s y Рассмотрим несколько примеров:

1. Система S - фирма, которая может находиться в одном из пяти возможных состояний: s ] - работает с прибылью;

s 2 - утратила перспективу развития и перестала приносить прибыль;

5 3 - стала объектом для потенциального поглощения;

s 4 - находится под внешним управлением;

s 5 - имущество ликвидируемой фирмы продается на торгах.

Граф состояний фирмы показан на рис. 4.2.

Рис. 4.2

• 2. Система S - банк, имеющий два отделения. Возможны следующие состояния системы:
• 5, - оба отделения работают с прибылью;

s 2 - первое отделение работает без прибыли, второе работает с прибылью;

5 3 - второе отделение работает без прибыли, первое работает с прибылью;

s 4 - оба отделения работают без прибыли.

Предполагается, что улучшение состояния не происходит.

Граф состояний представлен на рис. 4.3. Отметим, что на графе не показан возможный переход из состояния s ] непосредственно в s 4 , который осуществится, если банк сразу будет работать в убыток. Возможностью такого события можно пренебречь, что и подтверждает практика.

Рис. 4.3

3. Система S - инвестиционная компания, состоящая из двух трейдеров (отделов): I и II; каждый из них может в какой-то момент времени начать работать в убыток. Если это происходит, то руководство компании немедленно принимает меры для восстановления прибыльной работы отдела.

Возможные состояния системы: s - деятельность обоих отделов прибыльна; s 2 - первый отдел восстанавливается, второй работает с прибылью;

s 3 - первый отдел работает с прибылью, второй восстанавливается;

s 4 - оба отдела восстанавливаются.

Граф состояний системы показан на рис. 4.4.

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

Состояния системы будем для удобства нумеровать не одним, а двумя индексами; первый будет означать состояния первого трейдера (1 - работает с прибылью, 2 - его деятельность изучается руководством, 3 - восстанавливает прибыльную деятельность отдела); второй - те же состояния для второго трейдера. Например, s 23 будет означать: деятельность первого трейдера изучается, второй - восстанавливает прибыльную работу.

Возможные состояния системы S:

s u - деятельность обоих трейдеров приносит прибыль;

s l2 - первый трейдер работает с прибылью, деятельность второго изучается руководством компании;

5 13 - первый трейдер работает с прибылью, второй восстанавливает прибыльную деятельность отдела;

s 2l - деятельность первого трейдера изучается руководством, второй работает с прибылью;

s 22 - деятельность обоих трейдеров изучается руководством;

• 5 23 - работа первого трейдера изучается, второй трейдер восстанавливает прибыльную деятельность отдела;
• 5 31 - первый трейдер восстанавливает прибыльную деятельность отдела, второй работает с прибылью;
• 5 32 - прибыльная деятельность отдела восстанавливается первым трейдером, работа второго трейдера изучается;
• 5 33 - оба трейдера восстанавливают прибыльную работу своего отдела.

Всего девять состояний. Граф состояний показан на рис. 4.5.

Для системы массового обслуживания характерен случайный процесс. Изучение случайного процесса, протекающего в системе, выражение его математически и является предметом теории массового обслуживания.

Математический анализ работы системы массового обслуживания значительно облегчается, если случайный процесс этой работы является марковским. Процесс, протекающий в системе, называется марковским, если в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние. При исследовании экономических систем наибольшее применение имеют марковские случайные процессы с дискретными и непрерывными состояниями.

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

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

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

В исследовании систем массового обслуживания большое значение имеют случайные марковские процессы с дискретными состояниями и непрерывным временем.

Исследование марковских процессов сводится к изучению матриц переходных вероятностей (). Каждый элемент такой матрицы (поток событий) представляет собой вероятность перехода из заданного состояния (которому соответствует строка) к следующему состоянию (которому соответствует столбец). В этой матрице предусмотрены все возможные переходы данного множества состояний. Следовательно, процессы, которые можно описывать и моделировать с помощью матриц переходных вероятностей, должны обладать зависимостью вероятности конкретного состояния от непосредственно предшествующего состояния. Так выстраивается цепь Маркова. При этом цепью Маркова первого порядка называется процесс, для которого каждое конкретное состояние зависит только от его предшествующего состояния. Цепью Маркова второго и более высоких порядков называется процесс, в котором текущее состояние зависит от двух и более предшествующих.

Ниже представлены два примера матриц переходных вероятностей.

Матрицы переходных вероятностей можно изобразить графами переходных состояний, как показано на рисунке.

Пример

Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия.

В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1):

Первая итерация – построение матрицы двухступенчатых переходов.

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна

Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна

Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна

В результате расчетов получаем матрицу двухступенчатых переходов:

Результат достигается перемножением матрицы т,на матрицу с такими же значениями вероятностей:

Для проведения этих процедур в среде Excel необходимо выполнить следующие действия:

• 1) формировать матрицу;
• 2) вызывать функцию МУМНОЖ;
• 3) указывать первый массив – матрицу;
• 4) указывать второй массив (эта же матрица или другая);
• 5) ОК;
• 6) выделить зону новой матрицы;
• 7) F2;
• 8) Ctrl+Shift+Enter;
• 9) получить новую матрицу.

Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид:

Таким образом, в ближайшие два месяца работы предприятия вероятность получения прибыли от выпуска продукта выше, по сравнению с вероятностью получения убытка. Однако следует заметить, что вероятность получения прибыли падает, поэтому предприятию необходимо осуществить разработку нового продукта для замены производимого продукта.

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

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

Марковские процессы принято делить на 3 вида:

1. Марковская цепь – процесс, состояния которого дискретны (т.е. их можно перенумеровать), и время, по которому он рассматривается, также дискретно (т.е. процесс может менять свои состояния только в определенные моменты времени). Такой процесс идет (изменяется) по шагам (иначе - по тактам).

2. Дискретный марковский процесс – множество состояний дискретно (можно перечислить), а время непрерывно (переход из одного состояния в другое – в любой момент времени).

3. Непрерывный марковский процесс – множество состояний и время -непрерывные.

На практике Марковские процессы в чистом виде встречаются не часто. Однако нередко приходится иметь место с процессами, для которых влиянием предыстории можно пренебречь. Кроме того, если все параметры из «прошлого»,от которых зависит «будущее» включить в состоянии системы в «настоящем», то ее также можно рассматривать как Марковскую. Однако это часто приводит к значительному росту числа учитываемых переменных и невозможности получить решение задачи.

В исследование операций большое значение занимают так называемые Марковские случайные процессы с дискретными состояниями и непрерывным временем .

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

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

Например : Техническое устройство S состоит из двух узлов , каждый из которых в случайный момент времени может выйти из строя (отказать ). После этого мгновенно начинается ремонт узла (восстановление ),который продолжается случайное время.

Возможны следующие состояния системы:

Оба узла исправны;

Первый узел ремонтируется,второй исправен.

– второй узел ремонтируется,первый исправен

Оба узла ремонтируются.

Переход системы из состояния в состояние происходит в случайные моменты времени практически мгновенно. Состояния системы и связь между ними удобно отобразить с помощью графа состояний .

Состояния

Переходы

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

Если все потоки событий, переводящие систему S из состояния в состояние –простейшие , то процесс, протекающий в такой системе будетМарковским . Это обуславливается тем, что простейший поток не обладает последействием, т.е. в нем «будущее» не зависит от «прошлого» и, кроме того, он обладает свойством ординарности – вероятность одновременного появления двух и более событий бесконечно мала, т.е невозможен переход из состояния в состояние, минуя несколько промежуточных состояний.

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

Используя размеченный граф состояний системы можно построить математическую модель данного процесса.

Рассмотрим переходы системы из некоторого состояния в предыдущее или последующее . Фрагмент графа состояний в этом случае будет выглядеть следующим образом:

Пусть система в момент времени t находится в состоянии .

Обозначим (t)- вероятность i-ого состояния системы – вероятность того, что система в момент времени t находится в состоянии . Для любого момента времени 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 + б.м.

Таким образом, вероятность того, что система за время ∆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. Если их больше, то обычно решают уравнения численно- на ЭВМ (например методом Рунге-Кутта).

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

Так как в стационарном режиме все , следовательно, все =0. Приравняв в системе уравнений левые части 0 и, дополнив их уравнением =1, получим систему линейных алгебраических уравнений, решив которую найдём значения финальных вероятностей.

Пример. Пусть в нашей системе интенсивности отказов и восстановления элементов следующие

Отказы 1эл:

2эл:

Ремонт 1эл:

2эл:

P 0 +P 1 +P 2 +P 3 =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

Решив данную систему, получим

P 0 =6/15=0.4; P 1 =3/15=0.2; P 2 =4/15=0.27; P 3 =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 усл.ед.; в состоянии S 2 - доход 5;в состоянии S 3 -доход=0

Стоимость ремонта в единицу времени для эл-та 1- 1(S 1, S 3) усл.ед., эл-та 2- (S 2, S 3) 2 усл.ед. Тогда в стационарном режиме:

Доход системы в единицу времени будет:

W дох =8P 0 +3P 1 +5P 2 +0P 3 =8·0.4+3·0.2+5·0.27+0·0.13=5.15 усл.ед.

Стоимость ремонта в ед. времени:

W рем =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0·0.4+1·0.2+2·0.27+3·0.13=1.39 усл.ед.

Прибыль в единицу времени

W= W дох -W рем =5.15-1.39=3.76 усл.ед

Проведя определённые расходы можно изменить интенсивности λи μ и, соответственно, эффективность системы. Целесообразность таких расходов можно оценить, проведя пересчёт P i . и показателей эффективности системы.

МАРКОВСКИЙ ПРОЦЕСС

Процесс без последействия, - случайный процесс , эволюция к-рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот фиксировано (короче: "будущее" н "прошлое" процесса не зависят друг от друга при известном "настоящем").

Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .

Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т - подмножество действительной оси Пусть N t (соответственно N t ).есть s-алгебра в порожденная величинами X(s).при где Другими словами, N t (соответственно N t ) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t). Процесс X(t).наз. марковским процессом, если (почти наверное) для всех выполняется марковское свойство:

или, что то же самое, если для любых

М. п., для к-рого Тсодержится в множестве натуральных чисел, наз. Маркова цепью (впрочем, последний термин чаще всего ассоциируется со случаем не более чем счетного Е). Если Тявляется интервалом в а Ене более чем счетно, М. п. наз. цепью Маркова с непрерывным временем. Примеры М. п. с непрерывным временем доставляются диффузионными процессами и процессами с независимыми приращениями, в том числе пуассоновским и винеровским.

В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).

Пусть заданы:

а) где s-алгебра содержит все одноточечные множества в Е;

б) измеримое снабженное семейством s-алгебр таких, что если

в) (" ") x t =x t (w), определяющая при любых измеримое отображение

г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и

Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное

каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В ) - переходная функция или вероятность перехода процесса X(t). Если Енаделено топологией, а - совокупность борелевских множеств в Е, то принято говорить, что М. п. задан в Е. Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.

Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x ; t, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть

Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N, наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t , к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых

Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное

для Переходной функцией процесса X(t).считается Р(t, x, В ), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t можно заменить s-алгеброй , равной пересечению пополнений F t по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное ") и рассматривают марковскую случайную функцию где - мера на заданная равенством

М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое в где есть s-алгебра

борелевских подмножеств в . Непрерывные справа М. п. прогрессивно измеримы. Существует способ сводить неоднородный случай к однородному (см. ), и в дальнейшем речь будет идти об однородных М. п.

Строго . Пусть в измеримом пространстве задан М. п.

Функция наз. марковским моментом, если для всех При этом относят к семейству F t , если при (чаще всего F t интерпретируют как совокупность событий, связанных с эволюцией X(t).до момента т). Для полагают

Прогрессивно измеримый М. п. Xназ. строго марковским процессом (с. м. п.), если для любого марковского момента т и всех и соотношение

(строго марковское свойство) выполняется -почти наверное на множестве W t . При проверке (5) достаточно рассматривать лишь множества вида где в этом случае С. м. п. является, напр., любой непрерывный справа феллеровский М. п. в топологич. пространстве Е. М. п. наз. феллеровским марковским процессом, если функция

непрерывна всякий раз, когда f непрерывна и ограничена.

В классе с. м. п. выделяются те или иные подклассы. Пусть марковская Р(t, x, В ), заданная в метрическом локально компактном пространстве Е, стохастически непрерывна:

для любой окрестности Uкаждой точки Тогда если операторы переводят в себя непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В ).отвечает стандартный М. п. X, т. е. непрерывный справа с. м. п., для к-рого

Обрывающийся марковский процесс. Нередко физич. системы целесообразно описывать с помощью необрывающегося М. п., но лишь на временном интервале случайной длины. Кроме того, даже простые преобразования М. п. могут привести к процессу с траекториями, заданными на случайном интервале (см. Функционал от марковского процесса). Руководствуясь этими соображениями, вводят понятие обрывающегося М. п.

Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t (w) задается лишь для ) посредством равенства a F t определяется как в множестве

Набор где наз. обрывающимся марковским процессом (о. м. п.), полученным из с помощью обрыва (или убивания) в момент z. Величина z наз. моментом обрыва, или временем жизни, о. м. п. Фазовым пространством нового процесса служит где есть след s-алгебры в Е. Переходная функция о. м. п.- это сужение на множество Процесс X(t).наз. строго марковским процессом, или стандартным марковским процессом, если соответствующим свойством обладает Необрывающийся М. п. можно рассматривать как о. м. п. с моментом обрыва Неоднородный о. м. п. определяется аналогичным образом. М.

Марковские процессы и . М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная р(s, x, t, у ).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:

Функция р(s, x, t, у ).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса L(s, x ) = L (x).на гладких функциях совпадает с характеристич. оператором М. п. (см. Переходных операторов полугруппа ).

Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s уравнению (6) и условию

Аналогично, функция

удовлетворяет при s уравнению

и условию и 2 ( Т, x ) = 0.

Пусть тt - момент первого достижения границы дD области траекторией процесса Тогда при нек-рых условиях функция

удовлетворяет уравнению

и принимает значения ср на множестве

Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка

при довольно общих предположениях может быть записано в виде

В случае, когда Lи функции с, f не зависят от s, аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция

при нек-рых предположениях есть задачи

В случае, когдгг оператор Lвырождается (del b(s, х ) = 0 ).или дD недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.

Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений, абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.

Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x ), то вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.

В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.

Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, . - Теоретическая . 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в

Марковский процесс - дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2½x1t1) того, что… … Экономико-математический словарь

Марковский процесс - Дискретный или непрерывный случайный процесс X(t) , который можно полностью задать с помощью двух величин: вероятности P(x,t) того, что случайная величина x(t) в момент времени t равна x и вероятности P(x2, t2?x1t1) того, что если x при t = t1… … Справочник технического переводчика

Важный специальный вид случайных процессов. Примером марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Большой Энциклопедический словарь - Markovo procesas statusas T sritis automatika atitikmenys: angl. Markovprocess vok. Markovprozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus markovien, m … Automatikos terminų žodynas

марковский процесс - Markovo vyksmas statusas T sritis fizika atitikmenys: angl. Markov process; Markovian process vok. Markow Prozeß, m; Markowscher Prozeß, m rus. марковский процесс, m; процесс Маркова, m pranc. processus de Markoff, m; processus marcovien, m;… … Fizikos terminų žodynas

Важный специальный вид случайных процессов. Примером Марковского процесса может служить распад радиоактивного вещества, где вероятность распада данного атома за малый промежуток времени не зависит от течения процесса в предшествующий период.… … Энциклопедический словарь

Важный специальный вид случайных процессов (См. Случайный процесс), имеющих большое значение в приложениях теории вероятностей к различным разделам естествознания и техники. Примером М. п. может служить распад радиоактивного вещества.… … Большая советская энциклопедия

Выдающееся открытие в области математики, сделанное в 1906 русским ученым А.А. Марковым.