Главная Учебники - Разные Лекции (разные) - часть 34
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Кафедра компьютерных образовательных технологий Тема: Построение и использование имитационных моделей Работу выполнил студент Машков Андрей Сергеевич Техническое задание
1. Наименование темы: Построение и исследование имитационных моделей 2. Срок сдачи студентом законченной работы 05.06.07 3. Техническое задание и исходные данные к работе Разработать программу для имитационного моделирования системы массового обслуживания с 2 устройствами. В системе интервалы времени между поступлением требований являются независимыми случайными величинами со средним временем поступления требований Дисциплина обслуживания: циклическая с квантом q=1c. Оценке подлежат следующие параметры: · коэффициент использования системы · средняя задержка в очереди · среднее время ожидания · среднее по времени число требований в очереди · среднее по времени число требований в системе 4. Содержание курсовой работы (перечень подлежащих разработке вопросов): · Анализ задачи и обзор аналогов; · Выбор входных распределений; · Логика работы программы; · Построение генераторов случайных чисел; · Статистический анализ выходных данных моделирования; · Рекомендации по использованию результатов моделирования. 5. Перечень графического материала (с указанием обязательного материала): · Графики функций распределения вероятностей; · Графики функций плотности распределения вероятностей; · График по времени числа требований в очереди; · График по времени числа требований в системе; · График по времени коэффициента использования системы; · Блок-схемы алгоритмов. 6. Исходные материалы и пособия 1. Кельтон В., Лоу А. Имитационное моделирование. Классика CS. 3-ие изд. – СПб.:Питер; Киев: Издательская группа BHV, 2004. – 847 c. Содержание
Введение 1. Анализ задачи и обзор аналогов 2. Выбор входных распределений. Построение генераторов случайных чисел 3. Оценка входных параметров 3.1 Оценки средних значений 3.2 Интервальные оценки 3.3 Проверка статистических гипотез 3.4 Метод гистограмм 4. Логика работы программы 4.1 Блок-схема алгоритма программы 4.2 Интерфейс 5. Планирование эксперимента 5.1 Статический анализ выходных данных моделирования 5.2 Построение факторного плана 5.3 Эффекты взаимодействия и уравнения регрессии 6. Рекомендации по использованию результатов моделирования Заключение Приложение А Приложение Б Список литературы Введение
На производстве, в быту, военном деле, науке и т. д. часто встречаются процессы, которые, не вдаваясь в детали, можно описать следующим образом: с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой — происходит постоянное удовлетворение этих запросов. Та часть процесса, в которой возникают запросы, называется обслуживаемой системой, а та, которая принимает запросы и удовлетворяет их,— обслуживающей. Совокупность обслуживающей и обслуживаемой систем составляет систему массового обслуживания. Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного облуживания случайного потока требований при ограниченных ресурсах системы. Модели системы массового обслуживания являются наиболее часто используемым классом моделей со случайными факторами, что определяется повсеместным распространением систем такого типа. К настоящему времени разработано много моделей систем массового обслуживания, имеющих аналитическое решение. Но они далеко не исчерпывают все способы функционирования реальных обслуживающих систем. Кроме того, на практике не всегда выполняются предпосылки, лежащие в основе имеющихся аналитических моделей. Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и простоев каналов обслуживания. Эффективным методом решения задач теории массового обслуживания, как и многих других, не имеющих аналитического решения, является метод статистического моделирования, предусматривающий, имитацию на ЭВМ процессов, протекающих в исследуемой системе. Математическое описание процесса в этом случае задается алгоритмически. Моделирующий алгоритм многократно воспроизводит изучаемый случайный процесс, накапливает сведения о его протекании, и после обработки выдает оценки показателей работы системы. Целью любого компьютерного эксперимента является сбор информации о значениях переменных модели, наблюдаемых в процессе проведения эксперимента, и состояниях очередей, возникающих в процессе моделирования. Построение программы имитации поведения СМО основано на программировании цепочки событий, начиная от входных требований, поступающих в случайные моменты времени, занятия и освобождения серверов в соответствии со случайным характером длительности обработки каждого требования. Итогом работы программы является получение статистических отчетов о процессах в системе. В данной курсовой работе требуется разработать программу для имитационного моделирования системы массового обслуживания с двумя устройствами. В системе интервалы времени между поступлениями требований являются независимыми случайными величинами со средним временем Ā = 10 секунд. Когда требование поступает, а устройство свободно, обслуживание начинается немедленно. Время обслуживания является случайной величиной, некоррелированной с интервалами поступления требований. Среднее значение обслуживания требований – Ŝ = 10 секунд. Если при поступлении требования устройства заняты, то требование становится в очередь. Дисциплина обслуживания циклическая с квантом q=1c. Оценке подлежат следующие параметры: · коэффициент использования системы; · средняя задержка в очереди; · среднее время ожидания; · среднее по времени число требований в очереди; · среднее по времени число требований в системе. 1. Анализ задачи и обзор аналогов
Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований. Изучение СМО начинается с анализа входящего потока требований. Входящий поток требований представляет собой совокупность требований, которые поступают в систему и нуждаются в обслуживании. Входящий поток требований изучается с целью установления закономерностей этого потока и дальнейшего улучшения качества обслуживания. В данной работе СМО предназначена для обслуживания какого-то потока требований, поступающих в какие-то случайные моменты времени. Так как система циклично содержит квант q, то по истечению этого цикла если требование успело обслужиться, то оно покидает систему, в противном случае требование поступает в конец очереди. Далее время обработки этого требования уменьшается на квант q. Задача данной СМО – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужена; математического ожидания числа обслуженных требований и т.д.) от входных показателей (количества каналов в системе, параметров входящего потока требований и т.д.). Результирующими показателями или интересующими нас характеристиками СМО являются – показатели эффективности СМО, которые описывают, способна ли данная система справляться с потоком требований. Модель такой системы представлена на рисунке 1.1. Рисунок 1.1 – Модель циклическая с квантом q В действительности, многие системы работают по такому принципу: · Задача продавца газет. Партии товара Q поступают регулярно через Т, через этот промежуток продается случайное количество товара R, к моменту поставки новой партии старый товар теряет свои потребительские свойства. 2. Выбор входных распределений. Построение генераторов случайных чисел
Для многих реальных процессов поток требований достаточно хорошо описывается законом распределения Пуассона. Такой пот
ок называется простейшим. Простейший поток обладает
такими важными свойствами:
1) Свойством стационарности, которое выражает неизмен
ность вероятностного режима потока по времени. Это значит, что чис
ло т
ребований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погруз
ку в среднем в сутки должно быть одинаковым для различных периодов времени, к примеру, в начале и в конце декады.
2) Отсутствия последействия, которое обуславливает взаимную независимость поступления того или иного числа требований на обслуживание в непересекающиеся промежутки времени. Это значит, что число требований, поступающих в данный отрезок времени, не зависит от числа требований, обслуженных в предыдущем промежутке времени. Например, число автомобилей, прибывших за материалами в десятый день месяца, не зависит от числа автомобилей, обслуженных в четвертый или любой другой предыдущий день данного месяца. 3) Свойством ординарности, которое выражает практическую невозможность одновременного поступления двух или более требований (вероятность такого события неизмеримо мала по отношению к рассматриваемому промежутку времени, когда последний устремляют к нулю). Таким образом, при моделировании мы генерируем две экспоненциально распределенные псевдослучайные последовательности с заданными средними значениями Чтобы смоделировать экспоненциально распределенную случайную величину сначала генерируется стандартно равномерно распределенная случайная величина U, которая затем преобразуется в величину с экспоненциальным законом распределения согласно формуле: X = –b ln(U),(2.1) где b - математическое ожидание. Для генерации стандартно равномерно распределенной случайной величины U используется мультипликативный генератор: где: a = 630360016, m = 2147483647. Рассмотрим вид входных распределений на основе последовательностей из 1000 элементов с входными параметрами генераторов ( 3. Оценка входных параметров
3.1 Оценки средних значений
Оценка математического ожидания случайных величин X вычисляется по формуле: (3.1) где n – количество элементов. Для случайных величин Оценка дисперсии случайных величин вычисляется по формуле: Для случайных величин Оценка корреляции случайных величин вычисляется по формулам: где j = 1,…,n. Графики корреляции показаны на рисунках 3.1. и 3.2. Рисунок 3.1 – Корреляция величины Рисунок 3.2 – Корреляция величины S Графики зависимости последующего значения от предыдущего представлены на рисунках 3.3 и 3.4. Рисунок 3.3 – Зависимость Рисунок 3.4 – Зависимость 3.2 Интервальные оценки
Доверительный интервал для оценки математического ожидания случайной величины определяется формулой: где b = 0.95 – доверительная вероятность, Доверительные интервалы для оценки математического ожидания случайных величин (9.5886; 10.8315), (9.5627; 10.7928), 3.3 Проверка статистических гипотез
Проверка гипотез об экспоненциальном распределении величин A и S осуществляется с помощью метода c2
. Выдвигаем гипотезу о том, что случайные величины A и S распределены экспоненциально. Статистическая функция вычисляется по формуле: где Расчет проводился на k = 20. Если В результате были получены следующие значения Таким образом, обе гипотезы принимаются. Интервалы: [0 0,4879), [0.4879 1.0008), [1.0008 1.5415), [1.5415 2.1131), [2.1131 2.7193), [2.7193 3.3647), [3.3647 4.0547), [4.0547 4.7957), [4.7957 5.5962), [5.5962 6.4663), [6.4663 7.4194), [7.4194 8.4730), [8.4730 9.6508), [9.6508 10.9861), [10.9861 12.5276), [12.5276 14.3508), [14.3508 16.5823), [16.5823 19.4591), [19.4591 23.5138) . 3.4 Метод гистограмм
На рисунках 3.5 и 3.6 изображены гистограммы с функциями плотностей распределения вероятностей для A и S. Рисунок 3.5 –Гистограмма величины A Эта гистограмма показывает, что смоделированная случайная величина A распределена по экспоненциальному закону. Математическое ожидание случайной величины А равно 10. Рисунок 3.6 –Гистограмма величины S На гистограмме видно, что смоделированная случайная величина S распределена по экспоненциальному закону. Математическое ожидание случайной величины S равно 10. На рисунках 3.7 и 3.8 изображены графики функций распределения вероятностей для A и S. Рисунок 3.7 – Функция распределения величины A Рисунок 3.8 – Функция распределения величины S 4 Логика работы программы
4.1 Блок-схема алгоритма программы
На рисунке 4.1 представлена логика работы системы массового обслуживания с дисциплиной – циклическая с квантом q. Нет Рисунок 4.1- Блок-схема алгоритма программы На рисунке 4.2 представлена блок-схема блока поступления требования в устройство. Нет Да Рисунок 4.2 – Блок-схема поступления требования На рисунке 4.3 представлена блок-схема функции, обеспечивающей обработку требования, где q - максимальное время обслуживание требования. На рисунке 4.4 представлена блок-схема блока ухода требования и дополнительной обработки. Рисунок 4.3 – Блок-схема функции обработки требования Да Нет Рисунок 4.4- Блок-схема дополнительной обработки или ухода требования 4.2 Интерфейс
К графическому интерфейсу относится управление параметрами системы, такими как изменение входных параметров. На рисунке 4.5 представлено основное диалоговое окно графического интерфейса. Рисунок 4.5 - Основное диалоговое окно графического интерфейса Здесь имеются поля для ввода входных параметров, кнопки управления происходящим процессом. При нажатии на клавишу «Запуск» мы видим диалоговое окно, представленное на рисунке 4.6. Здесь можно заметить, что поля ввода входных параметров неактивны для изменения. Так же в графе «Выходные параметры системы» результаты показываются только по двум пунктам: системное время и время поступления следующей заявки. Кнопка «Графики» неактивна. Соответственно происходит выполнение работы программы. Рисунок 4.5 – Диалоговое окно при нажатии на кнопку «Запуск» При нажатии на кнопку «Стоп» происходит активация полей ввода «Параметры моделируемой системы». Так же выводится информация о промежуточных подсчётах. Можно посмотреть полученные графики. Это можно посмотреть на рисунке 4.6. Рисунок 4.6 - Диалоговое окно при нажатии на кнопку «Стоп» После окончательного прогона моделирования системы массового обслуживания и нажатия на кнопку «Графики» мы увидим: · график изменения коэффициента использования системы во времени на рисунке 4.7; · график текущего по времени числа заявок в очереди на рисунке 4.8; · график текущего по времени числа заявок в системе на рисунке 4.9; · график среднего по времени числа заявок в очереди и системе на рисунке 4.10. Рисунок 4.7 - Изменения коэффициента использования системы во времени Рисунок 4.8 - Текущее по времени число заявок в очереди Рисунок 4.9 - Текущее по времени число заявок в системе Рисунок 4.10 - Среднего по времени числа заявок в очереди и системе 5 Планирование эксперимента
5.1 Статический анализ выходных данных моделирования
Для анализа выходных параметров моделирования необходимо рассчитать количество экспериментов для построения факторного плана. Расчет количества экспериментов производится по формуле: где Результаты расчетов необходимого количества экспериментов приведены в таблице 5.1. Таблица 5.1 – Количество экспериментов A1 S1 p d w Q L 1 254789 251463 0,425622 9,23302 19,0935 0,564 2,2317 2 62315 56514 0,42811 10,1712 20,7671 0,609816 2,24761 3 54789623 1263532 0,500968 10,0617 20,1693 0,757584 2,54167 4 658765 459877 0,480135 8,99325 18,8155 0,549471 2,24218 5 678678 967567 0,421836 8,863665 18,111 0,477824 2,04563 6 872343 976723 0,490978 8,75354 18,384 0,53815 2,24663 7 98745 874509 0,476293 9,028 18,873 0,552332 2,27674 8 2148963 1247896 0,482266 9,24245 19,2856 0,534981 2,21667 9 2652567 4589642 0,411253 8,32548 17,9225 0,432992 2,0688 10 829192 873292 0,472514 9,23085 19,0708 0,622302 2,36714 n 8,090238 5,737406 3,266298 37,26833 5,93063 В таблице 5.1 приняты следующие обозначения: A1 – начальное значение величины A (поступления требования); S1 - начальное значение величины S (обработки требования); p, d, w, Q, L – выходные параметры, соответственно коэффициент использования, системы, средняя задержка в очереди, среднее время ожидания, среднее по времени число требований в очереди, среднее по времени число требований в системе; n – необходимое количество экспериментов вычисленное по формуле 5.1. Было определено максимальное значение n равное 37. 5.2 Построение факторного плана
В данной СМО входными переменными модели, т.е. факторами являются: · количество устройств; · среднее время поступления требований; · среднее время обработки требований. Выходными показателями работы СМО, т.е. откликами являются: · коэффициент использования системы; · средняя задержка в очереди; · среднее время ожидания; · среднее по времени число требований в очереди; · среднее по времени число требований в системе. В таблице 5.2 приведены уровни факторов и их значения. Таблица 5.2 – Значения уровней и факторов Фактор - + Количество устройств (m) 1 2 Среднее значение 11 12 Среднее значение 8 9 Значения факторов были подобраны эмпирически, основываясь на том, что нужно увеличить загруженность системы (повысить коэффициент использования системы), но при этом не должно создаваться ситуации, когда очередь постоянно возрастает. Т.е. значения двух факторов должны быть ограничены. Для планирования экспериментов был построен факторный план Таблица 5.3 – Факторный план N M ρ d W Q L 1 - - - 0,615924 24,9953 32,8826 1,74527 2,52777 2 + - - 0,364636 7,10077 15,1911 0,271809 1,48011 3 - + - 0,641983 19,9019 27,7597 1,13215 1,84383 4 + + - 0,282609 6,37251 13,9526 0,1287 1,08477 5 - - + 0,799233 31,835 40,4347 2,48326 3,37997 6 + - + 0,395812 7,81768 16,8574 0,265331 1,56789 7 - + + 0,619495 25,401 33,9974 1,56838 2,34359 8 + + + 0,356732 7,57915 16,4351 0,237693 1,45666 Полный факторный план Таблица А.1 - Результаты работы системы 1/11/8 № A S ρ d w Q L 1 25698 25745 0,6755528 20,4441 28,3593 1,27841 2,05395 2 35861 91752 0,680536 21,3554 29,1991 1,37816 2,14923 3 11867 378922 0,639325 19,8888 27,7547 1,21289 1,97175 4 26598 524568 0,657458 22,4653 30,3462 1,51871 2,31604 5 258569 256985 0,667673 20,8268 28,4641 1,35581 2,11021 6 585458 112362 0,596395 17,0318 24,4552 0,975926 1,69182 7 554265 556963 0,692 20,7156 28,8005 1,29098 2,08363 8 659123 456321 0,640571 22,6587 30,8684 1,38142 2,13753 9 542369 758963 0,713228 24,5171 32,0071 1,82475 2,60021 10 369258 741258 0,753513 30,4055 38,7389 2,30473 3,15114 11 456321 321456 0,639594 17,5491 25,3863 0,973815 1,71901 12 258321 123698 0,72446 29,3316 37,4017 2,24594 3,07944 13 546132 963659 0,734653 27,3305 35,6129 1,91317 2,72048 14 658741 336559 0,695646 23,1381 31,4143 1,4804 2,27275 15 439157 496326 0,711085 22,194 30,3506 1,39806 2,1861 16 486248 684268 0,694425 26,9778 35,1111 1,89538 2,68753 17 139852 369562 0,633895 20,6619 28,2276 1,33358 2,07694 18 341254 851147 0,705575 29,6748 37,9012 2,14604 2,94536 19 112354 774584 0,644321 17,6122 25,5628 0,961498 1,70932 20 546378 796541 0,761192 28,0322 36,2059 2,11432 2,95728 21 595985 747856 0,695619 23,7853 32,0953 1,52594 2,31901 22 446623 332256 0,781548 25,304 33,4814 1,77277 2,58992 23 882654 996548 0,743595 26,5645 34,6843 1,92301 2,74851 24 654845 695658 0,574422 17,751 25,1839 1,03218 1,74265 25 502508 360268 0,645467 23,8161 31,7211 1,65099 2,44626 26 459543 302369 0,591592 22,7245 30,5422 1,4158 2,13354 27 201301 800961 0,629991 27,2424 35,1988 1,92285 2,69709 28 548545 965236 0,727015 25,9111 33,9255 1,91621 2,74568 29 502401 658025 0,68132 23,6408 31,7551 1,57362 2,36523 30 990065 365852 0,673105 21,8759 29,6414 1,51489 2,31478 31 326587 562389 0,662329 21,9148 29,5617 1,47498 2,23395 32 743652 780954 0,723818 28,8251 36,8655 2,1632 2,98105 33 559658 412365 0,634386 31,1898 39,2282 2,42949 3,2553 34 678151 511247 0,666739 25,5455 33,4027 1,78458 2,5574 35 548545 965236 0,727015 25,9111 33,9255 1,91621 2,74568 36 502401 658025 0,68132 23,6408 31,7551 1,57362 2,36523 37 654845 695658 0,574422 17,751 25,1839 1,03218 1,74265 38 585458 112362 0,596395 17,0318 24,4552 0,975926 1,69182 Таблица А.2 - Результаты работы системы 2/11/8 № A S ρ d w Q L 1 543550 543550 0,338698 6,63765 14,8306 0,0359895 1,07935 2 546328 925328 0,325319 6,78376 14,7786 0,182953 1,322 3 512657 14751 0,314471 6,63436 14,1134 0,218668 1,28283 4 65412 365984 0,32293 6,79088 14,8843 0,155927 1,24995 5 541025 850257 0,312803 6,04349 13,5354 0,100849 1,11726 6 132052 956201 0.362961 6.90582 14.8984 0.227443 1.41849 7 548561 523659 0.319346 6.95141 14.6858 0.238178 1.32071 8 745695 652354 0.325195 6.68655 14.9192 0.147331 1.3253 9 569852 258741 0.357333 7.1276 15.5344 0.205545 1.43516 10 789632 123698 0.342605 6.81135 14.9676 0.192304 1.39074 11 120325 669520 0.316259 6.58486 14.6634 0.125711 1.21964 12 885695 336511 0.329522 6.72872 14.6084 0.167234 1.24897 13 125496 695124 0.308968 6.95665 14.969 0.175414 1.23178 14 23584 255963 0.316783 6.70453 14.7566 0.148303 1.22348 15 352147 357159 0.336722 7.22136 15.7185 0.193198 1.37311 16 645123 973451 0.338016 6.27922 13.9954 0.105584 1.19676 17 645121 782223 0.326981 6.54399 14.4811 0.106791 1.17305 18 203265 213025 0.372122 6.76579 14.807 0.192739 1.38204 19 112354 565239 0.319334 6.73003 14.6728 0.162247 1.23175 20 459548 365824 0.361309 6.80957 14.9258 0.15476 1.28074 21 659369 147524 0.318654 6.87234 15.0754 0.140456 1.2272 22 584215 753268 0.365926 6.56857 14.3551 0.163679 1.25831 23 787789 989989 0.366771 6.52882 14.4654 0.187632 1.4107 24 123235 654546 0.384813 7.60551 16.1285 0.2599 1.42453 25 636963 147414 0.344725 6.57443 14.6367 0.135911 1.2607 26 459543 302369 0.295819 6.812 14.6297 0.17923 1.2025 27 645123 973451 0.338016 6.27922 13.9954 0.105584 1.19676
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||