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

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

Министерство образования и науки РФ

Пермский национальный исследовательский политехнический университет

Кафедра автоматики и телемеханики

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

ИНДИВИДУАЛЬНАЯ РАБОТА

Вариант № 3.3.5

Выполнил

студент гр. АТз-12

Ситников Н.В.

Проверил

Зав. кафедрой АТ        д.т.н., профессор Южаков А.А.

Пермь 2015

Задание

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

Системы ПВО, характеризуется следующими параметрами:

·        Скорострельность каждой пусковой установки (выстрелов в минуту) - .

·        Вероятность поражения цели одной ракетой - .

·        Количество пусковых установок в одном канале обслуживания - .

·        Число установок, обстреливающих один самолёт - .

·        Зона обстрела - .

·        Скорость налетающих самолетов, при условии, что они не обстреливаются

·        Скорость налетающих самолетов, при условии, что они обстреливаются- .

·        Среднее расстояние между самолетами - .

·        Количество каналов обслуживания -

·        Число мест в очереди m=1

Расчетные характеристики:

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

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

 - среднее время очереди.

Введение

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

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

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

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

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

1.Основные характеристики СМО

1.      Работа каждого канала характеризуется временем, которое затрачивается на обслуживание одной заявки. В общем случае это время является случайным. Для простейших пуассоновских систем время обслуживания распределено по показательному закону с параметром m. Это эквивалентно тому, что на выходе непрерывно занятого канала будет простейший поток обслуженных заявок с параметром m. Как правило, все каналы имеют одинаковую интенсивность обслуживания m. В этом случае нет необходимости различать каналы (первый, второй, и т. д.). Помимо этого, будем считать, что заявка может обслуживаться любым из n каналов, т. е. любой из n каналов «доступен» для заявки.

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

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

,

где  - вероятность поражения цели одной выпущенной по ней ракетой.

Среднее время пребывания цели в зоне обстрела:

,

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

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

.

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

.

Таким образом, поток освобождений канала ПВО, определяемый этим выражением, имеет интенсивность

.

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

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

,

где - средний линейный интервал между самолетами.

В нашем случае время передачи информации мало и параметр освобождения канала определяется по формуле

2. Разработка имитационной модели

2.1Математическое описание имитационной модели

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

Приведём построение имитационной модели для заданной СМО.

Исходные данные для имитационной модели:

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

·        - число каналов обслуживания;

·        - интенсивность простейшего входящего потока заявок;

·        - интенсивность потока обслуживания заявок;

 - интенсивность простейшего потока освобождения канала;

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

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

Осуществив интегрирование, получим:

Решая это уравнение относительно , имеем:

.

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

.

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

,

где  - случайная величина в диапазоне , генерируемая ЭВМ.

Требуемые характеристику СМО можно определить следующим образом:

·      Среднее время очереди:

,

·      Вероятность полной загрузки:

,

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

,

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

Имитационное моделирование включает следующие этапы:

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

,

где  - модельное время.

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

. Генерация новой заявки. Генерируется время выполнения пришедшей заявки, т.к. оно распределено по пуассоновскому закону, то время выполнения:

,

где  - время выполнения пришедшей заявки.

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

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

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

Блок-схема имитационного моделирования приведена на рис.1. Описание блок-схемы алгоритма приведено ниже.

.2 Описание блок-схемы алгоритма

Описание блок-схемы:

) Установка начальных значений и обнуление счётчиков заявок, выполненных заявок, отказов.

Рассмотрим функционирование одного цикла моделирования:

) Обнуление счетчиков занятых каналов.

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

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

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

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

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

) Если нет мест в очереди, то заявка получает отказ в обслуживании и увеличивается на 1 счётчик отказов.

Далее идёт следующая итерация цикла.

9) Вычисление требуемых параметров СМО: -среднее число занятых каналов, - вероятность занятости канала, π_пз -вероятность полной занятости.

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

,

где - дисперсия; - задаваемая точность; -уровень значимости.

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

(В таблице 1 приложения 2 представлены полученные реализации).

Посчитаем дисперсию:

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

2.3 Анализ полученных результатов моделирования

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

Рассмотренный выше алгоритм построения имитационной модели реализован в программе imitaciya.pas. Текст программы в приложении 1, а результаты работы программы в виде таблицы - в приложении 2, графики представлены в приложении 3.

Проводя моделирование при увеличении числа обслуживающих приборов от 2 до 4, наблюдаем:

ü увеличение среднего числа обслуживающих каналов;

ü уменьшение вероятности полной занятости.

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

3. Разработка аналитической модели

3.1 Математическое описание аналитической модели

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

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

Этой системе соответствует граф состояний:

За состояние принимается наличие в системе одной заявки.

Таким образом, возможны два варианта

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

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

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

 - вероятность того, что система находится в состоянии .

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

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

Вероятность занятости канала:

Для упрощения дальнейших выкладок введём обозначения:

, , ,

С учетом этих обозначений получим:

, где (0 < i < h)

 ,(h<j<n)

 ,где (0<r<m)

Вероятность занятости каналов:

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

Вероятность полной загрузки:

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

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

3.2 Расчёт параметров СМО

Произведем расчет по графу состояний СМО.

1)      Запишем граф состояний и систему уравнений для двухканальной СМО ().

Система будет иметь 4 состояния:

1.   X₀ - нет заявок на обслуживании;

2.      X₁ - 1 заявка на обслуживании (обслуживается двумя каналами);

3.      X₂ - 2 заявки на обслуживании (обслуживаются двумя каналами);

.        Х₃ - 2 заявки на обслуживании (обслуживаются двумя каналами), 3-я заявка в очередь;

Граф состояний имеет вид:

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

Определим искомые параметры:

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

Среднее время очереди:

Вероятность полной загрузки:

2)      Запишем граф состояний и систему уравнений для трёхканальной СМО ().

В этом случае система будет иметь 5 состояния.

1.       X₀ - нет заявок на обслуживании;

2.      X₁ - 1 заявка на обслуживании (обслуживается двумя каналами);

.        X₂ - 2 заявки на обслуживании (одна обслуживается двумя каналами, другая - одним);

.        X₃ - 3 заявки в системе (каждая обслуживается одним прибором);

.        X₄ - 4 заявки в системе (3 заявки обслуживаются тремя каналами, четвертая в очередь);

Граф состояний имеет вид:

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

Определим искомые параметры:

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

Вероятность полной загрузки:

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

В этом случае система будет иметь 6 состояний.

1.       X₀ - нет заявок на обслуживании;

2.      X₁ - 1 заявка на обслуживании (обслуживается двумя каналами);

.        X₂ - 2 заявки на обслуживании (обе обслуживаются двумя каналами);

.        X₃ - 3 заявки на обслуживании (одна обслуживается двумя каналами, а на 2 оставшиеся приходится по одному каналу);

.        X₄ - 4 заявки в системе (каждая заявка обслуживается одним каналом);

6.      X₅ - 5 заявок в системе (четыре обслуживаются четырьмя приборами, одна в очереди);

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

Определим искомые параметры:

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

Среднее время очереди:

Вероятность полной загрузки:

.3 Анализ полученных результатов моделирования

В результате аналитического моделирования получены интересующие нас вероятностные характеристики системы. При аналитическом моделировании характеристики были посчитаны по заранее известным формулам [3]. Результаты аналитического моделирования представлены также в Приложении 2. А требуемые графики в Приложении 3. Также была исследована зависимость вероятностных характеристик системы от числа обслуживающих приборов. При увеличении числа обслуживающих приборов от 2 до 4 были выявлены следующие закономерности: вероятность обслуживания возрастает, вероятность занятости канала уменьшается, среднее число занятых каналов увеличивается. Эти закономерности в виде графиков представлены в Приложении 3.

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

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

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

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

,

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

Если , гипотезу об адекватности отвергают.

Если , гипотеза об адекватности принимается.

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

Значение для данных параметров равно 0.102.

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

Результаты расчетов сведём в таблицу.

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

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

Выводы

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

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

Имитационная модель строилась с учетом всех особенностей функционирования реальной системы и поэтому она достаточно точно описывает все вероятностные процессы. В основу имитационной модели положено рассмотрение работы системы на некотором отрезке времени. В результате этого можно определить вероятностные характеристики системы. Листинг программы имитационного моделирования imitaciya.pas приведён в Приложении 1.

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

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

ü увеличение среднего числа обслуживающих каналов;

ü уменьшение среднего времени очереди;

ü уменьшение вероятности полной занятости.

Соответствующие зависимости в виде графиков представлены в Приложении 3.

Список используемой литературы

1. ГОСТ 19.105-78. ЕСПД. «Общие требования к программным документам».

3. Гмурман В. Е., «Теория вероятностей и математическая статистика». М: Высшая школа, 1977.

Приложение 1

Листинг программ моделирования

{программа имитационного моделирования}

Program imitaciya;=3.57; {Интенсивность простейшего входящего потока}=1.147; {Интенсивность простейшего потока освобождения канала}=0.835; {Интенсивность простейшего потока обслуживания}_t=1000000; {Время моделирования}_kanalov=4; {Число каналов обслуживания}=2; {Параметр взаимопомощи}_svob,p:integer; {кол-во свободных в данный момент приборов}:real; {Количество выполненных заявок},otkaz:longint; {Кол-во заявок, кол-во отказов},ok:integer;:longint; {Текущее время при моделировании}_z0,t_z,t_obs:real; {Интервалы обслуживания и занятости заявки}:array[1..n_kanalov] of real;{Массив, в котором хранится время занятости текущего канала}_zan:array[1..n_kanalov] of real;{Массив, в котором хранится общее время занятости каждого канала во время моделирования}_vyp:array[1..n_kanalov] of real;{Массив, в котором хранится кол-во заявок, выполненных каждым каналом}

n_l_z:array[1..n_kanalov] of integer;

Pobs,Pzk:real; {Вероятность обслуживания и вероятность занятости канала}:real; {Среднее время простоя канала}_zero:array[1..l] of integer; {Номера свободных в данный момент каналов обслуживания}

begin;_z0:=0;:=0;:=0;:=0;i:=0 to n_kanalov do {Начальное обнуление параметров}_vyp[i]:=0;_zan[i]:=0;;t:=0 to time_t do {Основной цикл моделирования}

begini:=1 to n_kanalov do {Цикл проверки окончания обслуживания заявки}((t>n[i])AND(n[i]<>0)) then {Если текущее время больше, чем время окончания}{обслуживания заявки, то канал вобождается и увеличивается счётчик выполненных заявок}

n[i]:=0;:=vypolneno+1/n_l_z[i];_l_z[i]:=0;;;

if (t>=t_z0) then {Генерации прихода новой заявки}_z:=-100/lambda*ln((random(1000)+1)/1000);{генерация случайного интервала между заявками}_z0:=t_z0+t_z;(kolvo); {Счётчик числа пришедших заявок увеличивается на единицу }_svob:=0;i:=1 to l do n_zero[i]:=0; {Обнуляется массив номеров свободных каналов}:=1;i:=1 to n_kanalov do {Цикл поиска свободных каналов}

begin(n[i]=0) then(n_svob);_zero[p]:=i;

inc(p);;;(n_svob>=l) then begin {если число свободных каналов больше, чем l, то поступившая заявка обслуживается l приборами}_obs:=-100/(l*muz)*ln((random(1000)+1)/1000); {Генерация времени обслуживания заявки}i:=1 to l do {Распределяем обслуживание заявки по l каналам}[n_zero[i]]:=t+t_obs; {Записываем время окончания обслуживания заявки}

n_l_z[n_zero[i]]:=l;_zan[n_zero[i]]:=t_zan[n_zero[i]]+t_obs;{Общее время занятости i-го канала}_vyp[n_zero[i]]:=n_vyp[n_zero[i]]+1; {Число заявок, выполненных i-тым каналом}

ok:=1; {Заявка поставлена на обслужитвание};

else (n_svob>0)AND(n_svob<l) then begin {если число свободных каналов меньше, чем l, то заявка обслуживается меньшим числом}_obs:=-100/(n_svob*muz)*ln((random(1000)+1)/1000); {Генерация времени обслуживания заявки}i:=1 to n_svob do {Распределяем обслуживание заявки по оставшимся свободным каналам}[n_zero[i]]:=t+t_obs; {Записываем время окончания обслуживания заявки}

n_l_z[n_zero[i]]:=n_svob;_zan[n_zero[i]]:=t_zan[n_zero[i]]+t_obs;{Общее время занятости i-го канала}_vyp[n_zero[i]]:=n_vyp[n_zero[i]]+1; {Число заявок, выполненных i-тым каналом}

ok:=1; {Заявка поставлена на обслужитвание};ok:=0; {иначе заявка не поставлена на обслуживание}(ok<>1) then inc(otkaz); {Если заявка не поставлена на обслуживание, то увеличивается счётчик отказов на единицу};; {Окончание основного цикла моделирования}

{Вычисление интересующих параметров по результатам моделирования}

pzk:=0;i:=1 to n_kanalov do pzk:=pzk+t_zan[i]/time_t;:=pzk/n_kanalov; :=0;i:=1 to n_kanalov do if (n_vyp[i]<>0) then tpk:=tpk+(time_t-t_zan[i])/n_vyp[i];:=tpk/n_kanalov; :=mu/muz*vypolneno/kolvo;

writeln('Число заявок ',kolvo);('Выполнено ',vypolneno:5:0);('Время очереди ',toch/100:5:3); {Вывод результатов моделирования}('Вероятность полной занятости ',Ppz:5:3);('Среднее число занятых каналов ',t:5:3);

{readln; }.

Приложение 2

Таблица 1. Результаты имитационного моделирования:

Таблица 2. Сравнение результатов имитационного и аналитического моделирования

Приложение 3

Графики, полученные в результате моделирования.

График 1. Зависимость среднего числа занятых каналов от числа приборов для аналитической и имитационной моделей.

График 2. Зависимость среднего времени очереди от числа каналов для аналитической и имитационной моделей

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