Некоторые главы линейного программирования: теория игр, теория массового обслуживания (стр. 4 )

4.1. . 4.2. . 4.3. .

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

Теория систем массового обслуживания (СМО) начала развиваться в начале XX столетия. Иохансен в 1907 г. сформулировал основные предпосылки новой теории. В 1909 г. шведский математик Эрланг применил теорию вероятностей к исследованию зависимости обслуживания телефонных вызовов от числа поступающих на телефонную станцию вызовов. В нашей стране известный математик систематизировал основные положения СМО в монографии «Теория очередей». Именно такое название теории СМО используется за рубежом.

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

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

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

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

НЕ нашли? Не то? Что вы ищете?

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

1) входной поток заявок;

2) очередь;

3) каналы обслуживания;

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

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

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

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

Показатели эффективности СМО описывают ее возможность справляться с потоком заявок.

К числу показателей эффективности СМО с отказами относятся:

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

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

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

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

К числу показателей эффективности СМО с очередью относятся:

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

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

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

· вероятность того, что канал занят.

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

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

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

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

Пуассоновский поток событий обладает следующими свойствами:

— отсутствия последствия (число событий, попавших на заданный временной интервал, не зависит от числа событий, попавших на другие интервалы);

— ординарности (вероятность попадания на элементарный временной интервал двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события);

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

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

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

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

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

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

Рис. 1

На рис. 1 изображена СМО, состоящая из одного телефонного аппарата, который находится в двух возможных состояниях: либо свободен (S0), либо занят (S1); λ01 – интенсивность нагрузки аппарата, или количество заявок на переговоры в единицу времени; λ10 – интенсивность обслуживания аппаратом, или количество обслуживаемых заявок в единицу времени.

Стрелка из S0 в S1 означает переход системы из состояния «аппарат свободен» в состояние «аппарат занят». Стрелка из S1 в S0 означает обратный переход.

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

В общем случае вероятностью i-го состояния pi(t) называется вероятность того, что в момент t система будет находиться в состоянии Si.

Для любого момента t справедливо соотношение:

, (5)

где n+1 – общее число состояний СМО.

Определить вероятности состояний СМО можно, решив систему уравнений Колмогорова.

Алгоритм составления системы уравнений Колмогорова:

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

2. В правую часть каждого управления ставится:

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

б) минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го состояния.

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

Задав начальные условия и решив систему дифференциальных уравнений Колмогорова, находят систему функций времени pi(t), где i – номер состояния. Это позволяет получить дискретное распределение вероятностей СМО для любого момента времени. Для достаточно большого значения времени t независимо от начальных условий распределение вероятностей стабилизируется и практически не зависит от времени.

2.4. Одноканальная система массового обслуживания с отказами

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

Другая случайная величина Ts – время обслуживания каналом одной заявки – также распределена по закону Пуассона с параметром μ:

Параметры λ и μ называются соответственно интенсивностью потока заявок и интенсивностью потока обслуживания. Например, среднее значение равно математическому ожиданию M(Ts), откуда и следует формула и название μ:

Состояния СМО характеризуются простаиванием или занятостью ее канала, т. е. система может находиться в одном из двух состояний: S0 – канал свободен или S1 – канал занят. Из состояния S0 в состояние S1 систему переводит поток входящих заявок, а из состояния S1 в состояние S0 – поток обслуживаний. Плотности вероятностей перехода из состояния S0 в состояние S1 и обратно равны соответственно λ и μ. Граф состояний СМО показан на рис.2.

Рис. 2

Пусть p0(t) и p1(t) соответственно вероятности состояний системы S0 и S1 в момент времени t. Справедливо условие (5):

p0(t) + p1(t) =

В силу того, что процесс является марковским, вероятности p0(t) и p1(t) удовлетворяют системе уравнений Колмогорова:

Подстановка условия (6) в систему приводит к обыкновенному дифференциальному уравнению относительно p0(t)

. (7)

При условии, что в начальный момент времени t=0 канал свободен:

p0(0) = 1, p1(0) = 0,

получаем решение уравнения (7)

. (8)

Далее из условия (6) имеем

. (9)

Из формул (8) и (9) видно, что с ростом времени t вторые слагаемые в числителях стремятся к нулю, т. е. p0(t) и p1(t) заметно отличны от постоянных величин лишь в начале работы СМО. Рассмотрим предельные значения вероятностей состояния СМО, т. е. при . Тогда из (8) и (9) получаем:

Заметим, что при μ<λ вероятность отказа выше 0,5 и превышает вероятность обслуживания.

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

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

Вероятность отказа в обслуживании заявки, когда канал занят, это вероятность p1:

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

Аналогично, среднее время простоя канала равно

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

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

Решение. Телефонную станцию рассматриваем как одноканальную СМО с отказами. мин.; интенсивности поступающего и обслуженного потоков заявок равны соответственно λ = 0,8; μ = 0,67. Тогда по формулам, приведенным выше, имеем: Q = 0,455; pr = 0,545; А = λQ = 0,364 выз./мин. Заметим здесь, что абсолютная пропускная способность СМО А оказалась почти вдвое меньше интенсивности μ потока обслуживания, это обусловлено случайным характером потока заявок.

2.5. Одноканальная система массового обслуживания

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

Примером одноканальной СМО с неограниченной очередью является одна касса в универмаге.

Пусть поток заявок, поступающих в систему, имеет интенсивность λ, а поток обслуживания – интенсивность μ. Граф состояний подобной системы представлен на рис.3.

Рис. 3

На рис.3 введены следующие обозначения:

состояние S0 – канал свободен;

состояние S1 – канал занят, очереди нет;

состояние S2 – канал занят, одна заявка стоит в очереди; …;

состояние Sk – канал занят, k-1 заявок стоит в очереди и т. д.

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

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

Рис. 4

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

Здесь , где pi(t) – вероятность того, что в момент времени t СМО находится в состоянии Si.

Решение полученной системы из n+1 уравнений имеет вид:

(10)

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

Как следует из первого уравнения системы (10), предельные вероятности СМО, представленной на рис.3, определяются соотношениями

(в скобках стоит сумма бесконечной геометрической прогрессии со знаменателем ρ). Если ρ<1, то эта сумма равна

Таким образом, предельная вероятность состояния S0 СМО определяется соотношением .

Предельная вероятность любого состояния Sk СМО вычисляется по формуле (см. систему (10)):

. (11)

Т. к. ρ<1, то из последнего равенства следует, что вероятность p0 наибольшая.

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

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

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

. (12)

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

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

Таким образом получим

. (13)

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

. 14)

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

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

Решение. Найдем предельную интенсивность потока заявок:

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

Предельная вероятность того, что у кассы нет ни одного покупателя

Соответственно вероятность того, что касса занята,

Среднее число заявок на обслуживании, в системе, в очереди найдем по приведенным выше формулам (12-14).

заявок,

заявок.

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

мин.;

мин.

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

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

2.6. Упражнения

1. На телефонную линию приходит простейший поток вызовов с интенсивностью 0,9 выз./мин.; производительность линии 0,7 выз./мин. Вызов, пришедший на линию во время ее занятости, не обслуживается. Найти абсолютную пропускную способность линии, среднее время обслуживания одного вызова, вероятность отказа в обслуживании, среднее время пребывания заявки в системе.

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

3. Рассматривается круглосуточная работа пункта проведения профилактического осмотра автомашин с одним каналом. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,5 ч. На осмотр поступает в среднем 36 машин в сутки. Потоки заявок и обслуживаний – простейшие. В случае занятости канала машина покидает пункт осмотра необслуженной. Определить предельные вероятностные состояния и основные характеристики системы.

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

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

3. ОТВЕТЫ К УПРАЖНЕНИЯМ

К главе 1: 1.1. p*=(1;0), q*=(0;1), v=0; 1.2. p*=(2/3;1/3), q*=(1/2;1/2), v=0,3. 2.1. p*=(1;0), q*=(1;0), v=2; 2.2. p*=(3/4;1/4), q*=(1/2;1/2), v=1/2; 2.3. p*=(1/3;2/3), q*=(2/9,7/9), v=8/3; 2.4. p*=(2/3;1/3), q*=(1/2;1/2;0), v=1; 2.5. p*=(3/7;4/7), q*=(5/14;0;9/14), v=-1/7.

К главе 2: 1. A=0,394 выз./мин.; pr=0,5625; мин; мин; 2. μ=0,5 ед./мин=30 ед./ч; Q=0,25; pr=0,75; A = 22,5; 3. μ=2 маш./мин; p0=0,571; p1=0,429; Q=0,571; pr=0,429; A = 0,857; ч; ч; 4. μ=1/3; ρ=0,75; p0=0,25; pзан=0,75; заявок; заявки; заявок; мин; мин; мин; P(k≤3)=0,4336; 5. λ=0,35; ρ=0,7; p0=0,3; pзан=0,7; ; ; ; ; P(k≤1)=0,375.