Варжапетян А. - Исследование систем управления методами имитационного моделирования
Санкт-Петербургский Государственный университетаэрокосмического приборостроения
Список основных сокращений
АМП - амперпеременная
ВЭ - вычислительный эксперимент
ГСЧ - генератор случайных чисел
ДО - дисциплина обслуживания
FCFS ( устаревшее - FIFO ) - первый пришёл, первый обслужился
SPT (shortest process time ) наикратчайшее время обслуживания
ЕМВ - единица модельного времени
ИМ - имитационное моделирование или модель
ИН - идентификационный номер транзакта
КМ - компьютерное моделирование
КО - канал обслуживания
МАВ - машинное время
МВ - модельное время
ММ - математическое моделирование
МФ - модельный файл
ОБ - оператор блоков
ОО - оператор описания
ОУ - оператор управления
ПО - прибор обслуживания
ПР - пакетный режим
РВ - реальное время моделируемой системы
РРСЧ - равномерно распределённое случайное число
СБС - список ( цепь ) будущих событий
СЛА - стандартные логические атрибуты
СМО - система массового обслуживания
СП - список ( цепь ) пользователя
СЗ ( TG1 ) - счётчик завершений (число терминирований )
ССА - стандартные символьные атрибуты
СТС - список текущих событий
СЧА - стандартные числовые атрибуты
ТР - тестовый режим (режим дебагера)
УО - устройство обслуживания
Ха, Хакт - активный транзакт
ЯИМ - язык имитационного моделирования
Введение
В настоящее время одним из наиболее широко распространенных средств исследования и оптимизации функционирования систем управления (и вообще любых сложных социально-технических систем) является имитационное моделирование, в основном с применением современной вычислительной техники. ЭВМ программируется таким образом, чтобы программный продукт жил по законам, соответствующим условиям существования реальной системы.
Далее на такой имитационной модели можно отрабатывать воздействия различных факторов, влияющих на поведение системы, изучать влияние изменения внутренних параметров на эффективность функционирования и так далее.
Для создания таких моделей возможно использование как традиционных (так называемых универсальных языков программирования УЯП), так и специализированных программных средств (языков имитационного моделирования ЯИМ). Первые из них имеют следующие преимущества:
- доступность (большинство интерпретаторов распространенных УЯП, например, PASCAL, C++, распространяются за символическую плату, причем книги и прочую дополнительную информацию можно найти в любом специализированном магазине),
- возможность решения широкого класса задач,
- простота создание интерактивных дружественных интерфейсов для работы с конечным продуктом.
С другой стороны, специализированные языки имитационного моделирования по некоторым показателям превосходят УЯП. Их достоинства:
- значительно меньшие размеры программы, содержащей модель;
- идеологическое соответствие используемого средства поставленной цели;
- наличие специальных средств для обеспечения независимости случайных величин, генерируемых внутри программы;
- наличие специальных средств для отладки модели;
- относительная простота построения модели (по сравнению с УЯП).
Перечисленные выше особенности позволяют сделать однозначный выбор в пользу специализированных программных средств. Эти средства могут применяться, как в случаях простых моделей, когда на ЯИМ может получаться программа их нескольких строк, так и в случаях сложных моделей, когда написание модели на УЯП будет занимать чрезвычайно много времени из-за необходимости учитывать множество свойств моделируемого объекта.
В последнем случае существенным может стать и то обстоятельство, что модели на ЯИМ обычно требуют значительно меньшего времени на прогон (реализацию моделирования).
По каким же критериям может быть осуществлен выбор ЯИМ для конкретной задачи моделирования? Основные свойства, определяющие предпочтительность того или иного языка моделирования, следующие:
- возможности языка, т.е. способность описывать структуру системы, ее поведение и алгоритмы управления;
- простота применения для построения модели, реализация ее и представление результатов моделирования;
- предпочтение пользователя (удобство, простота, универсальность).
Выделим теперь несколько ЯИМ, приспособленных к решению задач, возникающих при имитационном моделировании человеко-машинных систем: наиболее известны такие языки, как GPSS, SIMSCRIPT и SIMULA. Сравнение этих программных средств по перечисленным выше критериям приведено в таблице 1.
Таблица 1
Сравнительные характеристики языков имитационного моделирования
| Возможности языка | Простота применения | Предпочтение пользователя |
| SIMULA | GPSS/H | SIMSCRIPT |
| GPSS/H | SIMSCRIPT | GPSS/H |
| SIMSCRIPT | SIMULA | SIMULA |
Как видно из сравнения, язык GPSS обладает преимуществом перед другими распространенными языками. Его особая привлекательность для целей обучения обуславливается тем, что он наиболее прост в применении.
На приведенной ниже схеме представлена логика обращения к ЯИМ GPSS, а точнее его последней и наиболее эффективной версии GPSS/H.
Виды моделирования: Физическое
Аналитическое
Компьютерное Типы компьютерного моделирования: Монте - Карло
Статистическое
Имитационное Разновидности ИМ: Симула
Симулинк
(более 500 разновидностей)
GPSS Версии GPSS: GPSS 360 (IBM, 1963, J.Gordon)
GPSS V ( DC, 1971, P. Hall)
GPSS PC (MSW, 1974, T. Springer)
GPSS World (MSW, 1999, A.Cox, T. Springer)
GPSS/H (Wolverine SWC, 1999, T. Henriksen) GPSS/H является наиболее эффективной версией из текстово-ориентированных версий GPSS (Л.1,2), а последний вариант GPSS World имеет интерфейс, приближенный к Windows. Профессиональная 32- разрядная версия GPSS/H работает под всеми версиями Windows: 98, 2000, NT, XP, версия, используемая для курсового проектирования, является студенческой (ограничение по числу операторов создаваемой модели, не более 100 и работа под МS DOS или предпочтительнее в оболочках NC, Far, VC). Кроме этих отличий студенческая версия дает полное представление о возможностях ЯИМ GPSS/H,
Позволяет получить начальные навыки работы как с самой программой, так и со встроенным отладчиком. Кроме задания по курсовому проектированию желательно, предваряя работу над заданием, провести практическое изучение различных вариантов построения модельного файла - МФ, изучить возможные ошибки и реакцию на них программы, воспользовавшись примером 3.2 параграфа 3.7 рассмотреть влияние разных команд отладчика.
Для использования возможностей программы достаточно РС 486.
Для более успешной работы над курсовым проектом следует предварительно внимательно прочесть главу 3.
Глава 1.Организация выполнения курсового проекта.
1.1 Указания и правила выполнения курсового проекта
В ходе выполнения курсового проекта кафедра назначает руководителя, который составляет задание по типовой форме, намечает график выполнения, проводит консультации и осуществляет процесс защиты курсового проекта.
Для выполнения курсового проекта каждому студенту выдаётся индивидуальное задание, утверждённое заведующим кафедрой, содержащее текстовое описание исследуемой системы - ИС, численные данные о переменных и параметрах, а также характеристики, которые необходимо оценить в процессе моделирования.
В ходе выполнения курсового проекта студент должен:
-выполнить формализацию описания ИС как дискретной системы,
-разработать алгоритмическое описание работы модели ИС,
-составить схему блоков (операторов) на языке GPSS/H-PC,
-провести моделирование в компьютерном классе кафедры,
-провести качественную и количественную оценку результатов,
-составить пояснительную записку.
Основные этапы курсового проекта
Этапы курсового проекта соответствуют этапам моделирования на ЭВМ реальных ИСУ. В основу машинного моделирования положены общие принципы, которые не зависят от вида используемого аналитического описания, формы представления процессов в машинной модели и применяемых языков описания модели.
К основным этапам моделирования сложных ИС относятся:
- Построение концептуальной модели ИС и её формализация.
- Алгоритмизация модели ИС и её машинная реализация.
- Получение и интерпретация результатов моделирования.
На первом этапе проводится изучение ИС с целью выделения основных составляющих процесса функционирования, определяются необходимые аппроксимации, и получается обобщённая схема модели, описывающая дискретные системы, описываемые теорией массового обслуживания. Основные аналитические модели ИСУ представляемые в виде систем массового обслуживания - СМО, приведены в главе 2 настоящих указаний.
На втором этапе полученная концептуальная (аналитическая) модель становится основой для разработки моделирующего алгоритма и построения имитационной модели на основе пакета GPSS/H. Описание особенностей моделирования на языке GPSS/H, описание блоков (операторов), а также примеры приведены в главе 3.
На третьем этапе осуществляется процесс моделирования, определяются заданные характеристики, делаются выводы и даются рекомендации.
Примерные сроки контроля выполнения проекта
Для выполнения курсового проекта достаточно PC IBM 386 DX, а при использовании языка GPSS/H PC v.3 , РС 486 серии или Пентиум. Для контроля процесса курсового проектирования следует
ориентироваться на примерные этапы приведенные ниже.
Подготовительный этап (1 - 4 недели) Студент должен разобраться с полученным заданием, подобрать рекомендованную литературу, выбрать концептуальную модель.
Проектный этап (5 9 недели) Студент должен ознакомиться с возможностями программного пакета (ПП), определить перечень функций, реализуемых блоками ПП, составить блок-схему,
выбрать критерии эффективности.
Реализационный этап (10 13 недели). Студент должен
окончательно отладить программу, получить и проанализировать результаты моделирования на ЭВМ.
Оформительский этап (14 15 недели). Студент должен оформить пояснительную записку в соответствии с принятыми в Университете требованиями. Записка должна давать достаточно полное представление о принципе решения задачи моделирования и включать все необходимые разделы, в том числе: выводы, заключение и список использованной литературы.
Общий объём записки не должен превышать 20 листов. Текст может быть написан от руки или набран на компьютере.
Заключительный этап (16 - 17 недели) - защита курсового проекта, которая осуществляется в соответствии с принятым на кафедре порядком.
Глава 2.Математическое обеспечение моделирования. Основные понятия теории массового обслуживания
Потоки заявок и их характеристики
Большинство событий, происходящих в системе, равно как потоки заявок и потоки их обслуживания чаще всего бывают случайными событиями, и лишь в некоторых случаях эти события детерминированы. Следует ввести две характеристики, имеющие по два состояния, тогда аналитические методы можно свести в классификационную таблицу аналитических моделей, исходя из двух основополагающих понятий:
- протяженности во времени,
- характера возникновения событий (отношения с внешней средой)
Рассмотрим эти понятия подробнее.
Протяженность во времени
Существует только два вида протекания, какого либо процесса во времени. Время может рассматриваться либо как непрерывная переменная t
Характер возникновения событий
При отсутствии случайных возмущений со стороны среды и полной определённости поведения компонентов системы имеем постоянную или детерминированную модель, для которой выберем индекс П. (во избежание путаницы с ранее введённым индексом Д). В большинстве случаев необходимо учитывать вероятностные характеристики всех воздействий, для этого класса моделей введём индекс В.
С учётом сказанного, классификация позволит рассматривать четыре типа моделей, а именно:
НП модели, ДП модели, НВ модели, ДВ модели.
Очевидно, что всё многообразие аналитических моделей можно разнести по этим классам. Обзор аналитических моделей невозможно провести в рамках указаний, подробнее см. (Л.
1,2). Ниже ограничимся сводной таблицей 2-1, которая содержит только некоторые аналитические модели и определяет область их применения.
Отметим, что приводимая ниже таблица иллюстрирует лишь предлагаемую идею классификации и не более того. НВ - модели наиболее подходят для моделирования на GPSS/H.
Таблица 2.1 Классификация математических моделей
|
Тип ММ Характеристика |
НП | ДП | ДВ | НВ |
|
Вид зависимости |
Дифференциальные и интегральные уравнения |
Теория разностных уравнений, конечные автоматы | Разностные стохастические уравнения, вероятностный автомат | Стохастические дифференциальные уравнения, теория массового обслуживания |
- Моменты первого порядка (мера положения) или математическое ожидание (среднее арифметическое, среднее геометрическое, среднее гармоническое, среднее квадратическое). Чаще всего используется среднее арифметическое:
- Момент второго порядка (мера рассеяния) дисперсия
или стандартное отклонение
Иногда используются моменты и более высокого порядка, называемые мерами формы и оценивающие отклонение от нормального распределения: третьего порядка ассиметрия и четвертого порядка эксцесс.
Среди непрерывных законов распределения случайных величин можно назвать: равномерный, нормальный, экспоненциальный законы и т.д.
Среди дискретных законов: Пуассона, Эрланга, геометрический и т.п.
Концептуальной схемой моделирования на GPSS/H является теория массового обслуживания. Как следует из названия, объект рассмотрения этой теории так называемые системы массового обслуживания (СМО). При моделировании на GPSS/H мы будем иметь дело с двумя потоками событий:
- входными потоками требований (приход клиентов в банк, покупателей в магазин, подъезд машин на заправку или на погрузку и т.д.).
- потоками обслуживания приходящих заявок.
Необходимо четко понимать различие между экспоненциальной и пуассоновской переменной, так как параметры указанных потоков можно задавать той или другой переменной (что и сделано в заданиях на курсовое проектирование).
При обсуждении прихода заявок (транзактов) можно с одной стороны, говорить об интервалах времени, а с другой, о темпе прихода заявок. Так, например, если интервал времени (промежуток между двумя последовательными приходами транзактов) в среднем равен 20 минутам, то темп прихода транзактов равен 3 событиям в час. Обычно при моделировании на GPSS/H чаще интересуются интервалом времени, так как возможно предсказать следующее событие, а программа устроена таким образом, что время рассматривается как непрерывная переменная, т.е. к первому моменту времени прихода транзакта приплюсовывается время прихода второго и т.д.
Поэтому случайное время прихода транзактов непрерывно !, а следовательно описывается непрерывным экспоненциальным распределением. В отличии от времени прихода, темп прихода дискретен по своей сути и измеряется целыми положительными числами. Так время прихода может быть любым, в том числе и дробным в заданном интервале, например
Отсюда следует, что процесс прихода событий пуассоновский, а интервалы прихода при этом подчиняются экспоненциальному закону. Чтобы это правило соблюдалось необходимо выполнение ряда условий:
- стационарности,
- ординарности,
- отсутствия последействия.
Стационарность случайного процесса означает, что на любом промежутке времени t вероятность прихода n заявок зависит только от числа n и величины промежутка t , но не изменяется от сдвига t по оси времени. При этом выполняется эргодическое свойство :- статистическое равенство n заявок , полученных при ИМ одной системы , или испытания n систем до прихода первой заявки . Формулирование этого свойства звучит достаточно просто : Совокупное значение по времени наблюдений равняется совокупному по ансамблю наблюдений .
Ординарность потока заявок означает невозможность появления более одной заявки в один и тот же момент времени.
Отсутствие последействия означает, что вероятность прихода n заявок в течение промежутка времени t не зависит от того, сколько пришло заявок до этого момента времени, выполнение этого условия гарантирует случайность и независимость событий . Такой поток называется простейшим, рассмотрим основные свойства простейшего потока
1. Устойчивость
Свойство устойчивости состоит в следующем: при суммировании независимых простейших потоков получается простейший поток с интенсивностью, равной сумме интенсивностей складывающихся потоков:
Для практических задач можно считать, что всякий поток, образующийся из любых нескольких (хотя бы 4-5) независимых ординарных потоков, является простейшим, причем интенсивности суммируются.
2. Разряжаемость
Поток заявок, полученный при исключении заявок с одинаковой вероятностью (при независимости этих исключений), также является простым потоком, причем интенсивность потока уменьшается пропорционально вероятности исключения:
где - интенсивность исходного потока.
3. В простейшем потоке распределение вероятности для промежутков времени между событиями таково, что малые промежутки более вероятны, чем большие. На практике это приводит к следующему важному результату: простейший поток заявок создает для системы массового обслуживания наименее благоприятную ситуацию; то есть, если некоторый результат получен в допущении, что поток простой, реальный результат будет не хуже теоретического.
Основные обозначения теории массового обслуживания
Системы массового обслуживания - СМО встречаются на каждом шагу, невозможно назвать область человеческой деятельности, где не возникает проблема обслуживания и создание очереди при занятости органа обслуживания (документооборот, телефонная связь, бизнес, торговля, промышленность, транспорт и т.д.).
В теории СМО разработаны идентичные модели для:
- Проектирования и эксплуатации систем, состоящих из большого числа аналогичных или похожих, но отличающихся производительностью компонентов (количество персонала, число линий связи, количество таможенных пунктов и т.п.).
- Отыскания оптимального количества оборудования (число лифтов в офисном здании, число грузовых терминалов и т.п.).
- Определения производительности той или иной системы
( производительность ЭВМ, пропускная способность канала связи и т.п.).
Очевидно, что можно назвать дополнительные возможности СМО и заключить, что во многих исследуемых системах сочетаются все указанные выше модели. Более того теория СМО быстро развиваеZся и появляются всё новые модели. В связи с этим ниже будут изложены только основополагающие идеи СМО, не претендующие, на какую либо новизну, являющиеся ориентиром для читателей не знакомых с теорией СМО и приводимые для лучшего понимания концептуальных основ ЯИМ GPSS/H .
Потоком заявок называется совокупность событий, случайно распределенных во времени. Соответственно, СМО представляет собой черный ящик, на входе и выходе которого наблюдаются потоки заявок.
Поток заявок рассматривается как случайный процесс, задаваемый функцией распределения промежутков времени между наступлениями двух последовательных случайных событий.
Интенсивность потока заявок среднее число заявок, поступающих в единицу времени. Интенсивность обозначается символом . Величина, обратная интенсивности, представляет собой средний интервал между наступлением соседних событий: tср=1/.
СМО можно описать, задавая (см. рис.2.1):
- входной поток заявок или требований v(t) (в GPSS/H транзакты), задающий вероятностный закон поступления заявок на обслуживание. Заявки могут поступать либо по одиночке, либо группами (пакетами). В GPSS/H входной поток задаётся оператором блока GENERATE .
- поток обслуживания u(t) - задающий вероятностный закон процесса обслуживания заявок. В GPSS/H поток обслуживания задаётся оператором блока ADVANCE.
- прибор обслуживания Pi , i =1,2, , N, состоящий из накопителя Hm емкостью 0 m, при m = 0 происходит потеря обслуживания, а при
m = все заявки ожидают обслуживания, промежуточные значения определяют ёмкость накопителя . В состав прибора также входит канал обслуживания Kp, p=1,2,,P при p =1 обслуживание называется одноканальным, а при p1 - многоканальным.
Если приборы обслуживания соединяются параллельно, то такое обслуживание называется однофазным, а если приборы соединяются последовательно, то многофазным, (ряд последовательных операций).
- очередь - задержка в обслуживании поступающих заявок, характеризующаяся дисциплиной очереди, т.е. порядком обслуживания заявок. Можно назвать разные виды дисциплины обслуживания:
- FIFO - первый пришёл - первый вышел (обслужился), в англоязычной литературе эта известная аббревиатура всё чаще заменяется на FCFS (first come first serve) - первый пришёл - первый обслужился ,
- LCFS - последним пришёл - первым обслужился, эта дисциплина предназначена для заявок с более высоким приоритетом, но эта дисциплина используется крайне редко, а чаще используется дисциплина следующего вида,
- SPT (shortest processing time) - кратчайшее время обслуживания, которое применяется для заявок с приоритетом, в GPSS/H эта дисциплина реализуется оператором блока PRIORITY.
- случайная дисциплина, например система опроса слушателей на практических занятиях.
Подчеркнём, что в GPSS/H факт создания очереди реализуется связанной парой операторов блоков QUEUE / DEPART .
- Выходной поток y ( t )- функция распределения, представляющая собой сумму двух вероятностных законов y1(t ) - поток обслуженных заявок и y2 ( t ) поток потерянных ( не обслуженных ) заявок, который образуется за счёт отказа в обслуживании из-за малого объёма накопителя по принципу m + 1 K, где К число заявок на входе прибора. В отдельных случаях заявка может остаться в приборе из-за окончания времени моделирования, поэтому в неравенстве появляется единица.
Всё сказанное объединим в рис 2.1. На рисунке 2.1 представлена структура прибора обслуживания с входящими и выходящими потоками. На рис. 2.1 б виды СМО, на котором прибор обслуживания для простоты представлен прямоугольником, внутреннее содержание которого представлено на рис.
2.1а.
Таким образом, однофазные ( простые ) СМО могут быть либо одноканальными, либо многоканальными. Многофазные СМО, представляющие последовательность различных операций, выполняемых различными приборами обслуживания, могут представлять собой комбинацию одно и многоканальных СМО.
