книги / Прикладная теория систем массового обслуживания.-1
.pdf( НАЧАЛО ^
_____Т
Ввод исходных данных;
Mi Qmin* Qmtxt n j, G, C_cycle;
\- интенсивность поступления заявок; ц - интенсивность обслуживания заявок; Qmia-минимальное число разрядов; &п1х - максимальное число разрядов; n_t - моделируемое количество заявок; G - число каналов;
ч. С_сус1е - число экспериментов
V.
Рис. 5.1. Блок-схема алгоритма имитационного моделирования
3. В системе моделируется приход N заявок.
Разыгрывается время прихода очередной заявки в систему и заносит ся в поле tosv; определяется число приборов, необходимых для ее обслу живания, и заносится в поле пп.
4-6. Подсчитывается число свободных приборов в системе. Если число приборов достаточно для обслуживания заявки, то уменьшается счетчик свободных приборов на соответствующее значение. По окончании обработки заявки освобождаются приборы (число освободившихся прибо ров добавляется к свободным, а также уменьшается счетчик заявок, нахо дящихся в системе, к). Признаком освобождения заявкой системы является то, что текущее время превысило время обслуживания заявки (которое предварительно проверяется на равенство нулю).
Если в системе нет обрабатываемых заявок, то увеличивается счет чик моментов, когда система свободна (п _sv).
7.Обрабатывается заявка, пришедшая в момент fM(W1+TPost.
8.Разыгрывается число приборов для ее обслуживания Ndev.
9.Определяется, достаточно ли приборов для обслуживания заявки. Если приборов не хватает, то заявка получает отказ; если приборов доста точно, заявка принимается на обслуживание.
10.В случае отказа увеличивается счетчик заявок, получивших отказ
«_otk.
11.Разыгрывается время обслуживания Tobs, вычисляется время ос вобождения (окончания обслуживания) Гмод + Tobs и заносится в поле tosv соответствующей динамической переменной.
12.В поле пп заносится количество приборов, захваченных заявкой, увеличивается счетчик заявок, находящихся на обслуживании в системе, к уменьшается счетчик свободных нейронов и_&ее.
13.Осуществляется переход к рассмотрению следующей заявки.
14.Если выполнены все реализации для данного количества прибо ров, то увеличивается количество нейронов в системе на величину шага.
15.Если промоделирован не весь диапазон, то производится модели рование для системы с новым числом нейронов.
16.После рассмотрения всех заявок вычисляется вероятность отказа Рот* для конкретных значений числа приборов в системе.
На основании изложенного алгоритма была разработана программа. При имитационном моделировании для получения статистически
достоверных результатов необходимо некоторое число К реализаций. Чем больше К, тем точнее оценки. Это число определяется либо предваритель но, либо в процессе моделирования с применением метода последователь ного анализа.
Первый метод считается классическим, хотя он менее эффективен, чем второй. Рассмотрим его, считая, что задачей имитации является опре деление среднего значения. Оценку среднего значения х можно рассмат-
— 1 К
ривать как значение случайной величины X = — ^ X i9 где Х{- независи м ы
мые одинаково распределенные случайные величины с неизвестным мате
матическим ожиданием М и дисперсией о2 Для достаточно больших К, пользуясь результатами центральной предельной теоремы, можно утвер
ждать, что X е к (м ,о /у 1 к ) или ^ ^ |
е К (0,1). Зададимся надежностью |
|
|
oVК |
|
а и потребуем, чтобы |
х - м < /а |
= а. Величину /а легко определить |
4 |
о 4 к |
|
по таблицам функций Лапласа. Тогда точность оценки будет удовлетво рять условию Р^Х - м \< (ас/л[к )= а . Таким образом, полученная точ
ность решения в зависимости от количества реализаций может быть най дена из формулы
, 2_ 2
к=^4 - .
“ V F
Если целью имитации является оценка вероятности, то число реали заций определяется аналогично. В качестве оценки неизвестной вероятно
сти событияр(А) используем величину p = m/N .
Введем в рассмотрение величину Xt - число наступлений события А в /-й реализации. Очевидно, что X, = 0 с вероятностью 1-р и Х{= 1 с веро ятностью р. Тогда M\Xj\ = р и D[X'] = р(1 - р \
к X
Легко показать, что p = m/K = Y,—L- В силу центральной предель-
/=1 |
К |
I А _-- р |
|
' |
|
ной теоремы для достаточно больших |
К р е К р |
— — Тогда по |
заданной надежности а по таблицам функции Лапласа легко определить
/а из условия р |
Р - Р |
<tn |
= а. Откуда точность оценки |
||||
Р(* ~ Р) |
|||||||
|
|
|
|
|
|
||
|
К |
|
|
|
|
|
|
|
, |
1р (]~ р ) |
г _ М |
- |
р ) |
||
|
ч |
~ к |
~ |
' к — |
т - |
■ |
При использовании формул для определения точности оценки требу ется знать истинные значения ст2 и р , которые обычно не известны. По этому поступим следующим образом. Зададимся произвольным числом реализаций, имитируем процесс и определим S и р величин о и р. Да лее по этим оценкам вычислим точность с которой они найдены; если по лученной точности будет недостаточно, то повторим процесс моделирова ния с уточненным значением К.
Результаты моделирования на основании алгоритма, показанного на рис. 5.1, приведены на рис. 5.2 и в табл. 5.1.
10 |
15 |
20 |
25 |
30 |
35 |
40 |
45 |
50 |
Число нейронов (-•— имитационная модель )
Рис. 5.2. Зависимость Р0бС, Ротк» РСВ от числа обслуживающих приборов системы
п
10
15
20
25
30
35
40
45
50
^отк
5,56 |
• 10'1 |
7,78 |
• 10’1 |
5,74 |
• 10'1 |
4,3810'1 |
|
2,98 |
• 1<г' |
2,02 |
• 10-1 |
1,27 |
W 1 |
J-J 00 |
о _ |
5,23 |
10'' |
|
|
|
|
|
Таблица 5.1 |
Робе |
Рс. |
Время моделиро |
|||
4,34 |
• 102 |
|
|
|
вания, с |
5,62 |
• Ю’1 |
0 |
|||
2,22 |
• 10’1 |
3,53 • |
10'1 |
2 |
|
4,26 |
• 10'1 |
3,02 |
• |
10'1 |
2 |
5,62 |
• 10'1 |
2,50 |
• |
10-1 |
3 |
7,0210'1 |
2,29 |
• |
10-' |
10 |
|
7,98 |
• 10'1 |
2,15 |
|
10-' |
53 |
8,73 |
• 10"' |
2,07 |
|
10'1 |
198 |
9,24 |
• 10"' |
2,00 |
• |
10'1 |
3569 |
9,48 |
• 10'1 |
1,87 |
|
10-' |
17598 |
6. ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
6.1. Последовательность выполнения работы
Объектом исследования являются: система телекоммуникаций, сис тема противоракетной обороны (ПРО), АЦП ПДА.
Начальный этап исследования состоит в ознакомлении с исследуе мым объектом и разработке имитационной статистической модели.
В соответствии с заданием необходимо определить тип модели: СМО с отказами или с очередью, без взаимопомощи или с взаимопомо щью.
После этого составляется блок-схема моделирующего алгоритма и определяются ее выходные параметры.
После тщательного анализа моделирующего алгоритма разрабатыва ется программа моделирования и определяются расчетные параметры ими тационной модели для 3-5 точек. По результатам расчета строятся необхо димые графики (к = f{n) - среднее число занятых каналов; Р0 =J[n) - ве
роятность обслуживания и т.д.)* Изменение расчетных параметров может быть связано с перебором
(по условию задачи на проектирование) числа обслуживающих приборов. На втором этапе исследования решается задача создания аналити
ческой модели.
При создании аналитической СМО определяются параметры входно го и обслуживающего потоков, строится граф состояний системы. По гра фу состояний для стационарного режима и пуассоновских входного и об служивающего потоков составляется система линейных алгебраических уравнений. Из решения СЛАУ определяются требуемые по заданию на проектирование характеристики.
После определения типа модели и требуемых характеристик состав ляется блок-схема алгоритма и определяются ее выходные параметры. За тем разрабатывается программа моделирования и определяются расчетные значения аналитической модели для тех же параметров, что и в имитаци онной статистической модели. По результатам расчета строятся необходи мые графики в тех же координатных осях, что и в имитационной статисти ческой модели.
Третий этап работы состоит в анализе полученных результатов. Не обходимо:
а) оценить на основании статистического критерия адекватность аналитической и имитационной моделей;
б) оценить расхождение моделей; в) указать, какие шаги необходимо предусмотреть для получения
адекватных моделей.
В выводах по работе следует привести алгоритм, позволяющий вести проектирование систем телекоммуникаций, ПРО и АЦП ПДА на основе разработанных моделей.
6.2. Оформление отчета
Отчет по работе оформляется в виде пояснительной записки, рисун ков и таблиц, листингов программ.
Пояснительная записка оформляется в соответствии с общими тре бованиями к текстовым документам по ГОСТ 2.105-68 и включает в себя разработанные аналитические и имитационные модели, расчеты с необхо димыми обоснованиями и пояснениями по принятым решениям. Записка начинается с титульного листа, далее следует задание на проектирование и содержание.
Впояснительную записку включаются следующие разделы:
1.Введение.
2.Разработка имитационной модели.
2.1.Математическое описание.
2.2.Описание блок-схемы алгоритма.
2.3.Анализ полученных результатов моделирования.
3.Разработка аналитической модели.
3.1.Математическое описание.
3.2.Описание блок-схемы алгоритма.
3.3.Анализ полученных результатов моделирования.
4.Сопоставление разработанных моделей и полученных результатов.
5.Выводы по работе.
6.Список литературы.
7.Приложения (листинги программ моделирования; таблицы резуль татов моделирования; графики, полученные в результате моделирования).
Объем текстовой части должен составлять около 20 страниц текста (формат А4). Графические материалы включают в себя блок-схемы, гра фики и пр.
6.3. Организация выполнения курсовой работы
Задание на выполнение курсовой работы каждый студент получает на первом занятии, отведенном расписанием для курсового проектирования.
Над заданием студенты работают под руководством преподавателя в часы, предусмотренные расписанием для курсового проектирования, и са мостоятельно в свободное от занятий время. Основное время отводится самостоятельной работе. Выполнение задания связано с усвоением и пере работкой значительного объема информации, получаемой из многих ис точников. Потому с первых шагов необходимые сведения следует записы вать на определенные листы работы, указывая источники информации, и хранить их в папке, выделенной для курсового проектирования.
Кафедра устанавливает часы консультаций, на которых студенты могут решать вопросы, возникающие в процессе работы над заданием. Приходить на консультацию нужно с четко сформулированными вопроса ми. Если вопросы возникли при работе над книгой, то для их решения нужно эту книгу принести с собой или выписать из нее непонятные места.
На консультациях руководитель работы не обязан указывать реше ние того или иного вопроса. Он должен выслушать объяснения студента и указать, что в них правильно, а что неправильно и в каком направлении работать.
Для контроля над ходом выполнения задания кафедра назначает два срока, следующие друг за другом с интервалом в две недели. В течение первых двух недель студент знакомится с проблематикой работы и создает имитационную и аналитическую модели. Согласовав разработанные моде ли с преподавателем, студент оставшиеся две недели разрабатывает и от лаживает программы моделирования (аналитическую и имитационную), получает результаты моделирования, оформляет отчет.
Готовый отчет о выполнении курсовой работы следует сдать на про верку руководителю не менее чем за 5 дней до защиты. Руководитель впра ве не допустить студента к защите, если он не представил курсовую работу на проверку в установленный срок. Руководитель в течение 1-2 дней прове ряет отчет и возвращает его студенту или с замечаниями, в соответствии с которыми тот должен сделать исправления в отчете, или подписанным, если отчет допущен к защите. Порядок и сроки защиты устанавливает кафедра. За неделю до начала защиты вывешивается список допущенных к защите студентов (с указанием даты, времени и места защиты).
Во время защиты студент должен сделать короткий (5-7 мин) доклад по существу выполненной работы, а затем ответить на вопросы. Студент, не представивший отчет в назначенный срок, допускается к защите только в сроки, установленные для ликвидации задолженностей.
СПИСОК ЛИТЕРАТУРЫ
1. Кофман А. Массовое обслуживание. Теория и приложения /
A.Кофман, Р. Крюон. - М.: Мир, 1965. - 303 с.
2.Саати Т.Л. Элементы теории массового обслуживания. - М.: Сов.
радио, 1971. - 520 с.
3. Гнеденко В.Б. Введение в теорию массового обслуживания / B. Б. Гнеденко, И.Н. Коваленко. - М.: .Машиностроение, 1969. - 432 с.
4.Бусленко Н.П. Метод статистических испытаний / Н.П. Бусленко, Ю.А. Шрайдер. - М.: ГИФМЛ, 1961. - 256 с.
5.Южаков А.А. Стохастические сети в проектировании технических
систем: Учеб, пособие / Перм. гос. техн. ун-т. - Пермь, 1999. - 131 с.
6.Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения. - М.: Наука, 1969. - 512 с.
7.Кендалл Д. Стохастические процессы, встречающиеся в теории
очередей, и их анализ методом вложенных цепей Маркова // Математика. - 1956 .-№ 6 .-С . 97-111.
8. Овчаров В.А. Прикладные задачи теории массового обслужива ния. - М.: Наука, 1987. - 324 с.
9. Smith W.L. Renewal theory and its ramification // J. Roy Statist. Sos. Ser.B. - 1958. - V.20, № 2. - P. 243-302.
10. Джейсуол H. Очереди с приоритетами. - M.: Мир, 1973. - 279 c. И. Риордан Дж. Вероятностные системы обслуживания. - М.: Связь,
1966.- 184 с.
12.Матушкин Н.Н. Мультипликативность распределения состояний замкнутой СМО при неоднородном входящем потоке / Н.Н. Матушкин,
А.А.Назаров, А.А. Южаков // Информационные управляющие системы / Перм. гос. техн. ун-т. - Пермь, 1996. - С. 39-47.
13.Бройтман М.Д. Анализ процессов буферизации в системах теле обработки / М.Д. Бройтман, Б.Я. Эттингер // Автоматика и вычислительная техника. - 1981. - № 2. - С. 55-61.
14.Скворцов А.В. Моделирование потоков в информационных сис темах/ / Приборы и системы управления. - 1983.-№ 9. - С. 17-18.
15.Ивановский В.Б. О мультипликативной форме решения в экспо ненциальных сетях с ограниченными очередями и блокировками // Авто матика и вычислительная техника. - 1983. - № 5. - С. 19-24.
16.Башарин Г.П. Анализ очередей в вычислительных сетях. Теория и методы расчета / Г.П. Башарин, П.П. Бочаров, Я.А. Коган. - М.: Наука, 1989.-336 с.
17.Южаков А.А. Прикладная теория систем массового обслужива ния: Учеб, пособие / Перм. гос. техн. ун-т. - Пермь, 2004. - 121 с.
18.Гитис Э.И. Аналого-цифровые преобразователи / Э.И. Гитис, Е.А. Пискунов. - М.: Энергоиздат, 1981. - 360 с.
Оглавление |
|
1. Элементы теории систем массового обслуживания.................. |
3 |
1.1. Виды распределения входящего потока и времени обслу |
|
живания |
3 |
1.2. Дисциплина обслуживания заявок............................................ |
4 |
1.3. Канал обслуживания.................................................................. |
5 |
1.4. Выходящий поток....................................................................... |
6 |
2. Полнодоступные системы. Обслуживание вызовов простей |
|
шего потока................................................................................................... |
6 |
2.1. Исторический обзор исследований в области СМ О ............. |
6 |
2.2. Математические модели полнодоступных систем |
8 |
2.2.1. Классическая система массового обслуживания с отказа |
|
ми |
8 |
2.2.2. Система массового обслуживания с ожиданием и приори |
|
тетом в обслуживании.................................................................................. |
11 |
3. Исследование системы противоракетной обороны как систе |
|
мы массового обслуживания..................................................................... |
16 |
3.1. Система противоракетной обороны с отказами и упорядо |
|
ченным обслуживанием................................................................................ |
20 |
3.2. Система противоракетной обороны с частичной взаимопо |
|
мощью между каналами............................................................................... |
24 |
3.3. Система противоракетной обороны с ожиданием, частич |
|
ной взаимопомощью между каналами и ограниченным временем на |
|
хождения заявки в системе......................................................................... |
28 |
4. Исследование аналого-цифрового преобразователя потоко |
|
вой динамической архитектуры как системы массового обслужива |
|
ния ................................................................................................................... |
34 |
4.1. Открытая векторная модель аналого-цифрового преобразо |
|
вателя потоковой динамической архитектуры........................................ |
36 |
4.2. Критерий эквивалентности уравнений глобального и де |
|
тального балансов для цепей Маркова...................................................... |
40 |
5. Построение имитационной модели............................................. |
48 |
6. Требования к выполнению курсовой работы............................ |
55 |
6.1. Последовательность выполнения работы |
55 |
6.2. Оформление отчета................................................................... |
56 |
6.3. Организация выполнения курсовой работы........................... |
57 |
Список литературы............................................................................. |
58 |
ЮЖАКОВ Александр Анатольевич
ПРИКЛАДНАЯ ТЕОРИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
Учебное пособие
Лит. редактор Н.Г. Важеиина Техн. редактор Г\Я. Шилоносова Корректор Е.В. Копытина
Лицензия ЛР Л» 020370
Подписано в печать 9.11.05. Формат 60x90/16. Набор компьютерный. Уел. печ. л. 3,75. Уч.-изд. л. 3,2. Тираж 125. Заказ № 134.
Редакционно-издательский отдел Пермского государственного технического университета
Адрес: 614600. Пермь, Комсомольский пр., 29
Отпечатано в Отделе электронных издательских систем ОЦНИТ Пермского государственного технического университета Адрес: 614600, Пермь, Комсомольский пр., 29, к. 113
тел. (3422)2198-033