Большие резервы повышения производительности труда и снижения издержек заложены в улучшении организации предоставления услуг как производственного, так и непроизводственного назначения. Разработка и применение усредненных нормативов на работы по обслуживанию во многих случаях не дают достаточного эффекта при определении необходимого количества персонала, так как условия, в которых осуществляются эти работы, различны даже на одном предприятии. Например, использование нормативов системы планово-предупредительного ремонта для выявления необходимого количества ремонтного персонала по текущему обслуживанию не сможет обеспечить выбор оптимального варианта в связи с тем, что объем работ по ремонту зависит от многих трудноучитываемых факторов: продолжительности работы оборудования с момента его установки, состояния оборудования и его загрузки по мощности и времени, квалификации ремонтного персонала, обеспечения запасными частями и т. п. То же самое можно сказать о роли нормативов в деятельности предприятий, осуществляющих предоставление услуг населению.
Оптимальная численность обслуживающего персонала в конкретных условиях может быть определена с помощью теории массового обслуживания.
Теория массового обслуживания, как принято ее называть в нашей стране, или теория очередей, по терминологии английских и американских авторов - одна из основных составных частей исследования операций. Постановка первых вопросов теории массового обслуживания связана с исследованиями датского ученого Эрланга, работавшего в области теории проводной связи.
Характерная особенность задач массового обслуживания, возникающих в экономике и организации производства и транспорта, в области физики частиц, автоматического управления, военного дела, в работе портов и телефонных станций, учреждений бытового обслуживания и т. д., состоит в наличии обслуживающей системы (рис. 8.6), на вход которой в какие-то неизвестные заранее моменты времени поступают заявки (требования). Например, на телефонную станцию (обслуживающая система) поступают вызовы абонентов (требования), в ремонтную мастерскую - машины на ремонт. В первом случае требования удовлетворяются, т. е. после вызова происходит соединение абонентов, если линии (каналы) обслуживания свободны, если же канал занят, требование получает отказ. Во втором случае, если обслуживающие каналы (например, бригада рабочих, осуществляющих ремонт) заняты, требование становится в очередь и ждет освобождения одного из каналов.
Рис. 8.6.
Таким образом, системы массового обслуживания можно разделить на два основных типа: системы с отказами и системы с ожиданием. Обслуживание в системе с ожиданием может осуществляться в порядке поступления требований по заранее заданному закону (устанавливается приоритет для некоторых требований по отношению к другим) или в случайном порядке.
Время ожидания в очереди может быть как неограниченным, так и ограниченным, т. е. требование, «прождав» некоторое время, покидает очередь и остается необслуженным.
Каждая система массового обслуживания характеризуется пропускной способностью, определяющейся числом каналов, их производительностью и характером потока требований. Производительность канала характеризуется временем обслуживания одного требования.
Предмет теории массового обслуживания - это установление зависимости между характером потока требований, производительностью отдельного канала, числом каналов и эффективностью обслуживания.
Показателями эффективности обслуживания в зависимости от условий задачи и целей исследования могут служить различные величины и функции: средний процент отказов, среднее время простоя, среднее время ожидания, средняя длина очереди, вероятность нулевого времени ожидания и т. д.
Поток требований, поступающих на вход системы массового обслуживания, можно считать потоком случайных событий, так как моменты поступления требований заранее неизвестны. Поток событий можно изобразить последовательностью моментов их появления на оси времени. Мы будем рассматривать поток однородных событий, различающихся лишь моментами появления. Если моменты появления событий разделены одинаковыми интервалами, поток событий называется регулярным. Однако типичен для систем массового обслуживания поток требований, поступающих в случайные моменты времени.
Поток событий называется ординарным, если вероятность попадания на элементарный участок Dt двух или более событий есть величина бесконечно малая по сравнению с вероятностью попадания одного события на этот участок. Это означает, что совпадение двух или более событий невозможно, требования приходят по одному, а не парами, тройками и т. д.
Поток событий называется стационарным, если вероятность попадания какого-то количества событий на определенный участок времени зависит только от длины этого участка, а не от расположения на оси времени, для стационарного потока характерна независимость вероятностных характеристик от времени, он имеет постоянную плотность (среднее число требований в единицу времени).
Поток событий называется потоком без последствия, если для любых неперекрывающихся участков времени количество событий, попадающих на один из них, не зависит от количества событий, попадающих на другие. Это означает, что требования поступают в систему независимо друг от друга.
Ординарный стационарный поток без последствия называется простейшим (или стационарным пуассоновским). Термин «пуассоновский поток» употребляется потому, что, как известно из теории вероятностей, для ординарного потока без последствия число событий, попадающих на участок t, распределено по закону Пуассона:
где Хх = а - математическое ожидание количества событий на участке т; X - параметр, характеризующий плотность потока (к > 0);
Рщ СО - вероятность того, что за время X произойдет т событий.
В частности, при т = 0
и есть вероятность того, что за время т не произойдет ни одного события. Отсюда можно получить
т. е. вероятность того, что за время т произойдет хотя бы одно событие.
В общем случае время обслуживания есть случайная величина, поэтому для получения количественных характеристик системы массового обслуживания необходимо задавать закон распределения времени обслуживания.
Задачи теории массового обслуживания имеют простое аналитическое решение, если поток требований является пуассоновским, а время обслуживания распределено по показательному закону:
t o6 - среднее время обслуживания требования.
В реальных задачах могут встретиться потоки более общего вида, где время обслуживания распределено не только по показательному закону.
Кроме того, различные системы массового обслуживания могут образовывать сеть, когда требования, выходящие из одних систем массового обслуживания с различными вероятностями, поступают на входы других систем или уходят из сети.
В сложных экономических системах ожидание требования начала обслуживания часто вызывает простой какой-то системы, в которую это требование должно поступить после обслуживания первой системой. В ряде случаев очень большие расходы вызывает простой обслуживающей системы (например, вычислительный центр, крупный завод), в других случаях нежелательно ожидание (например, в случае поступления очень важного заказа, важности результата для других систем и т. д.).
Обычно при решении экономических задач нужно достичь экстремального (минимального или максимального) значения некоторого критерия (функции стоимости), определяемого для различных конкретных условий. При исследовании работы систем массового обслуживания чаще всего минимизируются расходы из-за простоя и ожидания, потери вследствие ухода требования, оценивается целесообразность увеличения числа каналов.
Например, необходимо организовать ремонтное обслуживание оборудования в каком-либо цехе или на участке. Для этого нужно выделить определенное количество рабочих-ремонтников. Если рабочих будет мало, это вызовет простой оборудования в ожидании ремонта и соответственно простой производственных рабочих. Если же ремонтников будет слишком много, это приведет к нерациональному использованию их рабочего времени, к излишним затратам на их содержание. И в том и в другом случае производство будет иметь потери, которые в конечном счете обусловят снижение производительности труда и повышение себестоимости продукции. Необходимо выбрать вариант, при котором суммарные потери будут наименьшими.
Математические методы теории массового обслуживания дают возможность установить среднее количество требований, находящихся в системе, в очереди, среднее количество необслуженных требований, среднее время ожидания, вероятность отказа, вероятность того, что длина очереди не превысит заданную, и т. д.
Кратко рассмотрим подход к решению одной из классических задач теории массового обслуживания. Пусть имеется п станков и бригада из т человек, обслуживающая эти станки. Станок, работающий в момент времени t, отказывает к моменту t + т с вероятностью Р(т) = - 1 - е~ кх, где е~ кХ есть вероятность того, что за время t не произойдет ни одного отказа. Время ремонта станка - случайная величина г). Для такой системы можно вычислить среднее число простаивающих рабочих. Эта характеристика используется в дальнейшем для оптимального выбора соотношения между пит исходя из экономических критериев.
С применением методов теории массового обслуживания можно решать также задачи выбора наиболее рациональной организации многостаночного обслуживания. Например, необходимо установить, какое количество автоматов может эффективно обслуживать один рабочий. Если у рабочего будет слишком много станков, то неизбежны простои оборудования из-за того, что он не будет успевать своевременно заправлять их материалом, проверять качество изготовленной детали и т. п., если же обслуживаемых станков будет мало, рабочий будет систематически простаивать.
Задача в данном случае состоит в том, чтобы выбрать, исходя из конкретных условий работы оборудования и рабочего, наиболее выгодный для производства вариант.
Методы теории массового обслуживания смогут использоваться и при решении такого типа задач, как определение оптимальной численности бригады, обслуживающей какие-либо агрегаты (вагранки, печи и т. д.), определение необходимого количества транспортных средств для нужд цехов и т. д.
Рассмотрим математический аппарат, с помощью которого можно оценить функционирование в стационарном режиме простейших систем массового обслуживания с отказами при условии поступления в них пуассоновского потока требований. Такая задача впервые была решена Эрлангом, который получил следующие зависимости :
Вероятность того, что обслуживанием заняты К аппаратов (линий, приборов и т. д.)
где А - плотность потока заявок;
п - число аппаратов (линий, приборов и т. д.); т - параметр обслуживания.
Чаще всего в формулах используется параметр а = А/p, тогда предыдущую формулу запишем так:
Частными случаями этой формулы будут:
Вероятность того, что все обслуживающие аппараты свободны:
Вероятность того, что все обслуживающие аппараты заняты. Это одновременно и вероятность отказа в обслуживании вновь поступившего требования в систему:
На практике необходимо часто определять:
Среднее число приборов, занятых обслуживанием, и связанный с ними коэффициент занятости аппаратов:
Это будет и доля загруженных аппаратов за время обслуживания:
Среднее число аппаратов, свободных от обслуживания:
Коэффициент простоя аппаратов:
При решении практических задач целесообразно для проверки правильности полученных результатов пользоваться вполне очевидным равенством
Было доказано, что формулы Эрланга справедливы не только для случая, когда время распределено по показательному закону, но и для случаев любого распределения времени обслуживания. Этот результат позволит значительно расширить области применения формул Эрланга для решения многих практических задач.
Рассмотрим несколько примеров.
Пример 1. Необходимо оценить работу автоматизированной телефонной станции (АТС), которая имеет п = 5 линий связи. К услугам станции обращаются абоненты с требованиями на ведение разговоров. Естественно, что моменты поступления требований на станцию случайны и независимы друг от друга.
Задачу решим на примере простейшего потока требований. Пусть средняя плотность потока вызовов в единицу времени X = 2. Продолжительность каждого разговора - также величина случайная. Можно принять, что продолжительность разговоров различных абонентов подчинена показательному закону распределения. Пусть среднее время, необходимое для ведения каждого разговора, равно t o6 = 1 ед. времени. Может возникнуть сомнение в правомочности принятия показательного закона распределения времени ведения разговоров абонентов. Но, как уже говорилось выше, формулами Эрланга можно пользоваться при любых законах распределения времени разговоров абонентов.
В итоге в предлагаемом примере необходимо оценить функционирование АТС.
Решение
Находим параметр
Вероятность того, что все линии будут свободны при работе АТС, может быть определена по формуле (8.24):
Вероятность того, что абоненту будет отказано в обслуживании, рассчитывается по формуле (8.25):
Определяем среднее число занятых линий связи во время работы АТС.
Для проведения необходимых расчетов составим таблицу 8.3.
Таблица для расчета параметров задачи
По результатам расчетов получено:
Коэффициент простоя линий равен:
При решении этого примера целесообразно воспользоваться специальной таблицей 4 приложения 5 к книге (подобные таблицы приводятся и в других работах по массовому обслуживанию). Входом в нее является К и а, а из таблицы можно получить значения вероятностей Р к и их частных значений Р 0 и Р п.
Пример 2. Необходимо спроектировать АТС с пропускной способностью, при которой вероятность получения абонентом отказа в обслуживании не превосходила Р п X = 0,5 вызова в минуту. Считается, что средняя продолжительность разговора равна f o6 -2 мин. Определить необходимое число линий связи.
Значит, коэффициент загрузки линий связи равен:
Среднее число свободных линий связи равно:
Решение
Определяем параметр
Для составления расчетной таблицы воспользуемся таблицей 4 приложения 5 к работе .
Таблица 8.4
Определение вероятностей
Из данных таблицы 8.4 следует, что АТС нужно проектировать на 5 линий связи. При этом будет обеспечена связь одного абонента с другими с вероятностью Р = 0,997.
Несмотря на достаточно обширную область возможного применения теории массового обслуживания, следует отметить, что часто бывает довольно трудно подобрать подходящую модель для описания конкретной ситуации, а когда это удается, то возникают алгоритмические трудности ее решения.
- Вывод приводимых ниже формул можно найти в работе .
При решении многих задач оптимальной организации торговли, бытового обслуживания, складского хозяйства и т.п. часто используется интерпретация производственной структуры как системы массового обслуживания (СМО), т.е.системы в которой с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой стороны происходит постоянное удовлетворение этих запросов.
Всякая СМО включает 4 элемента:
1) источник требований (ИТ);
2) входящий поток требований;
3) система обслуживания, которая включает в себя:
· очередь,
· обслуживающее устройство (каналы обслуживания);
4) выходящий поток требований.
Требованием называется каждый отдельный запрос на выполнение какой-либо работы. Поступив в обслуживающую систему, требование (заявка) на обслуживание присоединяется к очереди других ранее поступивших требований и ждет обслуживания. Блок обслуживания выбирает очередное требование и начинает его обслуживать. После завершения обслуживания обслуживающая система приступает к обслуживанию следующего требования. Этот цикл работы СМО многократно повторяется.
К основным характеристикам СМО относятся:
· среднее число заявок находящихся в системе;
· среднее число заявок в очереди (ее длина);
· средняя продолжительность пребывания клиента в системе;
· средняя продолжительность пребывания клиента в очереди;
· среднее количество занятых средств обслуживания;
· среднее время обслуживания;
· вероятность отказа в обслуживании и др.
Для классификации СМО используется ряд признаков:
1. В зависимости от условий ожидания начала обслуживания различают:
· СМО с отказами (потерями) – требования получившие отказ (каналы заняты) теряются;
· СМО с ожиданием - требования становятся в очередь и ожидают обслуживания, такие СМО делятся на:
o СМО с ограниченной длиной очереди;
o СМО с неограниченной длиной очереди;
o СМО с ограниченным временем ожидания.
2. По числу каналов обслуживания различают два вида СМО:
· одноканальные;
· многоканальные.
3. По месту нахождения источника требования (ИТ) СМО делятся на два вида:
· разомкнутые – ИТ вне системы;
· замкнутые – ИТ в составе системы.
4. По дисциплине обслуживания (в зависимости от порядка выбора заявок на обслуживание) выделяют:
· СМО с приоритетом – вначале обслуживаются заявки с более высоким приоритетом;
· СМО без приоритета – приоритет в обслуживании заявок отсутствует.
Методы и модели исследования СМО можно разделить на
· аналитические;
· статистические.
Аналитические методы позволяют получить характеристики СМО как функции её параметров, но применимы эти методы к ограниченному кругу задач теории массового обслуживания (ТМО).
Простейший поток требований
В настоящее время достаточно хорошо разработана ТМО применительно к простейшему (Пуассоновскому) потоку заявок на обслуживание.
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой , где λ – параметр потока (число требований, поступающих в единицу времени).
Основные свойства простейшего потока:
Ординарность – практическая невозможность одновременного поступления двух и более требований.
Стационарность – означает, что среднее число требований (математическое ожидание) поступающих в систему в ед. времени (λ=const ) не меняется во времени.
Отсутствие последействия – число требований, поступивших в систему до момента времени t не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Δt .
Время обслуживания требований в системе
Важной характеристикой СМО является время обслуживания одного требования в системе. Оно является случайной величиной и может быть описано законом распределения.
Наиболее часто рассматривается как случайная величина (СВ), которая подчиняется экспоненциальному закону распределения.
Для этого закона функция распределения вероятности имеет вид: 
, т.е. вероятность того, что время обслуживания не превосходит некоторой величины t
, определяется формулой , где μ
– параметр экспоненциального закона распределения времени обслуживания требований в системе – т.е. величина, обратная среднему времени обслуживания одного требования , т.е. .
Теория массового обслуживания представляет собой область прикладной математики, использующую методы теории случайных процессов и теории вероятностей для исследования различной природы сложных систем. Теория массового обслуживания непосредственно не связана с оптимизацией. Назначение ее состоит в том, чтобы на основе результатов наблюдений за «входом» в систему предсказать ее возможности и организовать наилучшее обслуживание для конкретной ситуации и понять, как последнее отразится на стоимости системы в целом. Для систем, относящихся к системам массового обслуживания, существует определенный класс задач, решение которых позволяет ответить на актуальные для сегодняшнего времени вопросы. С какой интенсивностью должно проходить обслуживание или должен выполняться процесс при заданной интенсивности и других параметрах входящего потока требований, чтобы минимизировать очередь или задержку в подготовке документа или другого вида информации? Каковы вероятность появления задержки или очереди и ее величина? Сколько времени требование находится в очереди и каким образом минимизировать его задержку? Какова вероятность потери требования (клиента)? Какова должна быть оптимальная загрузка обслуживающих каналов? При каких параметрах системы достигаются минимальные потери прибыли? К этому перечню можно добавить еще целый ряд задач.
Система массового обслуживания (СМО) включает следующие структурообразующие объекты: источник требований; входной поток требований (поступление заявок); очередь; обслуживающую систему как совокупность каналов обслуживания заявок; выходной поток (об-служенные заявки или удовлетворенные требования). Рассмотрим их модели.
Источник требований. По месту нахождения источника, формиру-ющего требования, СМО делятся на разомкнутые, когда источник на-ходится вне системы, и замкнутые, когда источник находится внутри системы.?
Входной поток требований. Подавляющее большинство теоретиче-ских разработок по исследованию систем массового обслуживания вы-полнено для условия, когда входной поток требований является пуассоновским (простейшим). Этот поток обладает рядом важных свойств. Он стационарен, ординарен и не имеет последствий.
Следующее важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки.
В случае разделения пуассоновского потока на N независимых по-токов получим, что интенсивность потока Х(будет равна гХ, где г.-доля /-го потока во входном потоке требований.
Очередь. Очереди, определяемые как множество требований, ожи-дающих обслуживания, представляются несколькими моделями: оче-редь с отказами, с ограниченным временем ожидания (заявка ждет определенное время), ограниченной длиной и, наконец, неограничен-ным временем ожидания. Порядок поступления заявок на обслужива-ние называется дисциплиной очереди. Требования могут принимать
ся по мере поступления, случайным порядком, с приоритетом, по принципу «последняя - первой», по определенным каналам.
Процесс обслуживания. Основным параметром процесса обслужи-вания считается время обслуживания требования каналом у - f. (/ = 1, 2,..., т). Величина тв каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией ис-полнителя, технологией работ, окружающей средой и т.д. Законы рас-пределения случайной величины Ту могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения.
Важнейшее свойство экспоненциального распределения заключа-ется в следующем.
Выходной поток обслуженных требований. Выходной поток - это поток результатов деятельности, представленных выполненными тре-бованиями в виде той или иной продукции или услуги. К основным параметрам выходного потока относятся интенсивность выхода из си-стемы обслуженных требований и характер распределения времени между моментами выпуска продукции. В общем случае эти параметры определяются моделью входного потока, дисциплиной очереди и мо-делью обслуживания. Для СМО с параллельными каналами и одно-фазным обслуживанием существует теорема о том, что при пуассоновском входном потоке с параметром X и одинаковым для каждого канала распределением времени обслуживания с параметром ц в стационарном состоянии выходной поток имеет пуассоновское распределение с параметром g. В многофазных системах выходной поток одного канала служит входным потоком для другого канала.
Особенность моделей СМО связана с достаточно строгим математи-ческим описанием функционирования систем, что достигается благода-ря их унификации по ряду признаков. Так, в зависимости от модели ожидания требованием начала обслуживания различают следующие СМО:
системы с потерями или отказами;
системы с ожиданием;
системы с ограниченным временем ожидания (ВО);
системы с ограниченной длиной очереди (ДО).
По числу каналов обслуживания системы делятся на одноканальные (т = 1) и многоканальные (т > 1). Одной из форм классификации СМО служит кодовая классификация Д. Кендалла. В соответствии с этой классификацией характеристику СМО записывают в виде трех, четырех или пяти символов. Например, а/Ь/с, где а - тип распределения входного потока требований, Ъ - тип распределения времени обслуживания, с - число каналов обслуживания. Для пуассоновского и экспоненциального распределений принимают символ М, для любого произвольного распределения - символ в. Например, запись М/М/2 означает, что входной поток требований пуассоновский, время обслуживания распределено по экспоненциальному закону, в системе имеются два канала. Четвертый символ () указывает допустимую длину очереди, пятый (е) - порядок отбора требований.
Модели СМО могут быть детерминированными или вероятност-ными. В первом случае параметры и переменные модели - это посто-янные величины, во втором - случайные.
Исследование СМО заключается в нахождении показателей, харак-теризующих качество и условия работы обслуживающей системы и показателей, отражающих экономические последствия принятых ре-шений согласно первым показателям. К показателям первой группы относятся следующие.
Рассмотрим приемы вычисления показателей первой группы на
примере наиболее распространенной модели СМО (М/М/т > 2) с ожиданием, содержащей т параллельных обслуживающих каналов. Здесь поступающие требования не теряются и оставляют систему лишь после обслуживания. Каналы выполняют однородные операции, и время обслуживания каждым каналом * распределено по экспоненциальному закону с параметром т (10.5), а входящий поток - пуассоновский с параметром X (10.1); дисциплина очереди не регламентирована, и отсутствует ограничение на число поступающих требований. Модель СМО представляется в виде системы уравнений для стационарного состояния.
Пример. Требуется провести оценку эффективности централизации нескольких отделов или служб с однородными функциями. В качестве объекта рассматриваются две службы такси, которые приобрела компания «Автосервис». Заявки клиентов между службами распределяются поровну. Спрос на такси к диспетчеру поступает с частотой 10 вызовов в час. Среднее время обслуживания одного клиента составляет 11,5 мин. Вызовы такси распределены во времени по пуассоновскому закону, а продолжительность обслуживания одного клиента - по экспоненциальному закону. Каждая служба такси оснащена двумя автомобилями.
Возникает вопрос об экономической целесообразности централи-зации управления таксопарком. Для этого необходимо сравнить два варианта:
1) вариант с независимым обслуживанием системами типа (М/М/2) при51= 10 вызовов/ч,т = 11,5мин. ит = 2;
2) вариант с одной очередью типа (М/М/4) при X = 10 2 = 20 вызовов /ч, т - 11,5 мин. и /и = 4.
Приведенные оценки показывают, что централизация служб позволяет сократить среднее время ожидания клиентом вызванного по телефону такси примерно вдвое. Это не гарантия, что клиент откажется от заказа, но существенное сокращение времени ожидания. В дальнейшем, кроме создания единой службы такси, необходимо рассматривать вопросы увеличения парка такси. При решении задач с размерностью т > 5 методами теории массового обслуживания потребуется автоматизированное вычисление.
Подводя итоги, отметим, что теория массового обслуживания предоставляет исследователю множество разнообразных моделей и методов решения задач по повышению эффективности обслуживания по-
требителей, клиентов. Для ее изучения следует обратиться к фундаментальным трудам отечественных (А.Я. Хинчин, Б.В. Гнеденко, Н.П. Бусленко, И.Н. Коваленко) и зарубежных (А. Эрланг, Т.А. Саати, Г. Вагнер, X. Taxa) ученых, а также и к другим современным публикациям, например.
Марковские случайные процессы
Названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях и, в том числе, в исследовании операций и теории принятия оптимальных решений.
Марковский процесс - дискретный или непрерывный случайный процесс X (t ), который можно полностью задать с помощью двух величин:
· вероятности P (x ,t ) того, что случайная величина x (t ) в момент времени t равна x , и
· вероятности P (x 2 , t 2 |x 1 ,t 1) того, что если x при t = t 1 равен x 1 , то при t = t 2 он равен x 2 .
Вторая из этих величин называется вероятностью перехода из состояния x 1 при t = t 1 в состояние x 2 при t = t 2 .
Цепями Маркова называют дискретные по времени и значению Марковские
процессы.
Пример 1
Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
19.5.1. Формулы и определения Марковских цепей
Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)
Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)
независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:
P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.
Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е.
P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что P ij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.
Предположим, что некая фирма осуществляет доставку оборудования по Москве: в северный округ (обозначим А), южный (В) и центральный (С). Фирма имеет группу курьеров, которая обслуживает эти районы. Понятно, что для осуществления следующей доставки курьер едет в тот район, который на данный момент ему ближе. Статистически было определено следующее:
1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;
2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;
3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.
Таким образом, район следующей доставки определяется только предыдущей доставкой.
Матрица вероятностей перехода будет выглядеть следующим образом:
Например, р 12 = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А. Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит только от местонахождения в момент времени t.
Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:
1) сначала из С в С и потом из С в В;
2) С-->B и B-->B;
3) С-->A и A-->B.
Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:
P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)
Подставляя числовые значения:
P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33
Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки. Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.
Рассмотрим более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:
Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.
Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:
1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).
2 способ. Вычислить матрицу P 3:
Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:
Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).
Теория массового обслуживания
Это раздел исследования операций , который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях, как процессы обслуживания, т. е. удовлетворения каких-то запросов, заказов (напр., обслуживание кораблей в порту - их разгрузка и погрузка, обслуживание токарей в инструментальной кладовой цеха - выдача им резцов, бслуживание клиентов в прачечной - стирка белья и т. д.).
При всем разнообразии эти процессы имеют общие черты: требования на обслуживание нерегулярно (случайно) поступают в канал обслуживания (место у причала, окно в раздаточной) и в зависимости от его занятости, продолжительности обслуживания и других факторов образуют очередьтребований .
Теория массового обслуживания изучает статистические закономерности поступления требований и на этой основе вырабатывает решения , т. е. такие характеристики, при которых затраты времени на ожидание в очереди, с одной стороны, и на простой каналов обслуживания - с другой, были бы наименьшими. Всю систему производства и потребления товаров можно трактовать как систему массового обслуживания, где встречаются люди (клиенты) и товары. Сумма потерь времени на ожидание в очередях и на простои каналов обслуживания (хранение товаров на складах) рассматривается как мера эффективности изучаемой экономической системы .
Методы анализа систем массового обслуживания
Методы и модели, применяемые в теории массового обслуживания, можно условно разделить на аналитические и имитационные.
Аналитические методы теории массового обслуживания позволяют получить характеристики системы как некоторые функции параметров ее функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО.
Имитационные методы основаны на моделировании процессов массового обслуживания на ЭВМ и применяются, если невозможно применение аналитических моделей.
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения задач массового обслуживания, в которых входящий поток требований является простейшим (пуассоновским).
Для простейшего потока частота поступлений требований в систему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно к требований задается формулой:
Простейший поток обладает тремя основными свойствами:
1) ординарностью,
2) стационарностью и
3) отсутствием последействия.
Ординарность потока означает практическую невозможность одновременного поступления двух и более требований. Например, достаточно малой является вероятность того, что из группы станков, обслуживаемых бригадой ремонтников, одновременно выйдут из строя несколько станков.
Стационарным называется поток, для которого математическое ожидание числа требований, поступающих в систему в единицу времени (обозначим А, - параметр распределения Пуассона), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени At зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt
Например, если на ткацком станке в данный момент времени произошел обрыв нити и он устранен ткачихой, то это не определяет, произойдет новый обрыв на данном станке в следующий момент или нет, тем более это не влияет на вероятность возникновения обрыва на других станках.
Важная характеристика СМО - время обслуживания требований в системе. Время обслуживания одного требования является, как правило, случайной величиной и, следовательно, может быть описано законом распределения. Наибольшее распространение в теории и особенно в практических приложениях получил экспоненциальный закон распределения времени обслуживания. Функция распределения для этого закона имеет вид:
т.е. вероятность того, что время обслуживания не превзойдет некоторой величины t, определяется формулой (5.2), где µ - параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания
Системы массового обслуживания классифицируются:
1. В зависимости от условий ожидания начала обслуживания:
· СМО с потерями (отказами)
· СМО с ожиданием
В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и покидают систему. Классическим примером системы с отказами является телефонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и покидает систему.
В СМО с ожиданием требование, застав все обслуживающие каналы занятыми, становится в очередь и ожидает, пока освободится [ один из обслуживающих каналов.
СМО, допускающие очередь, но с ограниченным числом требований в ней, называются системами с ограниченной длиной очереди.
СМО, допускающие очередь, но с ограниченным сроком пребывания каждого требования в ней, называются системами с ограниченным временем ожидания.
2. По числу каналов обслуживания СМО делятся на:
Одноканальные;
Многоканальные.
3. По месту нахождения источника требований СМО подразделяются на:
разомкнутые, когда источник требования находится вне системы;
замкнутые, когда источник находится в самой системе.
19.7. Задачи анализа замкнутых и разомкнутых систем массового обслуживания
Замкнутые и разомкнутые системы,в зависимости от времени ожидания могут быть и системами массового обслуживания с ожиданием. Это наиболее распространенные СМО. Они изучаются с помощью аналитических моделей.
Системой массового обслуживания сожиданием называется система, в которой требования, поступившие в момент, когда все обслуживающие каналы заняты, ставятся в очередь и обслуживаются по мере освобождения каналов.
Примером разомкнутой системы может служить ателье по ремонту телевизоров. Здесь неисправные телевизоры - это источник требований на их обслуживание, они находятся вне самой системы, поэтому число требований можно считать неограниченным. К замкнутым СМО относится, например, станочный участок, в котором станки являются источником неисправностей, а следовательно, источником требований на их обслуживание, например, бригадой наладчиков.
Общая постановка задачи состоит в следующем. Система имеет п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование.
В систему поступает простейший (пуассоновский) поток требований с параметром А.. Если в момент поступления очередного требования в системе на обслуживании уже находится не менее п требований, т.е. все каналы заняты, то это требование становится в очередь и ждет начала обслуживания. Время обслуживания каждого требования - случайная величина, которая подчиняется экспоненциальному закону распределения с параметром µ .
СМО с ожиданием можно разбить на две большие группы: замкнутые и разомкнутые. К замкнутым относятся системы, в которых поступающий поток требований возникает в самой системе и ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
Если питающий источник обладает бесконечным числом требований и находится вне системы, то системы называют разомкнутыми. Примерами разомкнутых систем могут служить магазины, кассы вокзалов, портов и др. Для этих систем поступающий поток требований можно считать неограниченным. Кроме того, довольно распространены разомкнутые СМО с ожиданием и ограниченной длиной очереди, с ограниченным временем пребывания требования в очереди и др.
Отмеченные особенности функционирования СМО с ожиданием, обусловленные их видами, накладывают определенные условия на используемый математический аппарат. Расчет характеристик работы всех таких СМО может быть проведен на основе расчета вероятностей состояний СМО (так называемые формулы Эрланга).
Рассмотрим порядок расчета характеристик работы разомкнутых систем с ожиданием и ограниченной длиной очереди.
Такие СМО состоят из п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование. В систему поступает простейший поток требований с параметром А., а время обслуживания требования является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром ц. Если в момент поступления очередного требования все п каналов заняты, а в очереди стоит не меньше т требований, то требование становится в очередь. Если же в очереди уже стоит т требований, то поступившее требование покидает СМО. Другими словами, требование получает отказ, если в системе находится п + т требований. Из уравнений, описывающих состояние таких систем, могут быть получены следующие формулы для расчета их основных характеристик.
1. Вероятность того, что все обслуживающие каналы свободны,
(5.14)
2. Вероятность того, что в системе находится к требований при условии, что общее число этих требований не превосходит числа обслуживающих каналов; другими словами, вероятность того, что занято к каналов,
 |
3. Вероятность того, что в системе находится к требований, когда число этих требований больше числа обслуживающих каналов,
(5.16)
4. Вероятность того, что все обслуживающие каналы заняты,
(5.17)
5. Вероятность отказа
(5.18)
6. Средняя длина очереди
7. Среднее число свободных от обслуживания каналов
Пример 2. Фирма занимается доставкой грузов по заказам и имеет четыре машины, которые работают круглосуточно. Поток заказов является простейшим, и в среднем за час поступает одна заявка. Время перевозки грузов подчиняется экспоненциальному закону распределения, и в среднем перевозка одного груза занимает один час. При количестве заказов на перевозки, равном 10, фирма прекращает прием заявок до тех пор, пока очередь не уменьшится.
Требуется определить характеристики работы фирмы.
Решение. Данная система относится к типу СМО с ожиданием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:
Вероятность того, что все машины свободны от перевозки грузов, находится по формуле (5.14):
Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет
Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18) будет равна
, а средняя длина очереди в соответствии с формулой (5.19) составит
Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18), будет равна
а средняя длина очереди в соответствии с формулой (5.19) составит
Таким образом, заказчик практически никогда не получит отказа в принятии заявки на перевозку, однако загрузка машин будет достаточно мала. Так например, лишь в двух случаях из ста будут заняты все четыре машины.
Перейдем к рассмотрению алгоритмов расчета характеристик функционирования замкнутых СМО с ожиданием. Поскольку система замкнутая, то к постановке задачи следует добавить условие: поток поступающих требований ограничен, т.е. в системе обслуживания одновременно не может находиться больше т требований (т - число обслуживаемых объектов). Такие СМО называются также системами с ожиданием и ограниченным потоком требований.
За критерий, характеризующий качество функционирования рассматриваемой системы, примем отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе, или коэффициент простоя обслуживаемых объектов. В качестве другого критерия возьмем отношение среднего числа незанятых обслуживающих каналов к их общему числу, или коэффициент простоя обслуживающих каналов.
Первый из критериев характеризует потери времени из-за ожидания начала обслуживания. Второй критерий показывает полноту загрузки обслуживающей системы и имеет важное значение в задачах организации труда.
Очевидно, что очередь может возникнуть только в том случае, когда число каналов меньше наибольшего числа требований, находящихся одновременно в обслуживающей системе (п < т).
Приведем последовательность расчетов характеристик замкнутых СМО с ожиданием и необходимые формулы.
1. Параметр α=α/µ. -
показатель загрузки системы, т.е. математическое ожидание числа требований, поступающих в систему за время, равное средней длительности обслуживания 
2. Вероятность того, что занято к обслуживающих каналов при условии, что число требований, находящихся в системе, не превосходит числа обслуживающих каналов системы,
На промышленных предприятиях теория игр может использоваться для выбора оптимальных решений, например при создании рациональных запасов сырья, материалов, полуфабрикатов, в вопросах качества продукции и других экономических ситуациях. В первом случае противоборствуют две тенденции: увеличения запасов, в том числе и страховых, гарантирующих бесперебойную работу производства; сокращения запасов, обеспечивающих минимизацию затрат на их хранение; во втором - стремления к выпуску большего количества продукции, ведущего к снижению трудовых затрат; к повышению качества, сопровождающемуся часто уменьшением количества изделий и, следовательно, возрастанием трудовых затрат. В машиностроительном производстве противоборствующими направлениями являются стремление к максимальной экономии металла в конструкциях, с одной стороны, и обеспечение необходимой прочности конструкций - с другой.
В сельском хозяйстве теория игр может применяться при решении экономических задач, в которых оппозиционной силой выступает природа, и когда вероятность наступления тех или иных событий многовариантна или неизвестна.
Природные условия нередко сказываются и на эффективности работы промышленных предприятий.
Математическая теория массового обслуживания
Теория массового обслуживания является очень актуальной в наше время. От её совершенствования порой зависят очень важные компоненты современной жизни. Из сказанного выше мы видим, что СМО применяются во многих областях деятельности человека, которые связаны с удовлетворением потребностей заявителей на обслуживание.
Одним из самых главных мест применения СМО является экономика. Ведь где, как не в экономике больше всего сталкиваются с удовлетворением потребностей. Когда запросов на удовлетворение потребностей много, а средств удовлетворения меньше, чем запросов. Очень важным является правильно рассчитать систему обслуживания запросов, ведь если запросы будут потеряны из-за того, что их вовремя не обслужили – фирма (предприятие, банк и т.д.) потеряет значительную часть прибыли. Для оптимизации системы обслуживания и используется СМО. Её разработкой для конкретных условий занимаются менеджеры.
Теория массового обслуживания – это очень многогранное понятие. А, так как человеку свойственно все систематизировать для облегчения понимания, теория массового обслуживания стала базироваться на математическом аппарате. Математическое моделирование СМО является наиболее прогрессивным и точным.
Теория массового обслуживания впервые применялась в телефонии, а затем и в других областях хозяйственной деятельности.
Например, организация нормального процесса обслуживания покупателей связана с правильным определением следующих показателей: количества предприятий данного торгового профиля, численности продавцов в них (в том числе и "механических"), наличия соответствующих основных фондов, частоты завоза товаров, численности обслуживаемого населения, плотности обращаемости и потребности в соответствующих товарах (по групповому и внутригрупповому ассортименту). Если предположить, что предприятие располагает необходимыми основными фондами, торгует товарами, имеющимися в достаточном количестве (при нормальной частоте завоза), то и тогда в процессе обслуживания остаются такие переменные величины, которые могут существенно повлиять на качество обслуживания. Надлежит, следовательно, выбрать такой оптимальный вариант организации торгового обслуживания населения, при котором время обслуживания будет минимальным, качество - высоким, не будет излишних народнохозяйственных затрат. Математический аппарат теории массового обслуживания облегчает решение этой задачи.
Аналитическое моделирование на основе теории систем массового обслуживания.
При аналитическом моделировании исследование процессов или объектов заменяется построением их математических моделей и исследованием этих моделей. В основу метода положены идентичность формы уравнений и однозначность соотношений между переменными в уравнениях, описывающих оригинал и модель. Поскольку события, происходящие в локальных вычислительных сетях, носят случайный характер, то для их изучения наиболее подходящими являются вероятностные математические модели теории массового обслуживания. Объектами исследования в теории массового обслуживания являются системы массового обслуживания (СМО) и сети массового обслуживания (Семо). Системы массового обслуживания классифицируются по следующим признакам:
Закону распределения входного потока заявок;
Числу обслуживающих приборов;
Закону распределения времени обслуживания в обслуживающих приборах;
Числу мест в очереди;
Дисциплине обслуживания.
СМО классифицируются на разные группы в зависимости от состава, от времени пребывания в очереди до начала обслуживания, от дисциплины обслуживания требований.
По составу СМО бывают одноканальные (с одним обслуживающим устройством) и многоканальными (с большим числом обслуживающих устройств). Многоканальные системы могут состоять из обслуживающих устройств как одинаковой, так и разной производительности.
По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:
1) с неограниченным временем ожидания (с ожиданием),
2) с отказами;
3) смешанного типа.
В СМО с неограниченным временем ожидания очередное требование, застав все устройства занятыми, становится в очередь и ожидает обслуживания до тех пор, пока одно из устройств не освободится.
В системах с отказами поступившее требование, застав все устройства занятыми, покидает систему. Классическим примером системы с отказами может служить работа автоматической телефонной станции.
В системах смешанного типа поступившее требование, застав все (устройства занятыми, становятся в очередь и ожидают обслуживания в течение ограниченного времени. Не дождавшись обслуживания в установленное время, требование покидает систему.
В системах с определенной дисциплиной обслуживания поступившее требование, застав все устройства занятыми, в зависимости от своего приоритета, либо обслуживается вне очереди, либо становится в очередь.
Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства (каналы) и выходящий поток требований.
Таким образом, из вышеописанного можно сделать вывод о том, что теория массового обслуживания просто необходима в нашей жизни. Так как мы ежедневно имеем дело с очередями, то эта теория позволяет решать многие жизненные ситуации.
С точки зрения тех, кого обслуживают, очередь связана с бесполезной потерей времени и всегда ассоциируется только с отрицательным восприятием. Одной из важнейших экономических характеристик СМО является время, теряемое заявкой в очереди на ожидание обслуживания. Большое количество заявок, ожидающих обслуживания, кроме отрицательного влияния на субъективное восприятие, мешает нормальной работе даже при небольших временных затратах. Хорошо организованное обслуживание соответствует реально незначительному времени нахождения заявки в очереди. В условиях рыночной экономики и при наличии конкуренции низкий уровень обслуживания приводит к потере потенциальных заявок и снижению конкурентоспособности. Поэтому для менеджера важным является контролировать процессы образования очереди. Пренебрежение этой стороной менеджмента может привести к серьезным экономическим потерям, вплоть до вытеснения из рынка. Теория массового обслуживания дает методы анализа характеристик очереди и выявления путей ее уменьшения.
