Простейшие потоки марковские процессы и цепи решение. Потоки событий марковские случайные процессы потоки событий

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

Особенности фактора случайности

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

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

Сущностные особенности не запланированного фактора

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

• колебания в цепи;
• скорость движения;
• шероховатость поверхности на заданном участке.

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

Детальный разбор понятия случайности

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

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

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

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

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

Подробное токование понятия

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

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

Структурный разбор процессов

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

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

Описание дискретного состояния и непрерывности времени

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

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

Моделирование данного процесса

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

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

Вероятностные теории

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

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

Примеры теории вероятности

Примерами Марковских процессов в данной ситуации могут выступать:

• кафе;
• билетные кассы;
• ремонтных цеха;
• станции различного назначения и пр.

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

Скрытые модели процесса

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

Сущностное раскрытие скрытых Марковских моделей

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

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

Стационарный Марковский процесс

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

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

СМО – система, подразумевающая наличие в ней 2х процессов: поступления заявок и обслуживания заявок.

Условно схема представляется в виде

И Накопитель К

Обслуживающий прибор

Процесс поступления заявок – процесс по времени.

Поток событий – последовательность моментов времени наступления каких-либо событий.

С любой СМО связаны 3 потока:

1) входной поток. Последовательность моментов времени поступления заявок

2) выходной поток. Последовательность моментов времени ухода обслужившихся заявок.

3) поток обслуживаний. Последовательность моментов времени окончания ослуживания заявок в предположении что обслуживание осуществляется непрерывно.

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

Поток наз-ся регулярным , если интервалы времени между событиями в нём одинаковы. Нерегулярный – если интервалы времени м\ду событиями – случайные величины.

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

Поток наз-ся однородным , если он х-ся только множеством {ti} наступивших событий. Неоднородный – если он описывается множеством {ti,fi}, где ti – моменты времени наступления событий, fi – признак заявки.

Сами СМО подразделяются на СМО с отказами и СМО с очередями . СМО с очередями подразделяется на с ограниченной очередью и с неограниченной очередью. Частный случай – ограниченное время ожидания в очереди.

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

1) FIFO (first in – first out) – в порядке поступления;

2) LIFO (last in – first out) – первой обслуживается поступившая последней;

3) SIRO (service in random order) – в случайном порядке;

4) – приоритетные системы. (абсолютный и относительный приоритеты. При относительном заявки выстраиваются по значению приоритета – вначале высокие, потом ниже.)

Для краткой характеристики СМО Д.Кендалл ввел символику (нотацию)

m - число обслуживающих каналов;

n – количество мест ожидания (емкость накопителя).

k – кол-во источников.

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

А и В могут принимать значения:

D – детерминированное распределение;

М – показательное;

Е r – распределение Эрланга;

H r - гиперпоказательное;

G – распределение общего вида.

При этом подразумевается, что потоки являются рекуррентными , т.е. интервалы между событиями независимы и имеют одинаковое распределение. Обязательными в нотации являются первых 3 позиции. По умолчанию если n отсутствует имеем систему с отказами, если отсутствует k, то по умолчанию – один источник.

9. Простейший поток, его свойства и значение при исследовании смо.

Поток, удовлетворяющий следующим трем требованиям, называются простейшим.

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

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

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

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

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

вероятность того, что за интервал времени τ произойдет ровно m событий.

Условие отсутствие последствия (заявки поступают независимо друг от друга) наиболее существенно для простейшего потока.

пуассоновского распределения.

Вероятность того, что за не произойдет не одного события

Вероятность, что за времяпроизойдет хотя бы одно событие

Иногда удобней анализировать систему, рассматривая интервалы между событиями T:

Это показательный закон с интенсивностью .

Математическое ожидание и среднее квадратичное для T:

Свойство отсутствие последействия позволяет использовать для исследования простейшего потока аппарат Марковских цепей.

Введем состояния системы следующим образом – считаем систему, находящейся в состоянии S, если в момент времени t в системе находится S заявок.

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

(S=0, 1, 2…)

Разлагая в ряд, получим:

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

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

Простейшие или близкие к ним потоки часто встречаются на практике.

При суммировании достаточно большого кол-ва потоков с последействием, получается поток с последействием. В простейшем потоке приблизительно 68% маленьких интервалов

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

10. Непрерывно-стохастические модели (Q -схемы). Одноканальная СМО с блокировкой. Построение графа состояний .

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

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

В СМО можно выделить два стохастических процесса:

Поступление заявок на обслуживание;

Обслуживание заявок.

Поток событий – последовательность событий, происходящих одно за другим в некоторые моменты времени. В СМО будем выделять два потока:

Входной поток: множество моментов времени поступления в систему заявок;

Поток обслуживания: множество моментов окончания обработки системой заявок.

В общем случае СМО элементарного вида может быть представлено следующим образом

Обслуживающий прибор

И – источник;

О – очередь;

К – канал обслуживания.

Одноканальная СМО с блокировкой . Система M / M / 1/ n

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

Считаем, что теперь входной поток пуассоновский с интенсивностью, а поток обслуживания – пуассоновский с интенсивностью.

Как и прежде, дисциплина обслуживания FIFO с блокировкой источника.

Состояние – число заявок в системе.

Всего возможно n +3 состояния: от 0 до n +2 .

Обозначим
- вероятность прихода за
i заявок;

- вероятность обслуживания за
i заявок.

ввиду ординарное

Аналогично

+
=

1-
+

Система уравнений:
и
- вероятности состояний.

при
получим

Ввиду стационарности потоков имеем:

и
,

Аналогично для остальных строк системы.

Окончательно имеем:

Получена система алгебраических уравнений.

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

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

i=0, 1,….n+1

Обозначим

,

Используем уравнеие нормировки

;

;

Это сумма геометрической прогрессии:

Cреднее время обсл. заявки

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

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

Когда событий много и они следуют друг за другом, то они образуют поток . Заметим, что события при этом должны быть однородными, то есть похожими чем-то друг на друга. Например, появление водителей на АЗС, желающих заправить свой автомобиль. То есть, однородные события образуют некий ряд. При этом считается, что статистическая характеристика этого явления (интенсивность потока событий) задана. Интенсивность потока событий указывает, сколько в среднем происходит таких событий за единицу времени. Но когда именно произойдет каждое конкретное событие надо определить методами моделирования. Важно, что, когда мы сгенерируем, например, за 200 часов 1000 событий, их количество будет равно примерно величине средней интенсивности появления событий 1000/200 = 5 событий в час, что является статистической величиной, характеризующей этот поток в целом.

Интенсивность потока в некотором смысле является математическим ожиданием количества событий в единицу времени. Но реально может так оказаться, что в один час появится 4 события, в другой — 6, хотя в среднем получается 5 событий в час, поэтому одной величины для характеристики потока недостаточно. Второй величиной, характеризующей насколько велик разброс событий относительно математического ожидания, является, как и ранее, дисперсия. Собственно именно эта величина определяет случайность появления события, слабую предсказуемость момента его появления. Про эту величину мы расскажем в следующей лекции.

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

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

Интенсивность потока λ — это среднее число событий в единицу времени. Интенсивность потока можно рассчитать экспериментально по формуле: λ = N /T н , где N — число событий, произошедших за время наблюдения T н .

Если интервал между событиями τ j равен константе или определен какой-либо формулой в виде: t j = f (t j – 1) , то поток называется детерминированным . Иначе поток называется случайным .

Случайные потоки бывают:

• ординарные : вероятность одновременного появления двух и более событий равна нулю;
• стационарные : частота появления событий λ (t ) = const(t ) ;
• без последействия : вероятность появления случайного события не зависит от момента совершения предыдущих событий.

Пуассоновский поток

За эталон потока в моделировании принято брать пуассоновский поток .

Пуассоновский поток — это ординарный поток без последействия.

Как ранее было указано, вероятность того, что за интервал времени (t 0 , t 0 + τ ) произойдет m событий, определяется из закона Пуассона:

где a — параметр Пуассона.

Если λ (t ) = const(t ) , то это стационарный поток Пуассона (простейший). В этом случае a = λ · t . Если λ = var(t ) , то это нестационарный поток Пуассона .

Для простейшего потока вероятность появления m событий за время τ равна:

Вероятность непоявления (то есть ни одного, m = 0 ) события за время τ равна:

Рис. 28.2 иллюстрирует зависимость P 0 от времени. Очевидно, что чем больше время наблюдения, тем вероятность непоявления ни одного события меньше. Кроме того, чем более значение λ , тем круче идет график, то есть быстрее убывает вероятность. Это соответствует тому, что если интенсивность появления событий велика, то вероятность непоявления события быстро уменьшается со временем наблюдения.

Вероятность появления хотя бы одного события (P ХБ1С ) вычисляется так:

так как P ХБ1С + P 0 = 1 (либо появится хотя бы одно событие, либо не появится ни одного, — другого не дано).

Из графика на рис. 28.3 видно, что вероятность появления хотя бы одного события стремится со временем к единице, то есть при соответствующем длительном наблюдении события таковое обязательно рано или поздно произойдет. Чем дольше мы наблюдаем за событием (чем более t ), тем больше вероятность того, что событие произойдет — график функции монотонно возрастает.

Чем больше интенсивность появления события (чем больше λ ), тем быстрее наступает это событие, и тем быстрее функция стремится к единице. На графике параметр λ представлен крутизной линии (наклон касательной).

Если увеличивать λ , то при наблюдении за событием в течение одного и того же времени τ , вероятность наступления события возрастает (см. рис. 28.4 ). Очевидно, что график исходит из 0, так как если время наблюдения бесконечно мало, то вероятность того, что событие произойдет за это время, ничтожна. И наоборот, если время наблюдения бесконечно велико, то событие обязательно произойдет хотя бы один раз, значит, график стремится к значению вероятности равной 1.

Изучая закон, можно определить, что: m x = 1/λ , σ = 1/λ , то есть для простейшего потока m x = σ . Равенство математического ожидания среднеквадратичному отклонению означает, что данный поток — поток без последействия. Дисперсия (точнее, среднеквадратичное отклонение) такого потока велика. Физически это означает, что время появления события (расстояние между событиями) плохо предсказуемо, случайно, находится в интервале m x – σ < τ j < m x + σ . Хотя ясно, что в среднем оно примерно равно: τ j = m x = T н /N . Событие может появиться в любой момент времени, но в пределах разброса этого момента τ j относительно m x на [–σ ; +σ ] (величину последействия). На рис. 28.5 показаны возможные положения события 2 относительно оси времени при заданном σ . В данном случае говорят, что первое событие не влияет на второе, второе на третье и так далее, то есть последействие отсутствует.

По смыслу P равно r (см. лекцию 23. Моделирование случайного события. Моделирование полной группы несовместных событий), поэтому, выражая τ из формулы (*) , окончательно для определения интервалов между двумя случайными событиями имеем:

τ = –1/λ · Ln(r ) ,

где r — равномерно распределенное от 0 до 1 случайное число, которое берут из ГСЧ, τ — интервал между случайными событиями (случайная величина τ j ).

Пример 1 . Рассмотрим поток изделий, приходящих на технологическую операцию. Изделия приходят случайным образом — в среднем восемь штук за сутки (интенсивность потока λ = 8/24 [ед/час] ). Необходимо промоделировать этот процесс в течение T н = 100 часов . m = 1/λ = 24/8 = 3 , то есть в среднем одна деталь за три часа. Заметим, что σ = 3 . На рис. 28.6 представлен алгоритм, генерирующий поток случайных событий.

На рис. 28.7 показан результат работы алгоритма — моменты времени, когда детали приходили на операцию. Как видно, всего за период T н = 100 производственный узел обработал N = 33 изделия. Если запустить алгоритм снова, то N может оказаться равным, например, 34, 35 или 32. Но в среднем, за K прогонов алгоритма N будет равно 33.33… Если посчитать расстояния между событиями t сi и моментами времени, определяемыми как 3 · i , то в среднем величина будет равна σ = 3 .

Моделирование неординарных потоков событий

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

Допустим, что M k = 10 , σ = 4 (то есть, в среднем в 68 случаях из 100 приходит от 6 до 14 вагонов в составе поезда) и их число распределено по нормальному закону. В место, отмеченное (*) в предыдущем алгоритме (см. рис. 28.6 ), нужно вставить фрагмент, показанный на рис. 28.8 .

Пример 2 . Очень полезным в производстве является решение следующей задачи. Каково среднее время суточного простоя оборудования технологического узла, если узел обрабатывает каждое изделие случайное время, заданное интенсивностью потока случайных событий λ 2 ? При этом экспериментально установлено, что привозят изделия на обработку тоже в случайные моменты времени, заданные потоком λ 1 партиями по 8 штук, причем размер партии колеблется случайно по нормальному закону с m = 8 , σ = 2 (см. лекцию 25). До начала моделирования T = 0 на складе изделий не было. Необходимо промоделировать этот процесс в течение T н = 100 часов.

На рис. 28.9 представлен алгоритм, генерирующий случайным образом поток прихода партий изделий на обработку и поток случайных событий — выхода партий изделий с обработки.

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

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

T пр. ср. = 24 · (t 1 пр. + t 2 пр. + t 3 пр. + t 4 пр. + … + t N пр.)/T н .

Задание 1 . Меняя величину σ , установите зависимость T пр. ср. (σ ) . Задавая стоимость за простой узла 100 евро/час, установите годовые потери предприятия от нерегулярности в работе поставщиков. Предложите формулировку пункта договора предприятия с поставщиками «Величина штрафа за задержку поставки изделий».

Задание 2 . Меняя величину начального заполнения склада, установите, как изменятся годовые потери предприятия от нерегулярности в работе поставщиков в зависимости от принятой на предприятии величины запасов.

Моделирование нестационарных потоков событий

В ряде случаев интенсивность потока может меняться со временем λ (t ) . Такой поток называется нестационарным . Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11 ).

В этом случае распределение λ (t ) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6 , в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12 .

Цель лекции: освоение понятий поток событий, простейший поток событий, Марковский процесс.

1.Поток событий. Свойства потоков событий. Простейший поток событий. Формула Пуассона.

2. Процесс обслуживания как Марковский процесс.

3. Одноканальная СМО с ожиданием.

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

Примерами могут быть:

Поток вызовов на телефонной станции;

Поток сбоев компьютера;

Поток выстрелов, направляемых на цель, и т.д.

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

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

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

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

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

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

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

вероятность появления числа событий на втором интервале не зависит от числа появления событий на первом интервале.

Параметром потока называется предел

где - вероятность того, что на интервале появятся заявки.

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

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

Для стационарного и ординарного потока λ=μ.

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

Простейший поток подчиняется пуассоновскому закону распределения

где - интенсивность потока;

Количество событий, появляющихся за время .

Простейший поток можно задать функцией распределения промежутка между соседними вызовами

F(t)=P(zt),

P(z>t) равносильна вероятности того, что в промежутке длиной t не поступит не одного вызова.

F(t)=P(z>t)=1- (t)=1-

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

Свойства и характеристики простейшего потока:

а) для простейшего потока математическое ожидание и среднеквадратическое отклонение величины промежутка z равны между собой MZ= σz=1/λ;

б) Математическое ожидание и дисперсия числа вызовов i за промежуток времени t равны между собой Mi=Di= λt.

Совпадение этих величин используют на практике при проверке реального потока для соответствия его простейшему.

Рассмотрим некоторую физическую систему S={S 1 ,S 2 ,…S n }, которая переходит из состояния в состояние под влиянием каких-то случайных событий (вызовы, отказы, выстрелы). Будем себе это представлять так, будто события, переводящие систему из состояния в состояние, представляют собой какие-то потоки событий.

Пусть система S в момент времени t находится в состоянии S i и может перейти из него в состояние S j под влиянием какого-то пуассоновского потока событий с интенсивностью ij: как только появляется первое событие этого потока, система мгновенно переходит из S i в S j . Как мы знаем, вероятность этого перехода за элементарный промежуток времени (элемент вероятности перехода) равна, отсюда вытекает, что плотность вероятности перехода ij в непрерывной цепи Маркова представляет собой не что иное, как интенсивность потока событий, переводящих систему по соответствующей стрелке. Если все потоки событий, переводящие систему S из состояния в состояние пуассоновские, то процесс, протекающий в системе, будет марковским.

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

Пример. Техническая система S состоит из двух узлов I и II, каждый из которых независимо от другого может отказывать. Поток отказов первого узла пуассоновский с интенсивностью I , второго также пуассоновский с интенсивностью II . Каждый узел сразу после отказа начинает ремонтироваться (восстанавливаться). Поток восстановлений (окончаний ремонта узла) для обоих узлов - пуассоновский с интенсивностью. Составить граф состояний системы и написать уравнение Колмогорова. Состояния системы: S 11 - оба узла исправны; S 21 - первый узел ремонтируется, второй исправен; S 12, S 22 .

t=0 p 11 =1 p 21 =p 22 =p 12 =0

p 11 +p 12 +p 21 +p 22 =1.

Предельные вероятности состояний для непрерывной марковской цепи

Пусть имеется физическая система S={S 1 ,S 2 ,…S n }, в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Предположим, что ij =const, т.е. все потоки событий простейшие (стационарные пуассоновские). Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим p 1 (t), p 2 (t),… p n (t), при любом t. Поставим следующий вопрос, что будет происходить с системой S при t. Будут ли функции p i (t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными вероятностями состояний. Можно доказать теорему: если число состояний S конечно и из каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. Предположим, что поставленное условие выполнено и предельные вероятности существуют (i=1,2,…n), .

Таким образом, при t в системе S устанавливается некоторый предельный стационарный режим. Смысл этой вероятности: она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Для вычисления p i в системе уравнений Колмогорова, описывающих вероятности состояний, нужно положить все левые части (производные) равными 0. Систему получающихся линейных алгебраических уравнений надо решать совместно с уравнением.

Схема гибели и размножения

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 , ..., S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S 0 , S n) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

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

Для второго состояния S 1:

В силу (8.1) последнее равенство приводится к виду

где k принимает все значения от 0 до n. Итак, финальные вероятности р 0 , p 1 ,..., р n удовлетворяют уравнениям

кроме того, надо учесть нормировочное условие

p 0 + р 1 + р 2 +…+ р n =1 (8.3)

Решим эту систему уравнений. Из первого уравнения (8.2) выразим р 1 через р 0 .

Из второго, с учетом (8.4), получим:

из третьего, с учетом (8.5),

и вообще, для любого k (от 1 до N):

Обратим внимание на формулу (8.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний p 1 , р 2 , …, p n выражены через одну из них (p 0). Подставим эти выражения в нормировочное условие (8.3). Получим, вынося за скобку p 0:

отсюда получим выражение для р 0 .

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (8.4) -- (8.7)). Заметим, что коэффициенты при p 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (8.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

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

Задачи теории массового обслуживания. Классификация систем массового обслуживания и их основные характеристики

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

Всякая СМО предназначена для обслуживания какого-то потока заявок (или «требований»), поступающих в какие-то случайные моменты времени. Обслуживание заявки продолжается какое-то, вообще говоря, случайное время Т об, после чего канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времен обслуживания приводит к тому, что в какие-то периоды времени на входе СМО скапливается излишне большое число заявок (они либо становятся в очередь, либо покидают СМО необслуженными); в другие же периоды СМО будет работать с недогрузкой или вообще простаивать.

В СМО происходит какой-то СП с дискретными состояниями и непрерывным временем; состояние СМО меняется скачком в моменты появления каких-то событий (или прихода новой заявки, или окончания обслуживания, или момента, когда заявка, которой надоело ждать, покидает очередь). Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить СП, описать его математически. Этим и занимается теория МО.

Предмет теории массового обслуживания -- построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с интересующими нас характеристиками -- показателями эффективности СМО, описывающими, с той или другой точки зрения, ее способность справляться с потоком заявок. В качестве таких показателей (в зависимости от обстановки и целей исследования) могут применяться разные величины, например: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди и среднее время ожидания обслуживания; вероятность того, что число заявок в очереди превысит какое-то значение, и т. д. Область применения математических методов теории МО непрерывно расширяется и все больше выходит за пределы задач, связанных с «обслуживающими организациями» в буквальном смысле слова. Как своеобразные СМО могут рассматриваться: ЭВМ, системы сбора и обработки информации, автоматизированные производственные цеха, поточные линии, транспортные системы, системы ПВО и т.п.

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