«А. Г. Варжапетян ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ НА GPSS/H Учебное пособие Санкт Петербург 2007 УДК 519.682 ББК 22.18 В18 Рецензенты: кафедра морских информационных технологий Российского государственного ...»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

САНКТ ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

А. Г. Варжапетян

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

НА GPSS/H

Учебное пособие

Санкт Петербург 2007 УДК 519.682 ББК 22.18 В18 Рецензенты:

кафедра морских информационных технологий Российского государственного гидрометеорологического университета;

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

В18 Имитационное моделирование на GPSS/H: учебное пособие / А. Г. Варжапетян; ГУАП. — СПб., 2007. — 384 с.: ил.

ISBN 5 8088 В учебном пособии рассматриваются вопросы построения, логи ки действия и начал программирования на современной версии язы ка имитационного моделирования GPSS/H, который повышает эф фективность первой версии Д. Гордона.

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

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

УДК 519. ББК 22. © ГУАП, ISBN 5 8088 0228 8 © А. Г. Варжапетян,

СОДЕРЖАНИЕ

Условные сокращения...................................... Предисловие.............................................. Часть Общие вопросы компьютерного моделирования................. Глава Представление о компьютерном моделировании............... § 1.1. Классификация моделей............................ § 1.2. Компьютерное моделирование........................ § 1.3. Место имитационных моделей в общей структуре програм много обеспечения....................................... § 1.4. Достоинства и недостатки имитационного моделирования § 1.5. Основные этапы и задачи, реализуемые при имитационном моделировании......................................... § 1.6. Оценка адекватности имитационных моделей........... Глава Концептуальная модель для GPSS/H......................... § 2.1. Классификация математических моделей.............. § 2.2. Основные обозначения теории массового обслуживания... § 2.3. Некоторые аналитические модели системы массового об служивания............................................ 2.3.1. Распределение вероятностей длительности интервалов между заявками...................................... 2.3.2. Распределение вероятностей длительностей обслужива ния................................................. 2.3.3. Одноканальное обслуживание с пуассоновским входным потоком и экспоненциальным распределением длительностей 2.3.4. Многоканальное обслуживание с пуассоновским входным потоком и экспоненциальным распределением длительностей Глава § 3.3. Способы создания квазипараллелизма при имитационном § 3.5. Оценка качества базовых случайных величин, получаемых Часть Глава § 4.3. Основные правила работы с пакетом GPSS/H (студенческая Глава Принципы функционирования языка имитационного моделирова § 5.3. Правила окончания процесса имитационного моделирова 5.4.3*. Общие основы изменения флага состояния модели и Глава 6.2.1. Схема одноканального обслуживания без ухода Хакт из 6.2.2. Сбор дополнительной информации (использование оче 6.3.1. Многоканальное обслуживание групп идентичных серве 6.3.2. Перекрытие памятей и введение Хакт только при необ 6.3.5. Использование уровней приоритета для управления по § 6.4. Автоматизация процесса имитационного моделирования Глава Глава Статистические возможности языка имитационного моделирования § 8.1. Генерация случайных переменных с заданной функцией 8.1.1. Обоснование выбора функции распределения случайных 8.1.3. Получение случайных чисел с заданными функциями § 8.4. Выбор наилучшей альтернативы в Парето оптимальном Часть Расширение возможностей имитационного моделирования на языке имитационного моделирования GPSS/H....................... Глава § 9.2. Краткое описание программного продукта Proof Anima 9.2.1. Добавление анимации к моделированию с использова 10.1.1. Введение в SLX (Simulation Language with Extensibi

УСЛОВНЫЕ СОКРАЩЕНИЯ

АМП — амперпеременная БСВ — базовая случайная величина ВД — временная дискрета ВДв — время движения ВЭ — вычислительный эксперимент ГПС — гибкая производственная система ГСЧ — генератор случайных чисел ДО — дисциплина обслуживания ДСВ — дискретная случайная величина ЕВА — единица времени анимации ЖЦ — жизненный цикл ИН — идентификационный номер ИПС — индикатор перехода к сканированию ИС — индикатор состояния ИТ — информационные технологии КМ — компьютерное моделирование ЛМВ — локальное модельное время ММ — математическое моделирование МФ — модельный файл НОД — наибольший общий делитель ОБ — оператор блока ОВМ — обобщенный «будстреп» метод ОВО — оператор выходного отчета ОО — оператор описания ООП — объектно ориентированное программирование ОУ — оператор управления ПО — программное обеспечение ПП — программный пакет (продукт) ППП — пакет прикладных программ РР — равномерно распределенная случайная величина СБС — список будущих событий СЛА — стандартный логический атрибут СМО — система массового обслуживания СОБ — следующий оператор блока СП — список пользователя СС — счетчик свершений ССА — стандартный символьный атрибут СТС — список текущих событий СУ — система управления СУБД — система управления базами данных СЧА — стандартный числовой атрибут СЭ — случайный элемент ТОБ — текущий оператор блока УПМ — управляющая программа моделирования ФИС — флаг изменения состояния ЦКП — центральное композитное планирование ЯИМ — язык имитационного моделирования

ПРЕДИСЛОВИЕ

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

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

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

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

Методы менеджмента качества сложных систем не мыслятся сегодня без использования инструментов инжиниринга качества, таких как струк турирование или развертывание функции качества, робастное проектиро вание, система Махаланобиса—Тагути, метод шести сигм и т. д. Есте ственно, что ни один из этих методов не может не опираться на современ ное ПО.

Даже такое простое перечисление ключевых направлений современно го научно технического прогресса позволяет заключить, что исследова ние и разработка новых проектов невозможна без использования методов компьютерного моделирования. Мир КМ многогранен и охватывает спектр от моделирования простых систем и производственных ситуаций до ис следования взаимодействия социальных, экономических и природных си стем в их сложном переплетении и взаимодействии. Рассмотрению про блем КМ посвящен ряд публикаций [5, 6, 8, 9].

На протяжении ряда лет автор, работая в промышленности, занимался вопросами моделирования сложных систем управления [2, 3]. В данном учебном пособии автор ставит более скромную задачу — рассмотреть осо бенности языка имитационного моделирования (ЯИМ) GPSS/H. Зачастую упоминание об этом ЯИМ вызывает легкое отторжение, так как у всех возникает воспоминание о первой версии GPSS 1963 г. Однако рассматри ваемая здесь версия GPSS/H 1999 г. не только коренным образом отлича ется от ранних версий, но и имеет ряд уникальных черт, делающих ЯИМ приближенным к универсальным языкам программирования и открыва ющим ряд новых возможностей, весьма важных при исследовании систем массового обслуживания (СМО). Под разряд СМО подпадают многие зада чи из перечисленных направлений. Опыт преподавания ЯИМ в Санкт Пе тербургском государственном университете аэрокосмического приборо строения в рамках курсов «Исследование систем управления», «Автома тизированные системы научных исследований» и «Менеджмент качества»

показывает, что студенты и аспиранты не только осваивают идеи ЯИМ GPSS/H, но и успешно применяют их в своей практической инженерной и управленческой деятельности.

Прекрасно понимая, что проблема КМ весьма сложна и ее разные ас пекты требуют отдельных монографий, автор ограничился рассмотрени ем специфики и возможностей одного из ЯИМ, а именно GPSS/H. За рубе жом его описанию посвящено большое число публикаций, например [12– 15], а на русском языке написана только глава в монографии автора [4].

Тем не менее, ЯИМ заслуживает большего внимания и несомненно досто ин распространения не только для целей обучения студентов, но и для практического использования инженерами, менеджерами и научными ра ботниками.

Литературные источники легко могут быть пополнены с помощью по исковых систем Интернета по ключевому слову Simulation — GPSS/H.

Автор выражает искреннюю признательность профессору Мичиган ского университета США Томасу Шрайберу, творческие контакты с кото рым способствовали написанию этого учебного пособия, а также прези денту Wolverine Software Corp. Джеймсу Хенриксену, предоставившему в распоряжение автора ряд уникальных материалов.

Автор с сожалением констатирует, что в известных ему учебных заве дениях до сих пор пользуются первыми версиями ЯИМ GPSS, и надеется, что пособие будет способствовать продвижению новых идей.

Учебное пособие рассчитано на широкий круг читателей: так, исследо ватели смогут применять возможности ЯИМ для решения своих задач, преподаватели — использовать материалы пособия для лекций, а студен ты и аспиранты — для изучения общих идей имитационного моделирова ния.

Необходимость введения словаря, предваряющего основной текст, объясняется тем, что:

— в существующей научно технической литературе используются раз личные термины для определения одних и тех же или сходных понятий, связанных с КМ;

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

Определения, вошедшие в словарь, заимствованы из источников [4, 13] и ГОСТов.

Амперпеременная — переменная, введенная в GPSS/H и резко увели чивающая его вычислительную мощность. Название объясняется тем, что переменная обозначается знаком амперсанд — &.

Антитеза — значение случайного числа дополнительного потока, явля ющееся разностью между единицей и значением случайного числа основ ного потока.

Атрибут — стандартные числовые, символьные и логические харак теристики, а также характеристики встроенных функций.

Буфер (накопитель или память) — одна из единиц аппаратной катего рии, способная накапливать приходящие заявки.

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

Число реплик в прогоне зависит от заданной статистической точности или от времени, отведенного на прогон.

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

Заявка (в GPSS — транзакт) — динамический элемент, движущийся по модели от оператора к оператору блоков строго один в единицу вре мени.

Канал — путь прохождения заявок через систему массового обслужи вания (различают одноканальные и многоканальные СМО).

Компьютерное моделирование — расширение возможностей матема тического моделирования за счет использования последних достижений ИТ, внедряемых во все сферы человеческой деятельности.

Модель — отображение особенностей реальной системы путем созда ния концептуального или машинного описания.

Модуль — часть программы ИМ, включающая неисполняемый модуль описания, модуль исполнения и модуль управления.

Оператор — элемент ЯИМ, предназначенный для построения машин ной модели (различают операторы описания (compiler directives), опера торы блоков (blocks) и операторы управления (control statements)).

Операнд — числовое или символьное значение одной из характерис тик оператора любого вида.

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

Прибор (устройство) — одна из единиц аппаратной категории, осуще ствляющая обслуживание транзактов.

Приоритет — показатель значимости приходящего транзакта, являю щийся одним из его операндов.

Прогон — проведение вычислительного эксперимента с моделью, со стоящего из n реплик.

Процесс — совокупность событий, действий и связанных с ними времен ных отрезков, характеризующих функционирование системы или ее модели.

Список (последовательность) (в первоисточнике Chain — цепь) — пе речень транзактов, находящихся в одном из шести возможных списков:

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

Реплика — одна реализация вычислительного эксперимента или прогона.

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

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

Виды моделирования Физическое

GPSS PC

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

Первая часть «Общие вопросы компьютерного моделирования» содер жит три главы. Первая посвящена общим представлениям о классифика ции моделей, уточнению места компьютерного моделирования, содержа нию его отдельных разделов, уточнению схемы и порядка КМ. Во второй главе рассматриваются элементы теории массового обслуживания, являю щиеся основой для транзактного способа создания квазипараллелизма при ИМ. В третьей главе рассматриваются вопросы определения модельного времени, создания квазипараллелизма и особенности генерирования базо вых случайных величин (БСВ) с помощью генераторов случайных чисел.

Вторая часть «Язык имитационного моделирования GPSS/H» содержит пять глав. В четвертой и пятой главах уточняется место GPSS/H среди дру гих ЯИМ, проводится сравнительный анализ всех версий ЯИМ GPSS, рас сматриваются принципы построения и функционирования ЯИМ GPSS/H.

В первую очередь обращается внимание на внутреннюю организацию ЯИМ, что позволит более осознанно работать с пакетом. Опыт преподавания выя вил ряд моментов, наиболее трудных для восприятия студентами. К их числу относятся правила прекращения испытаний, организация непосле довательного прохождения транзактов, правила терминирования и некото рые другие. Шестая глава посвящена рассмотрению моделей одноканально го и многоканального обслуживания в пакетном режиме. Глава содержит ряд параграфов, посвященных различным аспектам ИМ (сбор дополнительной информации, автоматизации процесса ИМ, использование приоритета и т. п.). Седьмая глава посвящена работе с отладчиком (дебаггером) ЯИМ — рассмотрены особенности дебаггера и приведены примеры. В восьмой главе рассмотрены некоторые статистические задачи, посвященные использо ванию антитез, позволяющих сократить число реплик при одновремен ном уменьшении дисперсии, а также задача выбора наилучшего среди различных вариантов.

Третья часть содержит краткое описание новых программных пакетов (ПП), расширяющих возможности ЯИМ GPSS/H.

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

Разработчиком и распространителем ПП GPSS/H:

— профессиональной 32 разрядной версии, работающей под Windows 98, 2000, NT, XP;

— студенческой версии, работающей в эмуляции DOS или под любой оболочкой типа NC,VC, Far;

— пакета анимации движения транзактов Proof Animation;

— интегрированного пакета SLX (C + GPSS/H + специализированный язык) — является Wolverine Software Corporation 7617 Little River Tumpike, Suite Annandale, VA [email protected] Все реквизиты и прайс листы ПП можно найти на сайте корпорации.

ОБЩИЕ ВОПРОСЫ

КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ

ПРЕДСТАВЛЕНИЕ

О КОМПЬЮТЕРНОМ МОДЕЛИРОВАНИИ

Возможность представления моделью (лат. modulus — мера, об разец) природных явлений, процессов или объектов окружающего нас мира присуща человеку исследователю еще с ранних этапов раз вития общества. «Модель (по определению БСЭ) — образ (в том чис ле условный или мысленный) какого либо объекта или системы объектов, используемый при определенных условиях в качестве их “заместителя” или “представителя”.» Достаточно вспомнить хрус тальный небесный свод геоцентрической модели, модель атома и т. д.

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

Модель должна ответить на множество вопросов исследователя:

что будет, если …?; каковы размеры …?; насколько корректны упро щения …? и множество других.

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

Подчеркнем, что под информацией будем понимать не столько продукт человеческого разума, получаемый в процессе познания, сколько объективную философскую категорию, связывающую темп Рис. 1.1. Место имитационного моделирования в модельном пространстве процессов, происходящих в системе, с уровнем организации самой системы.

Информация через философскую категорию отражение связана с категорией материя [4]. Под отражением понимается свойство ма терии воспринимать и сохранять в своей структуре следы воздействия другой системы. По А. Урсулу, информация — отраженное разнооб разие реальности мира. Отсюда, чем полнее и разнообразнее модель динамической, нелинейной и неравновесной системы, тем более адек ватно она отображает реальную систему. Информация объективно присутствует всегда, даже в случае классической механики; так, при соударении двух тел второе получало информацию от первого, как ему двигаться. Правда, при этом вся информация сводилась к одной динамической силе и не давала ничего нового, поэтому и не бралась в расчет. Учет информации даже в простых случаях классической ди намики мог бы дать единую концепцию, объединяющую все разделы физики. Однако этот вопрос при всей его важности не имеет отноше ния к настоящему учебному пособию.

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

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

Ф — физическое (прямое) моделирование, Ф1 предусматривает использование в качестве модели саму систему (опытный образец), а Ф2 — другую систему со схожей физической природой (макет авто Рис. 1.2. Классификация методов моделирования мобиля, сооружения, плотины). Такой вид моделирования способ ствовал созданию теории подобия.

М — математическое моделирование (ММ), распадающееся на две большие группы М1 и М2.

М1 — аналитическое моделирование, которое можно разделить на М1.1 — явное аналитическое описание искомых характеристик системы на одном из языков математики (см. гл. 2); М1.2 — прибли женные численные методы, когда все объекты аппроксимируются числами или их комплектами в принятой числовой сетке, а резуль таты получаются в виде таблиц или графиков; М1.3 — качественные методы, когда изучаются свойства решений задач данного класса без нахождения самих решений. Зачастую эти методы реализуются с помощью экспертного оценивания. Такого вида методы широко ис пользуются в теории качества, квалиметрии, экономике, социоло гии и т. д.

М2 — компьютерное моделирование (см. § 1.2), когда математи ческая модель интерпретируется в программу для ЭВМ. Характерно, что с появления статьи Дж. Неймана и С. Улама в 1948 г. — первой работы по применению метода Монте Карло, многие специалисты продолжают называть КМ методами Монте Карло или статистиче ских испытаний. Это в принципе не верно, так как КМ разделилось на четыре направления [5, 9] (см. рис. 1.2).

М2.1 — методы Монте Карло или методы вычислительной мате матики, использующие методы М1.2 с учетом возможностей совре менных компьютеров. Этими методами можно вычислять любые, не берущиеся аналитическим путем, многократные интегралы, решать системы уравнений. Интересующимся методами вычислительной математики следует обратиться к многочисленной литературе.

М2.2 — методы ИМ (simulation), для которых характерно воспро изведение на ЭВМ процесса функционирования системы с сохранени ем его логической структуры и последовательности его протекания во времени, что позволяет путем многократного повторения набрать необходимые статистические данные и судить о состоянии объекта в различные моменты времени, оценивать выходные характеристики, выбирать оптимальное поведение или проводить сравнение альтер нативных вариантов. Основной акцент пособия делается на рассмот рение именно ИМ.

М2.3 — методы статистической обработки данных моделирова ния на основе методов планирования эксперимента. Имеется целый ряд монографий, посвященных этим вопросам, в том числе [1, 7].

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

— пакеты углубленного статистического анализа, написанные специалистами по статистике для таких же специалистов, с собствен ным языком, позволяющим программировать новые статистические процедуры (SAS, Statgraphics);

— пакеты базовой статистики, ориентированные на пользовате лей, не являющихся специалистами по статистическому анализу, и содержащие классические методы анализа с дружественным пользо вательским интерфейсом в виде многочисленных пояснений, приме ров и подсказок, среди них необходимо отметить прекрасный раздел по статистике в ППП MATLAB и ППП «Статистика»;

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

М2.4 — комплексы ИМ, объединяющие все названные виды КМ, пользовательский интерфейс, автоматизированные системы поддер жки принимаемых решений и т. д. Это перспективное развивающее ся направление предназначено для исследования сложных систем (подробнее см. работу [9]).

§ 1.2. КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ Из классификации (см. рис. 1.2) в силу направленности пособия будем рассматривать только один из видов КМ, а именно имитацион ное моделирование СМО, и частично вопросы статистической обра ботки результатов ИМ.

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

— разработки новых численных методов решения задач модели рования, возможных только при условии использования ИТ;

— стремительного увеличения объемов памяти и производитель ности ЭВМ, что позволяет на порядки увеличить размерности реша емых задач и перейти к качественно новым задачам моделирования.

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

В то же время возникла мощная оппозиция применению ММ в плохо структурируемых, не формализуемых областях, т. е. в таких областях, где человек (оператор, ЛОР, ЛПР) является основным эле ментом. По определению академика РАН РФ А. А. Самарского, про цесс ММ базируется на триаде «модель—алгоритм—программа». До появления ЭВМ основную роль играла модель в виде математиче ских уравнений, алгоритм представлял собой схему ручных расчетов для приближенного решения уравнений, а программа отсутствовала вообще. В начале использования ЭВМ первого поколения программе отводилась второстепенная роль — представление алгоритма в ма шинных кодах. Развитие ИТ привело к тому, что ЭВМ стали исполь зовать для моделирования процессов функционирования системы, причем в этом случае имелись алгоритм и программа, а математиче ская модель в ее классическом виде практически отсутствовала или молчаливо предполагалось, что математической моделью является одно из аналитических представлений. Это направление получило название имитационного моделирования и представлено в работах Н. П. Бусленко, Н. Н. Моисеева, Р. Шеннона и многих других. Та ким образом, в ММ началось опережающее развитие третьей компо ненты триады — программы или программного обеспечения процес са моделирования.

Необходимо четко понимать разницу между программированием и моделированием. Программирование в настоящее время располагает большим арсеналом языков программирования, средств автоматиза ции управления вычислительными ресурсами, создания программ, автоматизации работ с большими массивами данных, так называе мых систем управления базами данных (СУБД).

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

В связи со сказанным все чаще в литературе [4–6, 11] появляется термин компьютерное моделирование. КМ объединяет достижения математического моделирования, системного программирования и информационных технологий.

Автор не претендует на формулирование понятия КМ, помня все перипетии известной басни С. Михалкова «Слон живописец», однако приводит некоторые характерные черты КМ, инвариантные к области применения и направлениям исследования. Итак, КМ обладает:

• способностью понимать, интерпретировать и использовать фор мализованную и не формализованную информацию (математические формулы, логические правила, вербальные описания и т. п.);

• различными формами представления данных и знаний, запол няя пространство между ММ с его аналитическими формами описа ния и искусственным интеллектом с его формами и правилами пред ставления знаний;

• способностью участвовать в процессе не только автоматизации научных исследований за счет использования самой ЭВМ для моди фикации различных режимов применения КМ, но и интеграции всех этапов жизненного цикла системы путем использования быстро раз вивающихся методов ИТ (широко распространенные во всем мире CALS технологии, CASE технологии, технологии ICAM и IDEF);

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

Помня, что КМ разделяется на четыре подгруппы, следует иметь в виду, что обычно при использовании ЯИМ приходится обращаться и к методам Монте Карло, и к возможностям ППП, созданных для об работки статистических данных. Поскольку задачей пособия явля ется рассмотрение одного из ЯИМ—GPSS/H, специальные вопросы, относящиеся к М2.1, М2.3, М2.4, здесь не рассматриваются. Неко торые вопросы освещаются в работах [4, 5, 11], имеются многочис ленные ссылки на литературные источники; кроме того, нельзя за бывать о неисчерпаемых ресурсах Интернета.

§ 1.3. МЕСТО ИМИТАЦИОННЫХ МОДЕЛЕЙ В ОБЩЕЙ

СТРУКТУРЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

По Р. Шеннону, имитация — это «процесс конструирования ре альной системы и постановки эксперимента на ней». При этом лю бые характеристики определяются за счет проведения прогона или нескольких прогонов модели, каждый из которых включает задан ное число реплик (реализаций вычислительного эксперимента). ИМ можно использовать в двух направлениях:

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

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

Оба направления имеют право претендовать на соответствие клас сическому определению Шеннона. Чтобы уяснить место имитацион ных моделей в общей структуре ПО, рассмотрим уровни построения ПО.

Уровень 1. Машинные коды, автокоды, машинно ориентирован ные языки, операционные системы.

Уровень 2. Алгоритмические языки высокого уровня (С++, Pascal и др.), системы программирования СУБД.

Уровень 3. Специализированные алгоритмические языки модели рования, в том числе и имитационного (SIMULA, SIMSCRIPT, GPSS и др.).

Уровень 4. Интегрированные системы ИМ (например, SLX, СИМ), автоматизированные системы искусственного интеллекта (эксперт ные, поддержки принятия решений).

Объекты 1 го уровня не требуют никаких комментариев.

Языки 2 го уровня при их универсальности дороги и сложны.

Языки 3 го уровня, теряя в универсальности, приобретают на правленность на конкретную область и становятся простыми. Отме тим, что GPSS/H, сохранив все преимущества языков 3 го уровня, вобрал в себя многие положительные черты языков 2 го уровня (под робнее см. гл. 4).

Учитывая, что число ЯИМ на сегодняшний день превышает 600, выбор ЯИМ зависит от многих факторов: предметной области, ква лификации пользователя, наличия соответствующей ИТ и т. д.

Языки ИМ обладают рядом весьма привлекательных достоинств:

— удобством описания структуры исследуемой системы;

— учетом динамики функционирования и начальных условий;

— возможностью повторения испытаний;

— возможностью отладки и контроля;

— сбором и анализом необходимой статистики и принятием решений;

— простотой восприятия;

— простотой обучения;

— возможностью использования разработчиками системы, не яв ляющимися специалистами в области математики и программиро вания.

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

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

ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

Имитационное моделирование позволяет решать ряд сложных задач и имеет преимущества:

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

— при проведении ИМ выявляется характер связей между внут ренними параметрами системы и выходными характеристиками;

— при проведении ИМ можно менять темп моделирования: уско рять при моделировании явлений макромира (например, процессов на Солнце) или замедлять при моделировании явлений микромира (например, процесс существования элементарных частиц);

— при проведении сравнения и выбора альтернатив;

— при изучении узких мест в системе;

— при подготовке специалистов, осваивающих новую технику.

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

Достоинства ИМ 1. Возможность объединять традиционные математические и экс периментальные компьютерные методы.

2. Высокая эффективность применения при исследовании АСНИ, САПР, экспертных систем, сложных систем управления. По данным RAND Corp., консалтинговые фирмы из всей гаммы возможных средств анализа: линейного, нелинейного, динамического программирования, методов исследования операций, вычислительных методов — более чем в 60 % случаев прибегают к ИМ, так как ИМ позволяет получать ответы в терминах, понятных и привычных для пользователя.

3. Возможность исследовать объекты, физическое моделирование которых экономически нецелесообразно или невозможно.

4. Испытания объекта связаны с опасностью для здоровья человека.

5. Исследование еще не существующих объектов.

6. Исследование труднодоступных или ненаблюдаемых объектов.

7. Исследование плохо формализуемых экологических, социальных или экономических систем.

8. Исследование объектов практически любой сложности при боль шой детализации и снятии ограничений на вид функций распределе ния случайных величин.

Недостатки ИМ 1. Самым существенным недостатком является невозможность получить точечную оценку исследуемых характеристик, так как в результате ИМ можно оценить только математическое ожидание и дисперсию.

2. Потеря общности результатов, так как при ИМ оценивается конкретная система.

3. Трудности оптимизации, так как ИМ отвечает на вопрос, «что будет в случае, если..?», но не определяет, будут ли эти условия наи лучшими.

4. Трудности с оценкой адекватности ИМ.

5. Создание ИМ сложной системы длительно по времени и требует значительных денежных средств.

Несмотря на эти недостатки, все большее число исследователей прибегает к использованию ИМ в силу достоинств, указанных выше.

Для составления сложной ИМ необходимы опыт и приобретаемые на практике навыки. Это следует учитывать, чтобы при первых неуда чах не наступило разочарование в возможностях ИМ.

РЕАЛИЗУЕМЫЕ ПРИ ИМИТАЦИОННОМ МОДЕЛИРОВАНИИ

Процесс ИМ системы можно разделить на три последовательно выполняемых этапа (рис. 1.3):

I — построение математической (концептуальной) модели S (см.

гл. 2).

II — разработка моделирующего алгоритма S (см. гл. 4);

III — исследование системы S с помощью модели S (см. гл. 6, 8).

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

Построение математической модели на I этапе включает в себя пять взаимосвязанных подэтапов [4, 11]:

1) уяснение и постановка задачи, определение целей исследова ния;

2) декомпозиция системы на компоненты, допускающие удобное математическое или алгоритмическое описание;

3) определение параметров, переменных, пространства состояний системы, установление пределов изменения каждой характеристи ки;

4) выбор выходных показателей, т. е. вектора Q;

5) аналитическое описание с помощью выбранной концептуаль ной модели S системы S и проверка ее адекватности.

Построение математической модели системы S начинается с опре деления параметров системы и переменных, определяющих процесс функционирования системы.

На II этапе при переходе от концептуальной модели S к моделиру ющему алгоритму и имитационной модели S можно выделить пять основных подэтапов:

Рис. 1.3. Этапы представления модели 1) выбор способа имитации (см. гл. 3), а также вычислительных и программных средств реализации ИМ;

2) построение логической схемы моделирующего алгоритма;

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

4) программирование моделирующего алгоритма, т. е. разработка самой имитационной модели;

5) отладка, тестирование и проверка адекватности ИМ.

На III этапе можно выделить три основных подэтапа:

1) планирование вычислительных экспериментов;

2) проведение прогона или прогонов;

3) обработка, анализ и интерпретация результатов.

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

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

• что представляет собой система (характеристики, состав, взаи модействия, отношение с окружающей средой);

• как характеристики эволюционируют во времени;

• каков характер корреляционных связей;

• обладает ли система свойствами робастности и т. д.

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

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

Наконец, III этап является основным, ради которого и строилась модель, на этом этапе набирается статистика, позволяющая прини мать решения по любой из основных задач ИМ.

Следующие группы задач ИМ можно отнести к основным.

1. Оценка значений показателей выходного вектора Q, а также значений параметров компонентов.

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

3. Сравнение систем с разными вариантами структур и разными значениями параметров для одной функциональной структуры.

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

Любая из названных задач может быть решена на III этапе с помо щью методов планирования имитационных экспериментов. В резуль тате ИМ системы S при заданном времени и векторе параметров сис темы получается фазовая траектория системы S и значения выходных показателей для каждого интервала модель ного времени и для всего интервала моделирования в целом Результаты одного вычислительного эксперимента (ВЭ), имити рующего фазовую траекторию (1.1) и выходные показатели (1.2), называются репликой или реализацией. Итогом одной реплики яв ляется одно значение искомой характеристики. Для получения пред ставительной статистики необходимо провести ряд реплик в рамках одного прогона или ряд прогонов с меняющимися условиями, после чего проводится подэтап обработки данных ВЭ. Анализ полученной статистики может выявить и контринтуитивное поведение системы, что может быть вызвано плохим проведением I этапа или невыяв ленной неадекватностью модели исследуемой системе. Целью обра ботки статистики является не только оценка характеристик, но и уточнение асимптотических свойств, определение колебательности системы и областей устойчивости. На основе полученных результа тов принимаются необходимые решения. Названные группы задач практически перекрывают всю область возможных примене ний ИМ.

§ 1.6. ОЦЕНКА АДЕКВАТНОСТИ ИМИТАЦИОННЫХ МОДЕЛЕЙ

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

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

— согласуются ли результаты ИМ с предполагаемыми статисти ческими оценками.

Тем не менее, в последнее время появился ряд работ, делающих обнадеживающие попытки оценки адекватности, распадающейся на два связанных процесса:

верификации — т. е. проверки идентичности концептуальной мо дели исследуемой системы;

пригодности модели — возможности перенесения результатов мо делирования на исследуемую систему.

Верификация — общепринятая процедура и чаще всего неизбеж ная. Верификация предусматривает предупредительные и отладоч ные процедуры.

К предупредительным относятся:

• проверка пригодности входных данных, контроль набора и т. п.;

• построение программы в виде трех разделов:

структура модели, исходные данные, запуск программы со строгой последовательностью операторов;

• проверка датчиков БСВ;

• проверка точности вычислений (формат данных, округление, усечение).

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

Оценка пригодности в ИМ — процедура достаточно спорная, счи тается даже, что она может дискредитировать полезную модель. Кро ме того, оценка пригодности, являясь многокритериальным процес сом, достаточно сложна, и единой системы критериев для такой оцен ки не существует.

Анализ ряда статей позволил представить классификацию крите риев оценки пригодности (табл. 1.1).

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

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

Формально необходимо иметь две выборки и оценивать их статисти ческими методами (регрессионный и факторный анализ, хи квадрат и F критерии, тесты Тьюринга).

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

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

Методы оценки верификации и пригодности делятся на две группы:

— формальные (статистические);

— неформальные с привлечением пользователей и лиц, принима ющих решение.

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

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

КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ДЛЯ GPSS/H

§ 2.1. КЛАССИФИКАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

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

Рассмотрим эти понятия подробнее.

Можно рассматривать только два вида протекания какого либо процесса во времени. Время может рассматриваться либо как непре рывная переменная t [0, T], либо как дискретная t = it, i = 0,1, …, М, M = [T/], где — шаг дискретизации. Соответственно припи шем индексы Н и Д этим двум видам процессов, описываемых анали тическими моделями. Индекс Н соответствует аналоговым сигналам (постоянный, монотонный, синусоидальный и т. д.). Индекс Д — дискретным сигналам (импульсный — в виде отдельного импульса или их последовательности; цифровой, подобно 1 и 0 в ЭВМ, и т. п.).

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

С учетом сказанного, классификация позволит рассматривать че тыре типа моделей: НП, ДП, НВ, ДВ модели. Очевидно, что все многообразие аналитических моделей можно разнести по этим клас Таблица 2.1. Классификация математических моделей Характери стика

НП ДВ НВ

Вид зави Дифференци Теория раз Разностные Стохастиче симости альные и ин ностных урав стохастиче ские диффе сам. Обзор аналитических моделей невозможно провести в рамках од ного пособия, определенная попытка была сделана в работах [4, 11].

Ограничимся сводной табл. 2.1, которая содержит только некоторые аналитические модели и определяет область их применения.

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

ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Системы массового обслуживания встречаются на каждом шагу — невозможно назвать область человеческой деятельности, где не воз никают проблема обслуживания и создание очереди при занятости органа обслуживания (документооборот, телефонная связь, бизнес, торговля и т. д. В гл. 4 приведен список сфер, где можно применять ИМ на GPPS/H, а значит, где применимы методы СМО).

В теории СМО разработаны идентичные модели для:

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

— отыскания оптимального количества оборудования (число лиф тов в офисном здании, число грузовых терминалов и т. п.);

— определения производительности той или иной системы (про изводительность ЭВМ, пропускная способность канала связи и т. п.).

Очевидно, что можно назвать дополнительные возможности СМО и заключить, что во многих исследуемых системах сочетаются все указанные выше модели. Более того, теория СМО быстро развивает ся и появляются все новые модели. В связи с этим ниже будут изло жены только основополагающие идеи СМО, не претендующие на ка кую либо новизну, являющиеся ориентиром для читателей, не зна комых с теорией СМО, и приводимые для лучшего понимания кон цептуальных основ ЯИМ GPSS/H.

Систему МО можно описать рядом параметров.

• Входной поток заявок или требований v(t) (в GPSS/H — тран закты), задающий вероятностный закон поступления заявок на об служивание. Заявки могут поступать либо по одиночке, либо груп пами (пакетами). В GPSS/H входной поток задается оператором бло ка (ОБ) GENERATE (см. гл. 4, 5).

• Поток обслуживания u(t), задающий вероятностный закон про цесса обслуживания заявок. В GPSS/H поток обслуживания задает ся ОБ ADVANCE (см. гл. 5).

• Прибор обслуживания Pi, i =1, 2, …, N, состоящий из накопите ля Hi емкостью 0 m, при m = 0 происходит потеря обслужива ния, а при m = все заявки ожидают обслуживания, промежуточные значения определяют емкость накопителя. В состав прибора также входит канал обслуживания К = nj, j = 1, 2, …, L; при n = 1 обслужи вание называется одноканальным, а при n > 1 — многоканальным.

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

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

FIFO — первый пришел — первый вышел (обслужился), в англо язычной литературе эта известная аббревиатура все чаще заменяет ся на FCFS (first come first serve — первый пришел — первый обслу жился);

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

SPT (shortest processing time) — кратчайшее время обслужива ния, которое применяется для заявок с приоритетом, в GPSS/H эта дисциплина реализуется ОБ PRIORITY;

случайная дисциплина, например система опроса слушателей на практических занятиях.

В пособии будут рассматриваться только дисциплины FCFS и SPT.

Подчеркнем, что в GPSS/H факт создания очереди реализуется свя занной парой ОБ QUEUE / DEPART.

• Выходной поток y(t) — функция распределения, представляю щая собой сумму двух вероятностных законов: y1(t) — поток обслу женных заявок и y2(t) — поток потерянных (не обслуженных) зая вок, который образуется за счет отказа в обслуживании из за малого объема накопителя по принципу m + 1 < K, где K — число заявок на входе прибора. В отдельных случаях заявка может остаться в прибо ре из за окончания времени моделирования, поэтому в неравенстве появляется единица. Все сказанное объединим в рис. 2.1.

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

В 1953 г. Г. Кендалл предложил стандартные обозначения для введенных выше определений, которые и используются исследовате лями без изменений. Для однофазных СМО символика Кендалла выглядит следующим образом:

где A и B — входной поток и поток обслуживания соответственно;

n — число каналов, n 1; m — емкость накопителя.

v(t) Рис. 2.1. Блок схема элемента СМО: а — прибор обслуживания; б — виды 1 — одноканальная однофазная; 2 — многоканальная однофазная;

3 — одноканальная многофазная; 4 — многоканальная многофазная:

Н — накопитель; К — канал обслуживания; — поток входных заявок; — прибор обслуживания; — поток обслуженных заявок Потоки случайных событий могут иметь различный вид:

М — экспоненциальное распределение длительностей интервалов поступления заявок или длительностей обслуживания (индекс М — от определяющего слова марковский процесс, т. е. такой, когда пове дение процесса после момента времени t зависит лишь от состояния процесса в момент времени t и не зависит от поведения до момента времени t);

D — детерминированное распределение длительностей интерва лов поступления заявок или длительностей обслуживания;

Еk — поток Эрланга k го порядка для длительностей интервалов между приходами заявок или длительностей обслуживания;

GI — рекуррентный поток (длительности интервалов статисти чески независимы и имеют одинаковое распределение);

G — общий вид распределения.

Тогда в символах Кендалла вместо А и В подставляется символ одного из упомянутых потоков, например:

M/M/1 — экспоненциальные потоки с одним каналом обслужи вания и неограниченной емкостью;

D/GI/5/10 — детерминированный входной поток, рекуррентный поток обслуживания, многоканальное СМО с пятью одинаковыми каналами, емкость накопителя 10 и т. д.

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

§ 2.3. НЕКОТОРЫЕ АНАЛИТИЧЕСКИЕ МОДЕЛИ

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

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

Стационарность случайного процесса означает, что на любом про межутке времени t вероятность прихода n заявок зависит только от числа n и величины промежутка t, но не изменяется от сдвига t по оси времени. При этом выполняется эргодическое свойство — стати стическое равенство n заявок, полученных при ИМ одной системы, или испытания n систем до прихода первой заявки. Формулирование этого свойства звучит достаточно просто: «Совокупное по времени наблюдений равняется совокупному по ансамблю наблюдений».

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

Ординарность потока заявок означает невозможность появления более одной заявки в один и тот же момент времени. Как это реализу ется в GPSS/H, будет рассмотрено в ч. 2.

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

2.3.1. Распределение вероятностей длительности интервалов между заявками Пусть f(t) — плотность распределения длительностей t интерва лов между любой парой смежных заявок. Определим параметр пото ка как среднюю частоту появлений заявок, а 1/ — как среднее значение длительности интервала, тогда Например, если за дискрету времени примем 1 ч, а = 4, то среднее количество поступлений равняется 15 мин (1 / = 0,25) и наоборот, если каждые 10 мин в систему поступает одна заявка, то частота по ступлений равняется 0,1 заявки в минуту.

Для стационарного потока плотность определяется как такое распределение называется экспоненциальным.

Вычисляя вероятность попадания n заявок в произвольно вы бранный интервал Т, приходим к распределению Пуассона:

Полученные распределения отвечают всем свойствам простейше го потока, а именно:

— длительность интервалов взаимонезависима и одинаково рас пределена;

— ненулевая вероятность поступления заявок при t > 0;

— при интервале t, стремящемся к нулю, количество поступаю щих заявок не превышает единицы.

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

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

Пусть плотность распределения равна g (t), тогда среднее время обслуживания где — параметр (скорость) потока обслуживания.

Так, например, если за дискрету времени принять 1 ч, а = 5, то в течение часа прибор обслужит 5 требований и среднее время обслу живания равно 12 мин и наоборот; если на обслуживание заявки ухо дит 30 мин, то скорость обслуживания = 2. При расчете среднего времени обслуживания учитывается только время занятости прибо ра обслуживания.

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

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

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

а что заканчивается:

2.3.3. Одноканальное обслуживание с пуассоновским распределением длительностей обслуживания Рассмотрим пример, в котором имеется возможность аналитиче ского определения показателей эффективности функционирования СМО (М/М/1).

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

где Рn(t) — вероятность нахождения системы в состоянии xn (t) X в момент t, т. е. когда в ней находятся n заявок.

Вероятность нахождения в системе n заявок в момент времени (t + t) равна сумме трех вероятностей:

1) вероятности нахождения в системе n заявок в момент t, умно женной на вероятность того, что за время t в систему не поступает ни одной заявки и ни одна заявка не будет обслужена;

2) вероятности нахождения в системе (n – 1) заявки в момент t, умноженной на вероятность поступления одной заявки за время t, и ни одна заявка не будет обслужена;

3) вероятности нахождения в системе (n + 1) заявки в момент t +, где — пренебрежимо малый интервал времени, умноженной на ве роятность ухода одной заявки, при условии непоступления ни одной заявки.

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

Найдем выражение среднего числа заявок, находящихся в нако пителе, и среднего времени ожидания заявок в накопителе для ста ционарного состояния при загрузке = / < 1, коэффициент иног да называют траффик интенсивностью. Поскольку он также пред ставляет долю полного времени, в течение которого прибор не про стаивает, его иногда называют коэффициентом использования или загруженности.

Приравняв производные по времени t к нулю, получим уравне ния:

p0 = p1;

операции, имеем рn = np0, причем:

Следовательно, получим, что рn = рn (1 – ) — геометрическое рас пределение. Среднее число заявок в системе равно Среднее число заявок, находящихся в накопителе:

Среднее время ожидания заявок в накопителе:

Среднее время пребывания в системе Сведем основные операционные характеристики рассматриваемой системы с дисциплиной FCFS (FIFO) в табл. 2.2. Следует обратить внимание, что при возрастании коэффициента использования такие параметры как число заявок в системе, длина очереди, время пребы вания в системе начинают быстро возрастать. При заданной скорос ти обслуживания, когда коэффициент занятости невелик, основ ная доля среднего времени пребывания заявки в системе связана толь ко с процедурой обслуживания, при возрастании интенсивности вход ного потока большая часть времени пребывания заявки в системе обусловлена ожиданием обслуживания.

Таблица 2.2. Операционные характеристики СМО Рассмотрим конкретный пример использования табл. 2.2. Пусть дискрета времени равна 1 ч, а = 0,8, при этом прибор простаивает в среднем 0,2 ч (12 мин), а среднее количество требований в системе равно 4. При = 10 (скорость обслуживания равняется 10 ед./ч) сред няя продолжительность пребывания заявки в системе равняется 0,5 (30 мин), а пребывание в очереди из них занимает 24 мин.

Возможны ситуации, когда длина очереди ограничена. Если в СМО не может быть более L заявок, то длина очереди ограничена величиной L –1 и любая заявка сверх этого значения теряется и статистическое равновесие в этом случае достигается при любом значении [1].

2.3.4. Многоканальное обслуживание с пуассоновским распределением длительностей обслуживания Очевидно, что в большинстве случаев СМО являются многоканаль ными, символика Кендалла в этом случае имеет вид M/M/L, где вход ной поток имеет вид f(t) = e–t, поток обслуживаний g(t) = e–t, а число каналов равно L. Учтем, что режим функционирования лю бого канала не влияет на режимы функционирования других кана лов, длительности обслуживания являются случайными величина ми. Уравнения в конечных разностях аналогичны уравнениям (2.11).

Решение системы уравнений приводится без доказательств:

Установившийся режим функционирования СМО, определяемой выражениями (2.17) – (2.19), достигается при условии < L. Когда Pn определено, то большинство операционных характеристик вычис ляется с помощью элементарных алгебраических операций [1].

ПРИНЦИПЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

В настоящей главе будут рассмотрены некоторые основополагаю щие принципы построения любой имитационной модели, не обяза тельно реализуемой с помощью ЯИМ GPSS/H. В табл. 3.1 в качестве иллюстративного примера приведена классификация некоторых из вестных ЯИМ [4].

С появлением персональных ЭВМ интенсивно развиваются спе циализированные системы моделирования для этих типов компью теров. Часто они представляют собой развитие известных систем мо делирования для универсальных ЭВМ, например: GPSS, SIMSCRIPT II.5, SIMULAP, MiniDYNAMO, MicroDYNAMO/DOS, SLAM II/PC.

В книге Е. Киндлера «Языки программирования» приведен каталог наиболее известных зарубежных систем ИМ, включающий 200 наи менований. Некоторые из этих систем вошли в табл. 3.2. В таблице указаны, в основном, системы, предназначенные для использования на IBM совместимых универсальных (MF) и персональных (РС) ЭВМ.

Дополнительно указываются требуемый транслятор (с базового язы ка программирования), операционная система, а также некоторые Таблица 3.1. Классификация ЯИМ по способу имитации Непрерывный Аппроксимация диф DYNAMO, MIMIC Непрерывно дискрет Kомбинированный SLAM, НЕДИС Таблица 3.2. Классификация ЯИМ

OPTIC PC

DYNAMO III /F+/ 370 MF, Фортран Нелинейные модели MicroDYNAMO РС, 16 разрядные, РС MiniDYNAMO ProDYNAMO+ BEST NETWORK MF, Фортран SIMAN + Cinema PC, Фортран 77 анализа; ориентация на

TSIM VAX

LSMP PC

Продолжение табл. 3. на производственные процессы и контроль качества Системы моделирования экономических процессов Моделирование вычислительных и коммутационных систем (KС) Моделирование робототехнических систем Окончание табл. 3. Системы статистического моделирования и обработки данных особенности или возможности систем (в графе «Примечания»). По своему назначению системы разбиты на разделы. Первые четыре раз дела включают ЯИМ общего назначения, ориентированные на опре деленный тип модели. В последующих разделах системы объедине ны по типу предметной области либо условиям применения.

Таблицы 3.1, 3.2 дают общее представление о системном мире ЯИМ, однако существуют принципы, одинаковые для всех типов моделей:

— понятие о модельном времени;

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

— генерирование базовых случайных величин (чисел, векторов, процессов).

Все упомянутые принципы будут рассмотрены в последующих па раграфах настоящей главы.

Как уже упоминалось (§ 1.5), содержание любой задачи ИМ полу чается в результате реализации прогона или ряда прогонов модель ного файла, получения и обработки собранной статистики и приня тия решений на основе статистического анализа. Длительность ис пытаний зависит либо от заданной статистической точности, либо от заданного числа реплик в одном прогоне, либо от времени рассмот рения функционирования реальной системы (см. гл. 8). В связи со сказанным необходимо четко понимать, какие времена рассматрива ются при ИМ, и представлять их различие.

• Тр — реальное время функционирования исследуемой системы S, которое может быть очень большим, например, 10n лет при иссле довании космогонических процессов, либо, наоборот, очень малым — 10–n с при исследовании процессов, происходящих в микромире.

• Ти — машинное время имитации, отражающее затраты ресурса времени ЭВМ на организацию ИМ. В случае использования супер компьютеров, производительность которых превышает сотни гига флоп, минута машинного времени может стоить несколько тысяч дол ларов. Это ограничение должно учитываться создателями ИМ и да лее не рассматривается.

• Тм — модельное время (МВ), используемое в ИМ. Оно может быть сжато при исследовании процессов макромира или растянуто при опе рировании со сверхбыстрыми процессами в реальной системе. Кроме того, именно МВ позволяет избежать сложностей моделирования по ведения реальной системы. Так, в реальной системе события могут происходить одновременно в разных компонентах системы; в обыч ных, не мультипроцессорных, ЭВМ параллельные события вопло тить нельзя. Модельное время позволяет синхронизовать все собы тия и реализовать квазипараллелизм (см. § 3.2). При создании ИМ задание временной дискреты модельного времени является обязатель ным условием до начала процесса ИМ. Естественно, что разные зна чения времени процессов обязательно должны быть выражены в едином масштабе временной дискреты модельного времени. Так, например, если временная дискрета задана в минутах, другие вре менные периоды: часы, сутки, годы — должны быть также представ лены в минутах.

Введем обозначение временного интервала моделирования систе мы S (интервала МВ) где t0 — время начала моделирования (обычно полагают t0 = 0); Тм — время окончания моделирования; t — текущее значение МВ.

Построение модели системы S начинается с определения парамет ров системы и переменных, определяющих процесс функционирова ния системы.

1. Параметры системы 1, 2, …, m — это характеристики сис темы, остающиеся постоянными на всем интервале моделирования. Если значения {i} определены на некотором множестве то говорят, что имеется параметрическое семейство систем.

2. Множество переменных разбивают на два подмножества — независимых и зависимых переменных.

К независимым переменным отнесем следующие характери стики.

• Входные воздействия на систему (сигналы) u1, u2, …, un1. Вход ные воздействия в момент t Т характеризуются вектором Среди {ui} могут быть управляющие воздействия, например u1, u2,…, un1 (n1 n1), а остальные n1 – n1 воздействий — неуправляю щие.

• Воздействия внешней среды: среди них могут быть контролиру емые (наблюдаемые) и неконтролируемые (ненаблюдаемые), детер минированные и случайные воздействия. В момент t Т они характе ризуются вектором • Переменные, характеризующие состояние системы: x1, x2, …, xn3. В отличие от {i} состояния {xi} характеризуют свойства систе мы, изменяющиеся во времени. Состояние системы в момент време ни t Т описывается вектором где X — пространство состояний или фазовое пространство системы (множество возможных значений вектора х). Если t1< t2 t* — момент наступления ближайшего после ri будущего собы тия; r = ri — общее число событий в момент t*; t** и **— моменты ближайших будущих событий в ИМ, вычисленные по принципам t и x соответственно.

Модельное время t в ИМ можно рассматривать как функцию от числа событий, происходящих в ИМ. Очевидно: t(r) = t* < Тм, r = 0, 1, 2,..., t(r + 1) = t** = min tr +1,..., tr N+)1, Tм = t(r ) + min ( N+1, Tм t(r ) ; (3.6) где {tji) }, {(ji) } определяются соотношением (3.6). Заметим, что мо менты t** = Тм и ** = vt (если T v) являются моментами заверше ния моделирования. Правила (3.6) и (3.7) называются правилами из менения модельного времени по принципам t и x соответственно.

На практике отдается предпочтение принципу x. Принцип t используется лишь в случаях, когда:

1) события { Aj(i) } таковы, что tj(i) tj()1 const на всем интервале моделирования Тм, и, следовательно, можно подобрать интервал t изменения МВ, обеспечивающий минимальную погрешность аппрок симации (например, для разностных уравнений);

2) событий очень много и они появляются группами. В этом слу чае за счет групповой обработки событий { Aj(i) }, попавших внутрь очередного шага изменения t, удается уменьшить затраты машин ного времени.

В большинстве практически важных случаев события { Aj(i) } на ступают через случайные интервалы времени {tj(i) }. Поэтому способ задания шага до следующего события экономичнее (в смысле затрат машинного времени) и точнее (в смысле точности аппроксимации) фазовой траектории способа фиксированного изменения МВ. В связи с реализацией такого способа представления МВ при моделировании на GPSS/H в англоязычной литературе он называется моделирова нием дискретных событий (Discrete Event Simulation). Такое назва ние никоим образом не противоречит выбранному типу концептуаль ной НВ модели, а лишь отражает способ представления модельного времени.

§ 3.3. СПОСОБЫ СОЗДАНИЯ КВАЗИПАРАЛЛЕЛИЗМА

ПРИ ИМИТАЦИОННОМ МОДЕЛИРОВАНИИ

По Р. Шеннону, каждая ИМ представляет собой комбинацию ком понентов, параметров, переменных, функциональных зависимостей, ограничений, целевых функций.

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

Параметры выбираются исследователем, и обычно в течение про гона, а иногда и в процессе всего ИМ они сохраняются неизменными.

Переменные бывают внешние и внутренние.

Функциональные зависимости связывают переменные и парамет ры внутри компоненты или между компонентами.

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

Пример. Объектом имитации является движение космической раке ты. В режиме запуска можно выделить последовательность реальных дей ствий от R1i) на стартовой площадке до R3i) — сброса второй ступени.

Движение множества ракет представляет собой систему, а каждая i я ра кета является компонентой. В результате выполнения действий возника ют события Aj(i).

Отличие Rj i ) от dj определяет уровень детализации модели и порож дает ошибки имитации реальной системы. Очевидно, что каждое действие dj(i) описывается алгоритмом AE (ji). Тогда при переходе от события к со бытию реализуется действие при неизменном значении времени, а потом изменяется время на j. В принципе, возможно и обратное поведение, т. е. вначале изменяется время, а затем реализуется действие посредством алгоритма. Для реальной системы фазовая траектория запишется в виде 0 A1i) A2i) A3i) ; в имитационной модели — в виде 0 a A1i) b A2i) c A3i) или 1i) A1i) 2i) A2i) 3i) A3i).

В любом случае мы имеем активность АК j (dj i ), (i ) ) как некую моле кулу, содержащую описание алгоритма, приводящего к действию, и опе ратор изменения временной координаты I tj (временной модификатор).

На рис. 3.7 дается представление о различиях между исследуемой cистемой и ее моделью. Каждому компоненту системы соответствует аналогичный компонент модели, причем каждый компонент может AK(i)j = < AЛ(i)j, M(i)j > = Рис. 3.7. Отличия между системой и ее моделью включать ряд элементов со своими действиями, которым в модели соответствую алгоритм и модификатор времени.

Общее управление ведется с помощью УПМ, связывающей запуск алгоритмов, временных модификаторов, проверку условий имита ции, обработку статистики, окончание испытаний, выдачу резуль татов. Таким образом, описание ИМ разрастается в объеме по срав нению с описанием системы. ИМ состоит из двух частей: первая часть является переменной, объектно ориентированной и создается иссле дователем с помощью определенных процедур; вторая часть практи чески инвариантна к виду исследуемой системы и представляет со бой реализацию процедур синхронизации модели, запуска, сбора ста тистики и завершения имитации.

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

В табл. 3.3 приведены типы описания ИМ и способы организации квазипараллелизма в ИМ.

Одну и ту же систему можно представить одним из способов табл. 3.3, но ИМ на их основе отличаются размерами и количеством Таблица 3.3. Способы организации квазипараллелизма Тип описания ИМ Способ организации квазипараллелизма Транзактами Управление обслуживанием транзактов ресурсов, затрачиваемых на их создание, испытания и использова ние. Рассмотрим особенности и принципы организации квазипарал лелизма в ИМ каждым из указанных способов.

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

• все действия для элемента Aj(i) системы S различны и приводят к наступлению разных событий;

• каждое действие dj(i) характеризуется набором условий его вы полнения, представляемых алгоритмически;

• времена выполнения действий являются случайными величина ми с известными законами распределения.

Имитационная модель описывается в виде двух частей: множе ства активностей AE (i) и набора процедур выполнимости условий инициализации активностей. (Инициализация — передача управле ния от УПМ на выполнение алгоритма данной активности.) Затем происходит модификация временной координаты М(jt). Таким обра зом, ИМ представляет собой чередование выполнения алгоритмов ак тивностей, операторов модификации временной координаты ti и ал горитма УПМ. При этом способе приходится проверять много условий попадания активностей в список инициализированных, поэтому за траты машинного времени весьма велики. Этот способ применяется, когда важно оценить влияние действия на поведение системы.

Составление расписания событий Используется для систем, характеризующихся следующим:

• множество событий разбивается на небольшое число типов;

• определяются условия перехода от одного события к другому для всех типов событий;

• для каждого типа событий определена последовательность дей ствий, приводящая к изменению состояния системы;

• интервалы времени между последовательными наступлениями со бытий — случайные величины с известными законами распределения.

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

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

Для описания ИМ создается фиксированный набор операторов, в GPSS/H совместное число всех операторов (блоков управления и описания немногим превышает 100) и УПМ сканирует списки транзактов, инициализирует блоки, сдвигает модельное время. Со бытием в ИМ является момент инициализации транзакта, в резуль тате транзакт выступает в роли активности. (Поскольку далее будет рассматриваться только этот способ создания квазипаралле лизма, то подробное описание порядка действия при ИМ приво дится в гл. 4, 5).

Агрегатный способ При описании агрегата (под агрегатом понимается объединение ряда устройств для унификации концептуального описания [4]) применим любой из рассмотренных способов, так что выделение агрегатного спо соба достаточно условно. Функцией УПМ является проверка условий перехода агрегата в одно из особых состояний и моделирование выход ных сигналов агрегата. Агрегатный способ удобен при интерпретации системы, но требует больших затрат машинного времени.

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

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

§ 3.4. МЕТОДЫ ИМИТАЦИИ СЛУЧАЙНЫХ ЧИСЕЛ Любой процесс ИМ прежде всего зависит от качества случайных чисел, векторов или функций, вводимых в модель системы. В нашем случае они должны корректно представить входной поток заявок и поток их обслуживания (см. § 2.3). Любое случайное число или век тор, попадающий на вход модели системы, будем называть случай ным элементом * (СЭ). Во всех случаях СЭ * должен удовлетворять двум основным принципам:

1) сходство между оригиналом * и его моделью состоит в совпа дении вероятностных законов распределения или числовых харак теристик;

2) всякий СЭ конструируется как некая борелевская функция на основе БСВ, генерируемых тем или иным путем.

Первым способом получения БСВ можно назвать попытку У. Гос сета (псевдоним Стьюдент) в 1908 г., когда он использовал семизнач ные телефонные номера, отбрасывая первые три цифры, которые не являлись случайными по определению.

Предположим, получалась комбинация из 16 чисел 2127210128891172, если требовалось создать равномерно распреде ленную (РР) 8 разрядную БСВ, то эта комбинация давала только две РР БСВ: 1 = 0.21272101 и 2 = 0.28891172.

Первая таблица случайных чисел была разработана в 1927 г.

Л. Типпетом и содержала 41600 БСВ, достаточных для создания 8 разрядных БСВ. Кульминацией таблиц БСВ явился выпуск в 1955 г. корпорацией RAND одного миллиона БСВ, достаточных для получения 125000 8 разрядных БСВ. Очевидно, что для прове дения даже простого имитационного эксперимента такого количе ства БСВ явно недостаточно. Кроме того, хранение и воспроизведе ние табличных БСВ весьма сложно и длительно, поэтому табличные датчики используются только для назначения номеров телефонов, автомашин и практически не используются при ИМ на ЭВМ.

Следующим возможным вариантом датчиков БСВ является физи ческий датчик — специальное радиоэлектронное устройство, явля ющееся приставкой к ЭВМ, выходной сигнал которого имитирует БСВ. Он состоит из источника флуктуационного шума (например, «флуктуационно шумящей» радиолампы), значение которого в про извольный момент времени является случайной величиной с плотностью р(у), и нелинейного преобразователя где {} = [ / ] — дробная часть числа относительно заданно го > 0 ([] — целая часть числа ).

Исследуем вероятностные свойства. По правилам функциональ ного преобразования случайных величин, из (3.8) следует, что плот ность распределения Будем предполагать, что p(y) непрерывно дифференцируема и Применим к j му слагаемому из (3.10) в окрестности точки у = j линейную формулу Тейлора с остаточным членом Лагранжа:

где 0 < < 1. При 0 по свойствам плотности распределения поэтому из (3.9), (3.10) следует, что Таким образом, выбирая достаточно малой величиной, удается получить БСВ.

Недостатки физического датчика БСВ:

1) невозможность повторения некоторой ранее полученной реа лизации а (поскольку Р{ = a} = 0);

2) схемная нестабильность, приводящая к необходимости конт ролировать работу датчика при очередном его использовании.

По этим причинам на современных компьютерах физические дат чики БСВ используются весьма редко.

Указанными недостатками не обладает программный датчик БСВ — это программа, служащая для имитации на ЭВМ реализации а1, а2,... БСВ. Он может быть получен из физического датчика БСВ введением обратной связи. Будем рассматривать функционирование датчика во времени и обозначим: t — случайную величину, подвер гаемую преобразованию (3.8) в момент времени t; t — выходную ве личину датчика в момент t (случайное число). Источник флуктуаци онного шума в физическом датчике заменяется обратной связью использующей р ранее полученных выходных значений датчика.

В (3.13) t = 1, 2,..., a 0, –1, …, 1–p фиксируются заранее: i = = ai (i = 1 p, 0) и называются исходными (стартовыми) случайными числами.

Согласно (3.8), (3.13):

Рекуррентная формула (3.14) определяет последовательность псев дослучайных чисел а1–р, а2–р,..., а0, а1,..., аt,.... Термин «псевдослу чайные» используется по следующим причинам:

1) по происхождению эти числа не случайные; они получаются по известному детерминированному закону (3.14);

2) при специальном выборе функции Ф(·) по вероятностным ха рактеристикам эти числа похожи на реализации независимых БСВ.

Отметим, что понятие случайности последовательности можно связать со сложностью моделирующего алгоритма и, в частности, со сложностью функции Ф(·) в (3.14).

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

— скорость генерации БСВ;

— требования к памяти ЭВМ;

— количество и качество генерируемых независимых РР чисел.

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

3.4.2. Принципы моделирования БСВ Простейшим для моделирования на ЭВМ случайным эксперимен том является эксперимент, заключающийся в бросании точки на удачу в промежуток [0, 1). Результатом этого эксперимента являет ся координата точки. Математической моделью такого эксперимен та является вероятностное пространство (, F, P), где = [0, 1) — пространство элементарных событий (элементарное событие заключается в том, что координата брошенной точки равна );

F — — алгебра, порожденная интервалами из ; P — вероятностная мера, определенная для событий (подмножеств) А F и совпадаю щая с мерой Лебега, так что для события A = { : [0, x)} Базовой случайной величиной на (, F, P) будем называть непре рывную случайную величину равномерно распределенную на полуинтервале [0, 1).

Функция, распределенная БСВ, имеет вид а плотность распределения определяется формулой Будем обозначать закон распределения : R [0, 1].

Математическое ожидание БСВ (первый начальный момент) дисперсия (второй центральный момент) Наряду с простейшим экспериментом будем рассматривать состав ной случайный эксперимент, получающийся в результате r кратно го (r 1) повторения независимо друг от друга простейших экспери ментов. Результатом составного случайного эксперимента является последовательность из r независимых БСВ 1, …, r таких, что где i — координата точки, брошенной наудачу в [0, 1) в i м простей шем эксперименте.

Совместная плотность распределения вероятностей 1, …, r Согласно второму принципу моделирования случайных элемен тов, любой СЭ представляется для некоторого натурального r в виде функции f(.) от r независимых БСВ:

Таким образом, задача моделирования произвольного СЭ * раз бивается на две подзадачи:

1) моделирование на ЭВМ независимых БСВ 1, …, r;

2) нахождение функции f(.) такой, чтобы СЭ обладал требуемы ми вероятностным законом распределения и числовыми характерис тиками.

Поэтому моделирующий алгоритм состоит из двух блоков (рис. 3.8):

Для имитации одного и того же СЭ * может быть предложено несколько вариантов функциональных преобразований. Обычно пред Рис. 3.8. Моделирующий алгоритм БСВ: Б1 — блок моделирования БСВ (об щий для всех ); Б2 — блок функционального преобразования f(.) БСВ (различный для различных законов распределения вероятностей) почтение отдается варианту f(.), требующему меньших вычислитель ных затрат; для этого применяется понятие коэффициента исполь зования БСВ.

Коэффициентом использования БСВ K назовем величину, обрат ную числу r базовых случайных величин, используемых для модели рования одной реализации случайного элемента *:

Величина K является мерой вычислительных затрат на модели рование *. Чем меньше K, тем больше затраты. Целесообразно вы бирать такую функцию f(.), для которой K принимает наибольшее значение.

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

Рассмотрим случай, когда представление целых неотрицательных чисел на ЭВМ осуществляется с помощью k двоичных разрядов (би тов). Тогда С = {0, 1, 2k – 1} — множество 2k неотрицательных целых чисел, представимых в ЭВМ. Определим на (,, Р) ДСВ = () следующим образом:

Построение проиллюстрируем с помощью рис. 3.9. Разобьем про межуток [0, 1) на 2k отрезков одинаковой длины 2–k; для, попадаю щих в промежуток [i2–k, (i + 1)2–k), полагаем = () = i, i C.

Рис. 3.9. Построение По построению распределение ДСВ является равномерным на множестве С, т. е. все значения равновероятны, действительно: