МЕСТО ИМИТАЦИИ В МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ СИСТЕМ

Ю. И. Рыжиков (Санкт-Петербург)

 

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

·        аналитические;

·        численные (на основе аналитических);

·        программирование имитационных моделей на языках широкого применения (типа Фортрана);

·        оно же – на специализированных языках имитации.

Аналитические методы

Математической основой описания процессов рассматриваемого типа является теория очередей (в отечественной терминологии – массового обслуживания). Эта теория со времен А.К. Эрланга (1910-е гг.) прошла длинный путь развития и позволяет решать весьма широкий круг задач. Ее достоинством (как и любого аналитического подхода) является семантическая емкость, позволяющая немедленно извлечь из конечной формулы ряд важных следствий. Для примера получим и прокомментируем формулу (Полячека – Хинчина) среднего времени ожидания w начала обслуживания в одноканальной системе M/G/1.

Пусть  – интенсивность входящего потока,  – моменты распределения длительности обслуживания. Вновь прибывающая заявка должна дождаться завершения начатого обслуживания и обслуживания накопленной очереди. Средняя длительность остатка обслуживания составляет , вероятность занятости равна  (следствие закона сохранения заявок). Средняя длина очереди q = w (формула Литтла – закон сохранения стационарной очереди), а каждая заявка очереди займет систему в среднем на время .Закон сохранения объема работы требует равенства , откуда следует

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

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

·        верификации разработанных моделей или их фрагментов сравнением с известным решением;

·        проверки выполнения законов сохранения;

·        калибровки датчиков случайных чисел;

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

Численные методы

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

·        фазовые распределения с показательно распределенными задержками в фазе (эрлангово, гиперэкспоненциальное, коксово) – для расчета распределений вероятностей состояний сложных систем;

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

·        распределение Вейбулла – для построения по моментам функции распределения времени пребывания заявки в системе.

 

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

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

Моделирование на универсальных языках

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

·        стандартные средства ввода-вывода и редактирования информации, в том числе построения графиков и анимации;

·        богатейшие библиотеки подпрограмм численных методов и статистического анализа;

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

·        свободный выбор определяемых показателей;

·        применение методов уменьшения дисперсии результатов моделирования.

 

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

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

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

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

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

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

·        работой «втемную», т. е. без ясного понимания логики и возможностей интерпретатора, что может привести к трудно диагностируемым ошибкам;

·        избыточностью создаваемой «имитации» в подавляющем большинстве случаев, что многократно замедляет процесс моделирования (по опыту автора в сравнении GPSS и Фортрана – до 80 раз даже при закрытых окнах и отключенном показе таймера);

·        принципиальной невозможностью выхода из диапазона стандартизованных возможностей (в GPSS, к примеру, нет средств моделирования многоканальных приоритетных систем; дисциплин выбора заявок, отличных от FCFS и LCFS; получения распределений числа заявок в очередях и построения графиков в логарифмическом масштабе и т. п.). Возможно, что часть этих проблем может быть решена какими-то косвенными методами, но пути к ним далеко не очевидны.

 

Наметившееся увеличение гибкости систем моделирования (в GPSS World – появление языка PLUS) позволяет перенести в них значительную часть приемов и опыта моделирования на универсальных языках. С другой стороны, знакомство с логикой интерпретатора GPSS (в этом, к сожалению, Help и другая сопроводительная документация помогают плохо) может подсказать «фортранирующему» программисту ряд полезных идей.

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

Заключение

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

Литература

1.     Климов Г.П. Стохастические системы обслуживания. – М.: Наука, Физмат, 1968. – 243 с.

2.     Рыжиков Ю.И. Машинные методы расчета систем массового обслуживания. – Л.: ВИКИ им. А.Ф. Можайского, 1979. – 177 с.

3.     Рыжиков Ю.И. Имитационное моделирование систем массового обслуживания. – Л.: ВИККИ им. А.Ф. Можайского, 1991. – 111 с.

4.     Рыжиков Ю.И. Имитационное моделирование. Теория и технологии (подготовлено к изданию) – СПб, 2003, 367 с.

5.     Рыжиков Ю.И. Компьютерный расчет систем и сетей с очередями (подготовлено к изданию) – СПб, 2003, 357 с.

6.     Советов Б.Я., Яковлев С.А. Моделирование систем. – М.: Высшая школа, 1998. – 320 с.

7.     Советов Б.Я., Яковлев С.А. Моделирование систем: практикум – М.: Высшая школа, 1999. – 224 с.