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

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

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

Таким образом, процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем: состояние СМО меняется скачком в моменты появления прихода новой заявки или окончания обслуживания (клиент пришел - клиент ушел).

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

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

Рассмотрим следующий пример.

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

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

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

Если абстрагироваться от реального наполнения моделей СМО (мастерская, аптека, АТС, лифты в доме и т. д.), СМО можно описать, задавая следующие ее составляющие (рис. 9.1):

1.Входящий поток требований.

2.Дисциплину очереди.

3.Механизм обслуживания.

4.Выходящий поток требований.

Рис. 9.1. Модель теории массового обслуживания

В некоторых системах «очередь» отсутствует.

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

Приоритет может быть абсолютным или относительным.

СМО могут быть открытыми и закрытыми. В первой - поток заявок не зависит от состояния самой СМО (сколько каналов занято), во

второй - зависит. Пример - наладка группы станков одним рабочим. Здесь интенсивность «требований» со стороны станков зависит от того, сколько их уже неисправно.

Классификация СМО не ограничивается приведенными разновидностями.

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

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

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

ность может быть как постоянной, так и зависящей от t. Например, поток машин ночью не так интенсивен, как днем.

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

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

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

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

ний, поступивших в систему за, не зависит от того, сколько требований поступило за промежуток.

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

Пусть случайная величинаобозначает число требований на интервале .

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

Заметим, что

где

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

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

Можно показать, что для простейшего потока число требований в промежутке времени длиной t распределено по закону Пуассона с параметром(см. п. 7.2.1), т. е.

Стационарность и отсутствие последействия налицо, ординарность (т. е. условие (9.1)) вытекает из равенства

которое можно проверить по правилу Лопиталя.

Параметр X здесь характеризует интенсивность потока. Действительно,

Простейший поток еще называют стационарным пуассоновским.

Пример 1. Рассмотрим наладку станков одним рабочим. Предполагается, что все станки находятся приблизительно в одинаковом состоянии (последнее обеспечивает стационарность потока поломок). Вероятность поломки одного станка невелика (двух, трех и т. д. - тем более) - отсюда следует ординарность. Кроме того, если станков много, а среднее время ремонта мало, то можно считать, что поток поломок не имеет последействия. Другими словами, он является простейшим.

Решение. Пусть интенсивностьполомки/ч. По формуле (9.2)

прии t =1 найдем вероятность k поломок в течение часа

Составим табл. 9.1. Таблица 9.1

k

....

p k (1)

0,05

0,15

0,22

0,22

0,17

0,05

....

Следующее важное понятие ТМО - это время обслуживания.

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

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

Параметр(аналогично параметрувходящего потока) определяет интенсивность обслуживания; величина является средним временем обслуживания t одной заявки:

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

Далее коротко опишем я-канальную систему массового обслуживания с отказами. Это «классическая» задача ТМО, возникшая из практических нужд телефонии и решенная в начале ХХ века датским математиком Эрлангом. Задача ставится так.

Имеется я каналов, на которые поступает простейший поток заявок с интенсивностью X. Если в момент поступления очередного требования имеется хотя бы один свободный аппарат, то любой из аппаратов немед-

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

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

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

. А - абсолютная пропускная способность, т. е. среднее число заявок, обслуживаемых в единицу времени;

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

. Р отк - вероятность отказа, или того, что заявка покинет СМО необслуженной;

Среднее число занятых каналов;

. - вероятность того, что занято ровно k каналов, и, в частности, Р 0 - вероятность простоя системы;

. - коэффициент занятости каналов в процентах (%);

.
- коэффициент простоя каналов

в процентах (%). Обозначим

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

а вероятностиприимеют вид

Формулы (9.6), (9.7) для вероятностей Р к называются формулами Эрланга - в честь основателя ТМО. С их помощью можно вычислить остальные интересующие нас характеристики СМО. Так, вероятность Действительно, для того чтобы пришедшая заявка получила отказ, необходимо, чтобы все я каналов были заняты. Итак,

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

Абсолютную пропускную способность получим, умножая интенсивность потока заявок на Q:

Среднее число занятых каналовпо определению математического ожидания с учетом формул (9.6) и (9.7) равно

Отметим, что, зная вероятность отказав обслуживании

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

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

Отсюда заключаем, что на АТС в среднем занято 2 линии из 5, каждая линия загружена всего на 39 %, теряется приблизительно 4 вызова из 100. Таким образом, АТС работает не слишком эффективно, и вполне можно сократить общее число линий и (или) увеличить интенсивность потока заявок.

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

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

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

Таким образом, загрузка каждого из двух оставшихся продавцов немного вырастет (с 0,53 до 1/2 . 1,2 = 0,6 рабочего дня), зато «коэффициент полезного действия» аптеки упадет с 0,79 до 0,6, поскольку в сложившейся ситуации будет обслужено лишь 60 % ((1 - 0,4) . 100 %) потенциальных клиентов, а не 79 % как ранее при трех продавцах.

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

Каждая система массового обслуживания состоит из определенного числа обслуживающих единиц, в том числе приборов, при-

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

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

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

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

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

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

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

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

В качестве показателей эффективности систем массового обслуживания могут использоваться следующие:

Среднее количество заявок в очереди;

Среднее время ожидания на обслуживание;

Вероятность отказа в обслуживании без ожидания;

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

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

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

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

1. Абсолютная пропускная способность (А) - показатель, который показывает среднее количество заявок, обслуживаемых в единицу времени. Он рассчитывается по формуле

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

Интенсивность потока обслуживания.

При этом интенсивность потока обслуживания является обратной величиной к среднему времени обслуживания ():

2. Относительная пропускная способность (Q) - показатель, характеризующий среднюю долю заявок, которая поступила и обслуживается системой. Вычисляется по формуле

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

4. Среднее число занятых каналов () (для многоканальной системы). Этот показатель рассчитывается следующим образом:

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

В многоканальных системах массового обслуживания с предельными вероятностями используют формулы для предельных вероятностей состояния, которые получили название формул Эрланга в честь А.К. Эрланга (конец XIX - начало XX в.) - Датского инженера, математика, основателя теории массового обслуживания.

Вероятность отказа системы массового обслуживания - это предельная вероятность того, что все п каналов системы будут заняты, то есть:

;

, ..., ...,.

Относительная пропускная способность - вероятность того, что заявка будет обслужена определяется:

.

Абсолютная пропускная способность рассчитывается:

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

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

1. Определить показатели эффективности работы системы массового обслуживания (переговорного пункта) при наличии одного телефонного номера.

2. Определить оптимальное количество телефонных номеров на переговорном пункте, если условием оптимальности считать

удовольствие в среднем из каждых 100 заявок не менее 80 заявок на переговоры.

1. Рассчитаем интенсивность потока обслуживания:

.

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

.

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

3. Вероятность отказа в обслуживании () составит:

.

Итак, в среднем 80% заявок, которые поступят на переговоры, получат отказ в обслуживании.

4. Абсолютная пропускная способность системы массового обслуживания - переговорного пункта равно

.

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

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

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

5. Вычислим интенсивность нагрузки канала:

.

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

6. Для получения характеристик системы (переговорного пункта) и выбора оптимального варианта количества номеров следует постепенно увеличивать число каналов (телефонных номеров) n = 2,3,4, ..., превращая таким образом имеющуюся систему массового обслуживания с одноканальной в многоканальную. Тогда относительная пропускная способность составит:

;

;

за;.

Абсолютная пропускная способность равна:

Аналогично рассчитаем основные характеристики системы массового обслуживания для 3, 4, 5, 6 каналов обслуживания (номеров телефонов) и сведем их в табл. 13.5.

Таблица 13.5. Основные характеристики обслуживания заявок на переговоры переговорным пунктом в зависимости от количества номеров

Итак, по условиям оптимальности Q 3 = 0,8, поэтому на переговорном пункте необходимо установить 3 телефонных номера (в этом случае Q = 0,80). Это означает, что за час будут обслуживаться в среднем 64 заявки (А = 64), а среднее число занятых номеров (каналов) равна

.

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

Введение

Теория случайных процессов (случайных функций) - это раздел математической науки, изучающий закономерности случайных явлений в динамике их развития.

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

Теория массового обслуживания опирается на теорию вероятностей и математическую статистику. Первоначальное развитие теории массового обслуживания связано с именем датского ученого А.К. Эрланга (1878-1929), с его трудами в области проектирования и эксплуатации телефонных станций.

Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.

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

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

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

1. Определение случайного процесса и его характеристики

Случайным процессом X(t) называется процесс, значение которого при любом значении аргумента t является случайной величиной.

Другими словами, случайный процесс представляет собой функцию, которая в результате испытания может принять тот или иной конкретный вид, неизвестный заранее. При фиксированном t = to X(to) представляет собой обычную случайную величину, т.е. сечение случайного процесса в момент tо.

Реализацией случайного процесса X (t, w) называется неслучайная функция x(t), в которую превращается случайный процесс X(t) в результате испытания (при фиксированном w), т.е. конкретный вид, принимаемый случайным процессом X(t), его траектория.

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

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

Математическим ожиданием случайного процесса X(t) называется неслучайная функция ax(t), которая при любом значении переменной t равна математическому ожиданию соответствующего сечения случайного процесса X(t), т.е. ax(t) = M .

Дисперсией случайного процесса X(t) называется неслучайная функция. Dx(t), при любом значении переменной t равная дисперсии соответствующего сечения случайного процесса X(t), т.е. Dx(t) = D .

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

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

Корреляционной функцией случайного процесса X(t) называется неслучайная функция

двух переменных t1 и t2, которая при каждой паре переменных t1и t2 равна ковариации соответствующих сечений X(t1) и X(t2) случайного процесса.

Нормированной корреляционной функцией случайного процесса X(t) называется функция

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

2. Основные понятия теории массового обслуживания

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

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

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

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

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

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

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

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

Процесс работы СМО представляет собой случайный процесс.

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

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

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

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент to счетчик показывает So. Вероятность того, что в момент t > to счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S1, зависит от So, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента to.

Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S - группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент to. Вероятность того, что в момент t > to материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в каком состояний находится система в данный момент to, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента to.

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

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

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

. Потоки событий

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

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

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

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

Поток событий называется потоком без последействия, если для - любых-двух непересекающихся участков времени Т1 и Т2 число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).

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

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

Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа п независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям Аi (i=1,2…п)) получается поток, близкий к простейшему с интенсивностью X, равной сумме интенсивностей входящих потоков, т.е.:

Биномиальный закон распределения:

с параметрами

Биномиальное распределение стремится к распределению Пуассона с параметром

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

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

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

и обратно по величине интенсивности потока

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

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

Для простейшего потока с интенсивностью вероятность попадания на элементарный (малый) отрезок времени At хотя бы одного события потока равна:

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

5. Уравнения Колмогорова. Предельные вероятности состояний

Соответствующий граф состояний процесса изображен на рис. к задаче. Будем полагать, что все переходы системы из состояния Si в Sj происходят под воздействием простейших потоков событий с интенсивностями (i, j =0, 1, 2,3); так, переход системы из состояния S0 вS1 будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния S0 в S1 - под воздействием потока «окончаний ремонтов» первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. выше). Рассматриваемая система S имеет четыре возможных состояния: S0, S1 S2, S3. Вероятностью i-го состояния называется вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

Рассмотрим систему в момент t и, задав малый промежуток At, найдем вероятность po (t + At) того, что система в момент t+At будет находиться в состоянии S0. Это достигается разными способами.

1.Система в момент t с вероятностью po (t) находилась в состоянии S0, а за время At не вышла из него.

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

А вероятность того, что система не выйдет из состояния S0, равна . Вероятность того, что система будет находиться в состоянии S0 и не выйдет из него за время At, равна по теореме умножения вероятностей:

Система в момент t с вероятностью p1 (t) (или p2 (t)) находилась в состоянии S1 или S2 и за время At перешла в состояние

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

Применяя теорему сложения вероятностей, получим:

Переходя к пределу при At 0 (приближенные равенстваперейдут в точные), получим в левой части уравнения производную (обозначим ее для простоты ):

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

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

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

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

Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задавать так называемые начальные условия, в данном случае - вероятности состояний системы в начальный момент t = 0. Так, например, систему уравнений естественно решать при условии, что в начальный момент оба узда исправны и система находилась в состоянии So, т.е. при начальных условиях

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы pi(t) в предельном стационарном режиме, т.е. при , которые называются предельными (финальными) вероятностями состояний.

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

Предельная вероятность состояния Si имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния So, т.е. р0=0,5, то это означает, что в среднем половину времени система находится в состоянии S0.

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

Процессы гибели и размножения

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

Рассмотрим упорядоченное множество состояний системы S0, S1, S2,…, Sk. Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния Sk-1 возможны переходы либо в состояние либо в состояние S k+11.

В соответствии с правилом составления таких уравнений (уравнением Колмогорова) получим: для состояния S0

Заключение

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

Использованная литература

случайный массовый марковский колмогоров

1. Н.Ш. Кремер «Теория вероятностей и математическая статистика» Юнити, г. Москва, 2003 г.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Модели теории массового обслуживания

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

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

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

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

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

Основными элементами СМО являются:

Входящий поток заявок (требований) на обслуживание;

Очередь заявок на обслуживание;

Приборы (каналы) обслуживания;

Выходящий поток обслуженных заявок (рисунок 8.5).

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

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

Рисунок 8.5 - Обобщенная схема СМО

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

Каковы вероят­ность появления задержки или очереди и ее величина? Сколько време­ни требование находится в очереди и каким образом минимизировать его задержку?

Какова вероятность потери требования (клиента)?

Ка­кова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибы­ли?

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

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

Часто входной поток заявок представляется в виде про­стейшего потока, обладающего свойством стационарности, от­сутствия последствия и ординарности.

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

Для простейшего потока поступление заявок в СМО описы­вается законом распределения Пуассона

Р к (τ ) ,

где Р к (τ ) -вероятность поступления к заявок за время τ ;

λ - интенсивность входного потока.

Важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной по­ток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью λ i (i = 1, 2, ..., N), то его интенсивность будет определяться по формуле

λ = λ l + λ 2 +...+ λ N .

В случае разделения пуассоновского потока на N независимых по­токов получим, что интенсивность потока λ i будет равна r i λ ,где r i - доля i-го потока во входном потоке требований.

Очередью является множество заявок (требований), ожи­дающих обслуживание.

В зависимости от допустимости и характера формирования очереди системы массового обслуживания подразделяются:

1. СМО с отказами - формирование очереди не разрешено, поэтому заявка, пришедшая в момент, когда все каналы заняты, получает отказ и теряется. Пример: АТС (выполнение заказов к определенному сроку), система ПВО объекта (цель в зоне об­стрела пребывает мало времени).

2. СМО с неограниченным ожиданием - поступившая заяв­ка, застав все обслуживающие приборы занятыми, становится в очередь и дожидается обслуживания. Число мест для ожидания (длина очереди) не ограничено. Не ограничивается и время ожидания. Пример: предприятия бытового обслуживания, такие как мастерские по ремонту часов, обуви.

3. СМО смешанного типа. В этих системах имеется очередь,
на которую накладываются ограничения. Например: на макси­мальную длину очереди (I тип – с ограниченной ДО) или на время ожидания заявки в очереди (П тип – с ограниченным ВО). Примерами СМО I-го типа являются мастер­ские по ремонту радиоаппаратуры с ограниченными площадями для ее хранения. Торговые точки по продаже фруктов, овощей, которые могут храниться ограниченное время, являются смешан­ными СМО II -го типа.

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

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

а) в порядке поступления заявок (первым пришел – первым обслужился) - магазины, предприятия бытового обслуживания;

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

в) в соответствии с приоритетом (участники ВОВ в поликлинике);

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

Основным параметром процесса обслужи­вания считается время обслуживания заявки каналом (обслуживающим прибором j) – t j (j=1,2,…,m).

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

F(t) = l – e - μt ,

где m - положительный параметр, определяющий интенсивность обслужи­вания требований;

где Е (t) - математическое ожидание случайной величины обслуживания тре­бования t j .

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

Если СМО состоит из неоднородных каналов, то , если
же все каналы однородные, то .

По количеству обслуживающих приборов (каналов) СМО де­лятся на:

Одноканальные;

Многоканальные.

Структура СМО и характерис­тика ее элементов приведены на рисунке 8.6.

Исследование СМО заключается в нахождении показателей, харак­теризующих качество и условия работы обслуживающей системы и показателей, отражающих экономические последствия принятых ре­шений.

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

Рисунок 8.6 – Структура и характеристика элементов СМО

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

средняя длина очереди,

среднее время ожидания в очереди,

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

среднее время пребывания в СМО и др.

В качестве критерия оптимизации применяют:

Максимум прибыли от эксплуатации СМО;

Минимум суммарных потерь, связанных с простоем кана­лов, простоем заявок в очереди и уходом необслуженных за­явок;

Обеспечение заданной пропускной способности.

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

Вопросы для самопроверки

1. Понятие о математических моделях и моделировании.

2. Что представляет собой экономико-статистическая модель и производственная функция?

3. Применение графических и графоаналитических моделей в управлении.

4. Использование корреляционного анализа для выявления связи между параметрами

5. Виды и методы построения регрессионных моделей.

6. Статистическое исследование причинно-следственных связей.

7. Классификация математических моделей по четырем аспектам детализации (по В.А. Кардашу).

8. Классификация моделей по применяемому математическому аппарату. Понятие о балансовых моделях.

9. Этапы моделирования. Проверка модели на адекватность.

10. Понятие о системах массового обслуживания (СМО). Составные части СМО.

11. СМО с отказами и с очередью. Разновидности очередей.

12. Одноканальные и многоканальные СМО. Дисциплины обслуживания

13. Моделирование СМО. Показатели, получаемые при экспериментах на модели СМО.

14. Критерии оптимизации систем массового обслуживания.

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

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

Марковский процесс - дискретный или непрерывный случайный процесс X (t ), который можно полностью задать с помощью двух величин:

· вероятности P (x ,t ) того, что случайная величина x (t ) в момент времени t равна x , и

· вероятности P (x 2 , t 2 |x 1 ,t 1) того, что если x при t = t 1 равен x 1 , то при t = t 2 он равен x 2 .

Вторая из этих величин называется вероятностью перехода из состояния x 1 при t = t 1 в состояние x 2 при t = t 2 .

Цепями Маркова называют дискретные по времени и значению Марковские

процессы.

Пример 1

Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.

19.5.1. Формулы и определения Марковских цепей

Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.

Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.

Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е.

P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что P ij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.

Практический пример 1.

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

1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;

3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.

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

Матрица вероятностей перехода будет выглядеть следующим образом:

Например, р 12 = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А. Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С-->B и B-->B;

3) С-->A и A-->B.

Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Подставляя числовые значения:

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки. Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.

Рассмотрим более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:

Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).

2 способ. Вычислить матрицу P 3:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Теория массового обслуживания

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

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

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

Методы анализа систем массового обслуживания

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

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

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

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

Для простейшего потока частота поступлений требований в сис­тему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно к требований задается формулой:

Простейший поток обладает тремя основными свойствами:

1) ординарностью,

2) стационарностью и

3) отсутствием после­действия.

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

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

Отсутствие последействия означает, что число требований, по­ступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt

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

Важная характеристика СМО - время обслуживания требований в системе. Время обслуживания одного требования является, как правило, случайной величиной и, следовательно, может быть опи­сано законом распределения. Наибольшее распространение в тео­рии и особенно в практических приложениях получил экспоненци­альный закон распределения времени обслуживания. Функция распре­деления для этого закона имеет вид:

т.е. вероятность того, что время обслуживания не превзойдет неко­торой величины t, определяется формулой (5.2), где µ - параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания

Системы массового обслуживания классифицируются:

1. В зависимости от условий ожидания начала обслуживания:

· СМО с потерями (отказами)

· СМО с ожиданием

В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и покидают сис­тему. Классическим примером системы с отказами является теле­фонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и покидает систему.

В СМО с ожиданием требование, застав все обслуживающие ка­налы занятыми, становится в очередь и ожидает, пока освободится [ один из обслуживающих каналов.

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

СМО, допускающие очередь, но с ограниченным сроком пре­бывания каждого требования в ней, называются системами с ограниченным временем ожидания.

2. По числу каналов обслуживания СМО делятся на:

Одноканальные;

Многоканальные.

3. По месту нахождения источника тре­бований СМО подразделяются на:

разомкнутые, когда источник требования находится вне сис­темы;

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

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

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

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

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

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

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

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

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

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

Рассмотрим порядок расчета характеристик работы разомкнутых систем с ожиданием и ограниченной длиной очереди.

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

1. Вероятность того, что все обслуживающие каналы свободны,

(5.14)

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

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

(5.16)

4. Вероятность того, что все обслуживающие каналы заняты,

(5.17)

5. Вероятность отказа

(5.18)

6. Средняя длина очереди

7. Среднее число свободных от обслуживания каналов

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

Требуется определить характеристики работы фирмы.

Решение. Данная система относится к типу СМО с ожида­нием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:

Вероятность того, что все машины свободны от перевозки гру­зов, находится по формуле (5.14):

Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет

Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18) будет равна

, а средняя длина очереди в соответствии с формулой (5.19) составит

Тогда вероятность отказа в принятии заказа на перевозку, рас­считываемая по формуле (5.18), будет равна

а средняя длина очереди в соответствии с формулой (5.19) составит

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

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

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

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

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

Приведем последовательность расчетов характеристик замкну­тых СМО с ожиданием и необходимые формулы.

1. Параметр α=α/µ. - показатель загрузки системы, т.е. мате­матическое ожидание числа требований, поступающих в систему за время, равное средней длительности обслуживания

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