Содержание к диссертации
Введение
1 Анализ методов и средств компьютерного моделирования систем и сетей массового обслуживания 12
1.1 Анализ аспектов построения аналитических, численных и имитационных моделей 12
1.2 Методы представления моделей систем и сетей массового обслуживания 18
1.3 Концептуальные модели сетей массового обслуживания 22
1.4 Анализ существующих средств компьютерного моделирования 27
1.5 Анализ технологий построения приложений к системе MathCad 35
Выводы 40
2 Моделирование систем и сетей массового обслуживания ; с применением аналитических и численных методов 42
2.1 Приведение модели системы массового обслуживания типа М/М/т/п
к модели типа М/М/т/ 42
2.2 Модельное представление систем массового обслуживания в пространстве состояний 46
2.3 Структурированное модельное представление сетей массового обслуживания в пространстве состояний 53
2.4 Методика построения модели сети массового обслуживания на основе представления сети в виде сети Петри 63
2.5 Исследование нелинейных систем и сетей массового обслуживания с применением преобразования Лапласа 69
Выводы 78
3 Математическое и алгоритмическое обеспечение приложения для имитационного моделирования 79
3.1 Представление модельного времени 79
3.2 Модели и алгоритмы источников импульсов 82
3.3 Модели и алгоритмы узлов обслуживания з
3.4 Модельное представление сетей массового обслуживания 90
3.5 Модели компонентов обработки результатов имитационного моделирования 91
3.6 Технология разработки программного комплекса на C++ для Mathcad 95
Выводы 107
4 Проведение вычислительных экспериментов с приложением 108
4.1 Исследование источников импульсов 108
4.2 Исследование узлов обслуживания
4.2.1 Одноканальная СМО без буфера (М/М/1/0) 123
4.2.2 Одноканальная СМО с ограниченным буфером (М/М/1/2) 125
4.2.3 Одноканальная СМО с бесконечным буфером (М/М/1) 127
4.2.4 Трехканальная СМО без буфера (М/М/3/0) 130
4.2.5 Трехканальная СМО с буфером ограниченной емкости (М/М/3/3) 132
4.2.6 Трехканальная СМО с буфером неограниченной емкости (ММ/3) 134
4.2.7 Двухузловая СМО без буфера с неоднородным потоком заявок
4.2.7.1 Анализ адекватности имитационной модели 137
4.2.7.2 Анализ чувствительности имитационной модели 142
4.2.7.3 Анализ устойчивости имитационной модели 143
4.3 Анализ процесса обработки кодограмм в модуле разведки и управления 145
Выводы 151
Заключение 152
Список терминов 154
Список использованных источников
- Концептуальные модели сетей массового обслуживания
- Модельное представление систем массового обслуживания в пространстве состояний
- Модели и алгоритмы источников импульсов
- Одноканальная СМО с бесконечным буфером (М/М/1)
Введение к работе
Актуальность темы. Актуальность применения метода компьютерного моделирования систем и сетей массового обслуживания обусловлена сложностью процессов функционирования. Интерес представляет анализ систем с нестационарными входными параметрами, которые могут быть исследованы с помощью аналитического и численного методов моделирования. При отсутствии физической модели сложной системы, из-за большой размерности модели или невозможности приведения процесса к марковскому единственным подходом является применение имитационного моделирования.
Значительный вклад в развитие математических и имитационных методов моделирования внесли А. А. Марков, А. Н. Колмогоров, А. Я. Хинчин,
Л. Клейнрок, Р. Шеннон, Т. Саати, Л. А. Овчаров, Е. С. Вентцель, Б. В. Гнеденко, И. Н. Коваленко, Н. П. Бусленко, В. Е. Котов, Дж. Питерсон, В. Кельтон,
А. Лоу, А. А. Самарский, Э. К. Алгазинов, Т. И. Алиев, П. П. Макарычев и др.
В настоящее время для имитационного моделирования разработаны специализированные проблемно-ориентированные программные средства Arena, AnyLogic, GPSS, Vissim, ExtendSim, AutoMod, Promodel и др., к недостаткам которых можно отнести сравнительно высокую стоимость и требование достаточно высокого уровня подготовки персонала; а также универсальные математические пакеты Mathcad, Matlab, Maple, Mathematica, Scilab, Maxima, FreeMat и др.
К достоинствам математических пакетов следует отнести наличие простого и удобного интерфейса, библиотеки встроенных функций, графических средств представления результатов, возможность символьных вычислений, а также возможность интеграции с множеством специализированных программных продуктов. Кроме того, математические пакеты являются инструментальными средствами, позволяющими реализовать как численное, так и имитационное моделирование систем. В математическом пакете Mathcad имеется возможность взаимодействия со следующими программными продуктами: приложением для моделирования систем на сигнальном или физическом уровне VisSim/Comm PE, программными комплексами САПР Pro/ENGINEER, SolidWorks, AutoCAD, чертежным приложением SmartSketch, табличным процессором Exсel, математическим пакетом Matlab. Открытая архитектура приложения в сочетании с поддержкой технологий NET, HTML и XML позволяет легко интегрировать Mathcad практически в любые IT-структуры и инженерные приложения. Поддерживаются стандартные языки программирования сценариев, такие как VBScript и JScript. Имеется возможность создания электронных книг (e-Book).
Однако моделирование достаточно сложных систем и сетей массового обслуживания средствами математических пакетов занимает значительно больше времени по сравнению с использованием универсальных языков программирования. Это обусловлено тем, что встроенные в математические пакеты языки программирования являются интерпретируемыми, а универсальные, такие как C++, Pascal, Java, Basic, – компилируемыми. Помимо этого, при разработке имитационных моделей в среде математических пакетов отсутствует возможность скрытия исходного кода и создания достаточно удобного интерфейса.
Для объединения достоинств математических пакетов и универсальных языков программирования в математические пакеты встроен инструмент подключения внешних модулей, написанных на языке С++. Математическая система Mathcad имеет многофункциональное ядро, однако прямой доступ к большинству операций ядра для пользователей закрыт. Для расширения функциональных возможностей в системе Mathcad содержится инструмент, позволяющий перевести пользовательские функции, написанные на языке С++, в разряд встроенных через механизм DLL (Dynamic Link Library). Сами функции, созданные через механизм DLL, имеют универсальный характер и могут подключаться к другим расчетным и программным средам (Matlab, Mathematica, Scilab, FreeMat). Mathcad поставляется с дополнительными библиотеками, предназначенными для анализа данных, обработки сигналов и изображений, волнового преобразования, пакетами строительства, электротехники и машиностроения. Основная проблема, связанная с подключением внешних модулей, заключается в том, что в среде Mathcad не предусмотрена библиотека для проведения имитационного моделирования, в связи с чем отсутствует алгоритм построения математической модели для организации имитационного моделирования систем и сетей массового обслуживания. Таким образом, задача разработки комплекса прикладных программ имитационного моделирования, который может быть встроен в Mathcad, а также в другие математические пакеты, является актуальной.
Объект исследования: комплекс прикладных программ в виде библиотеки динамической компоновки для имитационного моделирования систем и сетей массового обслуживания в среде математических пакетов.
Предмет исследования: аналитические, численные и имитационные модели процессов в системах и сетях массового обслуживания в среде математических пакетов.
Целью диссертационной работы является теоретическое обоснование и исследование моделей, алгоритмов для создания комплекса программ, обеспечивающего расширение функциональных возможностей математического пакета в области компьютерного моделирования систем и сетей массового обслуживания.
Для достижения поставленной цели решены следующие задачи:
- анализ теоретического и прикладного аспектов компьютерного моделирования процессов в системах и сетях массового обслуживания;
- теоретическое обоснование и исследование моделей для анализа неустановившихся процессов дискретных моделей систем и сетей массового обслуживания численными методами;
- теоретическое обоснование и исследование моделей систем и сетей массового обслуживания для создания библиотеки динамической компоновки имитационного моделирования средствами математического пакета;
- разработка и экспериментальное исследование комплекса прикладных программ в виде библиотеки динамической компоновки для имитационного моделирования процессов в системах и сетях массового обслуживания средствами математического пакета Mathcad операционной системы Windows.
Методы исследования основаны на использовании положений теории аналитического, численного и имитационного моделирования, теории систем и сетей массового обслуживания, теории вероятностей и прикладной математической статистики, теории случайных процессов, теории математической логики, теории графов и теории концептуального программирования.
Научная новизна работы заключается в следующем:
1) предложена процедура преобразования модели системы массового обслуживания с ограниченным буфером к системе массового обслуживания с неограниченным буфером, отличительная особенность которой состоит в оценке величины погрешности и обеспечении снижения размерности модели;
2) предложена методика построения аналитических моделей экспоненциальных сетей массового обслуживания, отличающаяся представлением потока обслуженных отдельным узлом заявок в виде функции от распределения вероятностей состояний, что обеспечивает анализ узловых характеристик и снижение размерности модели;
3) разработана методика преобразования модели сети массового обслуживания в виде сети Петри к аналитической и численной моделям с использованием интегрального преобразования Лапласа, которая отличается модельными представлениями в виде дерева достижимости и размеченного графа переходов случайного процесса, обеспечивающая линеаризацию модели;
4) разработан алгоритм расчета узловых характеристик имитационной модели сети массового обслуживания, который отличается оценкой распределения вероятностей состояний, что позволяет провести сравнительный анализ результатов имитационного моделирования с решениями системы уравнений Колмогорова и оценить степень адекватности имитационной модели;
5) разработан алгоритм визуализации потоков заявок и узловых характеристик сети массового обслуживания, который, в отличие от известных, обеспечивает графическое представление процессов функционирования во времени узла сети по выбору (занятости каналов и суммарной занятости узла, потерь и занятости буфера, суммарной занятости каналов и буфера);
6) разработаны и исследованы имитационные модели для реализации комплекса программ моделирования сетей массового обслуживания в виде внешней библиотеки динамической компоновки для операционной системы Windows, который, в отличие от известных, содержит набор компонентов для конструирования моделей, что обеспечивает снижение затрат времени на реализацию компьютерного моделирования за счет исключения процедуры программирования.
Достоверность результатов работы основана на результатах проведенных исследований:
- соответствия псевдослучайных величин, полученных разработанными генераторами заявок, их теоретическим законам распределения по критерию согласия «-квадрат»;
- исследование имитационных моделей узлов обслуживания на адекватность, чувствительность и устойчивость;
- сравнительный анализ выходных характеристик имитационных моделей систем массового обслуживания с аналогичными характеристиками, полученными аналитическим способом.
Практическая значимость работы. Разработанный программный комплекс может быть использован для моделирования процессов в различных прикладных областях: производстве, экономике, управлении, экологии и др.
Программный комплекс состоит из следующих компонентов:
- блок имитационного моделирования систем и сетей массового обслуживания: поддерживается ввод численных значений входных параметров в окно интерфейса, что позволяет минимизировать время обучения персонала;
- блок статистической обработки результатов моделирования: помимо вывода значений вероятностей состояний узлов сети, осуществляется расчет вероятностей занятости каналов в узлах, среднего времени обслуживания и ожидания в узлах, средней длины очереди в узлах;
- блок визуализации параметров функционирования систем и сетей массового обслуживания: обеспечивает наглядность функционирования любого узла сети.
Благодаря особенностям технологии разработки данный комплекс программ носит универсальный характер и может быть подключен к другим математическим пакетам.
Реализация и внедрение результатов работы. Комплекс программ имитационного моделирования и практические результаты внедрены в ОАО «Научно-производственное предприятие “Рубин”».
Материалы диссертационной работы использованы при проведении лабораторных занятий по дисциплинам «Теория массового обслуживания», «Компьютерное моделирование», изучаемым студентами специальности 230105.65 –
«Программное обеспечение вычислительной техники и автоматизированных систем» факультета вычислительной техники ПГУ.
Основные положения, выносимые на защиту:
1) процедура преобразования модели системы массового обслуживания с ограниченным буфером к системе массового обслуживания с неограниченным буфером, обеспечивающая снижение размерности модели;
2) методика построения аналитических моделей экспоненциальных сетей массового обслуживания, основанная на представлении потока обслуженных отдельным узлом заявок в виде функции от распределения вероятностей состояний, что обеспечивает возможность расчета узловых характеристик и снижение размерности модели;
3) методика преобразования модели сети массового обслуживания в виде сети Петри к аналитической и численной моделям с использованием интегрального преобразования Лапласа, обеспечивающая линеаризацию модели;
4) алгоритм расчета узловых характеристик имитационной модели сети массового обслуживания, который характеризуется оценкой распределения вероятностей состояний, обеспечивающий проведение сравнительного анализа результатов имитационного моделирования с решениями системы уравнений Колмогорова;
5) алгоритм визуализации потока заявок и выходных характеристик, обеспечивающий отображение процесса функционирования выбранного узла;
6) имитационные модели для реализации комплекса программ имитационного моделирования систем и сетей массового обслуживания в виде внешней библиотеки динамической компоновки DLL, обеспечивающего интеграцию как с Mathсad, так и с другими математическими пакетами, поддерживающего конструкторский подход к построению моделей, что позволяет снизить трудоемкость их разработки в среде математических пакетов.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях: V (юбилейной) Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2011 г.); V Международной научно-технической конференции молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (Пенза, 2011 г.); Международной научно-практической конференции «Молодежь и наука: модернизация и инновационное развитие страны» (Пенза, 2011 г.); V Всероссийской молодежной научной конференции «Мавлютовские чтения» (Уфа, 2011 г.); XVI Международной научно-методической конференции «Университетское образование» (Пенза, 2012 г.); Международной молодежной конференции в рамках фестиваля науки «Математические проблемы современной теории управления системами и процессами» (Воронеж, 2012 г.); XII Международной заочной научно-практической конференции «Инновации в науке» (Новосибирск, 2012 г.); VIII Международной научно-практической конференции «Современное состояние естественных и технических наук»
(Москва, 2012 г.).
Публикации. По теме диссертационного исследования опубликовано
11 печатных работ: 3 статьи в изданиях из перечня ВАК, 8 – в других из-даниях.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 145 наименований и трех приложений. Объем работы: 172 страницы основного текста, включающего 87 рисунков, 27 таблиц и 51 страницу приложений.
Концептуальные модели сетей массового обслуживания
На диаграммах IDEF0 явно не указываются последовательность выполнения действий и время. Этот недостаток восполняет использование еще одной распространенной в рамках технологии SADT графической нотации - IDEF3, называемой также диаграммой потока работ (Workflow). Нотация IDEF3 ориентирована на описание логики информационного взаимодействия в системе на основе сбора данных, необходимых для проведения структурного анализа системы. Она дополняет технологию IDEF0. Возможности этой технологи позволяют моделировать и анализировать альтернативные сценарии развития изучаемых процессов.
Основными элементами, с помощью которых создаются диаграммы IDEF3, являются единицы работ (процессов), связи между ними, ссылочные объекты, а также перекрестки слияния и разветвления, представляющие собой элементы для отображения логики взаимодействия потоков. При построении моделей систем в нотации IDEF3 используются соединения, или перекрестки, определяющие ветвление процесса и указывающие ан порядок завершения или начала выполнения нескольких действий. Соединения реализуют логические операции «и», «или», а также «исключающее или». На рисунке 6 представлен пример построения модели в виде диаграммы IDEF3, описывающей технологический процесс изготовления детали.
Изготовление детали по двум альтернативным технологиям в нотации IDEF3 В IDEF3 может проводиться множественная декомпозиция диаграмм. Различают два вида декомпозиции: сценарий и описание. Описание включает все возможные пути развития процесса. Сценарий является частным случаем описания и иллюстрирует только один путь развития процесса. Важной спецификой IDEF3 является ориентация технологии на воспроизведение логики и причинно-следственных связей, действующих в системе при протекании моделируемых процессов. Это дает основания для использования этих моделей в ходе анализа, реализуемого средствами имитационного моделирования.
Таким образом, к достоинствам применения моделей IDEF следует отнести: полноту описания структуры системы, комплексность декомпозиции, наличие жестких требований, обеспечивающих получение моделей стандартного вида и простоту документирования процессов.
Таким образом, построение модели системы с использованием нотаций IDEFO, IDEF3 обеспечивает целостность и полноту описания структуры и функций системы, логики взаимодействия процессов и соответствующих им материальных и информационных потоков. Однако для комплексного анализа динамики процесса и определения его характеристик данной модели недостаточно. В этой связи необходимо использовать аппарат имитационного моделирования с целью проведения динамического многовариантного анализа и оптимизации процессов системы. Имитационное моделирование системы позволяет получить ее алгоритмическое описание посредством моделирующих алгоритмов, в соответствии с которыми вырабатывается информация, описывающая элементарные явления исследуемого процесса с учетом их связей и взаимных влияний. Получаемая таким образом информация о состояниях процесса используется для определения результирующих характеристик системы.
В настоящее время метод имитационного моделирования является одним из самых мощных и наиболее эффективных методов исследования процессов и систем самой различной природы и степени сложности. Используя результаты имитационного моделирования, можно описать поведение системы, оценить влияние различных параметров системы на ее характеристики, выявить преимущества и недостатки предлагаемых изменений, прогнозировать поведение системы. В связи с этим наблюдается устойчивый рост количества используемых инструментальных средств моделирования в самых различных областях, связанных с управлением и принятием решений технического, экономического, организационного, социального характера. Реализация имитационного моделирования может быть осуществлена с использованием специализированных проблемно-ориентированных программных средств (Arena, AnyLogic, GPSS, Vissim, ExtendSim, AutoMod, Promodel и др.), отличительные особенности которых состоят в сравнительно высокой стоимости и требовании достаточного уровня подготовки персонала, а также универсальных математических пакетов (Mathcad, Matlab, Maple, Mathematica и др.).
К достоинствам математических пакетов следует отнести простой и удобный интерфейс, широкую библиотеку встроенных функций и численных методов, возможность символьных вычислений, графические средства представления результатов, а также возможность интеграции со специализированными программными продуктами имитационного моделирования. Кроме того, математические пакеты являются инструментальными средствами, позволяющими реализовать как аналитическое, так и имитационное моделирование систем [91].
Однако моделирование достаточно сложных систем средствами математических пакетов занимает значительно больше времени, чем на универсальных языках программирования, за счет того, что встроенные в математические пакеты языки программирования являются интерпретируемыми, а универсальные - компилируемыми. Помимо этого, при разработке имитационных моделей в среде математических систем отсутствует возможность скрытия исходного кода и создания достаточно удобного интерфейса.
С целью совмещения достоинств математических пакетов и универсальных языков программирования в математические пакеты входит инструмент подключения внешних модулей, написанных на языках C++, Java, Visual Basic. Основные ограничения использования данного механизма связаны с отсутствием единой технологии расширения функциональных возможностей математических систем, а также недостаточной развитостью данной технологии, вследствие чего имеется целый ряд ограничений, связанных с разработкой внешних модулей и интеграцией в математические пакеты.
Модельное представление систем массового обслуживания в пространстве состояний
Сигналы на входе и выходе системы являются функциями времени, т.е. отображениями множества моментов времени Т на множество X входных и множество Y выходных сигналов. Математическая модель системы определяется оператором S, отображающим множество входных сигналов на множество выходных сигналов: Х- Уили {y(t)} = S{x(t)}, x(t)e X, y(t)e У. Оператор S характеризует так называемую модель «вход-выход» системы [47]. Теорию систем, использующую модель «вход-выход», называют макротеорией систем. Модель «вход-выход» описывает только соотношение между сигналами на входе и выходе системы и не отображает внутреннее состояние системы. По этой причине указанную модель иногда называют «черным ящиком».
Иная ситуация возникает, когда входной сигнал известен лишь на конечном интервале времени [і0,Г\. Тогда мгновенное значение y(t)выходного сигнала зависит не только от заданного отрезка х входного сигнала, но и состояния z(t0) системы в момент времени t0, в котором закодировано все «прошлое» системы. Таким образом, состоянием системы в момент времени t0 называют набор сведений о прошлом системы, который в совокупности с входным сигналом, заданным на интервале [t0,t], необходим и достаточен для однозначного определения выходного сигнала, т.е. y(t) = D,[z(t0),х ].
Состояние системы также изменяется во времени и определяется уравнением перехода y(t) = A,[z(t0),x ]. Соотношения, учитывающие внутреннее состояние системы, характеризуют так называемую модель «вход-состояние-выход» системы. Теорию систем, использующую данную модель, называют микротеорией систем [118].
В ряде практических задач приходится встречаться с такой ситуацией, когда первоначальный поток требований, проходя через ряд последовательных обслуживающих приборов, теряет некоторую долю составляющих его элементов. Такой поток принято называть редеющим потоком [57]. Доказано, что пуассоновский входящий поток, редея случайным образом, образует пуассоновский поток, а поток потерь также является пуассоновским [121]. Таким образом, для проведения аналитического анализа экспоненциальной сети массового обслуживания (СеМО) можно независимо исследовать ее узлы, представляющие системы массового обслуживания (СМО) типа М/М/т/п. Для нахождения характеристик узлов СеМО необходимо рассчитать интенсивность входных потоков [44].
Динамические стохастические системы, которыми, в частности, являются СМО и СеМО, характеризуются параметрами, в общем случае зависящими от времени. Если система удовлетворяет условию эргодичности, то существует стационарный (установившийся) режим функционирования, при котором параметры не зависят от времени. Такой режим и его характеристики представляют особый интерес при решении практических задач.
Как известно, m-узловая СМО (т 1) с «-местным буфером (и 0), представляющая систему типа гибели - размножения, описывается системой линейных дифференциальных уравнений Колмогорова [105], решениями которой являются значения вероятностей состояний pQ(t),px(t),...pm+„{t).
Определим интенсивность выходного потока одноузловой СМО с п местным буфером (« 0) . Вероятностное разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью V(t) = рЯ(0, где X(t) - интенсивность исходного потока. Поток исключенных заявок - тоже простейший с интенсивностью X\t) = (1 - рЖО [3].
Пусть на вход нестационарной СМО Ml Ml \ In, функциональная схема которой представлена на рисунке 11, подается пуассоновский поток с параметром
Графики переходного процесса в СМО типа Ml Ml ИЗ Из графиков, представленных на рисунке 12, видно, что значение выходного потока y(t) при t = 0 равно нулю и на отрезке t є [0,5] непрерывно возрастает, стремясь к значению 0.2, однако при t = 5 достигает значения 0.181. Значение выходного потока на отрезке t є (5,25] непрерывно возрастает, стремясь к значению 0.5, однако при t = 25 достигает значения 0.453.
Рассмотрим m-узловую СМО (т 1)с «-местным буфером (« 0). Пусть на вход СМО Ml Ml ml п, функциональная схема которой представлена на рисунке 13, подается пуассоновский поток с параметром X(t).
Модели и алгоритмы источников импульсов
Динамическая природа дискретно-событийных имитационных моделей требует отслеживания текущего значения имитационного времени по мере функционирования имитационной модели. Необходим также механизм для продвижения имитационного времени от одного значения к другому. В имитационной модели переменная, обеспечивающая текущее значение модельного времени называется часами мопельного времени. П и создании модели на таких универсальных языках, как FORTRAN или С, единица времени для часов модельного времени никогда не устанавливается явно. Подразумевается, что оно будет указываться в тех же единицах, что и входные параметры, К тому же модельное время и время, необходимое для прогона имитационной модели на компьютере, как правило, невозможно соотнести.
Существует два основных подхода к продвижению модельного времени: продвижение времени от события к событию и продвижение времени с постоянным шагом [142]. Первый подход имеет существенное преимущество , заключающееся в значительной экономии машинного времени и чаще всего используется при имитационном моделировании большинством разработчиков; создающих свои модели на универсальных языках. Поэтому в дискретно-событийных моделях, рассматриваемых в этой работе, применяется продвижение модельного времени от события к событию. При использовании продвижения времени от события к событию часы модельного времени в исходном состоянии устанавливаются в «ноль» и определяется время возникновения будущих событий. После этого часы модельного времени переходят на время возникновения ближайшего события, и в этот момент обновляются состояние системы с учетом произошедшего события, а также сведения о времени возникновения будущих событий. Затем часы модельного времени продвигаются ко времени возникновения следующего (нового) ближайшего события, обновляется состояние системы и определяется время будущих событий, и т. д. Процесс продвижения модельного времени от времени возникновения одного события ко времени возникновения другого продолжается до тех пор, пока не будет выполнено какое-либо условие останова, указанное заранее. Поскольку в дискретно-событийной имитационной модели все изменения происходят только во время возникновения событий, периоды бездействия системы просто пропускаются, и часы переводятся со времени возникновения одного события на время возникновения другого. При продвижении времени с постоянным шагом такие периоды бездействия не пропускаются, для обеспечения точности величина шага должка выбираться достаточно малой, что приводит к большим затратам компьютерного времени [49].
Моделирующий алгоритм комплекса программ представлен на рисунке 34. В нем в рамках внешнего цикла по числу статистических испытаний и вложенного цикла по времени моделирования в соответствии с методом особых состояний осуществляется поиск ближайшего по времени изменения состояний элементов системы, связанного либо с поступлением новой заявки от источника, либо с освобождением канала обслуживания. После этого осуществляется переход к соответствующему модулю имитации активности. После завершения внешнего цикла производится статистическая обработка и визуализация результатов имитационного моделирования. Начало
Изложенный алгоритм отвечает задаче построения имитационных моделей таких сложных систем, как СМО и СеМО на основе Q-схем с использованием универсальных языков программирования высокого уровня. 3.2 Модели и алгоритмы источников импульсов
Любая сложная система функционирует с элементами случайности. Случайный характер носит воздействие шумов и помех в каналах передачи информации, элементы системы случайным образом могут выходить из строя, сами потоки данных, циркулирующие в системе, носят стохастический характері Именно поэтому при исследовании вариантов построения систем реализуется метод статистического моделирования, в рамках которого непременно должна осуществляться имитация случайных событий, случайных величин и случайных процессов, действующих в системе.
Центральное место в перечне вопросов, связанных с имитацией стохастических элементов системы, занимает проблема построения датчиков случайных величин с заданными законами распределения. При этом базовыми алгоритмом, на основе которого могут быть получены алгоритмы и программы моделирования любых случайных величин, является алгоритм (датчик) стандартной равномерно распределенной случайной величины. Функция распределения F(x), функция плотности вероятностей fix), а также математическое ожидание м и дисперсия D этой величины на отрезке [а,Ь] определяются соотношениями [23]: 0,х а F{x) = Х й L St Ч ,a x b, fix) = Ъ-а \,х Ъ ,xe[a,b] b + a ib-a)2 „ ,М_ 0_ 0,хе[а,Ь] Функция DoubleRand() использует стандартную функцию С-библиотеки stdlib.h rand() и возвращает равномерно распределенное случайное число в интервале [0,1].Для имитации равномерного распределения в интервале [а,Ь] используется формула: x = a + ib-a)-Rn, где Rn- равномерно распределенное случайное число в интервале [0,1]. Листинг программы ravnom с входным параметром «интенсивность импульсов» представлен ниже double ravnom(double lam)
Специализированные программные средства, предназначенные для вероятностного моделирования, обычно имеют специальные встроенные процедуры генерирования случайных величин с разными законами распределений. В C++ встроен генератор только для равномерного распределения. Имея стандартный датчик равномерной случайной величины в интервале [0,1], можно получить простые алгоритмы генерации случайных величин с другими распределениями.
Так, для генерации случайных чисел, распределенных по экспоненциальному закону с параметром X, используется метод нелинейного функционального преобразования [138]. Идея метода вытекает из следующей теоремы.
Пусть случайная величина а имеет равномерное распределение в интервале [0,1] и связана со случайной величиной Ь, соотношением: тогда случайная величина Ъ, имеет плотность распределения вероятностей вида /О) и может быть найдена на основе обратного функционального преобразования = р ] (а), если такое преобразование существует (условием этого является существование первой производной у функции распределения). Доказательство теоремы приведено в источнике [138].
Одноканальная СМО с бесконечным буфером (М/М/1)
Устойчивость модели рассматривается как способность сохранять адекватность при исследовании эффективности системы на всем возможном диапазоне рабочей нагрузки [1]. При этом устойчивость результатов моделирования оцененивается методами математической статистики. Решение задачи заключается в том, чтобы проверить гипотезу относительно свойств некоторого множества элементов, называемого генеральной совокупностью, оценивая свойства какого-либо подмножества генеральной совокупности (т.е. выборки). Устойчивость результатов моделирования можно рассматривать как признак, подлежащий оценке. Для проверки гипотезы об устойчивости результатов может быть использован критерий Уилкоксона [56].
Критерий Уилкоксона служит для проверки того, относятся ли две выборки к одной и той же генеральной совокупности.
Проверка указанной гипотезы проводится в следующем порядке: 1. Формируются две независимые выборки вероятности занятости второго какала pz2\ и pzTl при сохранении всех значений входных характеристик: Xt =0.4, Х2 = 0.3, ц, =0.5, \i2 =0.6, Т = 500, t = 10, где t - шаг моделирования. Значения членов выборокpz2\ ирг22 представлены в таблицах 21, 22; 2. Относительно законов распределения pz2\ и pz22 никаких предположений не делается; 3. В случаеpz21 t pz22„ /-0...49 пара значений образует инверсию; 4. Подсчитывается полное число инверсий и = 1315. иа, где щ,п2- количество 5. Гипотезу не следует отвергать, если 2 членов в первой и второй выборке соответственно (и,=И2=50), 144 «/z2(«j +n2 +1) критическое значение (для заданного уровня значимости 0.95), za =1.62 - коэффициент, определяющийся из таблицы 1.1.2.6.2 [12]. и- и„ = 242, пхпг = 14.5. Очевидно, что в данном случае согласно критерию Уилкоксона гипотезу о принадлежности данных выборок одной генеральной совокупности не следует отвергать. Визуализацию анализа модели на устойчивость иллюстрируют графики, представленные на рисунке 80.
Визуализация анализа модели на устойчивость Значения первой выборки вероятностей занятости второго узла представлены в таблице 22.
Модель процесса обработки кодограмм, представленная на рисунке 81, располагает двумя генераторами кодограмм, функционирующими по детерминированному закону с временем генерации 28.75 мс. Проценты разрежения потоков первого и второго типов бракованными кодограммами варьируются. Имеются один узел обслуживания с интенсивностью обслуживания одной кодограммы ц, изменяющейся от 25 до 32 мс и два четырехместных буфера, в которые случайным образом поступают кодограммы первого, второго типа и бракованные. Если на первом месте в буфере оказывается бракованная кодограмма, она покидает буфер. В случае, если все места в буфере заняты и отсутствует пара, буфер автоматически очищается. На обслуживание поступает пара разнотипных кодограмм, взятых из одного буфера. При этом обслуживание кодограмм осуществляется последовательно в порядке времени поступления. Цикл завершается после обслуживания 100 пар кодограмм. Требуется найти вероятности потерь.
График плотности вероятностей для нормального распределения времени обслуживания Входными параметрами комплекса программ имитационного моделирования являются времена генерации соседних кодограмм; проценты разрежения бракованными кодограммами, устанавливаемые для каждого генератора в пределах от 0 до 99%; среднее время обработки и среднеквадратическое отклонение; объем буферов. Выходными характеристиками являются вероятность занятости узла, среднее время обслуживания, средние длины очередей в первом и втором буферах, средние времена ожидания в буферах кодограмм первого и второго типов, вероятности потерь кодограмм первого и второго типов, количество прошедших обслуживание пар, время выхода из узла последней пары. С помощью комплекса программ имитационного моделирования было проведено 7 экспериментов с пятидесятикратным повторением. Результаты имитационного моделирования представлены в таблице 24.
Выводы: в результате проведения экспериментов с различным разрежением потоков кодограмм от 10 до 90% с пятидесятикратным повторением каждого и вычислением усредненных значений было установлено: 1) вероятность потерь принимает минимальное значение при 10%-ном разрежении обоих потоков бракованными кодограммами, равное 0.18, время выполнения цикла составляет 3968 мс; 2) вероятность потерь принимает максимальное значение при 10%-ном разрежении одного из потоков и 90%-ном разрежении другого, равное 0.627, время выполнения цикла составляет 8395 мс.
