Имитационное моделирование экономических процессов

Размещено на http://www.allbest.ru/

БЕЛКООПСОЮЗ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«БЕЛОРУССКИЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ

УНИВЕРСИТЕТ ПОТРЕБИТЕЛЬСКОЙ КООПЕРАЦИИ»

Кафедра информационно-вычислительных систем

Лекции для студентов заочного отделения

Имитационное моделирование экономических процессов

Автор-составитель доц. Еськова О.И.

Гомель 2007



Тема 1. Введение в имитационное моделирование

1.1 Имитационное моделирование как метод исследования сложных систем

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

Модели бывают материальные (физические) и математические. Среди математических моделей выделяют два типа: аналитические и имитационные (рис.1).

Рис 1. Классификация моделей

В аналитических моделях поведение сложной системы описывается в виде алгебраических, интегральных, дифференциальных и иных соотношений и логических условий. Наиболее простым примером аналитической модели является соотношение , где S - расстояние, v - скорость перемещения, t - время.

Аналитическая модель требует введения ряда упрощений. Часто такое упрощение получается слишком грубым приближением действительности и результаты не могут быть применены на практике. Например, та же формула

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

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

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

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

К достоинствам имитационного моделирования можно отнести:

1) свободу от каких-либо ограничений на класс решаемых задач;

2) наглядность;

3) возможность исследования системы на различных уровнях детализации;

4) возможность контроля над характеристиками системы в динамике.

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

дороговизна;

большой расход машинного времени;

результаты исследования обладают меньшей степенью общности по сравнению с аналитическими моделями;

не существует надежных методов оценки адекватности имитационной модели.

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

в случаях “безысходности”, когда сложность ситуации превосходит возможности аналитических методов;

если не существует четкой постановки задачи исследования и идет процесс познания объекта моделирования (модель служит средством изучения явления);

когда необходимо контролировать протекание процессов в системе путем замедления или ускорения явлений в ходе имитации;

при подготовке специалистов и приобретении ими навыков в эксплуатации новой техники.

Метод имитационного моделирования разрабатывался прежде всего для исследования систем массового обслуживания (систем с очередями). Об этом свидетельствует содержание первой отечественной монографии по моделированию: Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний и его реализация на электронных цифровых машинах. - М.:Наука, 1962., а также книга признанного классика GPSS Томаса Шрайбера: Моделирование на GPSS, 1980г.

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

1957 - Робинсон - об иерархической системе складов нефтепродуктов;

1961 - Берман - о перераспределении запасов;

1964 - Джислер - о снабжении авиационных баз.

1.2 Этапы имитационного моделирования

Трудоемкость имитационного моделирования делает особо важными вопросы технологии и организации работ. По оценкам специалистов США, разработка даже простых моделей оценивается в 5-6 человеко-месяцев (30 тыс. долларов), а сложных - на два порядка больше

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

1) Описание системы и разработка концептуальной модели.

2) Подготовка данных.

3) Разработка моделирующего алгоритма и построение имитационной модели.

4) Оценка адекватности.

5) Планирование экспериментов.

6) Планирование прогонов.

7) Машинный эксперимент.

8) Анализ и интерпретация результатов.

9) Принятие решений относительно исследуемого объекта.

10) Документирование.

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

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

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

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

Оценка адекватности модели заключается в проверке:

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

согласия постулируемых законов распределения с первичными данными;

синтаксической корректности программы моделирования;

соответствия результатов имитационного моделирования и известного аналитического решения (при условиях существования этого решения);

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

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

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

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

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

Этапы 7-9 в дополнительных пояснениях не нуждаются.

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



1.3 Программное обеспечение имитационного моделирования

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

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

Рис.2. Классификация ПО имитационного моделирования

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

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

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

генераторы случайных чисел;

продвижение модельного времени;

добавление и удаление записей из списка событий;

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

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

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

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

Исторически системы имитационного моделирования разделились на два основных типа: языки имитационного моделирования и проблемно - ориентированные системы моделирования.

Языки моделирования по своей природе универсальны, они предполагают написание кода модели. Хотя некоторые языки могут быть ориентированы на решение конкретного вида задач (например, моделирование СМО), но при этом спектр решаемых задач достаточно широк.

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

Многообразие систем имитационного моделирования (сейчас их известно более 500) вызвано применением имитационного моделирования в различных предметных областях, ориентацией на различные типы систем (дискретные или непрерывные), использованием различных типов компьютеров и способов имитации.



Тема 2. Основные понятия имитационного моделирования

2.1 Пример моделируемой системы

Основные понятия моделирования будем рассматривать на примере простой системы массового обслуживания с одним обслуживающим устройством и одной очередью. Таким обслуживающим устройством может быть продавец в маленьком магазине, билетер в театральной кассе, кладовщик на складе или центральный процессор в вычислительной системе. В литературе обслуживающее устройство может называться также прибором или каналом обслуживания. Пусть для определенности мы будем рассматривать парикмахерскую с одним креслом. Обслуживающим устройством является парикмахер. Клиенты приходят в парикмахерскую в случайные моменты времени, ждут своей очереди на обслуживание (если в этом возникает необходимость). Их обслуживают по принципу “первый пришел - первым обслужен”. После этого они уходят. Схематично структура этой системы показана на рис.3.

Рис.3 Структура моделируемой системы.

Будем предполагать также, что интервал времени между прибывающими в парикмахерскую клиентами есть случайная величина, имеющая равномерный закон распределения от a до b, и принимающая только целые значения. (В современной версии языка GPSS ограничения целочисленности нет, но мы примем это пока для простоты). Обычно равномерное распределение задается средним значением () и размахом, т.е. половиной интервала (). Например, распределение от 12 до 24 запишется как 186. Такая запись означает, что случайная величина принимает значения 12, 13, 14, 15, …, 24 с равной вероятностью. Поскольку всего имеется 13 целых значений от 12 до 24, вероятность каждого из них равна 1/13.

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

Время обслуживания клиента парикмахером есть также равномерно распределенная случайная величина. Например, если время обслуживания может принимать значения от 12 до 20 с, то такое распределение будет представлено как 164.

Целью моделирования является определение ряда статистических величин, таких как:

Число клиентов, обслуженных за данный промежуток времени (например, за рабочий день).

Число клиентов, которые попали на обслуживание сразу же по прибытии (им не пришлось ожидать в очереди).

Среднее время пребывания клиента в очереди.

Средняя длина очереди.

Максимальная длина очереди.

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



2.2 События и таймер модельного времени

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

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

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

Следует четко понимать отличие времени моделирования и модельного времени. Модельное время - это значение переменной “таймер модельного времени”, которое является образом реального времени моделируемой системы. А время моделирования - это время, затраченное компьютером на выполнение имитационного эксперимента - “прогонов” модели. Очевидно, что время моделирования зависит не от того, какой реальный интервал времени имитируется, а от того, сколько событий происходит в системе.

Все события можно разделить на две категории: основные и вспомогательные.

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

Вспомогательными называются события, время возникновения которых невозможно запланировать заранее. Они являются следствием основных и происходят в те же моменты времени, что и основные события. Примером вспомогательного события является поступление клиента на обслуживание. Оно возникает, если ему непосредственно предшествует основное событие. Например, если возникло основное событие “приход клиента” и парикмахер свободен, то возникает и вспомогательное событие “поступление клиента на обслуживание”. Или если возникло основное событие “окончание обслуживания” и имеются клиенты, ожидающие в очереди, тогда также происходит вспомогательное событие “поступление клиента на обслуживание”.

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

2.3 Механизмы продвижения времени

Существует два основных подхода к продвижению модельного времени: продвижение времени от события к событию (принцип x) и продвижение времени с постоянным шагом (принцип t).

Согласно принципу t таймер модельного времени всегда продвигается точно на t единиц времени (для какого-то выбранного заранее значения t). После каждого обновления таймера производится проверка с целью определить, произошли ли какие-либо события в течение предыдущего интервала времени. Если они были, то упрощенно считается, что все они произошли в конце интервала. Состояние системы соответствующим образом меняется. (рис.4) На этом рисунке ei - это действительное время возникновения события.

Рис.4. Продвижение времени с постоянным шагом

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

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

Рис.5. Продвижение времени от события к событию

2.4 Организация продвижения времени в системе GPSS для моделируемого примера

Для организации продвижения времени в системе GPSS World принят принцип x. Поскольку вспомогательные события происходят в те же моменты времени, что и основные, достаточно предусмотреть изменение таймера модельного времени в моменты прихода клиента в парикмахерскую и окончания обслуживания очередного клиента. Моделирующий алгоритм GPSS после поступления очередного клиента в парикмахерскую планирует приход следующего клиента, разыгрывая случайное число в соответствие с заданным распределением. Это значение можно интерпретировать как величину интервала времени, которое должно пройти прежде, чем появится следующий клиент. Тогда время появления следующего клиента может быть рассчитано как сумма текущего значения таймера модельного времени и разыгранного значения интервала (см. рис.6.).

Рис.6. Временная диаграмма планирования прихода очередного клиента.

Обслуживание клиента имитируется задержкой на время обслуживания. Окончание обслуживания планируется в тот момент, когда клиент поступает на обслуживание (садится в кресло к парикмахеру). Это делается аналогично процедуре планирования прихода следующего клиента (см. рис.7.).

Рис.7. Временная диаграмма планирования завершения обслуживания клиента.

Пусть, например, разыгранные значения интервалов времени между приходами клиентов составляют:

14, 13, 17, 15,…;

а разыгранные значения времени обслуживания клиента составляют

18, 12, 14,…

Временная диаграмма изменения состояний системы имеет следующий вид (рис. 8)..

Рис.8. Временная диаграмма изменения состояний моделируемой системы

На этой диаграмме ось t1 показывает моменты поступления клиентов в парикмахерскую, а ось t2 показывает обслуживание клиентов парикмахером. Поскольку на нее пунктиром спроектированы моменты поступления клиентов, она фактически показывает все моменты времени, в которые в системе происходят какие-либо события. Таким образом, из этой диаграммы очевидно, что таймер модельного времени будет получать последовательно следующие значения: 14, 27, 32, 44, 58, 59,… В таблице 1. перечислены события, который должны быть промоделированы в эти моменты времени

Таблица 1. События в парикмахерской с одним парикмахером

Значение таймера модельного времени	События, происходящие в этот момент времени
14	Приход первого клиента, поступление его на обслуживание
27	Приход второго клиента
32	Окончание обслуживания первого клиента, поступление второго клиента на обслуживание
44	Окончание обслуживания второго клиента, приход третьего клиента, поступление третьего клиента на обслуживание
58	Окончание обслуживания третьего клиента
59	Приход четвертого клиента, поступление его на обслуживание.



Тема 3. Система моделирования GPSS World

3.1 Общая характеристика системы GPSS World

Система GPSS (General Purpose Simulating System=Общецелевая система моделирования) предназначена для разработки и использования имитационных моделей дискретных сложных систем. Она наиболее подходит для моделирования систем массового обслуживания. Впервые созданная Джеффри Гордоном в фирме IBM в начале 1960-х годов, система GPSS является самым популярным в мире инструментом имитации и являет редкий пример долгожительства в мире программного обеспечения. Тем, кто заинтересуется развитием этой системы и использованием ее в России и других странах бывшего СССР, можно рекомендовать сайт www.GPSS.ru, который поддерживается фирмой Элина - Сервис.

Будем рассматривать современную версию языка GPSS и систему GPSS World, разработанную фирмой Minuteman Software. Студенческую версию этой системы можно бесплатно скачать с сайта фирмы Minuteman www.minutemansoftware.com Она имеет стандартный оконный интерфейс и средства для реализации всех этапов имитационного моделирования на языке GPSS:

Текстовый редактор и встроенные шаблоны блоков для ввода модели;

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

Средства автоматического сбора статистических данных;

Средства отладки модели и контроля динамики процесса имитации;

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



3.2 Объекты языка GPSS

Выделяют четыре основных категории объектов GPSS (таблица 2).

Таблица 2. Объекты языка GPSS

Категория объекта	Тип объекта	Мнемоническое обозначение
Динамическая	Транзакт	-
Статическая, или оборудование	Устройство	F
	Память	S
	Ключ	L
Статистическая	Очередь	Q
	Таблица	T
Операционная	Блок	-

Динамическая категория объектов представлена одним типом - транзактом. Транзакт имитирует единицу исследуемого потока запросов на обслуживание. Например, транзакт может представлять клиента, пришедшего в парикмахерскую или магазин, деталь, подлежащую обработке на станке, автомобиль в модели транспортной системы, задание пользователя в вычислительной системе и т.д. Транзакт во многом аналогичен заявке в системе массового обслуживания (СМО), но это понятие более широкое и сложное. Таким образом, транзакт - это динамический (т.е. движущийся) элемент GPSS-модели. Работа модели заключается в перемещении транзактов от одного операционного блока к другому. Именно транзакт, двигаясь по модели, является инициатором смены состояний моделируемой системы. С каждым транзактом связан ряд параметров. Например, транзакту может быть присвоен приоритет, который определяет порядок обслуживания его в очереди. Транзакты с более высоким приоритетом выбираются на обслуживание в первую очередь. Или, например, если транзакт имитирует собой судно, параметром может быть количество груза, подлежащего разгрузке. Это значение может быть использовано для определения времени разгрузки у причала порта.

К статической категории (оборудованию) относятся устройства, памяти и ключи. Устройства (FACILITY) используются для моделирования ресурса, который в каждый момент времени может быть занят только одним транзактом (одноканальная СМО). Например, кассир, парикмахер или продавец, если он один обслуживает клиентов; центральный процессор в вычислительной системе, кладовщик на складе и т.п. Памяти (STORAGE) представляют оборудование, которое может использоваться несколькими транзактами одновременно (многоканальные СМО). Например, запоминающее устройство вычислительной системы, стоянка автомобилей с ограниченным числом мест, несколько причалов в порту и т.д. Логические ключи (SWITCH) служат для блокировки или изменения маршрута движения транзактов. Они могут быть использованы в модели, например, для изображения светофора или переключателя.

Статистические объекты (очереди и таблицы) предназначены для сбора статистических данных в различных точках модели и представления их в виде стандартных показателей. Очередь (QUEUE) - это объект, предназначенный для сбора статистики по ожидающим обслуживания транзактам (среднее время ожидания, максимальная длина очереди и т.д.). Объект “очередь” не влияет на создание очереди транзактов, а лишь служит для сбора статистики по тем очередям, которые нас интересуют. Таблица (TABLE) используется для сбора статистической информации в виде эмпирических функций распределения случайных величин, получаемых в ходе моделирования.

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

Блоки относятся к категории операционных объектов и задают логику функционирования моделируемого процесса или системы, определяют пути движения транзактов между объектами категории оборудования. В общем случае модель представляет собой несколько отдельных сегментов, каждый из которых состоит из последовательности блоков и определяет путь движения некоторого типа транзактов. Сегмент обычно начинается блоком GENERATE и может заканчиваться блоком TERMINATE. Все события в моделируемой системе происходят в результате входа транзактов в блоки и выполнения блоками своих функций. Основные функции блоков следующие:

создание (генерация) и уничтожение транзактов;

задержка транзакта на некоторый интервал времени;

изменение маршрута движения транзактов;

изменение числовых атрибутов объектов.

Каждому блоку соответствует оператор языка GPSS. Кроме того, программа модели может быть представлена в виде блок-схемы, на которой каждому блоку соответствует характерная фигура.

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

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

транзакт входит в блок, функцией которого является удаление транзакта из модели;

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

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

Каждый блок в модели имеет номер, который присваивается ему автоматически, согласно месту его расположения в модели. Кроме того, блок может иметь символическое имя (метку), которое используется для ссылки на этот блок при передаче управления. Блок может иметь до 8 операндов, уточняющих его действие. Для удобства записи обычно операнды обозначаются символами A, B, C, …, H. Если операнды блока в явном виде не заданы, интерпретатор GPSS полагает их значение по умолчанию.

Кроме операторов блоков, разработчик модели может использовать еще два вида операторов: операторы описания объектов и управляющие операторы. Операторы описания позволяют определить переменную, функцию, описать емкость памяти (количество каналов многоканальной СМО), параметры таблицы и пр. Управляющие операторы позволяют задать условия моделирования, такие как продолжительность моделирования, число прогонов модели, порядок и условия сбора статистики. В системе GPSS World управляющие операторы можно как вносить в текст самой модели, так и задавать через командное меню системы.

3.3 Простейшие операторы GPSS

3.3.1 Введение транзактов в модель

Для ввода транзактов в модель используется блок GENERATE (Создать). Он создает (генерирует) транзакты в модели согласно заданному закону распределения интервала времени между их поступлением. Этот блок может иметь 5 операндов, т.е. имеет вид:

GENERATE A,B,C,D,E

Операнды A,B,…,E указывают следующие характеристики входного потока (в скобках значение по умолчанию):

A - средний интервал времени между поступлением транзактов (0);

B - половина поля допуска (размах) интервала равномерного распределения (0);

C - время создание первого транзакта (0);

D - ограничитель количества создаваемых транзактов (бесконечность);

E - приоритет создаваемых транзактов (0). В GPSS возможно всего 128 уровней приоритета, они задаются числами от 0 до 127. Чем больше значение приоритета, тем больше преимуществ получает при продвижении по модели транзакт;

На начальном этапе будем рассматривать только равномерное распределение интервалов между транзактами. Для задания других видов распределений нужно использовать специальные функции.

Примеры:

GENERATE 5,3

Генерируются транзакты с равномерным распределением интервала поступления 53. Планирование прихода первого транзакта происходит в момент времени, равный 0, путем розыгрыша случайного целочисленного значения от 2 до 8.

GENERATE 10

Поскольку размах (операнд B) по умолчанию равен 0, получаем детерминированный (определенный точно) интервал времени между транзактами, равный 10. Первый транзакт приходит в момент времени 10, второй - в момент 20 и т.д.

GENERATE 3,3,10,5

Первый транзакт приходит в момент времени 10. После этого интервалы прибытия находят из равномерного распределения 33, т.е. от 0 до 6 включительно. После прихода пяти транзактов работа блока заканчивается.

GENERATE 8,1,,,4

Транзакты создаются с интервалом 81. Приход первого транзакта рассчитывается в момент времени 0. Количество транзактов не ограничено. (Пропущены операнды С и D). Все создаваемые транзакты имеют приоритет, равный 4.

В системе GPSS World предполагается, что приходящий “извне” транзакт входит в блок GENERATE, и в момент его входа в этот блок планируется время прибытия следующего транзакта. Приход самого первого транзакта планируется до начала процесса моделирования.

3.3.2 Удаление транзактов из модели

Транзакты удаляются из модели (уничтожаются), попадая в блок TERMINATE. Блоки TERMINATE (Уничтожить) всегда позволяют выйти из модели всем транзактам, которые пытаются это сделать. Блок TERMINATE может иметь один операнд, т.е. имеет вид

TERMINATE A

Операнд A (по умолчанию 0) указывает число, на которое уменьшается содержимое счетчика числа завершений.

Счетчик числа завершений - это переменная, которая используется для управления окончанием процесса моделирования. Счетчик завершений в модели только один, хотя блоков TERMINATE может быть несколько. При достижении значения счетчика завершений, равного 0, моделирование завершается. Начальное значение счетчика завершений задается с помощью управляющего оператора START (Начать моделирование), имеющего следующий формат:

START A,B

Операнд A - начальное значение счетчика завершений (по умолчанию 0).

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

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

Счетчик завершений используется для того, чтобы:

ограничить число транзактов, “прогоняемых” в модели;

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

Например, мы хотим закончить моделирование, когда 100-ый транзакт покинет модель. Тогда можно задать в операторе TERMINATE значение операнда A, равное 1:

TERMINATE 1

А начать моделирование командой (или оператором)

START 100

Другая ситуация, если мы хотим закончить моделирование по истечении некоторого времени. Например, мы моделируем работу парикмахерской в течение рабочего дня (8 ч), а единицей времени является одна минута. Тогда в момент времени, равный 480 минут, моделирование должно быть закончено, независимо от того, сколько клиентов прошло через нее, и сколько ней сейчас находятся. Для этого в модель вводится дополнительный сегмент (соответствующий таймеру времени) вида:

GENERATE 480

TERMINATE 1

При этом начальное значение счетчика завершений командой START должно быть задано равное 1, а все другие блоки TERMINATE (уничтожающие транзактов - клиентов) не должны содержать параметров. Тогда в момент модельного времени, равный 480, будет сгенерирован транзакт-таймер и сразу же уничтожен. При этом счетчик завершений станет равен 0, и моделирование прекратится.

3.3.3 Управление устройствами

Объект типа “устройство” является аналогом канала обслуживания в СМО. В каждый момент времени он может быть занят только одним транзактом. Если устройство занято, транзакты ожидают в очереди его освобождения.

Занятие устройства транзактом выполняется блоком SEIZE (Занять) формата:

SEIZE A

Операнд A - символическое или числовое имя устройства. Правила записи всех символических имен в GPSS (будь то имя устройства, имя очереди, имя переменной или метка в модели) следующие:

Первые три символа должны быть буквами.

Имя не должно быть ключевым словом системы GPSS.

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

Вход транзакта в блок SEIZE моделирует занятие устройства. Если транзакт пытается войти в этот блок, то производятся следующие действия:

Проверяется состояние устройства.

Если устройство свободно, то состояние устройства изменяется на “занято”, а транзакту разрешается дальнейшее продвижение.

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

Освобождение устройства выполняется блоком RELEASE (Освободить) формата:

RELEASE A

Операнд A - символическое или числовое имя устройства.

Этот блок разрешает вход и выход транзакту в любом случае. Когда транзакт входит в этот блок, состояние устройства изменяется на “свободно”. Попытка входа в блок RELEASE транзакта, ранее не прошедшего блок SEIZE с тем же именем в поле А, что и в блоке RELEASE, приводит к прекращению моделирования из-за нарушения логики процесса.

Если разработчик модели использует пару блоков SEIZE - RELEASE с одним и тем же именем устройства, то тем самым он сообщает системе о наличии такого устройства и необходимости регистрировать статистические данные по нему. По окончании моделирования в отчете выводятся следующие статистические характеристики устройства:

1) Коэффициент использования: доля времени, в течение которого устройство было занято обслуживанием, в общем модельном времени. Рассчитывается как отношение времени занятости устройства к общему модельному времени, в течении которого имитировалась система. В отчете имеет имя (UTIL.)

2) Среднее время обслуживания. В отчете - (AVE.TIME)

3) Количество обслуживаний (число транзактов, входивших в блок SEIZE). Учитывается в том числе и тот транзакт, который в момент окончания моделирования продолжает обслуживание). В отчете - (ENTRIES)

3.3.4 Задержка транзактов во времени

Моделирования обслуживания на транзакта на устройстве выполняется задержкой этого транзакта на случайное (в общем случае) время обслуживания. Реализуется это в GPSS с помощью блока ADVANCE (Задержать) формата:

ADVANCE A,B

A - среднее значение времени задержки (0);

B - половина поля допуска (размах) интервала времени задержки (0).

Блок ADVANCE никогда не препятствует входу транзакта. Любое число транзактов может находится в этом блоке одновременно. Когда транзакт попадает в этот блок, разыгрывается случайное значение времени пребывания в нем, согласно операндам A и B. Далее транзакт будет находиться в блоке ADVANCE до истечения этого времени. Как и в случае блока GENERATE, для реализации других видов распределений, отличных от равномерного, нужно использовать в качестве аргументов специальные функции.

Примеры.

ADVANCE 10,2

Время задержки распределено равномерно в интервале 102.

ADVANCE 100

Время задержки любого транзакта равно 100 (неслучайное значение, т.к. параметр B по умолчанию равен 0).

SEIZE MASTER

ADVANCE 16,4

RELEASE MASTER

Классический пример использования цепочки SEIZE-ADVANCE-RELEASE для моделирования работы устройства (парикмахера из нашего примера). Транзакт, двигающийся по этой цепочке, займет устройство с символическим именем MASTER, задержится там на 164 единицы времени, и затем покинет его. Когда данный транзакт войдет в блок RELEASE, и отработает процедура этого блока, следующий транзакт сможет использовать устройство MASTER.

3.3.5 Сбор статистики при ожидании в очереди

Как уже отмечалось выше, если устройство занято каким-либо транзактом, то блок SEIZE запрещает вход всем остальным транзактам. Эти транзакты, которые тоже хотели бы занять устройство, остаются в предыдущем блоке. Там они могут накапливаться, образуя очередь. Дисциплина обслуживания этой очереди, принятая по умолчанию в GPSS, - это “первым пришел - первым обслужен в пределах одного класса приоритетов”. Таким образом, после освобождения устройства, из очереди выбирается тот транзакт, который имеет больший приоритет, а среди транзактов одинакового приоритета - тот, который пришел ранее. Очереди в системе образуются автоматически, в результате того, что транзакты вынуждены ожидать освобождения устройства. По некоторым очередям разработчик модели может собирать статистику моделирования, а именно:

Максимальное число транзактов в очереди. В отчете (MAX).

Среднее число транзактов в очереди. В отчете (AVE.CONT).

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

Число транзактов, которые были зарегистрированы, но не потратили никакого времени на ожидание в очереди (нулевые входы) (ENTRY(0)).

Среднее время ожидания в очереди (с учетом и без учета нулевых входов) (AVE.TIME и AVE (-0)).

Для того, чтобы организовать сбор такой статистики (а не для того, чтобы организовать очередь), служат блоки QUEUE (Стать в очередь) и DEPART (Покинуть очередь).

QUEUE A,B DEPART A,B

A - Символическое имя или номер очереди, к которой нужно присоединиться или покинуть (по умолчанию ошибка);

B - число занимаемых или освобождаемых мест в очереди (по умолчанию 1).

Блоки QUEUE и DEPART всегда пропускают транзакт. При входе транзакта в блок QUEUE моделирующая программа GPSS выполняет действия, фиксирующие вхождение транзакта в очередь (увеличение счетчика входов, запоминание времени постановки транзакта в очередь и т.д.). Когда же транзакт проходит блок DEPART, выполняются действия, регистрирующие выход транзакта из очереди и расчет соответствующих характеристик этого транзакта. Следует отметить, что моделирующий алгоритм GPSS устроен так, что среднее время пребывания в очереди рассчитывается с учетом и тех транзактов, которые в момент окончания моделирования находятся в очереди. Поэтому среднее время пребывания в очереди получается несколько заниженным, т.к. транзакты, находящиеся в очереди, должны были бы оставаться в ней еще некоторое время. Статистику по очередям, для которых организован сбор статистики блоками QUEUE - DEPART, пользователь получает в отчете по окончанию моделирования.

В системе GPSS транзакт может присутствовать одновременно не более, чем в пяти очередях. Ситуация, в которой может потребоваться присутствие транзакта в нескольких очередях одновременно, может возникнуть, например, при моделировании поведения покупателя в магазине, который занимает очереди сразу в несколько отделов.

В таблице 3 показаны элементы блок-схемы, соответствующие перечисленным выше блокам.

Таблица 3. Фигуры блок-схемы, соответствующие операторам блоков

GENERATE A,B
TERMINATE A
SEIZE A
RELEASE A
	ADVANCE A,B

Размещено на http://www.allbest.ru/

QUEUE A
DEPART A



3.3.6 Модель работы парикмахерской

Рассмотрим теперь модель парикмахерской с одним креслом (рис.9). Блок-схема этой модели приведена на рис.10.

*Модель работы парикмахерской

* Сегмент клиентов

GENERATE 18,6; Приход клиентов(1)

QUEUE QMASTER; Присоединение к очереди (2)

SEIZE MASTER; Переход в кресло парикмахера (3)

DEPART QMASTER; Уход из очереди(4)

ADVANCE 16,4; Обслуживание у парикмахера (5)

RELEASE MASTER; Освобождение парикмахера (6)

TERMINATE; Уход из парикмахерской(7)

* Сегмент таймера

GENERATE 480;Приход транзакта-таймера (8)

TERMINATE 1; Завершение прогона (9)

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



Рис.10. Блок-схема модели парикмахерской

Для того, чтобы начать моделирование, должна быть подана команда START 1 (или включена в текст модели). Эта команда дает начальное значение, равное 1, счетчику числа завершений, и начинает процесс моделирования.

Итак, транзакты создаются блоком GENERATE (1) согласно равномерному распределению с интервалом 186. Транзакт моделирует клиента, приходящего в парикмахерскую. Созданный транзакт продвигается далее в блок (2), где регистрируется его присоединение к очереди QMASTER. Затем транзакт пытается занять устройство MASTER, имитирующее парикмахера (блок 3). Если ему это удается, то состояние устройства меняется на “занято”, а транзакт продвигается в блок (4), регистрирующий его уход из очереди QMASTER. В случае неудачи транзакт остается в блоке (2) и ожидает в очереди освобождения устройства. После регистрации выхода из очереди, транзакт поступает в блок (5), где моделируется обслуживание клиента парикмахером задержкой на время 164. Затем транзакт поступает на блок (6), который изменяет состояние прибора на “свободно”, и далее проходит в блок (7), где уничтожается без изменения счетчика завершений. Второй сегмент модели состоит из двух блоков (8) и (9). Блок (8) генерирует транзакт-таймер, который приходит в момент модельного времени, равный 480, и символизирует звонок к окончанию рабочего дня. Этот транзакт тут же уничтожается блоком (9), при этом значение счетчика завершений уменьшается на 1 и становится равным 0. Моделирование прекращается.

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

Таким образом, в модели неявным образом объявлено устройство с именем MASTER. Транзакты, ожидающие в очереди к этому устройству, скапливаются в блоке (2) QUEUE QMASTER. По этой очереди регистрируется статистика под символическим именем QMASTER.

3.3.7 Изменение маршрутов движения транзактов

Для изменения маршрута транзактов в модели применяются блоки TRANSFER, GATE, TEST, LOOP. Транзакты, входящие в эти блоки, далее продвигаются не к следующему блоку, а к блокам, адрес которых определяется либо указывается в операторах. Ниже рассматривается только блок TRANSFER.

Блок TRANSFER может иметь четыре операнда (A, B, C, D). Существуют девять режимов использования этого блока, которые определяются по значению операнда A. Рассмотрим основные из них:

1). Безусловный переход

TRANSFER ,B

здесь B - имя (адрес) блока, к которому направляется транзакт (операнд A отсутствует).

Пример.

TRANSFER ,CPU2

Транзакт направляется к блоку с именем CPU2.

2). Условный переход с одним альтернативным адресом:

TRANSFER BOTH,B,C

где BOTH -тип режима;

B - имя (адрес) блока, к которому направляется транзакт (основной адрес). По умолчанию - следующий блок;

C - альтернативный адрес, куда направляется транзакт при невозможности войти в блок с адресом B.

Если ни один из блоков, указанных в операторе TRANSFER, не может принять транзакт, то он остается в блоке TRANSFER, и в дальнейшем моделирующая система будет делать попытки продвинуть этот транзакт при каждом изменении модельного времени

Примеры.

TRANSFER BOTH,KASS1,KASS2

TRANSFER BOTH,,TWO

В первом операторе транзакт первоначально направляется к блоку с именем (меткой) KASS1. При невозможности войти в этот блок транзакт направляется к блоку с именем KASS2. Во втором операторе транзакт делает попытку войти в следующий блок (значение параметра B по умолчанию), а если ему это не удается, он направляется к блоку с именем TWO.

3). Статистический переход (переход с заданной вероятностью):

TRANSFER A,B,C

Здесь A - вероятность перехода транзакта по адресу С;

В - альтернативный адрес.

Если операнд A представляет собой целое число, то оно трактуется как количество тысячных долей вероятности и преобразуется в вероятность автоматически.

Примеры.

TRANSFER .370,THIS,THAT

С вероятностью 0,37 транзакт перейдет к блоку THAT, а с вероятностью 0,63 - к блоку THIS.

TRANSFER 750,,NEW_PLACE

С вероятностью 0,75 транзакт передается на блок NEW_PLACE, а с вероятностью 0,25 - на следующий блок.

Если транзакт не принимает ни один из блоков, куда делалась попытка его протолкнуть, то он остается в блоке TRANSFER. В этом случае моделирующая программа повторяет попытки переправить транзакт пи каждом изменении модельного времени. На блок-схеме блок TRANSFER изображается в виде ромба (см. рис. 11 и 12).

Рис.11. Блок TRANSFER в режиме безусловной передачи

Рис.12. Блок TRANSFER в режиме статистического перехода или перехода с одним альтернативным адресом

3.3.8 Моделирование многоканальных устройств

Многоканальному устройству в системе GPSS соответствует объект память (символическое обозначение S). Память может выполнять параллельное обслуживание нескольких транзактов. При этом необходимо, чтобы такое обслуживание было однородным, т.е. обладало некоторыми общими свойствами. Например, среднее время обслуживания и разброс этого времени для кассиров банка, одновременно обслуживающих клиентов, должно быть одинаковым. Если же они обслуживают с разной скоростью, то для их имитации следует использовать несколько параллельно расположенных устройств.

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

NameSTORAGEA

Где Name - имя (номер) памяти; A - емкость памяти.

Например,

1 STORAGE 100; память с номером 1 емкости 100

PAM STORAGE 10; память именем PAM емкости 10

Операторы описания памятей обычно помещаются в начале программы перед первым оператором GENERATE.

Изменение состояния памяти в модели осуществляется с помощью операторов занятия и освобождения памяти ENTER и LEAVE :

ENTERA,B

LEAVEA,B

Где A - имя (номер памяти);

B - число единиц памяти, занимаемых (освобождаемых) транзактом при входе в блоки (по умолчанию 1).

Примером, когда один транзакт может потребовать несколько единиц памяти, является моделирование причала в порту. В зависимости от размера корабль может потребовать использование нескольких причалов. Транзакт не может войти в блок ENTER, если нет достаточного количества свободных единиц памяти.

На блок-схеме блоки ENTER и LEAVE изображаются, как показано на рис. 13.

Рис13. Блоки ENTER (ВОЙТИ) и LEAVE (ВЫЙТИ).

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

Рис.14. Многоканальная система массового обслуживания с одной очередью и приоритетами

В конце моделирования по каждой памяти в отчете распечатывается статистика: количество свободных каналов памяти на момент окончания моделирования (REM.),

минимальное и максимальное количество одновременно занятых каналов (MIN. и MAX.),

счетчик входов (ENTRIES),

среднее число занятых каналов (AVE.C.),

коэффициент использования памяти (UTIL.).

Тема 4. Генерация случайных чисел

4.1 Общие принципы генерации случайных величин

Имитационное моделирование требует использования большого количества случайных величин. Например, в моделях систем массового обслуживания требуется получение случайного интервала времени между поступлениями заявок, а также случайное время их обслуживания. Кроме того, случайные числа могут быть нужны для определения маршрута движения транзакта (блок TRANSFER в режиме статистической передачи), розыгрыша объема покупки или спроса на товар в моделях управления запасами, и т.д. Моделирование этих случайных величин может быть выполнено на основе наблюдений за реальной системой. Результаты наблюдений могут быть использованы в модели либо непосредственно (т.е. в “сыром виде”), либо через генераторы случайных чисел, воспроизводящие их статистические аналоги.