Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.

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

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

В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:

S 0 – все станки работают, манипулятор стоит.

S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.

S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.

S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.

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

Рис.4.6.

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

p 0 – вероятность того, что все станки работают.

Манипулятор работает при состояниях системы от S 1 до S m ­ . Тогда вероятность его загрузки равна: .

Число станков, находящихся в очереди связано с состояниями S 2 , – S m , при этом один станок обслуживается, а (k-1) – ожидают. Тогда, среднее число станков в очереди: .

Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): .

Среднее использование одного станка:

Применение метода Монте-Карло для решения задач, связанных с теорией массового обслуживания

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

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

Случайные величины k являются длинами интервалов времени между последовательными моментами t k .

Совокупность случайных величин i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины k , поэтому часто пользуются соответствующей функцией плотности f (z 1 , z 2 ,..., z k ) .

Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины k независимы. Поэтому . Функцииf i (z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала k (i >1) поступила заявка. В отличие от этого функция f 1 (z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.

Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:

где  – плотность стационарного потока.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЧАСТЬ 3.

Модель М/М/1/N

разомкнутыми (или открытыми)

.

N > k заявок.



, где k



; ; ; …;

; ; .

В общем виде

или

для всех . Здесь

. (3.1.1)

Сводка формул

; ;

(факториальные многочлены);

; ; ;

; ; ; ;

; ; ;

; ; ;

; ;

;

;

; ;

;

;

; .

Модель М/М/m//N

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

Граф такой системы имеет вид, изображенный на рис. 11 (на языке символики Кендалла – это система М/М/m//N). Вычисляя вероятности стационарных состояний системы обычным образом, имеем

; ; ;

; ;

; … ;

; ;

,

так что в общем виде

при ;

при

или при ; при

Где – биномиальные коэффициенты. Ясно, что при этом

.

Для случая очереди нет, и тогда имеем особенно простую зависимость (формула бинома Ньютона)

Сводка формул

;

при ;

при ;

; ;

; ;

; ; ; ;

; ; ;

; ;

;

; ;

;

;

;
;

; ; ; ;

; .

Сводка формул

; ;

; ;

; ;

; ;

; ; ; ;

.

Модель М/М/m/Е/N

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

метров может быть сведена к любому из них. Предположим, что в системе имеется конечное число требований, m обслуживающих приборов (каналов) и, кроме того, конечное число мест для ожидания, что общее число требований в очереди не может превышать E . Предположим также, что , при этом все требования, поступающие в систему тогда, когда в ней уже имеется заявок, теряются и немедленно возвращаются в группу поступающих так, как будто бы они были полностью обслужены (на языке символики Кендалла – это система М/М/m/E/N). Граф состояний такой СМО имеет вид, изображенный на рис. 13. При эта модель переходит в модель зам-кнутой многоканальной СМО, рассмотренную в § 3.2, а при в модель Энгсета.

Решение уравнений Колмогорова в данном случае вполне аналогично тому, которое было получено в § 3.2 для модели М/М/m//N, так что запишем сразу его конечный результат, которым является связка формул

при ;

при

.

Сводка формул

;

при ;

при ;

; ;

; ;

; ;

;

; ; ; ;

;

; ;

;

;

.

Сводка формул

;

при ;

при ;

; ;

;

; ;

; ; ; ;

; ; ;

;

; ;

.

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

ЧАСТЬ 3.

МОДЕЛИ ЗАМКНУТЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Модель М/М/1/N

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

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

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

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

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

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

ным . Или, что то же самое, ‑ это среднее время нахождения одного требования в источнике заявок от окончания обслуживания и до его возвращения обратно в систему. В этом случае физический смысл интенсивности , очевидно, заключается в том, что она определяет среднее число возвращений в единицу времени (своего рода частоту возвращений) одной заявки после обслуживания обратно в систему. И тогда, в свою очередь, общая интенсивность поступающих в систему требований равна , где k – номер состояния системы, то есть число заявок, реально в ней находящихся, как в очереди, так и под обслуживанием. Граф такой системы изображен на рис. 10. В рамках символики Кендалла такие системы массового обслуживания обозначают аббревиатурой М/М/1//N, в которой последний символ означает полное (предельное) число заявок в системе.

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

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

; ; ; …;

; ; .

В общем виде

или

для всех . Здесь

– так называемые факториальные многочлены или обобщенные степени . Ясно, что при этом

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

§1. Марковские цепи с конечным числом состояний и дискретным временем.

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S 1, S 2,…, S n, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t 1, t 2, t 3, …, называемые шагами .

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

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

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

Рис. 1

Вершины графа S 1, S 2, S 3 обозначают возможные состояния системы. Стрелка, направленная из вершины S i в вершину S j обозначает переход S i → S j; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i -той вершине графа, обозначает, что система остается в состоянии S i с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n ´n , элементами которой являются вероятности переходов p ij между вершинами графа. Например, граф на рис.1 описывается матрицей P :

https://pandia.ru/text/78/171/images/image003_65.gif" width="95" height="33 src="> (1.1)

Условие (1.1) - обычное свойство вероятностей, а условие (1.2) (сумма элементов любой стрелки равна 1) означает, что система S обязательно либо переходит их какого-то состояния S i в другое состояние, либо остается в состоянии S i.

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

(1.3)

В общем случае перехода S i → S j за m шагов для элементов https://pandia.ru/text/78/171/images/image008_47.gif" width="164 height=58" height="58">, 1 ≤ l ≤ m

Полагая в (1.4) l = 1 и l = m - 1 получим два эквивалентных выражения для https://pandia.ru/text/78/171/images/image009_45.gif" width="162" height="65 src="> (1.5)

. (1.6)

Пример 1. Для графа на рис.1 найти вероятность перехода системы из состояния S 1 в состояние S 2 за 3 шага.

Решение. Вероятность перехода S 1 → S 2 за 1 шаг равна . Найдем вначале , используя формулу (1.5), в которой полагаем m = 2.

https://pandia.ru/text/78/171/images/image014_31.gif" width="142" height="54 src=">.

Как видно из этой формулы, в дополнение к необходимо вычислить также https://pandia.ru/text/78/171/images/image016_30.gif" width="38" height="30">:

https://pandia.ru/text/78/171/images/image018_27.gif" width="576" height="58 src=">

Таким образом

https://pandia.ru/text/78/171/images/image020_25.gif" width="156" height="123 src=">.

Если обозначить через P (m) матрицу, элементами которой являются - вероятности переходов из S i в S j за m шагов, то справедлива формула

P (m) = P m, (1.7)

где матрица P m получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы (называемым также стохастическим вектором ).

= (q 1, q 2,…,q n),

где q j-вероятность того, что исходным состоянием системы является S j состояние. Аналогично (1.1) и (1.2) справедливы соотношения

0 ≤ q i ≤1; https://pandia.ru/text/78/171/images/image025_19.gif" width="218 height=35" height="35">

вектор состояния системы после m шагов, где - вероятность того, что после m шагов система находится в S i состоянии. Тогда справедлива формула

(1.8)

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

Решение. Исходное состояние системы характеризуется вектором =(0,7; 0; 0,3). После первого шага (m = 1) система перейдет в состояние

После второго шага система окажется в состоянии

Ответ: Состояние системы S после двух шагов характеризуется вектором (0,519; 0,17; 0,311).

При решении задач в примерах 1, 2 предполагалось, что вероятности переходов P ij остаются постоянными. Такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.

§2. Марковские цепи с конечным числом состояний и непрерывным временем.

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

; (i ≠ j ). (2.1)

Если величины λ ij не зависят от t , то марковский процесс называется однородным. Если за время Δt система может изменить свое состояние не более чем один раз, то говорят, что случайный процесс является ординарным. Величину λ ij называют интенсивностью перехода системы из S i в S j. На графе состояний системы численные значения λ ij ставят рядом со стрелками, показывающими переходы в вершины графа (рис. 2).

https://pandia.ru/text/78/171/images/image036_12.gif" width="101 height=62" height="62"> (2.2)

Распределение вероятностей состояний системы, которое можно характеризовать вектором https://pandia.ru/text/78/171/images/image038_11.gif" width="21 height=27" height="27"> являются константами.

Состояния S i и S j называются сообщающимися, если возможны переходы S i ↔ S j (на рис. 2 сообщающимися являются состояния S 1 и S 2, а S 1, S 3 и S 2, S 3 такими не являются).

Состояние S i называется существенным, если всякое S j, достижимое из S i, является сообщающимся с S i. Состояние S i называется несущественным, если оно не является существенным (на рис. 2 существенными являются состояния S 1 и S 2).

Если существуют предельные вероятности состояний системы

(2.3)

не зависящие от начального состояния системы, то говорят, что при t → ∞ в системе устанавливается стационарный режим.

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

Теорема 1. Если S i – несущественное состояние, то

(2.4)

т. е. при t → ∞ система выходит из любого несущественного состояния (для системы на рис. 2 т. к. S 3 – несущественное состояние).

Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой (система на рис.2 удовлетворяет этому условию, т. к. существенные состояния S 1 и S 2 сообщаются между собой).

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p 1(t ), p 2(t ),…, p n(t ) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. Рассмотрим получение уравнений Колмогорова на конкретном примере.

Пример 3. Записать уравнения Колмогорова для системы, изображенной на рис.2. Найти финальные вероятности для состояний системы.

Решение. Рассмотрим вначале вершину графа S 1. Вероятность p 1(t + Δt ) того, что система в момент времени (t + Δt ) будет находиться в состоянии S 1 достигается двумя способами:

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

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

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

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

p 1(t + Δt ) = p 1(t ) (1 - λ12 Δt ) + p 2(t ) (1 - λ21 Δt ) + p 3(t ) (1 – λ31 Δt );https://pandia.ru/text/78/171/images/image043_10.gif" width="20" height="16 src=">

https://pandia.ru/text/78/171/images/image045_11.gif" width="269" height="46 src="> (2.5)

Аналогично, рассматривая вершины графа S 2 и S 3 , получим уравнения

, (2.6)

https://pandia.ru/text/78/171/images/image048_10.gif" width="217" height="84 src=">

Из последнего уравнения следует, что p 3 = 0. Решая оставшиеся уравнения, получим p 1= 2/3, p 2 = 1/3.

Ответ: вектор состояния системы в стационарном режиме равен

С учетом рассмотренного примера сформулируем общее правило составления уравнений Колмогорова:

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

§3. Процессы рождения и гибели.

Так называется широкий класс случайных процессов, происходящих в системе, размеченный граф состояний которой изображен на рис. 3.
https://pandia.ru/text/78/171/images/image052_9.gif" width="61" height="12">
λ0 λ1 λ2 λg-2 λ g-1

https://pandia.ru/text/78/171/images/image054_9.gif" width="32" height="12">.gif" width="61" height="12">μ0 μ1 μ2 μg-2 μg-1

Здесь величины λ 0, λ 1,…, λ g-1 - интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины μ 0, μ 1,…, μ g-1 - интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

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

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

для состояния S 0:

p 0∙λ 0Δt = p 1∙μ 0Δt ;λ 0 p 0 = μ 0 p 1;

для состояния S 1:

р 1·(λ 1 + μ 0)Δt = p 0∙λ 0Δt + p 2∙μ 1·Δt ;(λ 1 + μ 0) p 1 = λ 0 p 0 + μ 1p 2.

Последнее уравнение с учётом предыдущего можно привести к виду λ 1 p 1 = μ 1p 2 . Аналогично можно получить уравнения для остальных состояний системы. В результате получится система уравнений:

https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23 src=">.gif" width="94" height="54 src="> (3.3)

§4. Основные понятия и классификация систем массового обслуживания. Простейший поток заявок.

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

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

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

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

1)отсутствие последействия , т. е. заявки поступают независимо друг от друга;

2)стационарность, т. е. вероятность поступления данного числа заявок на любом временнóм отрезке [t 1, t 2] зависит лишь от величины этого отрезка и не зависит от значения t 1, что позволяет говорить о среднем числе заявок за единицу времени, l, называемом интенсивностью потока заявок ;

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

Для простейшего потока вероятность p i(t ) поступления в СМО ровно i заявок за время t вычисляется по формуле

(4.1)

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

Функция распределения F (t ) случайного интервала времени T между двумя последовательными заявками по определению равна F (t ) = P (T < t ). Но P (T <t )=1 - P (T ≥ t ), где P (T ≥ t ) – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t , т. е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (4.1) при i = 0. Таким образом,

P (T https://pandia.ru/text/78/171/images/image067_9.gif" width="177" height="28 src="> (t > 0),

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

https://pandia.ru/text/78/171/images/image069_9.gif" width="91" height="39 src=">.gif" width="364" height="48 src=">;

б) при решении этого пункта целесообразно использовать противоположную вероятность:

https://pandia.ru/text/78/171/images/image073_8.gif" width="167" height="30 src=">.gif" width="243" height="31 src=">.gif" width="72 height=31" height="31">

https://pandia.ru/text/78/171/images/image079_7.gif" width="320" height="31 src=">

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

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

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

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

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

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

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

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

n – число каналов в СМО ;

λ – интенсивность поступления в СМО заявок ;

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

ρ = λ /μ – коэффициент загрузки СМО;

m – число мест в очереди ;

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

Q ≡ p обс - вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО); при этом

Q = p обс = 1 - р отк; (4.5)

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

А = λ∙Q ; (4.6)

L смо - среднее число заявок , находящихся в СМО;

https://pandia.ru/text/78/171/images/image083_7.gif" width="22" height="27 src="> определяется как математическое ожидание случайного числа занятых обслуживанием n каналов:

https://pandia.ru/text/78/171/images/image085_7.gif" width="95" height="27 src="> - коэффициент занятости каналов ;

t ож - среднее время ожидания (обслуживания) заявки в очереди,

v = 1/t ож - интенсивность потока ухода заявок из очереди.

L оч - среднее число заявок в очереди (если очередь есть); определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

https://pandia.ru/text/78/171/images/image087_6.gif" width="87" height="31 src="> - среднее время пребывания заявки в СМО;

https://pandia.ru/text/78/171/images/image089_7.gif" width="229" height="48 src="> (4.9)

Здесь λ и μ – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S 0 обозначает, что канал свободен, а S 1 - что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид (см. пример 3)

https://pandia.ru/text/78/171/images/image093_7.gif" width="168" height="50 src="> , (5.1)

https://pandia.ru/text/78/171/images/image095_7.gif" width="197" height="51 src=">; .

Таким образом, обслуживается лишь 62,5% звонков, что нельзя считать удовлетворительным. Абсолютная пропускная способность СМО

А = λQ = λp обс = 1,2∙0,625(мин)-1 = 0,75(мин)-1,

т. е. в среднем обслуживается 0,75 звонка в минуту.

§ 6. Многоканальная СМО с отказами.

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна λ , а интенсивность обслуживания заявки каждым каналом равна μ . Размеченный граф состояний системы изображён на рис. 5.

https://pandia.ru/text/78/171/images/image099_6.gif" width="106" height="29"> означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью λ независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина kμ характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять g = n и

https://pandia.ru/text/78/171/images/image101_6.gif" width="234" height="51 src="> (6.2)

https://pandia.ru/text/78/171/images/image103_6.gif" width="84 height=29" height="29"> (6.3)

Формулы (6.2) и (6.3) называются формулами Эрланга – основателя теории массового обслуживания.

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

https://pandia.ru/text/78/171/images/image105_6.gif" width="215" height="44"> (6.5)

Абсолютную пропускную способность найдём из (4.6) и (6.5):

https://pandia.ru/text/78/171/images/image107_6.gif" width="24" height="24 src="> можно найти по формуле:

https://pandia.ru/text/78/171/images/image108_6.gif" width="158" height="46 src="> (6.7)

Пример 7. Найти оптимальное число телефонных номеров на предприятии, если заявки на переговоры поступают с интенсивностью 1,2 заявки в минуту, а средняя продолжительность разговора по телефону составляет https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23"> Оптимальное число каналов n неизвестно. Используя формулы (6.2) – (6.7) найдём характеристики СМО при различных значениях n и заполним таблицу 1.

Таблица 1

р отк

р обс

А [мин-1]

Оптимальным числом телефонных номеров можно считать n = 6, когда выполняется 97,6% заявок. При этом за каждую минуту обслуживается в среднем 1,171 заявки. Для решения 2-го и 3-го пунктов задачи воспользуемся формулой (4.1). Имеем:

а) https://pandia.ru/text/78/171/images/image112_6.gif" width="513" height="61">

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

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

λ λ λ λ λ λ

μ μ μ μ μ μ

Рис.6

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

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

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

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

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

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

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рис.6 является частным случаем системы рождения и гибели (рис.3), если в последней принять g = m + 1 и

λ i = λ , μ i = μ , (). (7.1)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (3.2) и (3.3) с учётом (7.1). В результате получим:

p k = ρk ∙p 0, (7.3)

При ρ = 1 формулы (7.2), (7.3) принимают вид

https://pandia.ru/text/78/171/images/image123_6.gif" width="88" height="25 src="> (7.4)

При m = 0 (очереди нет) формулы (7.2), (7.3) переходят в формулы (5.1) и (5.2) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm +1, т. е. вероятность отказа в обслуживании заявки равна

p отк = р m +1 = ρm +1p 0. (7.5)

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

Q = p обс = 1 – р отк = ρm +1p 0, (7.6)

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

https://pandia.ru/text/78/171/images/image124_6.gif" width="251" height="49 src="> (7.8)

При ρ = 1 формула (7.8) принимает вид

https://pandia.ru/text/78/171/images/image126_6.gif" width="265" height="53 src="> (7.10)

При ρ = 1, из (7.10) получим:

https://pandia.ru/text/78/171/images/image128_6.gif" width="223" height="47 src=">

р отк = ρ m+1 ∙ p 0 ≈ (1,5)6 ∙ 0,031 ≈ 0,354,

т. е. 35,4% покупателей получают отказ в обслуживании, что недопустимо много. Среднее число людей, стоящих в очереди, находим по формуле (7.8)

https://pandia.ru/text/78/171/images/image130_6.gif" width="212" height="45 src=">

т. е. не очень большое. Увеличение очереди до m = 10 даёт

p 0 ≈ 0,0039, p отк ≈ 0,0336,

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

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

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

λ λ λ λ λ

μ μ μ μ μ

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них m → ∞. При этом необходимо различать два существенно разных случая: а) ρ ≥ 1; б) ρ < 1. В первом случае, как это видно из формул (7.2), (7.3), p 0 = 0 и pk = 0 (при всех конечных значениях k ). Это означает, что при t → ∞ очередь неограниченно возрастает, т. е. этот случай практического интереса не представляет.

Рассмотрим случай, когда ρ < 1. Формулы (7.2) и (7.3) при этом запишутся в виде

р 0 = 1 - ρ , (8.1)

р k = ρk ∙ (1 – ρ ), k = 1, 2,… (8.2)

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

Q = p обс =

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

А = λ ∙ Q = λ . (8.4)

Среднее число заявок в очереди получим из формулы(7.8) при m → ∞

https://pandia.ru/text/78/171/images/image140_6.gif" width="105" height="29 src=">, (8.6)

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

https://pandia.ru/text/78/171/images/image142_6.gif" width="187" height="48 src="> покупателя,

а среднее число покупателей, находящихся в СМО (т. е. у кассы), равно

https://pandia.ru/text/78/171/images/image144_6.gif" width="208" height="47 src=">

что вполне приемлемо.

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

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

Очереди нет Очередь есть

λ λ λ λ λ λ

μ 2μ nμ nμ nμ nμ

S 0 - все каналы свободны, очереди нет;

S l - заняты l каналов https://pandia.ru/text/78/171/images/image147_6.gif" width="65" height="26">.

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

S 0 → S 0; Sg → Sn +m ; Sk → Sl , ; Sk → Sn +i , https://pandia.ru/text/78/171/images/image150_7.gif" width="377" height="56">. (9.1)

Выражения для финальных вероятностей легко найти из формул (3.2) и (3.3) с учётом (8.6). В результате получим:

https://pandia.ru/text/78/171/images/image152_6.gif" width="80" height="47 src=">, ; ,. (9.3)

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все n каналов заняты, т. е. когда в системе будет находиться либо n , либо n + 1,…, либо (n + m – 1)заявок. Так как эти события несовместимы, то вероятность образования очереди р оч равна сумме соответствующих вероятностей p n, p n+1,…, p n+m-1:

https://pandia.ru/text/78/171/images/image156_3.gif" width="166" height="48 src=">. (9.5)

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

https://pandia.ru/text/78/171/images/image158_6.gif" width="231" height="43 src="> (9.7)

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

https://pandia.ru/text/78/171/images/image160_6.gif" width="192" height="51"> (9.9)

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

L смо = L оч + L обс. (9.10)

Среднее время пребывания заявки в СМО и в очереди определяется формулами (4.9) и (4.10).

При ρ = n в формулах (9.2), (9.4), (9.8) возникает неопределённость типа 0/0. В этом случае, раскрывая неопределённость можно получить:

https://pandia.ru/text/78/171/images/image162_5.gif" width="149" height="44 src=">; , (9.12)

https://pandia.ru/text/78/171/images/image165_5.gif" width="195" height="49 src=">, (9.14)

https://pandia.ru/text/78/171/images/image167_5.gif" width="305" height="53 src=">

т. е. грузчики работают практически без отдыха.

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

Т. е. вероятность отказа не столь велика. Относительная пропускная способность равна

Q = p обс = 1 – р отк ≈ 1 – 0,145 = 0,855.

Среднее число машин в очереди находим по формуле (9.14).

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

· Поликлиника, обслуживающая данную территорию.

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

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

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

Пусть n – число каналов обслуживания, s – число потенциальных заявок, λ –интенсивность потока заявок каждого потенциального требования, m – интенсивность обслуживания, . Поток

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

(4.27)

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

(4.28)

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

Через находим абсолютную пропускную способность системы

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

(4.31)

Пример решения задачи.

Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью λ = 0,5 отказа в час. Среднее время ремонта ч. Определить пропускную способность системы.

Решение

Эта задача рассматривает замкнутую СМО,

Вероятность простоя рабочего определяется по формуле (4.27):

Вероятность занятости рабочего

.

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

Станков в час.

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

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



Задания для самостоятельной работы.

1. Станция «Железная дорога» в мегаполисе принимает составы для разгрузки угля на платформах. В среднем за сутки на станцию прибывают 16 составов с углем. Поступление носит случайный характер. Плотность прихода составов показала, что поступление на разгрузку удовлетворяет пуассоновскому потоку с параметром состава в час. Время разгрузки состава является случайной величиной, удовлетворяющей экспоненциальному закону со средним временем разгрузки час. Простой состава в сутки составляет y.e; простой платформы в сутки за опоздание прихода состава – y.e; стоимость эксплуатации платформы в сутки – y.e. Издержки подсчитать за сутки. Требуется провести анализ эффективности функционирования станции.

2. Интернет-провайдер в небольшом городе имеет 5 выделенных каналов обслуживания. В среднем на обслуживание одного клиента уходит 25 минут. В систему в среднем поступает 6 заказов в час. Если свободных каналов нет, следует отказ. Определить характеристики обслуживания: вероятность отказа, среднее число занятых обслуживанием линий связи, абсолютную и относительную пропускные способности, вероятность обслуживания. Найти число выделенных каналов, при котором относительная пропускная способность системы будет не менее 0,95. Считать, что потоки заявок и обслуживаний простейшие.

3. Порт имеет один причал для разгрузки судов. Интенсивность потока 0,4 в сутки, среднее время разгрузки одного судна 2 суток. В предположении неограниченности очереди определить показатели эффективности работы причала и вероятность ожидания разгрузки не более 2 судов.

4. Порт имеет один причал для разгрузки судов. Интенсивность потока 0,4 в сутки, среднее время разгрузки одного судна 2 суток. Определить показатели работы порта при условии, что судно покидает порт при наличии в очереди более 3 судов.

Что означают следующие термины и понятия?

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

Теперь вы должны уметь:

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

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

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

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

o строить математические модели массового обслуживания;

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

Контрольные вопросы:

1. Дайте определение системы массового обслуживания с неограниченной очередью.

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

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

4. Дайте определение системы массового обслуживания с отказами.

5. Определите процесс функционирования системы массового обслуживания с отказами.

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

7. Дайте определение системы массового обслуживания с ограниченной очередью.

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

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

10. В чем особенности замкнутых систем массового обслуживания?


список ЛИТЕРАТУРЫ

1. Акулич И.А. Математическое программирование в примерах и задачах. – М.: Высшая школа. 1986.

2. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. – М.: Финансы и статистика. 2001. – 368 с.

3. Гнеденко, Б.В. Введение в теорию массового обслуживания /Б.В. Гнеденко, И.Н. Коваленко: 3-е изд., испр. и доп. – М.: Эдиториал УРСС, 2005. – 400 с.

4. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. – М.: ДИС, 1997.

5. Исследование операций в экономике / под ред. Н.Ш. Кремера М.: Банки и биржи, изд-кое объединение ЮНИТИ, 2000.

6. Количественные методы финансового анализа / под ред. Стивена Дж. Брауна и Марка П. Крицмена. – М.: ИНФРА-М, 1996.

7. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. – М.: ДЕЛО, 2000.

8. Кремер Н.Ш., Путко Б.А. Эконометрика: учебник для вузов / под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ-ДАНА, 2002. – 311с.

9. Лабскер Л.Г., Бабешко Л.О. Игровые методы в управлении экономикой и бизнесом. – М.: ДЕЛО, 2001. – 464 с.

10. Солодовников А.С., Бабайцев В.А., Брайлов А.В. Математика в экономике. – М.: Финансы и статистика, 1999.

11. Шелобаев С.И. Математические методы и модели. Экономика, финансы, бизнес: учебное пособие для вузов. – М.: ЮНИТИ-ДАНА, 2000. – 367 с.

12. Экономико-математические методы и прикладные модели: учебное пособие для вузов // В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. – М.: ЮНИТИ, 1999. – 391 с.

13. Экономический анализ: ситуации, тесты, примеры, задачи, выбор оптимальных решений, финансовое прогнозирование / под ред. проф. Баканова М.И. и проф. Шеремета А.Д. – М.: Финансы и статистика, 2000.


Приложение

Таблица значений функции Лапласса

x Ф(x) x Ф(x) x Ф(x) x Ф(x)
0.00 0.0000 0.32 0.1255 0.64 0.2389 0.96 0.3315
0.01 0.0040 0.33 0.1293 0.65 0.2422 0.97 0.3340
0.02 0.0080 0.34 0.1331 0.66 0.2454 0.98 0.3365
0.03 0.0120 0.35 0.1368 0.67 0.2486 0.99 0.3389
0.04 0.0160 0.36 0.1406 0.68 0.2517 1.00 0.3413
0.05 0.0199 0.37 0.1443 0.69 0.2549 1.01 0.3438
0.06 0.0239 0.38 0.1480 0.70 0.2580 1.02 0.3461
0.07 0.0279 0.39 0.1517 0.71 0.2611 1.03 0.3485
0.08 0.0319 0.40 0.1554 0.72 0.2642 1.04 0.3508
0.09 0.0359 0.41 0.1591 0.73 0.2673 1.05 0.3531
0.10 0.0398 0.42 0.1628 0.74 0.2703 1.06 0.3554
0.11 0.0438 0.43 0.1664 0.75 0.2734 1.07 0.3577
0.12 0.0478 0.44 0.1700 0.76 0.2764 1.08 0.3599
0.13 0.0517 0.45 0.1736 0.77 0.2794 1.09 0.3621
0.14 0.0557 0.46 0.1772 0.78 0.2823 1.10 0.3643
0.15 0.0596 0.47 0.1808 0.79 0.2852 1.11 0.3665
0.16 0.0636 0.48 0.1844 0.80 0.2881 1.12 0.3686
0.17 0.0675 0.49 0.1879 0.81 0.2910 1.13 0.3708.
0.18 0.0714 0.50 0.1915 0.82 0.2939 1.14 0.3729
0.19 0.0753 0.51 0.1950 0.83 0.2967 1.15 0.3749
0.20 0.0793 0.52 0.1985 0.84 0.2995 1.16 0.3770
0.21 0.0832 0.53 0.2019 0.85 0.3023 1.17 0.3790
0.22 0.0871 0.54 0.2054 0.86 0.3051 1.18 0.3810
0.23 0.0910 0.55 0.2088 0.87 0.3078 1.19 0.3830
0.24 0.0948 0.56 0.2123 0.88 0.3106 1.20 0.3849
0.25 0.0987 0.57 0.2157 0.89 0.3133 1.21 0.3869
0.26 0.1026 0.58 0.2190 0.90 0.3159 1.22 0.3883
0.27 0.1064 0.59 0.2224 0.91 0.3186 1.23 0.3907
0.28 0.1103 0.60 0.2257 0.92 0.3212 1.24 0.3925
0.29 0.1141 0.61 0.2291 0.93 0.3238 1.25 0.3944
0.30 0.1179 0.62 0.2324 0.94 0.3264
0.31 0.1217 0.63 0.2357 0.95 0.3289

Продолжение приложения

x Ф(x) x Ф(x) x Ф(x) x Ф(x)
1.26 0.3962 1.59 0.4441 1.92 0.4726 2.50 0.4938
1.27 0.3980 1.60 0.4452 1.93 0.4732 2.52 0.4941
1.28 0.3997 1.61 0.4463 1.94 0.4738 2.54 0.4945
1.29 0.4015 1.62 0.4474 1.95 0.4744 2.56 0.4948
1.30 0.4032 1.63 0.4484 1.96 0.4750 2.58 0.4951
1.31 0.4049 1.64 0.4495 1.97 0.4756 2.60 0.4953
1.32 0.4066 1.65 0.4505 1.98 0.4761 2.62 0.4956
1.33 0.4082 1.66 0.4515 1.99 0.4767 2.64 0.4959
1.34 0.4099 1.67 0.4525 2.00 0.4772 2.66 0.4961
1.35 0.4115 1.68 0.4535 2.02 0.4783 2.68 0.4963
1.36 0.4131 1.69 0.4545 2.04 0.4793 2.70 0.4965
1.37 0.4147 1.70 0.4554 2.06 0.4803 2.72 0.4967
1.38 0.4162 1.71 0.4564 2.08 0.4812 -2.74 0.4969
1.39 0.4177 1.72 0.4573 2.10 0.4821 2.76 0.4971
1.40 0.4192 1.73 0.4582 2.12 0.4830 2.78 0.4973
1.41 0.4207 1.74 0.4591 2.14 0.4838 2.80 0.4974
1.42 0.4222 1.75 0.4599 2.16 0.4846 2.82 0.4976
1.43 0.4236 1.76 0.4608 2.18 0.4854 2.84 0.4977
1.44 0.4251 1.77 0.4616 2.20 0.4861 2.86 0.4979
1.45 0.4265 1.78 0.4625 2.22 0.4868 2.88 0.4980
1.46 0.4279 1.79 0.4633 2.24 0.4875 2.90 0.4981
1.47 0.4292 1.80 0.4641 2.26 0.4881 2.92 0.4982
1.48 0.4306 1.81 0.4649 2.28 0.4887 2.94 0.4984
1.49 0.4319 1.82 0.4656 2.30 0.4893 2.96 0.4985
1.50 0.4332 1.83 0.4664 2.32 0.4898 2.98 0.4986
1.51 0.4345 1.84 0.4671 2.34 0.4904 3.00 0.49865
1.52 0.4357 1.85 0.4678 2.36 0.4909 3.20 0.49931
1.53 0.4370 1.86 0.4686 2.38 0.4913 3.40 0.49966
1.54 0.4382 1.87 0.4693 2.40 0.4918 3.60 0.49984
1.55 0.4394 1.88 0.4699 2.42 0.4922 3.80 0.49992
1.56 0.4406 1.89 0.4706 2.44 0.4927 4.00 0.49996
1.57 0.4418 1.90 0.4713 2.46 0.4931 4.50 0.49999
1.58 0.4429 1 1.91 0.4719 2.48 0.4934 S 5.00 0.49999

Татьяна Владимировна Калашникова

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

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

. (5.21)

Известно, что сумма геометрической прогрессии равна

Для установившегося режима (α = const, m→∞) система работает только при условии

, (5.23)

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

С учетом этого, вероятность Р 0 определяется по формуле

(5.25)

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

где m пк - среднее число простаивающих (незанятых каналов); M(S) - средняя длина очереди; а кан - убытки от простоя канала обслуживания в единицу времени; а авт - убытки от простоя автомобиля (потеря прибыли) в единицу времени.

Рис. 5.5. Зависимость удельных затрат на содержание каналов обслуживания (), убытков от простоя в ожидании обслуживания (), и суммарных (), от числа каналов в СМО.

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

Применение ТМО и метода статистического моделирования для определения оптимальных решений



Общие сведения

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

Под законами больших чисел в теории вероятностей понимается ряд теорем, в которых доказывается сходимость по вероятности статистических характеристик и некоторых постоянных чисел. Так одна из теорем П.Л. Чебышева формулируется так: «При неограниченном увеличении числа независимых испытаний п среднее арифметическое равноточных результатов наблюдений х i случайной величины х , имеющую конечную дисперсию Д [х ], сходится по вероятности к математическому ожиданию М [х ] этой случайной величины.

Теорема Бернулли формулируется так: «При неограниченном увеличении числа независимых испытаний в одних и тех же условиях частость Р(А) наступления события А сходится к его вероятности Р . Поэтому для определения вероятности какого либо события, например вероятности состояний СМО (Р 0 , Р 1 , …Р к ) вычисляются частости для одной реализации, а затем для большого числа реализаций (п =1000). Результат усредняют и с некоторым приближением определяют искомые вероятности состояний системы, математическое ожидание числа занятых каналов, длины очереди и др.