Рисунок 0 - 2 Потоки событий (а) и простейший поток (б)

10.5.2.1. Стационарность

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

Рисунок 0-2 , а) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

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

10.5.2.2. Отсутствие последействия

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

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

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

Рисунок 0 - 3 Распределение Пуассона

Рассмотрим на оси t простейший поток событий с интенсивностью λ. (Рисунок 0-2 б). Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

F(t) = P(T (0-2)

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

F (t ) = 1 - Р0

Вероятность Р 0 найдем по формуле (1), полагая m = 0:

откуда функция распределения величины Т будет:

(0-3)

Чтобы найти плотность распределения f (t ) случайной величины Т, необходимо продифференцировать выражение (0‑1) по t :

0-4)

Закон распределения с плотностью (0‑4) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.

Рисунок 0 - 4 Экспоненциальное распределение

Найдем числовые характеристики случайной величины Т - математическое ожидание (среднее значение) M [ t ]= m t , и дисперсию D t . Имеем

( 0-5)

(интегрируя по частям) .

Дисперсия величины Т составляет:

(0-6)

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

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

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

Пример СМО- 1 .

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

Рассчитаем вероятность Р (m ) появления m сообщений в 1 с. Так как λ = 2, то из предыдущей формулы имеем

Подставляя m = 0, 1, 2, 3, получим следующие величины (с точностью до четырех десятичных знаков):

Рисунок 0 - 5 Пример простейшего потока

Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).

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

Пример СМО- 2 .

Прибор (сервер), обрабатывающей три сообщения в 1с.

Пусть имеется оборудование, которое может обрабатывать три сообщения в 1 с (µ=3). Поступает всреднем два сообщения в 1с, причем в соответствии c распределением Пуассона. Какая часть этих сообщений будет обрабатываться сразу же после поступления?

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

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

Другими словами, 85,71% сообщений будут обслуживаться немедленно, а 14,29% с некоторой задержкой. Как видим, задержка в обработке одного сообщения на время, большее времени обработки 3 сообщений, будет встречаться редко. Время обработки 1сообщения составляет в среднем 1/3 с. Следовательно, задержка более 1с будет редким явлением, что вполне приемлемо для большинства систем.

Пример СМО- 3

· Если кассир банка занят в течение 80% своего рабочего времени, а остальное время он тратит на ожидание клиентов, то его можно рассматривать как устройство с коэффициентом использования 0,8.

· Если канал связи используется для передачи 8-битовых символов со скоростью 2400 бит/с, т. е. передается максимум 2400/8 символов в 1 с, и мы строим систему, в которой суммарный объем данных составляет 12000 символов, посылаемых от различных устройств через канал связи в минуту наибольшей нагрузки (включая синхронизацию, символы конца сообщений, управляющие и т. д.), то коэффициент использования оборудования канала связи в течение этой минуты равен

· Если механизм доступа к файлу в час наибольшей нагрузки осуществляет 9000 обращений к файлу, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования механизма доступа в час наибольшей нагрузки составляет

Понятие коэффициента использования оборудования будет использоваться довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

Используя предыдущую формулу, можно составить таблицы значений функции Пуассона, по которым можно определить вероятность поступления m или более сообщений в данный отрезок времени. Например, если в среднем поступает 3,1 сообщения в секунду [т. е. λ = 3,1], то вероятность поступления 5 и более сообщений в данную секунду равна 0,2018 (для m = 5 в таблице). Или в аналитическом виде

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

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

ρ ≤ 0,9

Эти значения можно получить с помощью таблиц Пуассона.

Пусть снова средняя скорость поступления сообщений λ = 3,1 сообщения/с. Из таблиц следует, что вероятность поступления 6 или более сообщений в 1 с равна 0,0943. Следовательно, это число можно взять в качестве критерия нагрузки для проведения начальных расчетов.

10.6.2. Задачи проектирования

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

Чем больше коэффициент использования оборудования, тем длиннее возникающие очереди. Как будет показано ниже, можно спроектировать удовлетворительно работающую систему с коэффициентом использований ρ =0,7 но коэффициент, превышающий ρ > 0,9, может привести к ухудшению качества обслуживания. Другими словами, если канал пересылки массива данных имеет загрузку 20%, вряд ли на нем возникнет очередь. Если же загрузка; составляет 0,9, то, как правило, будут образовываться очереди, иногда очень большие.

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

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

· Какова длина очереди?

· Сколько времени на нее будет затрачиваться?

На вопросы подобного типа можно ответить с помощью теории очередей.

10.6.3. Системы массового обслуживания, их классы и основные характеристики

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

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

СМО классифицируются на системы с:

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

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

Обслуживание (дисциплина очереди) в системе с ожиданием может быть

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

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

· стековым (первой из очереди выбирается последняя заявка).

· Приоритетным

o со статическим приоритетом

o с динамическим приоритетом

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

Системы с очередью делятся на системы

· с неограниченным ожиданием и

· с ограниченным ожиданием.

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

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

· длины очереди (числа заявок, одновременно находящихся в очереди система с ограниченной длиной очереди),

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

· общего времени пребывания заявки в СМО

и т. д.

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

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

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

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

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

и т. д.

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

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

· среднее число заявок в системе (в очереди и под обслуживанием);

· среднее время ожидания заявки в очереди;

· среднее время пребывания заявки в системе (в очереди и под обслуживанием);

а также и другие характеристики ожидания.

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

Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок λ , производительность каждого канала (среднее число заявок μ, обслуживаемое каналом в единицу времени), условия образования очереди (ограничения, если они есть).

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.

10.6.4. Формулы расчета характеристик СМО для случая обслуживания с одним прибором

Рисунок 0 - 6 Модель системы массового обслуживания с очередью

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

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

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

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

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

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

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

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

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

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

Рассмотрим следующий пример. Имеется шесть типов сообщений с временами обслуживания 15, 20, 25, 30, 35 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

10.6.6. Пример расчета

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

Время ответа системы и его стандартное отклонение рассчитаны с учетом времени ввода данных с АРМа, печатания и оформления документа.

Действия кассира были прохронометрированы. Время обслуживания ts равно общему времени, затрачиваемому кассиром на клиента. Коэффициент использования кассира ρ пропорционален времени его занятости. Если λ число клиентов в часы пик, то ρ для кассира равно

Предположим, что в часы пик приходит 30 клиентов в час. В среднем кассир тратит 1,5 мин на клиента. Тогда

ρ =(1,5 * 30) / 60 = 0,75

т. е. кассир используется на 75%.

Число людей в очереди можно быстро оценить с помощью графиков. Из них следует, что если ρ = 0,75, то среднее число nq людей в очереди у кассы лежит между 1,88 и 3,0 в зависимости от стандартного отклонения для t s .

Предположим, что измерение стандартного отклонения для t s дало величину 0,5 мин. Тогда

σ s = 0,33 t s

Из графика на первом рисунке находим, что nq = 2,0, т. е. в среднем у кассы буду ожидать два клиента.

Общее время, в течение которого клиент стоит у кассы, может быть найдено как

t ∑ = t q + t s = 2,5 мин + 1,5 мин=4мин

где t s вычисляется с помощью формулы Хинчина-Полачека.

10.6.7. Фактор усиления

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

Увеличение входного трафика на небольшое число х%. приводит к увеличению размеров очереди приблизительно на

Если коэффициент использования оборудования равен 50%, то это увеличение равно 4ts % для экспоненциального закона распределения времени обслуживания. Но если коэффициент использования оборудования равен 90%, то увеличение размера очереди равно 100ts %, что в 25 раз больше. Незначительное увеличение нагрузки при 90%-ном использовании оборудования приводит к 25-кратному увеличению размеров очереди по сравнению со случаем 50%-ного использования оборудования.

Аналогично время пребывания в очереди увеличивается на

При экспоненциально распределенном времени обслуживания эта величина имеет значение 4 t s 2 для коэффициента использования оборудования, равного 50%, и 100 t s 2 для коэффициента 90%, т. е. снова в 25 раз хуже.

Кроме того, для малых коэффициентов использования оборудования влияние изменений σs на размер очереди незначительно. Однако для больших коэффициентов изменение σ s сильно сказывается на размере очереди. Поэтому при проектировании систем с высоким коэффициентом использования оборудования желательно получить точные сведения о параметре σ s . Неточность предположения относительно экспоненциальности распределения t s наиболее ощутима при больших значениях ρ. Более того, если вдруг время обслуживания возрастет, что возможно в каналах связи при передаче длинных сообщений, то в случае большого ρ образуется значительная очередь.

За последние десятилетия в самых разных областях народного хозяйства возникла необходимость решения вероятностных задач, связанных с работой систем массового обслуживания. Примерами таких систем служат телефонные станции, ремонтные мастерские, торговые предприятия, билетные кассы и т.д. работа любой системы массового обслуживания состоит в обслуживании поступающего в нее потока требований (вызовы абонентов, при ход покупателей в магазин, требования на выполнение работы в мастерской и т. д.).
Математическая дисциплина, изучающая модели реальных систем массового обслуживания, получила название теории массового обслуживания. Задача теории массового обслуживания - установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужено; математического ожидания числа обслуженных требований и т. д.) от входных показателей (количество приборов в системе, параметров входящего потока требований и т. д.) установить такие зависимости в формульном виде можно только для простых систем массового обслуживания. Изучение же реальных систем проводится путем имитации, или моделирования их работы на ЭВМ с привлечением метода статистических испытаний.
Система массового обслуживания считается заданной, если определены:
1) входящий поток требований, или, иначе говоря, закон распределения, характеризующий моменты времени поступления требований в систему. Первопричину требований называют источником. В дальнейшем условимся считать, что источник располагает неограниченным числом требований и что требования однородны, т. е. различаются только моментами появления в системе;
2) система обслуживания, состоящая из накопителя и узла обслуживания. Последний представляет собой одно или несколько обслуживающих устройств, которые в дальнейшем будем называть приборами. Каждое требование должно поступить на один из приборов, чтобы пройти обслуживание. Может оказаться, что требованиям придется ожидать, пока приборы освободятся. В этом случае требования находятся в накопителе, образуя одну или несколько очередей. Положим, что переход требования из накопителя в узел обслуживания происходит мгновенно;
3) время обслуживания требования каждым прибором, которое является случайной величиной и характеризуется некоторым законом распределения;
4) дисциплина ожидания, т. е. совокупность правил, регламентирующих количество требований, находящихся в один и тот же момент времени в системе. Система, в которой поступившее требование получает отказ, когда все приборы заняты, называется системой без ожидания. Если требование, заставшее все приборы занятыми, становится в очередь и ожидает до тех пор,
пока освободиться один из приборов, то такая система называется чистой системой с ожиданием. Система, в которой требование, заставшее все приборы занятыми, становится в очередь только в том случае, когда число требований, находящихся в системе, не превышает определенного уровня (в противном случае происходит потеря требования), называется смешанной системой обслуживания;
5) дисциплина обслуживания, т. е. совокупность правил, в соответствии с которыми требование выбирается из очереди для обслуживания. Наиболее часто на практике используются следующие правила:
- заявки принимаются к обслуживанию в порядке очереди;
- заявки принимаются к обслуживанию по минимальному времени получения отказа;
- заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями;
6) дисциплина очереди, т.е. совокупность правил, в соответствии с которыми требование отдает предпочтение той или иной очереди (если их не сколько) и располагается в выбранной очереди. Например, поступившее требование может занять место в самой короткой очереди; в этой очереди оно может расположиться последним (такая очередь называется упорядоченной), а может пойти на обслуживание вне очереди. Возможны и другие варианты.

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

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

1 Внешнее проектирование

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

2 Внутреннее проектирование - проектирование отдельных элементов
системы

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

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

При исследовании сложных систем методом имитационного моделирования существенное внимание уделяется учету случайных факторов.
В качестве математических схем, используемых для формализации действия этих факторов, используются случайные события, случайные величины и случайные процессы (функции). Формирование на ЭВМ реализаций случайных объектов любой природы сводится к выработке и преобразованию случайных чисел. Рассмотрим способ получения возможных значений случайных величин с заданным законом распределения. Для формирования возможных значений случайных величин с заданным законом распределения исходным материалом служат случайные величины, имеющие равномерное распределение в интервале (0, 1). Другими словами, возможные значения xi случайной величины £, имеющей равномерное распределение в интервале (0, 1), могут быть преобразованы в возможные значения yi случайной величины г), закон распределения которой задан. Способ преобразования состоит в том, что из равномерно распределенной совокупности отбираются случайные числа, удовлетворяющие некоторому условию таким образом, чтобы отобранные числа подчинялись заданному закону распределения.
Предположим, что необходимо получить последовательность случайных чисел yi , имеющих функцию плотности 1^(у). Если область определения функции f^y) не ограничена с одной или обеих сторон, необходимо перейти к соответствующему усеченному распределению. Пусть область возможных значений для усеченного распределения равна (a, b).
От случайной величины г), соответствующей функции плотности f ^ y), перейдем к f.
Случайная величина Ъ, будет иметь область возможных значений (0, 1) и функцию плотности f ^(z), задаваемую выражением.
Пусть максимальное значение f^(z) равно f m . Зададим равномерные распределения в интервалах (0, 1) случайных чисел x 2 i-1 и x 2 i. Процедура по лучения последовательности yi случайных чисел, имеющих функцию плотности ^(у), сводится к следующему:
1) из исходной совокупности выбираются пары случайных чисел x2i-1,
2) для этих чисел проверяется справедливость неравенства
х 21 <-- ^[а + (Ъ-а)х 2М ] (3)
m
3) если неравенство (3) выполнено, то очередное число yi определяется из соотношения
yi =a + (b-а)х 21 (4)
При моделировании процессов обслуживания возникает необходимость формирования реализаций случайного потока однородных событий (заявок). Каждое событие потока характеризуется моментом времени tj, в который оно наступает. Чтобы описать случайный поток однородных событий как случайный процесс, достаточно задать закон распределения, характеризующий последовательность случайных величин tj. Для того, чтобы получить реализацию потока однородных событий t1, t2..., tk, необходимо сформировать реализацию z b z 2 ,...,zk k-мерного случайного вектора ££2,..., Sk и вычислить значения ti в соответствии со следующими соотношениями:
t 2 =
Пусть стационарный ординарный поток с ограниченным последействием задан функцией плотности f(z). В соответствии с формулой Пальма (6) найдем функцию плотности f1(z1) для первого интервала z1.
1- Jf (u) du
Теперь можно сформировать случайное число z b как было показано выше, соответствующее функции плотности f1(z1), и получить момент появления первой заявки t1 = z1 . Далее формируем ряд случайных чисел, соответствующих функции плотности f(z), и при помощи соотношения (4) вычисляем значения величин t2, t3 ,.., tk.
4 Обработка результатов моделирования
При реализации моделирующих алгоритмов на ЭВМ вырабатывается информация о состояниях исследуемой системы. Эта информация является исходным материалом для определения приближенных значений искомых величин, или, как принято говорить, оценок для искомых величин.
Оценка вероятности события А вычисляется по формуле
p(A) = mN . (7)
Оценка среднего значения x случайной величины Ъ, вычисляется по
формуле
_ 1 n
k =1
Оценка S 2 для дисперсии случайной величины ^ вычисляется по формуле
1 N 1 (N Л 2
S 2 =1 YA xk 2-5> J (9)
Оценка корреляционного момента К^ для случайных величин Ъ, и ц с возможными значениями x k и y k соответственно вычисляется по формуле
1 N 1 NN
У> [ Ух

5 Пример моделирования СМО
Рассмотрим следующую систему:
1 Требования поступают в случайные моменты времени, при этом
промежуток времени Q между любыми двумя последовательными требованиями имеет показательный закон с параметром i, т. е. функция распределения имеет вид
>0. (11) Система обслуживания состоит из s одинаковых, пронумерованных приборов.
3 Время Т о бсл - случайная величина с равномерным законом распределения на отрезке .
4 Система без ожидания, т.е. требование, заставшее все приборы занятыми, покидает систему.
5 Дисциплина обслуживания такова: если в момент поступления k - го требования первый прибор свободен, то он приступает к обслуживанию требования; если этот прибор занят, а второй свободен, то требование обслуживается вторым прибором, и т.д.
Требуется оценить математические ожидания числа требований, обслуженных системой за время Т и получивших отказ.
За начальный момент расчета выберем момент поступления первого требования Т1=0. Введем следующие обозначения: Тk- момент поступления k-го требования; ti - момент окончания обслуживания требования i-м прибором, i=1, 2, 3, ...,s.
Предположим, что в момент T 1 все приборы свободны.
Первое требование поступает на прибор 1. Время обслуживания этим прибором имеет равномерное распределение на отрезке . Поэтому конкретное значение tобсл этого времени находим по формуле
(12)
где r- значение случайной величины R , равномерно распределенной на отрезке . Прибор 1 будет занят в течение времени t о бсл. Поэтому момент времени t 1 окончания обслуживания требования прибором 1 следует считать равным: t 1 = Т1+ t о бсл.
Затем следует добавить единицу в счетчик обслуженных требований и перейти к рассмотрению следующего требования.
Предположим, что k требований уже рассмотрено. Определим момент Т k+1 поступления (k+1)-го требования. Для этого найдем значение т промежутка времени между последовательными требованиями. Так как этот про межуток имеет показательный закон, то
12
х = - In r (13)
| Ll
где r -очередное значение случайной величины R . Тогда момент посту пления (k+1)-го требования: Т k +1 = Тк+ Т.
Свободен ли в этот момент первый прибор? Для ответа на этот вопрос необходимо проверить условие ti < Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>Т k +1, то первый прибор в момент Т k +1 занят. В этом случае проверяем, свободен ли второй прибор. Если условие i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, то проверяем условие 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >Т k +1, то в момент Т k +1 все приборы заняты. В этом случае прибавляем единицу в счетчик отказов и переходим к рассмотрению следующего требования. Каждый раз, вычислив Т k +1, надо проверить еще ус ловие окончания реализации: Tk + i < T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Повторив такое испытание n раз (с использованием различных r) и усреднив результаты опытов, определим оценки математических ожиданий числа обслуженных требований и числа требований, получивших отказ:
(14)
(Ji
n j =1
где (n обсл) j и (n отк) j - значения величин n обсл и n отк в j -ом опыте.
13

Список использованных источников
1 Емельянов А.А. Имитационное моделирование экономических процессов [Текст]: Учеб. пособие для вузов / А.А. Емельянов, Е.А. Власова, Р.В. Дума. - М. : Финансы и статистика, 2002. - 368с.
2 Бусленко, Н.П. Моделирование сложных систем [Текст]/ Н.П. Бусленко.- М. : Наука, 1978. - 399с.
3 Советов Б.Я. Моделирование систем [Текст]: Учеб. для вузов / Б.Я. Сове тов, С.А. Яковлев. -М. : Высш. школа, 1985. - 271 с.
4 Советов Б.Я. Моделирование систем [Текст]: Лабораторный практи кум: Учеб. пособие для вузов по специальности: "Автом. сист. обработ. инф. и управл." / Б.Я. Советов, С.А. Яковлев. -М. : Высш. шк., 1989. - 80 с.
5 Максимей И.В. Имитационное моделирование на ЭВМ [Текст]/ Максимей, И.В. -М: РАДИО И СВЯЗЬ, 1988. - 231с.
6 Вентцель Е.С. Теория вероятностей [ Текст ] : учеб. для вузов / Е.С. Вент цель.- М. : Высш. шк., 2001. - 575 с.
7 Гмурман, В.Е. Теория вероятностей и математическая статисти ка [ Текст ] : учеб. пособие / В.Е. Гмурман.- М. : Высш. шк., 2001. - 479 с.
Приложение А
(обязательное)
Примерные темы расчетно-графических работ
1 На травмопункте работает один врач. Длительность лечения больного
и промежутки времени между поступлениями больных - случайные величи ны, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
2 В городском автохозяйстве две ремонтные зоны. Первая обслуживает ремонты краткой и средней продолжительности, вторая - средней и долгой. По мере поломок в автохозяйство доставляют транспорт; промежуток време ни между доставками - случайная пуассоновская величина. Продолжительности ремонта - случайная величина с нормальным законом распределения. Смоделировать описанную систему. Оценить средние времена ожидания в очереди транспорта, требующие соответственно краткосрочного, среднесрочного и длительного ремонта.
3 Мини-маркет с одним контролером - кассиром обслуживает покупа телей, входящий поток которых подчиняется закону Пуассона с параметром 20 покупателей/час. Провести моделирование описанного процесса и определить вероятность простоя контролера - кассира среднюю длину очереди, среднее число покупателей в мини-маркете, среднее время ожидания обслуживания, среднее время пребывания покупателей в мини-маркете и дайте оценку его работы.
4 На АТС поступают заявки на междугородние переговоры. Поток зая вок является пуассоновским. В среднем за 1 час поступает 13 заявок. Найдите среднее число заявок, поступающих за сутки, среднее время между появлением заявок. На телефонной станции появляются сбои в работе, если за полчаса на нее поступит более 50 заявок. Найдите вероятность сбоя станции.
5 На станцию технического обслуживания поступает простейший по
ток заявок с интенсивностью 1 автомобиль за 2 ч. Во дворе в очереди может находиться не более 3 машин. Среднее время ремонта - 2 часа. Дайте оценку работы СМО и разработайте рекомендации по улучшению обслуживания.
6 Одна ткачиха обслуживает группу станков, осуществляя по мере необходимости краткосрочное вмешательство, длительность которого - случайная величина. Смоделировать описанную ситуацию. Какова вероятность простоя сразу двух станков. Как велико среднее время простоя одного станка.
7 На междугородней телефонной станции две телефонистки обслуживают общую очередь заказов. Очередной заказ обслуживает та телефонистка, которая первой освободилась. Если обе в момент поступления заказа заняты, звонок аннулируется. Смоделировать процесс, считая входные потоки пуассоновскими.
8 На травмопункте работают два врача. Длительность лечения больно
го и промежутки времени между поступлениями больных - случайные вели чины, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
9 На междугородней телефонной станции две телефонистки обслужи
вают общую очередь заказов. Очередной заказ обслуживает та телефонистка,
которая первой освободилась. Если обе в момент поступления заказа заняты, то формируется очередь. Смоделировать процесс, считая входные потоки пу- ассоновскими.
10 В системе передачи данных осуществляется обмен пакетами данных между узлами A и B по дуплексному каналу связи. Пакеты поступают в пункты системы от абонентов с интервалами времени между ними 10 ± 3 мс. Передача пакета занимает 10 мс. В пунктах имеются буферные регистры, ко торые могут хранить два пакета, включая передаваемый. В случае прихода пакета в момент занятости регистров пунктам системы предоставляется вы ход на спутниковую полудуплексную линию связи, которая осуществляет передачу пакетов данных за 10 ± 5 мс. При занятости спутниковой линии па кет получает отказ. Смоделировать обмен информацией в системе передачи данных в течение 1 мин. Определить частоту вызовов спутниковой линии и ее загрузку. В случае возможности отказов определить необходимый для безотказной работы системы объем буферных регистров.
11 Пусть на телефонной станции с одним входом используется обычная система: если абонент занят, то очередь не формируется и надо звонить сно ва. Смоделировать ситуацию: три абонента пытаются дозвониться до одного и того же владельца номера и в случае успеха разговаривают с ним некоторое (случайное по длительности) время. Какова вероятность того, что некто, пы тающийся дозвониться, не сможет это сделать за определенное время Т.
12 Торговая фирма планирует выполнять заказы на приобретение това ров по телефону, для чего необходимо установить соответствующую мини- АТС с несколькими телефонными аппаратами. Если заказ поступает, когда все линии заняты, то клиент получает отказ. Если в момент поступления за явки хотя бы одна линия свободна, то производится переключение на эту линию и оформляется заказ. Интенсивность входящего потока заявок составляет 30 заказов в час. Длительность оформления заявки в среднем равна 5 мин. Определите оптимальное число каналов обслуживания, чтобы обеспечить условие стационарной работы СМО.
13 В магазине самообслуживание 6 контролеров - кассиров. Входящий поток покупателей подчиняется закону Пуассона с интенсивностью 120 чел/час. Один кассир может обслужить 40 человек в час. Определите вероят ность простоя кассира, среднее число покупателей в очереди, среднее время ожидания, среднее число занятых кассиров. Дайте оценку работы СМО.
14 В магазин самообслуживания поступает пуассоновский поток с ин тенсивностью 200 покупателей в час. В течение дня их обслуживают 3 кон тролера-кассира с интенсивностью 90 покупателей в час. Интенсивность входного потока покупателей в часы пик возрастает до величины 400 поку пателей в час, а в часы спада достигает величины 100 покупателей в час. Определите вероятность образования очереди в магазине и среднюю длину очереди в течение дня, а также необходимое число контролеров-кассиров в часы пик и часы спада, обеспечивающие такую же длину очереди и вероятность ее образования, как и в номинальном режиме.
15 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания 100 чел/час. Кассир может обслужить 60 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
16 Провести моделирование очереди в магазине с одним продавцом при равновероятных законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
17 Провести моделирование очереди в магазине с одним продавцом при пуассоновских законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
18 Создайте модель бензоколонки. Найдите показатели качества обслуживания заявок. Определите количество стоек с тем, чтобы очередь не увеличивалась.
19 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания, 60 человек в час. Кассир может обслужить 35 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
20 Разработайте модель автобусного маршрута с n остановками. Определите показатели эффективности использования СМО.

ВВЕДЕНИЕ

ГЛАВА I. ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1 Общие понятие теории массового обслуживания

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

1.3 Графы состояний СМО

1.4 Случайные процессы

Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

2.1 Уравнения Колмогорова

2.2 Процессы «рождения – гибели»

2.3 Экономико-математическая постановка задач массового обслуживания

Глава III. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Одноканальная СМО с отказами в обслуживании

3.2 Многоканальная СМО с отказами в обслуживании

3.3 Модель многофазной системы обслуживания туристов

3.4 Одноканальная СМО с ограниченной длиной очереди

3.5 Одноканальная СМО с неограниченной очередью

3.6 Многоканальная СМО с ограниченной длиной очереди

3.7 Многоканальная СМО с неограниченной очередью

3.8 Анализ системы массового обслуживания супермаркета

ЗАКЛЮЧЕНИЕ

Введение

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

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

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

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

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

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

Глава I . Постановка задач массового обслуживание

1.1 Общие понятие теории массового обслуживания

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

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

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

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

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

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

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

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

Действительно, продолжительность пребывания покупателя в супермаркете зависит, с одной стороны, от личностных качеств покупателя, его запросов, от ассортимента товаров, который он собирается приобрести, а с другой - от формы организации обслуживания и обслуживающего персонала, что может значительно повлиять на время пребывания покупателя в супермаркете и интенсивность обслуживания. Например, овладение кассирами-контролерами работы «слепым» методом на кассовом аппарате позволило увеличить пропускную способность узлов расчета в 1,3 раза и сэкономить время, затрачиваемое на расчеты с покупателями по каждой кассе более чем на 1,5 ч в день. Внедрение единого узла расчета в супермаркете дает ощутимые преимущества покупателю. Так, если при традиционной форме расчетов время обслуживания одного покупателя составляло в среднем 1,5 мин, то при введении единого узла расчета - 67 с. Из них 44 с уходят на оформление покупки в секции и 23 с непосредственно на расчеты за покупки. Если покупатель делает несколько покупок в разных секциях, то потери времени сокращаются при приобретении двух покупок в 1,4 раза, трех - в 1,9, пяти - в 2,9 раза.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P m, n = a m _e -a ; (m=0,n),

где величина а = пр - среднее число событий, попадающих на промежуток времени t, которое можно определить через интенсивность потока событий Xследующим образом: a= λ τ

Размерность интенсивности потока X есть среднее число событий в единицу времени. Между п и λ, р и τ имеется следующая связь:

где t- весь промежуток времени, на котором рассматривается действие потока событий.

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

По условию в течение времени T не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощью вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т.е. m= 0, тогда

F(t)=1-P 0 =1-(a 0 *e -a)0!=1-e -Xt ,t≥0

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

P(T<∆t)=1-e - λ t ≈1- ≈ λΔt

Плотность распределения промежутка времени между двумя последовательными событиями получим, продифференцировав F(t) по времени,

f(t)= λe- λ t ,t≥0

Пользуясь полученной функцией плотности распределения, можно получить числовые характеристики случайной величины Т: математическое ожидание М (Т), дисперсию D(T) и среднее квадратическое отклонение σ(Т).

М(Т)= λ ∞ ∫ 0 t*e - λt *dt=1/ λ ; D(T)=1/ λ 2 ; σ(T)=1/ λ .

Отсюда можно сделать следующий вывод: средний интервал времени Т между любыми двумя соседними событиями в простейшем потоке в среднем равен 1/λ , и его среднее квадратическое отклонение также равно 1/λ, λ где, - интенсивность потока, т.е. среднее число событий, происходящих в единицу времени. Закон распределения случайной величины, обладающей такими свойствами М(Т) = Т, называется показательным (или экспоненциальным), а величина λ, является параметром этого показательного закона. Таким образом, для простейшего потока математическое ожидание интервала времени между соседними событиями равно его среднеквадратическому отклонению. В этом случае вероятность того, что число заявок, поступающих на обслуживание за промежуток времени t, равно к, определяется по закону Пуассона:

P k (t)=(λt) k / k! *e -λ t ,

где λ - интенсивность поступления потока заявок, среднее число событий в СМО за единицу времени, например[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] .

Для такого потока заявок время между двумя соседними заявками Т распределено экспоненциально с плотностью вероятности:

ƒ(t)= λe - λ t .

Случайное время ожидания в очереди начала обслуживания t оч тоже можно считать распределенным экспоненциально:

ƒ (t оч)=V*e - v t оч,

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

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

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

ƒ(t обс)=µ*е µ t обс,

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

µ=1/ t обс [чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] ,

где t обс - среднее время обслуживания заявок.

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

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

Важным частным случаем потока Пальма является так называемый поток Эрланга.

Этот поток получается «прореживанием» простейшего потока. Такое «прореживание» производится путем отбора по определенному правилу событий из простейшего потока.

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

Можно получить потоки Эрланга любого к-го порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.

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

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

Перечисленные выше характеристики к, τ, λ, L оч, Т оч, v, t обс, µ, р, Р k являются наиболее общими для СМО, которые являются обычно лишь некоторой частью целевой функции, поскольку необходимо учитывать еще и показатели коммерческой деятельности.

1.3 Графы состояний СМО

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

12

Рис. 1.3. Размеченный граф состояний СМО

Система может находиться в одном из трех состояний: S 0 -канал свободен, простаивает, S 1 - канал занят обслуживанием, S 2 - канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S 0 в S l происходит под воздействием простейшего потока заявок интенсивностью λ 01 а из состояния S l в состояние S 0 систему переводит поток обслуживания с интенсивностью λ 01 . Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность:p i (t) того, что система будет находиться в состоянии S i в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t 0 , t 1, t 2 ,..., t k ,..., t n система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая. случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния S t в любое другое Sjне зависит от того, когда и как система перешла в состояние S t . Описывается марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера к, то марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятности состояний для любого значения к-числа заявок поступивших на обслуживание.

1.4 Случайные процессы

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

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

Такие случайные процессы называются процессами без последствия, или марковскими, в которых при фиксированном настоящем будущее состояние СМО не зависит от прошлого. Случайный процесс, протекающий в системе, называется марковским случайным процессом, или «процессом без последствия», если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния t > t 0 системы S i , - в будущем (t>t Q) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние, т.е. оттого, как развивался процесс в прошлом.

Марковские случайные процессы делятся на два класса: процессы с дискретными и непрерывными состояниями. Процесс с дискретными состояниями возникает в сиcтемах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S o -телефоны свободны; S l - один из телефонов занят; S 2 - оба телефона заняты.

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

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

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

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

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

Глава II . Уравнения описывающие системы массового обслуживания

2.1 Уравнения Колмогорова

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S o , S l , S 2 (см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S i в состояние Sjпроисходят под воздействием простейших потоков событий с интенсивностями λ ij , а обратный переход под воздействием другого потока λ ij ,. Введем обозначение p i как вероятность того, что в момент времени t система находится в состоянии S i . Для любого момента времени tсправедливо записать нормировочное условие-сумма вероятностей всех состояний равна 1:

Σp i (t)=p 0 (t)+ p 1 (t)+ p 2 (t)=1

Проведем анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р 1 (t+ Δt) того, что система в момент времени (t+ Δt) будет находиться в состоянии S 1 которое достигается разными вариантами:

а) система в момент t с вероятностью p 1 (t) находилась в состоянии S 1 и за малое приращение времени Δt так и не перешла в другое соседнее состояние - ни в S 0 , ни bS 2 . Вывести систему из состояния S 1 можно суммарным простейшим потоком c интенсивностью (λ 10 +λ 12), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S 1 за малый промежуток времени Δtприближенно равна (λ 10 +λ 12)* Δt. Тогда вероятность невыхода из этого состояния равна .Bсоответствии с этим вероятность того, что система останется в состоянии Siна основании теоремы умножения вероятностей, равна:

p 1 (t) ;

б)система находилась в соседнем состоянии S o и за малое время Δt перешла в состояние S o Переход системы происходит под воздействием потока λ 01 с вероятностью, приближенно равной λ 01 Δt

Вероятность того, что система будет находиться в состоянии S 1 , в этом варианте равна p o (t)λ 01 Δt;

в) система находилась в состоянии S 2 и за время Δt перешла в состояние S 1 под воздействием потока интенсивностью λ 21 с вероятностью, приближенно равной λ 21 Δt. Вероятность того, что система будет находиться в состоянии S 1 , равна p 2 (t) λ 21 Δt.

Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

p 2 (t+Δt)= p 1 (t) + p o (t)λ 01 Δt+p 2 (t) λ 21 Δt ,

которое можно записать иначе:

p 2 (t+Δt)-p 1 (t)/ Δt= p o (t)λ 01 + p 2 (t) λ 21 - p 1 (t) (λ 10 +λ 12) .

Переходя к пределу при Δt-> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp 2 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

что является дифференциальным уравнением.

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

dp 0 /dt= p 1 λ 10 ,

dp 1 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

dp 2 /dt= p 1 λ 12 +p 2 λ 21 .

Для составления уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО S i в функции времени p i (t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S 0 – равна p 0 = 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S o . Например, при отсутствии заявок на обслуживание к = 0, р 0 = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S o и простаивает, если продолжительность рабочего дня составляет 10 ч.

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

Например, для СМО, имеющей размеченный граф из трех состояний S o , S 1 , S 2 рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

Для состояния S o → p 0 λ 01 = p 1 λ 10

Для состояния S 1 →p 1 (λ 10 +λ 12) = p 0 λ 01 +p 2 λ 21

Для состояния S 2 → p 2 λ 21 = p 1 λ 12

p 0 +p 1 +p 2 =1

dp 4 (t)/dt=λ 34 p 3 (t) - λ 43 p 4 (t) ,

p 1 (t)+ p 2 (t)+ p 3 (t)+ p 4 (t)=1 .

К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S 1, то начальные условия можно записать так:

p 1 (0)=1, p 2 (0)= p 3 (0)= p 4 (0)=0 .

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

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

p i (t), p 2 (t),…., p n (t) .

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

lim p i (t) = p i (i=1,2,…,n) ; t→∞

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

Вычислить предельные вероятности состояния р i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.

2.2 Процессы «рождения – гибели»

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

S 3

kjlS n

μ 0 μ 1 μ 3 μ 4 μ n-1

Рис. 2.1 Размеченный граф процесса «рождения - гибели»

Этот граф воспроизводит известную биологическую интерпретацию: величина λ k отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.

Для Марковского процесса «рождения - гибели», описанного стохастическим графом, приведенным на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления уравнений для конечнего числа n предельных вероятностей состояния системы S 1 , S 2 , S 3 ,… S k ,…, S n , составим соответствующие уравнения для каждого состояния:

для состояния S 0 -λ 0 p 0 =μ 0 p 1 ;

для состояния S 1 -(λ 1 +μ 0)p 1 = λ 0 p 0 +μ 1 p 2 , которое с учетом предыдущего уравнения для состояния S 0 можно преобразовать к виду λ 1 р 1 = μ 1 p 2 .

Аналогично можно составить уравнения для остальных состояний системы S 2 , S 3 ,…, S k ,…, S n . В результате получим следующую систему уравнений:

Решая эту систему уравнений, можно получить выражения, определяющие финальные состояния системы массового обслуживания:

Следует заметить, что в формулы определения финальных вероятностей состояний р 1 , р 2 , р 3 ,…, р n , входят слагаемые, являющиеся составной частью суммы выражения, определяющей р 0 . В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния S k , а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния S k , т.е. μ 0 , μ 1 , μ 2 , μ 3 ,… μ k . В связи с этим запишем эти модели в более компактном виде:

к=1,n

2.3 Экономико-математическая постановка задач массового обслуживания

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

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

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

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

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

Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Т оч =0, поскольку по своей природе в таких системах существование очереди невозможно, то L оч =0 и, следовательно, вероятность ее образования Р оч =0. По числу заявок k определятся режим работы системы, ее состояние: при k=0 – простой каналов, при 1n – обслуживание и отказ. Показателями таких СМО являются вероятность отказа в обслуживании Р отк, вероятность обслуживания Р обс, среднее время простоя канала t пр, среднее число занятых n з и свободных каналов n св, среднее обслуживания t обс, абсолютная пропускная способность А.

Для СМО с неограниченным ожиданием характерно, что вероятность обслуживания заявки Р обс =1, поскольку длина очереди и время ожидания начала обслуживания не ограничены, т.е. формально L оч →∞ и Т оч →∞. В системах возможны следующие режимы работы: при k=0 наблюдается простой каналов обслуживания, при 1n – обслуживание и очередь. Показателями таких эффективности таких СМО являются среднее число заявок в очереди L оч, среднее число заявок в системе k, среднее время пребывания заявки в системе Т смо, абсолютная пропускная способность А.

В СМО с ожиданием с ограничением на длину очереди, если число заявок в системе k=0, то наблюдается простой каналов, при 1n+m- обслуживание, очередь и отказ в ожидании обслуживания. Показателями эффективности таких СМО являются вероятность отказа в обслуживании Р отк - вероятность обслуживания Р обс, среднее число заявок в очереди L оч, среднее число заявок в системе L смо среднее время пребывания заявки в системе Т смо, абсолютная пропускная способность А.

Таким образом, перечень характеристик систем массового обслуживания можно представить следующим образом: среднее время обслуживания – t обс; среднее время ожидания в очереди – Т оч; среднее пребывания В СМО – Т смо; средняя длина очереди - L оч; среднее число заявок в СМО- L смо; количество каналов обслуживания – n; интенсивность входного потока заявок – λ; интенсивность обслуживания – μ; интенсивность нагрузки – ρ; коэффициент нагрузки – α; относительная пропускная способность – Q; абсалютная пропускная способность – А; доля времени простоя в СМО – Р 0 ; доля обслуженных заявок – Р обс; доля потерянных заявок – Р отк, среднее число занятых каналов – n з; среднее число свободных каналов - n св; коэффициент загрузки каналов – К з; среднее время простоя каналов - t пр.

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

Это часто связано с решением вопросов согласованной рабоиы цепочки или совокупностей СМО.

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

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

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

С= (С ио +С ип) →min

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

С={(С пр n св +С экз n з)+С оч Р обс λ(Т оч +t обс)+С из Р отк λ}→min.

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

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

С={С экз n з +C пр (n-n з)+C отк *Р отк *λ+С сист * n з }→min

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

К об =[(З пу *К у)+(З пв *К в)+(З пд *К д)+(З пз *К з)+(З по *К 0)+(З кт *К кт)]*К мп,

где З пу – значимость показателя устойчивости ассортимента товаров;

К у - коэффициент устойчивости ассортимента товаров;

З пв – значимость показателя внедрения прогрессивных методов продажи товаров;

К в – коэффициент внедрения прогрессивных методов продажи товаров;

З пд – значимость показателя дополнительного обслуживания;

К д - коэффициент дополнительного обслуживания;

З пз - значимость показателя завершенности покупки;

К з - коэффициент завершенности покупки;

З по - значимость показателя затрат времени на ожидание в обслуживании;

К о – показатель затрат времени на ожидание обслуживания;

З кт – значимость показателя качества труда коллектива;

К кт – коэффициент качества труда коллектива;

К мп – показатель культуры обслуживания по мнению покупателей;

Для анализа СМО можно выбирать и другие критерии оценки эффективности работы СМО. Например, в качестве такого критерия для систем с отказами можно выбирать вероятность отказа Р отк, значение которого не превышало бы заранее заданной величины. Например, требование Р отк <0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.

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

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

3.1 Одноканальная СМО с отказами в обслуживании

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

Работу одноканальной СМО n=1 можно представить в виде размеченного графа состояний (3.1).

Переходы СМО из одного состояния S 0 в другое S 1 происходят под действием входного потока заявок с интенсивностью λ, а обратный переход – под действием потока обслуживания с интенсивностью μ.

S 0

S 1

S 0 – канал обслуживания свободен; S 1 – канал занят обслуживанием;

Рис. 3.1 Размеченный граф состояний одноканальной СМО

Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:

Откуда получим дифференциальное уравнение для определения вероятности р 0 (t) состояния S 0:

Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S 0 , тогда р 0 (0)=1, р 1 (0)=0.

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

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

Вероятность р 0 (t) уменьшается с течением времени и в пределе при t→∞ стремится к величине

а вероятность р 1 (t) в то же время увеличивается от 0, стремясь в пределе при t→∞ к величине

Эти пределы вероятностей могут быть получены непосредственно из уравнений Колмогорова при условии

Функции р 0 (t) и р 1 (t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.

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

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

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

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

В пределе при t→∞ практически уже при t>3τ значение относительной пропускной способности будет равно

Абсолютная пропускная способность, определяющая число заявок, обслуживаемых в единицу времени в пределе при t→∞, равна:

Соответственно доля заявок, получивших отказ, составляет в этих же предельных условиях:

а общее число не обслуженных заявок равно

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

3.2 Многоканальная СМО с отказами в обслуживании

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

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

Туристические фирмы по продаже путевок имеют два, три, четыре и более каналов, как, например, фирма Express-Line.

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

S 0

S 1

S k

S n

μ 2μkμ (k+1)μ nμ

Рис. 3.2. Размеченный граф состояний многоканальной СМО с отказами

Поток обслуживания в каждом канале имеет интенсивность μ. По числу заявок СМО определяются ее состояния S k , представленные в виде размеченного графа:

S 0 – все каналы свободны k=0,

S 1 – занят только один канал, k=1,

S 2 – заняты только два канала, k=2,

S k – заняты k каналов,

S n – заняты все n каналов, k= n.

Состояния многоканальной СМО меняются скачкообразно в случайные моменты времени. Переход из одного состояния, например S 0 в S 1 , происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния S k в S k -1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из S n в S n -1 , имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера – математика- основателя теории массового обслуживания.

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

.

Вычислив все вероятности состояний n – канальной СМО с отказами р 0 , р 1 , р 2 , …,р k ,…, р n , можно найти характеристики системы обслуживания.

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

k=n.

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

Р отк +Р обс =1

На этом основании относительная пропускная способность опредляется по формуле

Q = P обс = 1-Р отк =1-Р n

Абсолютную пропускную способность СМО можно определить по формуле

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

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

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

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

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

Среднее время пребывания заявки в системе в установившемся режиме определятся формулой Литтла

Т смо = n з /λ.

3.3 Модель многофазной системы обслуживания туристов

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

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

Поиск Выбор Выбор Решение

референт

поиск фирмы тура по туру

Оплата Перелет Исход

Рис. 3.3 Модель многофазной системы обслуживания туристов

Проблема с позиции массового обслуживания туристов, уезжающих на отдых, заключается в определении точного места отдыха (тура), адекватного требованиям претендента, соответствующего его здоровью и финансовым возможностям и представлениям об отдыхе в целом. В этом ему могут способствовать турфирмы, поиск которых осуществляется обычно из рекламных сообщений СМО р, затем после выбора фирмы происходит получение консультаций по телефону СМО т, после удовлетворительного разговора приезд в турфирму и получение более детальных консультаций лично с референтом, затем оплата путевки и получение обслуживания от авиакомпании по перелету СМО а и в конечном счете обслуживания в отеле СМ0 0 . Дальнейшее развитие рекомендаций по улучшению работы СМО фирмы связано с изменением профессионального содержания переговоров с клиентами по телефону. Для этого необходимо углубить анализ, связанный с детализацией диалога референта с клиентами, поскольку далеко не каждый переговоры по телефону приводит к заключению договора на приобретение путевки. Проведение формализации задачи обслуживания указало на необходимость формирования полного (необходимого и достаточного) перечня характеристик и их точных значений предмета коммерческой сделки. Затем проводятся ранжирование этих характеристик, например методом парных сравнений, и расположения в диалоге по степени их значимости, например: время года (зима), месяц (январь), климат (сухой), температура воздуха (+25"С), влажность (40%), географическое место (ближе к экватору), время авиаперелета (до 5 часов), трансферт, страна (Египет), город (Хургада), море (Красное), температура воды в море (+23°С), ранг отеля (4 звезды, работающий кондиционер, гарантия наличия шампуня в номере), удаленность от моря (до 300 м), удаленность от магазинов (рядом), удаленность от дискотек и других источников шума (подальше, тишина в течение сна в отеле), питание (шведский стол - завтрак, ужин, частота изменения меню за неделю), отели (Princes, Marlin-In, Hour-Palace), экскурсии (Каир, Луксор, коралловые острова, подводное плавание), увеселительные шоу, спортивные игры, цена путевки, форма оплаты, содержание страховки, что брать с собой, что купить на месте, гарантии, штрафные санкции.

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

0, если характеристика менее значима,

а ij = 1, если характеристика равнозначима,

2, если характеристика доминирует.

После этого определяются значения сумм оценок по каждому показателю строки S i =∑a ij , вес каждой характеристики M i = S i /n 2 и соответственно интегральный критерий, на основе которого можно провести выбор турфирмы, тура или отеля, по формуле

F = ∑ M i * x i -» max.

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

F b = ∑ M i * Б i * x i -> max.

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

3.4 Одноканальная СМО с ограниченной длиной очереди

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения-гибели», с тем отличием, что при наличии только одного канала.

S m

S 3

S 2

S 1

S 0

λ λλλ... λ

μ μμμ... μ

Рис. 3.4. Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны

Состояния СМО можно представить следующим образом:

S 0 - канал обслуживания свободен,

S, - канал обслуживания занят, но очереди нет,

S 2 - канал обслуживания занят, в очереди стоит одна заявка,

S 3 - канал обслуживания занят, в очереди стоят две заявки,

S m +1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.

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

p 1 = ρ * ρ о

p 2 =ρ 2 * ρ 0

p k =ρ k * ρ 0

P m+1 = p m=1 * ρ 0

p 0 = -1

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

ρ= (1- ρ )

Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р 0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2). Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании. Действительно, выражение для предельной вероятности р 0 в случае т = 0 имеет вид:

p о = μ / (λ+μ)

И в случае λ = μ имеет величину р 0 = 1 / 2.

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

Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии S m +1 и, следовательно, все места в очереди да заняты и один канал обслуживает Поэтому вероятность отказа определяется вероятностью появлением

Состояния S m +1:

P отк = p m +1 = ρ m +1 * p 0

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

Q = 1- p отк = 1- ρ m+1 * p 0

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

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

случайная величина кпринимает следующие только целочисленные значения:

1 - в очереди стоит одна заявка,

2 - в очереди две заявки,

т-в очереди все места заняты

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

k	1	2	m
p i	p 2	p 3	p m+1

Математическое ожидание этой случайной величины равно:

L оч = 1* p 2 +2* p 3 +...+ m* p m +1

В общем случае при p ≠1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

L оч = p 2 * 1- p m * (m-m*p+1) * p 0

В частном случае при р = 1, когда все вероятности p k оказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m ( m +1)

Тогда получим формулу

L’ оч = m(m+1) * p 0 = m(m+1) (p=1).

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

Т оч = L оч /А (при р ≠ 1) и Т 1 оч = L’ оч /А(при р = 1).

Такой результат, когда оказывается, что Т оч ~ 1/ λ, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина L оч является функцией от λ и μ и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.

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

Если отказаться от ограничения на длину очереди, т.е. устремить m-> →∞, то случаи р < 1 и р ≥1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

p k =р k *(1 - р)

При достаточно большом к вероятность p k стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А -λ Q - λ следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:

L оч =p 2 1-p

а среднее время ожидания по формуле Литтла

Т оч = L оч /А

В пределе р << 1 получаем Т оч = ρ / μт.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р ≥ 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t → ∞). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки. Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем ρ и μ, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.

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

L смо= m +1 ;2

Т смо= L смо; при p ≠1

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

Т смо= m +1 при p ≠1 2μ

3.5 Одноканальная СМО с неограниченной очередью

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

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

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

Рассмотрим простейшую одноканальную СМО с ожиданием обслуживания, на которую поступает пуассоновский поток заявок с интенсивностью λ и интенсивностью обслуживания µ.

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

Размеченный граф состояний такой системы приведен на рис. 3.5

Количество возможных состояний ее бесконечно:

Канал свободен, очереди нет, ;

Канал занят обслуживанием, очереди нет, ;

Канал занят, одна заявка в очереди, ;

Канал занят , заявка в очереди.

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

Рис. 3.5 Граф состояний одноканальной СМО с неограниченной очередью.

Следует заметить, что для СМО с ограниченной длиной очереди в формуле

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

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

Вероятность пребывания в очереди k заявок равна:

;

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

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

;

Среднее время пребывания заявки в системе –

;

Среднее время пребывания заявки с системе –

.

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

3.6 Многоканальная СМО с ограниченной длиной очереди

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

Все каналы свободны, ;

Занят только один канал (любой), ;

Заняты только два канала (любых), ;

Заняты все каналов, .

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

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

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

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

Граф состояний n-канальной СМО с очередью, ограниченной m местами на рис.3.6

Рис. 3.6 Граф состояний n-канальной СМО с ограничением на длину очереди m

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

Запишем выражения для предельных вероятностей состояний:

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

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

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

Относительная пропускная способность будет равна:

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

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

Среднее число простаивающих каналов –

Коэффициент занятости (использования) каналов –

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

Среднее число заявок, находящихся в очередях –

В случае если , эта формула принимает другой вид –

Среднее время ожидания в очереди определяется формулами Литтла –

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

3.7 Многоканальная СМО с неограниченной очередью

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

S - все каналы свободны, k=0;

S - занят один канал, остальные свободны, k=1;

S - заняты два канала, остальные свободны, k=2;

S - заняты все n каналов, k=n, очереди нет;

S - заняты все n каналов, одна заявка в очереди, k=n+1,

S - заняты все n каналов, r заявок в очереди, k=n+r,

Вероятности состояний получим из формул для многоканальной СМО с ограниченной очередью при переходе к пределу при m. Следует заметить, что сумма геометрической прогрессии в выражении для p расходится при уровне загрузки p/n>1, очередь будет бесконечно возрастать, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Очереди нет

…

…

Рис.3.7 Размеченный граф состояний многоканальной СМО

с неограниченной очередью

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

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

среднее число заявок в очереди –

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

среднее число заявок в СМО –

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

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

На этом основании можно определить вероятность, или долю времени занятости всех каналов обслуживанием

Если же все каналы уже заняты обслуживанием, то вероятность состояния определяется выражением

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

Среднее число заявок, находящихся в очереди и ожидающих обслуживания, равно:

Среднее время ожидания заявки в очереди по формуле Литтла: и в системе

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

среднее число свободных каналов:

коэффициент занятости каналов обслуживанием:

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

3.8 Анализ системы массового обслуживания супермаркета

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

СМО

СМО

Интенсивность входного потока покупателей;

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

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

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

Рис.4.1. Модель двухфазной СМО торгового зала универсама

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

1) экономико-организационные факторы: система материальной ответственности в универсаме; средняя стоимость и структура одной покупки;

2) организационная структура кассового узла;

3) технико-технологические факторы: применяемые типы кассовых аппаратов и кассовых кабин; применяемая контролером-кассиром технология обслуживания покупателей; соответствие мощности кассового узла интенсивности покупательских потоков.

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

Рассмотрим обе фазы системы обслуживания:

1) выбор покупателями товаров в зоне самообслуживания;

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

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

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

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

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

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

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

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

Часы работы	День недели
	пятница			суббота			воскресенье
	оче-редь,	количество покупателей без покупок		оче-редь,	количество покупателей без покупок		оче-редь,	количество покупателей без покупок
		чел.	%		чел.	%		чел.	%
с 9 до 10	2	38	5	5	60	5,4	7	64	4,2
с 10 до 11	3	44	5,3	5	67	5	6	62	3,7
с 11 до 12	3	54	6,5	4	60	5,8	7	121	8,8
с 12 до 13	2	43	4,9	4	63	5,5	8	156	10
с 14 до 15	2	48	5,5	6	79	6,7	7	125	6,5
с 15 до 16	3	61	7,3	6	97	6,4	5	85	7,2
с 16 до 17	4	77	7,1	8	140	9,7	5	76	6
с 17 до 18	5	91	6,8	7	92	8,4	4	83	7,2
с 18 до 19	5	130	7,3	6	88	5,9	7	132	8
с 19 до 20	6	105	7,6	6	77	6
с 20 до 21	6	58	7	5	39	4,4
Итого	749	6,5	862	6,3	904	4,5

В организации работы кассового узла универсама имеется еще одна важная особенность, которая значительно влияет на его пропускную способность: наличие экспресс-касс (одной-двух покупок). Изучение структуры потока покупателей в универсамах по типу кассового обслуживания показывает, что поток оборот составляет 12,9% (табл. 4.2).

Дни недели	Потоки покупателей			Товарооборот
	всего	по экспресс-кассам	% к дневномупотоку	всего	по экспресс-кассам	% к дневному товарообороту
Летний период
Понедельник	11182	3856	34,5	39669,2	3128,39	7,9
Вторник	10207	1627	15,9	38526,6	1842,25	4,8
Среда	10175	2435	24	33945	2047,37	6
Четверг	10318	2202	21,3	36355,6	1778,9	4,9
Пятница	11377	2469	21,7	43250,9	5572,46	12,9
Суббота	10962	1561	14,2	39873	1307,62	3,3
Воскресенье	10894	2043	18,8	35237,6	1883,38	5,1
Зимний период
Понедельник	10269	1857	18,1	37121,6	2429,73	6,5
Вторник	10784	1665	15,4	38460,9	1950,41	5,1
Среда	11167	3729	33,4	39440,3	4912,99	12,49,4
Четверг	11521	2451	21,3	40000,7	3764,58	9,4
Пятница	11485	1878	16,4	43669,5	2900,73	6,6
Суббота	13689	2498	18,2	52336,9	4752,77	9,1
Воскресенье	13436	4471	33,3	47679,9	6051,93	12,7

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

1) функцию распределения времени покупателей на выбор товаров в зоне самообслуживания;

2) функцию распределения времени работы контролера-кассира для обычных касс и экспресс-касс;

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

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

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

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

Функция распределения времени обслуживания покупателей контролерами-кассирами является экспоненциальной, такое допущение не приводит к большим ошибкам.

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

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

Целевая функция может быть записана в общем виде связи (критерия) выручки от реализации от характеристик СМО:

где - кассовый узел состоит из =7 касс обычного типа и =2 экспресс-касс,

Интенсивность обслуживания покупателей в зоне обычных касс – 0,823 чел./мин;

Интенсивность нагрузки кассовых аппаратов в зоне обычных касс – 6,65,

Интенсивность обслуживания покупателей в зоне экспресс-касс – 2,18 чел./мин;

Интенсивность входящего потока в зону обычных касс – 5,47 чел./мин

Интенсивность нагрузки кассовых аппаратов в зоне экспресс-касс – 1,63,

Интенсивность входящего потока в зону экспресс-касс – 3,55 чел./мин;

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

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

В табл.6.6.3 приведены результаты характеристик качества функционирования СМО в зоне расчетного узла.

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

Из приведенных данных в табл. 4.3 следует, что если бы для расчета была выбрана:

1) модель с отказами, то 22,6% потока покупателей, обслуживаемых обычными кассами, и соответственно 33,6% потока покупателей, обслуживаемых экспресс-кассами, должны были бы уйти без покупок;

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

Табл. 4.3 Характеристики системы массового обслуживания покупателей в зоне расчетного узла

Тип кассы	Количество касс в узле	Тип СМО	Характеристики СМО
			Среднее число занятых касс,	среднее время ожидания обслуживания,	Вероятность потери заявок,
Обычные кассы	7	с отказами с ожиданием с ограничением
Экспресс-кассы	2	с отказами с ожиданием с ограничением

3) модель с ограничением на длину очереди, то только 0,12% потока покупателей, обслуживаемых обычными кассами, и 1,8% потока покупателей, обслуживаемых экспресс-кассами, покинут торговый зал без покупок. Следовательно, модель с ограничением на длину очереди позволяет более точно и реально описать процесс обслуживания покупателей в зоне кассового узла.

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

Анализ данных этой таблицы показывает, что не учет фактора «Структура потока покупателей по типу кассового обслуживания» на стадии технологического проектирования может привести к увеличению зоны расчетного узла на 22-33%, а отсюда соответственно и к уменьшению установочных и выставочных площадей торгово-технологического оборудования и товарной массы, размещаемой в торговом зале.

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

№ п/п	Характеристики СМО	Единица измерения	Обозначение		Показатели, рассчитанные по типам универсамов торговой площади, кв. м
					Без экспресс-касс						С учетом экспресс-касс
					650		1000		2000		650			1000			2000
											Обычные кассы		Экспресс-кассы	Обычные кассы		экспресс-кассы	Обычные кассы		экспресс-кассы
1	Количество покупателей	чел.	k		2310		3340		6680		1460		850	2040		1300	4080		2600
2	Интенсивность входящего потока		λ		9,64		13,9		27,9		6,08		3,55	8,55		5,41	17,1		10,8
3	Интенсивность обслуживания	чел./мин	μ		0,823		0,823		0,823		0,823		2,18	0,823		2,18	0,823		2,18
4	Интенсивность нагрузки	-	ρ		11,7		16,95		33,8		6,65		1,63	10,35		2,48	20,7		4,95
5	Количество кассовых аппаратов	шт.	n		12		17		34		7		2	11		3	21		5
6	Общее количество касс расчетного узла	шт.		∑n		12		17		34		9			14			26

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

На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количества касс время ожидания покупателей в очереди растет, а затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требования Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла, тем вероятность потери требований будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как ожидания и вероятность потерь будут резко уменьшаться.

Для универсама торговой площадью 650 этот предел для зоны обычных касс лежит между 6 и 7 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания – 2,66 мин, а вероятность потери заявок очень мала – 0,1%. Таким образом, которая позволит получить минимальные совокупные затраты на массовое обслуживание покупателей.

Тип кассового обслуживания	Количество кассовых аппаратов в узле n, шт.	Характеристики системы обслуживания		Средняя выручка за 1 ч. руб.	Средняя потеря выручки за 1 ч. руб	Число покупателей в зоне расчетного узла	Площадь зоны расчетного узла, Sy, м	Удель ный вес площади зоны узла 650/ Sy
		Среднее время ожидания, Т,мин	Вероятность потери заявок
Зоны Обычных касс
Зоны экспресс-касс

Заключение

На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количество касс время ожидания покупателей в очереди растет. А затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требований Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла. Тем вероятность потери требований будет уменьшаться и соответственно тем большее число покупателей будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как расчетный узел превысит оптимальный мощность, время ожидания и вероятность потерь будут резко уменьшаться.

Для универсама торговой площадью 650 кв. метров этот предел для зоны обычных касс лежит между 6-8 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания- 2,66 мин, а вероятность потери заявок очень мало - 0,1 % . Таким образом, задача состоит в выборе такой мощности кассового узла, которая позволит получит минимальные совокупные затраты на массовое обслуживание покупателей.

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

Четвериков С. Ю. , Попов М.А.

Россия, Институт экономики и предпринимательства (г. Москва)

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

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

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

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

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

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

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

Параметры X и ц имеют простой физический смысл:

X - среднее число поступающих за единицу времени требований или интенсивность входящего потока;

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

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

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

Так называемую загрузку системы.

Тогда неравенство (1) можно переписать в виде:

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

Наконец, еще одно замечание к функционированию системы с детерминированными характеристиками:

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

в случае р

наконец, если р > 1, то за единицу времени очередь в среднем увеличивается на Мр-1).

В реальных системах массового обслуживания существенную роль играют элементы случайности:

во-первых, времена между поступлениями требований не являются детерминированными;

во-вторых, не являются детерминированными времена обслуживания требований.

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

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

Рассмотрим формализованное описание СМО. Основными параметрами СМО являются:

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

структура системы;

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

дисциплина обслуживания.

Рассмотрим эти параметры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• 1. Гнеденко Б.В. Курс теории вероятностей. М.: Физматгиз, 1961.
• 2. Феллер В. Введение в теорию вероятностей и ее приложения.T.I. М.: Мир,
• 1984.
• 3. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966.
• 4. Саати Т.Л. Элементы теории массового обслуживания и ее приложения. М.: Сов. радио, 1965.

Курсовая работа

«Имитационное моделирование системы массового обслуживания»

по курсу «Исследование операций»

Введение

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

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

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

– Абсолютная пропускная способность системы (А

Q

– вероятность отказа обслуживания заявки ();

k );

– среднее число заявок в очереди ();

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

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

1. Основные характеристики CМОи показатели их эффективности

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 Уравнения Колмогорова

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

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

Например, для графа состояний, приведенного на рис. 1, уравнения Колмогорова имеют вид:

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

,

,

Следовательно, одно из уравнений системы можно отбросить и заменить уравнением (1.2.1).

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

1.3 Финальные вероятности и граф состояний СМО

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

Смысл финальных вероятностей состоит в том, что они равны среднему относительному времени нахождения системы в данном состоянии.

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

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

Рис. 2. Граф состояний в моделях СМО

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

Получается система из ( n +1) уравнения, которая решается методом исключения. Этот метод заключается в том, что последовательно все вероятности системы выражаются через вероятность .

,

.

Подставляя эти выражения в последнее уравнение системы, находим , затем находим остальные вероятности состояний СМО.

1.4 Показатели эффективности СМО

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

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

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

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

– среднее число занятых каналов (k );

– среднее число заявок в СМО ();

– среднее время пребывания заявки в системе ();

– среднее число заявок в очереди () – длина очереди;

– среднее число заявок в системе ();

– среднее время пребывания заявки в очереди ();

– среднее время пребывания заявки в системе ()

– степень загрузки канала (), т.е. вероятность того, что канал занят;

– среднее число заявок, обслуживаемых в единицу времени;

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

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

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

(1.4.1)

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

Формулы для вычисления показателей эффективности приведены в таб. 1.

Таблица 1.

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

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

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

Компьютерное имитационное моделирование следует рассматривать как статический эксперимент.

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

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

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

1.6 Построение имитационных моделей

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

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

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

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

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

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

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

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

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

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

, , т.е. , где

Исправленная дисперсия, ,

N – число прогонов программы, – надежность, .

2. Аналитическое моделирование СМО

2.1 Граф состояний системы и уравнения Колмогорова

Рассмотрим двухканальную систему массового обслуживания (n = 2) с ограниченной очередью равной шести (m = 4). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4,8 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 2 и показательным законом распределения временем обслуживания.

Данная система имеет 7 состояний, обозначим их:

S 0 – система свободная, нет заявок;

S 1 – 1 заявка на обслуживании, очередь пуста;

S 2 – 2 заявки на обслуживании, очередь пуста;

S 3 – 2 заявки на обслуживании, 1 заявка в очереди;

S 4 – 2 заявки на обслуживании, 2 заявки в очереди;

S 5 – 2 заявки на обслуживании, 3 заявки в очереди;

S 6 – 2 заявки на обслуживании, 4 заявки в очереди;

Вероятности прихода системы в состояния S 0 , S 1 , S 2 , …, S 6 соответственно равны Р 0 , Р 1 , Р 2 , …, Р 6 .

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

Рис. 3. Граф состояний двухканальной СМО

Для построенного графа запишем уравнения Колмогорова:

Чтобы решить данную систему зададим начальные условия:

Систему уравнений Колмогорова (систему дифференциальных уравнений) решим численным методом Эйлера с помощью программного пакета Maple 11 (см. Приложение 1).

Метод Эйлера

где- в нашем случае, это правые части уравнений Колмогорова, n=6.

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

Значения вероятностей СМО при равны:

Рис. 4. Зависимости вероятностей состояний системы от времени

P 0

P 5

P 4

P 3

P 2

P 1

2.2 Финальные вероятности системы

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

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

Решим данную систему линейных уравнений с помощью программного пакета Maple 11 (см. Приложение 1).

Получим финальные вероятности системы:

Сравнение вероятностей, полученных из системы уравнений Колмогорова при , с финальными вероятностями показывает, что ошибки равны:

Т.е. достаточно малы. Это подтверждает правильность полученных результатов.

2.3 Расчет показатели эффективности системы по финальным вероятностям

Найдем показатели эффективности системы массового обслуживания.

Сначала вычислим приведенную интенсивность потока заявок:

1) Вероятность отказав обслуживании заявки, т.е. вероятность того, что заявка покидает систему не обслуженной.В нашем случае заявке отказывается в обслуживании, если все 2 канала заняты, и очередь максимально заполнена (т.е. 4 человек в очереди), это соответствует состоянию системы S 6 . Т.к. вероятность прихода системы в состояние S 6 равна Р 6 , то

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

5) Среднее время пребывания заявки в очередиопределяется формулой Литтла:

3. Имитационное моделирование СМО

3.1 Алгоритм метода имитационного моделирования СМО (пошаговый подход)

Рассмотрим двухканальную систему массового обслуживания (n = 2) с максимальной длиной очереди равной шести (m = 4). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4,8 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 2 и показательным законом распределения временем обслуживания.

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

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

Где (3.1.1)

Исходя из условия (3.1.1) определим шаг по времени .

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

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

В программе это осуществляет isRequested () . Интервал времени примем постоянным и равным 0,0001, тогда отношение будет равно 10000. Если заявка поступила, то она принимает значение «истина», в противном случае значение «ложь».

bool isRequested()

double r = R. NextDouble();

if (r < (timeStep * lambda))

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

double GetServiceTime()

double r = R. NextDouble();

return (-1/mu*Math. Log (1-r, Math.E));

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

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

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

По истечении времени Т , т.е., после моделирования работы СМО, вычисляются показатели эффективности работы системы и результаты выводятся на экран.

3.2 Блок-схема программы

Блок-схема программы, реализующей описанный алгоритм, приведена на рис. 5.

Рис. 5. Блок-схема программы

Распишем некоторые блоки более подробно.

Блок 1. Задание начальных значений параметров.

Random R; // Генератор случайных чисел

public uint maxQueueLength; // Максимальная длина очереди

public uint channelCount; // Число каналов в системе

public double lambda; // Интенсивность потока поступления заявок

public double mu; // Интенсивность потока обслуживания заявок

public double timeStep; // Шагповремени

public double timeOfFinishProcessingReq; // Время окончания обслуживания заявки во всех каналах

public double timeInQueue; // Время пребывания СМО в состояниях с очередью

public double processingTime; // Времяработысистемы

public double totalProcessingTime; // Суммарноевремяобслуживаниязаявок

public uint requestEntryCount; // Числопоступившихзаявок

public uint declinedRequestCount; // Числоотказанныхзаявок

public uint acceptedRequestCount; // Числообслуженныхзаявок

uint queueLength; // Длина очереди //

Тип, описывающий состояния СМО

enum SysCondition {S0, S1, S2, S3, S4, S5, S6};

SysCondition currentSystemCondition; // Текущее состояние системы

Задание состояний системы. Выделим у данной 2-х канальной системы 7 различных состояний: S 0 , S 1 . S 6 . СМО находится в состоянии S 0 , когда система свободна; S 1 – хотя бы один канал свободен; в состоянии S 2 , когда все каналы заняты, и есть место в очереди; в состоянии S 6 – все каналы заняты, и очередь достигла максимальной длины (queueLength = 4).

Определяем текущее состояние системы с помощью функции GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

{p_currentCondit ++;}

return p_currentCondit + (int) QueueLength;

Изменение времени пребывания СМО в состояниях с длиной очереди 1, 2,3,4. Это реализуется следующим программным кодом:

if (queueLength > 0)

timeInQueue += timeStep;

if (queueLength > 1)

{timeInQueue += timeStep;}

Присутствует такая операция, как помещение заявки на обслуживание в свободный канал. Просматриваются, начиная с первого, все каналы, когда выполняется условие timeOfFinishProcessingReq [ i ] <= 0 (канал свободен), в него подается заявка, т.е. генерируется время окончания обслуживания заявки.

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq [i] <= 0)

timeOfFinishProcessingReq [i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq [i];

Обслуживаниезаявоквканалахмоделируетсякодом:

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq [i] > 0)

timeOfFinishProcessingReq [i] -= timeStep;

Алгоритм метода имитационного моделирования реализован на языке программирования C#.

3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования

Наиболее важными являются такие показатели, как:

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

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

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

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

5) Среднее время пребывания заявки в очереди определяется формулой Литтла

6) Среднее число занятых каналовопределяется следующим образом:

7) Процент заявок, которым было отказано в обслуживании, находится по формуле

8) Процент обслуженных заявок находится по формуле

3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования

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

Величина попадает в доверительный интервал, если выполняется неравенство

, где

математическое ожидание (среднее значение), находится по формуле

Исправленная дисперсия,

,

N =20 – число прогонов,

– надежность. При и N =20 .

Результат работы программы представлен на рис. 6.

Рис. 6. Вид программы

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

Таблица 2.

Показатели эффективности СМО	Результаты аналитического моделирования	Результаты имитационного моделирования (послед. шаг)	Результаты имитационного моделирования
			Нижняя граница доверительного интервала	Верхняя граница доверительного интервала
Вероятность отказа		0,174698253017626	0,158495148639101	0,246483801571923
Относительная пропускная способность		0,825301746982374	0,753516198428077	0,841504851360899
Абсолютная пропускная способность		3,96144838551539	3,61687775245477	4,03922328653232
Средняя длина очереди		1,68655313447018	1,62655862750852	2,10148609204869
Среднее время пребывания заявки в очереди	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Среднее число занятых каналов		1,9807241927577	1,80843887622738	2,01961164326616

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

Заключение

В данной работе рассмотрены основные методы моделирования СМО и расчета показателей их эффективности.

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

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

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

Литература

1. Вентцель Е.С. Исследование операций. – М.: Дрофа, 2004. – 208 с.

2. Волков И.К., Загоруйко Е.А. Исследование операций. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2002. – 435 с.

3. Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2000. – 447 с.

4. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике. – М.: Высшая школа, 1979. – 400 с.

5. Ивницкий В.Л. Теория сетей массового обслуживания. – М.: Физматлит, 2004. – 772 с.

6. Исследование операций в экономике/ под ред. Н.Ш. Кремера. – М.: Юнити, 2004. – 407 с.

7. Таха Х.А. Введение в исследование операций. – М.: ИД «Вильямс», 2005. – 902 с.

8. Харин Ю.С., Малюгин В.И., Кирлица В.П. и др. Основы имитационного и статистического моделирования. – Минск: Дизайн ПРО, 1997. – 288 с.