Доктор технических наук, доцент Михайлов В.В. Современные инструментальные средства автоматизации моделирования

COMPUTATIONAL SCIENCE: Ensuring Americas Competitiveness (доклад PITAC – Presidents Information Technology Committee, 2005) – новая стратегическая компьютерная инициатива для обеспечения конкурентоспособности США

А.А.Самарский – математическое моделирование и вычислительный эксперимент 1986 г. – Постановление ЦК КПСС и СМ СССР об усилении научно-исследовательских работ в области математики. Предусматривались создание службы математического моделирования и разработка общегосударственной программы широкого использования математического моделирования в различных отраслях народного хозяйства. 5 Сравнение результатов расчета с данными опыта, уточнение модели 3 Программирование 1 Построение математической модели 2 Составление разностной схемы 4 Расчеты на ЭВМ

Полезность методов исследования операций в повседневной научной работе Методы Относительная ценность Теория вероятностей (и статистические оценки)0,182 Экономический анализ (оценки эффективности затрат)0,150 Имитационное моделирование0,143 Линейное программирование0,120 Управление запасами0,097 Массовое обслуживание (теория очередей)0,085 Сетевые модели (упорядочение операций)0,072 Модели замены0,042 Теория игр0,040 Динамическое программирование0,031 Методы поиска0,020 Нелинейное программирование0,018 1,000

Методы, наиболее часто используемые во внутрифирменном планировании Методы Частота использо- вания Процент Имитационное моделирование6029 Линейное программирование4321 Сетевые методы (включая ПЕРТ и МКП)2814 Теория управления запасами2412 Нелинейное программирование168 Динамическое программирование84 Целочисленное программирование73 Теория массового обслуживания73 Прочие

Организационные проблемы комплексного моделирования (проблемы финансирования, менеджмент) Высокая стоимость программного обеспечения КМ На настоящий момент среди систем имитационного моделирования ведущее положение на мировом рынке занимают следующие программные продукты: Arena (Rockwell Automation, Inc.), ProModel (ProModel Corp.), AutoMod (Applied Materials, Inc.), eM-Plant (Tecnomatix Technologies, Ltd, Германия), ReThink (Gensym Corp.), Extend (Imagine That, Inc.), AnyLogic (ООО «Экс Джей Текнолоджис», РФ), Simul8 (Simul8 Corp.), SIMPROCESS (CACI Products Company), FlexSim (Flexsim Software Products, Inc). Относительно высокая стоимость проектов КМ Высокая стоимость оплаты труда специалистов в области КМ Ошибки управления проектов, связанных с КМ

Актуальность и особенности имитационного моделирования сложных объектов

GPSS GPSS – это неординарное явление м мире программирования конца -60-х/ начала 70-х годов. Это был один из самых удачных на то время проблемно- ориентированных языков программирования. Первая версия языка GPSS была введена в IBM в октябре 1961 г. Проблемной областью GPSS являются системы массового обслуживания (системы с очередями). Основой имитационных алгоритмов в GPSS является дискретно-событийный подход, разработанный Джеффри Гордоном. В GPSS разработчикам удалось четко пройти по грани как соответствия проблемной области (по терминологии, функциям, методологии исследования и т. д.), так и эффективности программирования. GPSS по праву считается языком, который сделал моделирование практической деятельностью, доступной широким массам программистов www:gpss.ru Рыжиков Ю.И. Имитационное моделирование: теория и прктика. Алтекс-А, с. Бражников А.Н. Имитационное моделирование. Возможности GPSS WORLD. Реноме, с. Варжапетян А.Г. Имитационное моделирование на GPSS/H. ГУАП Шрайдер Г.Д. Моделирование с использованием GPSS. Эл.версия.

GPSS Основные показатели качества обслуживания: общее количество обслуженных заявок за какой- либо промежуток времени; пропускная способность – среднее число заявок, обслуженных в единицу времени; доля заявок обслуженных; доля заявок, получивших отказ; время пребывания заявки в системе (от момента поступления заявки в систему до момента завершения ее обслуживания); среднее время обслуживания (функция распределения времени обслуживания); средняя длина очереди; среднее время ожидания; загрузка каналов – коэффициент использования (как доля времени, в течение которого ОУ было занято) – характеризует степень простоя ОУ;

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

GPSS GPSS относится к классу процессно- (транзактно) - ориентированных систем моделирования. GPSS является способом алгоритмизации дискрет' ных динамических систем. Примеры моделируемых объектов: транспорт' ные объекты, склады, производственные системы, магазины, торговые объекты, сети ЭВМ, системы передачи сообщений. Функциональная структура GPSS рассматривается на двух уровнях. 1 уровень определяется комбинацией основных функциональных объектов таких, как: устройства; памяти; ключи (логические переключатели); очереди; транзакты. 2 уровень – блок-схема модели, составленная из типовых блоков, между которыми перемещаются транзакты.

Аппаратно ориентированные объекты GPSS: Транзакты являются абстрактными подвижными элементами, которые являются аналогами различных объектов реального мира (сообщения, транспортные средства, люди, детали т.д.) Это динамические функциональные элементы GPSS, которые отражают реальные заявки на обслуживание. Транзакты двигаются по модели, появляются в ней с той же интенсивностью, что и реальные заявки. Устройства моделируют объекты, в которых может происходить обработка транзактов, что связано с затратами времени. Устройства являются аналогами каналов СМО (каждое устройство в данный момент времени может быть занять лишь одним транзактом). Памяти предназначены для моделирования объектов, обладающих eмкостью. Логические переключатели принимают значение включено/выклю- чено, позволяют изменять пути следования транзактов в модели.

Аппаратно ориентированные объекты GPSS: Статистические объекты: очереди, таблицы На 2 уровне модель на языке GPSS имеет наглядное графическое представление в виде блок-схемы. Блоки – операционные объекты GPSS. Каждый блок имеет стандартное обозначение. Последовательность блоков – это есть последовательность операторов на языке GPSS. Любую модель на языке GPSS можно представить в виде совокупности блоков, между которыми перемещаются транзакты, они имеют вход-выход, в блоках реализуются все действия, связанные с обслуживанием транзакта (создание и уничтожение транзактов, изменение параметров транзакта, управление потоками транзактов, и т.д.). Таким образом, на языке GPSS составляется и реализуется функциональная блок-схема.

MatLab Развивающийся пакет с широким спектром приложений, за счет использования пакетов ToolBox - матричный анализ, обработка сигналов и изображений, анализ динамических систем, задачи матфизики, оптимизация, работу с картографическими изображениями, нейронные сети, генетические алгоритмы, нечеткая логика и др. Справочная система с описанием встроенных функций, доступ из командной строки к кратким сведениям о функциях, электронные книги по MatLab и ToolBox. Открытость кодов Интеграция с Microsoft Word и Excel, доступ к базам данных Access, SQL, Oracle. Символьные вычисления с использованием ядра пакета Maple Визуальная среда GUIDE для написания приложений с графическим интерфейсом пользователя Программный интерфейс API для связи среды MatLab с программами, написанными на языке С или Fortran.

Литература Дьяконов В.П. MatLab. СПб.: Питер, с. Ануфриев И. Самоучитель ManLab 5.3/6.x CПб.:БХВ-Петербург, с.l Гультяев А. Визуальное моделирование в среде MatLab.СПб.: Питер, с. Потемкин И.Г. Система инженерных и научных расчетов MatLab 5.x : в 2-х т. М.:ДИАЛОГ-МИФИ,

Maple Пакет символьных вычислений и численных решений Алгебраические преобразования Интегрирование и дифференцирование аналитических ыфункций в общем виде Решение систем дифференциальных уравнений в аналитическом виде Матричные и векторные вычисления Решение задач из теории графов и теории групп Комбинаторика и теория групп Визуализация результатов вычислений с использованием 2D и 3D графики Статистический анализ Более 20 библиотек по различным областям знаний Древовидная справочная система с примерами, которые можно проигрывать со своими данными

Справочная информация Прохоров Г.В., Леденев М.А., Колбеев В.В. Пакет символьных вычислений Maple V. М.: Петит, с.

Model-Vision Поддержка гибридных моделей Описание дискретных объектов картами состояний UML Описание непрерывных объектов системами уравнений в математической нотации Поддержка компонентного моделирования с направленными и ненаправленными связями Инкрементный транслятор и диагностика ошибок Типовая конструкция MV – обобщенный гибридный автомат, как последовательная композиция непрерывных компонент, взаимодействующих через начальные условия Колесов Ю.Б., Сениченков Ю.Б. Моделирование систем. Динамические и гибридные системы. СПб.: БХЗ-Петербург, Колесов Ю.Б. Объектно-ориентированное моделирование сложных динамических систем. СПб.: СПбГПУ, с. Колесов Ю.Б., Сениченков Ю.Б. Визуальное моделирование сложных динамических систем.

Формализм гибридного автомата. Гибридный автомат: H = {t, G, V, C, P, A, F}, где: G – ориентированный граф, вершины которого это множество дискретных состояний автомата, S – дуги графа, E - возможные переходы из состояния в состояние, S0 – начальное состояние, t – непрерывное время V = (Vc, Vd) – множество непрерывных Vc и дискретных Vd переменных, C – множество непрерывных отображений, P – множество логических предикатов, A – множество мгновенных действий, F = {Fc, Fp, Fa} - Fc: C S – отображение, сопоставляющее множеству непрерывных отображений состояния автомата, Fp: P E – отображение, сопоставляющее множеству предикатов множество переходов, Fa: A E – отображение, сопоставляющее множеству мгновенных действий множество переходов

Формы математических моделей, которые непосредственно поддерживаются численными методами. Система ДУ первого порядка, разрешенная относительно производных: где – F непрерывная функция в окрестности t 0. Система алгебраических уравнений 0 = G(y, w, t), G - корректна по числу уравнений и структурно не вырождена. А – невырожденная матрица. - система АУ относительно производных корректна. Система дифференциально-алгебраических уравнений индекса 1 в форме Хессенберга. Система дифференциально-алгебраических уравнений индекса 2 в форме Хессенберга. Более удобным является задание непрерывной системы в естественной форме: или

Главное окно приложений MVS

Окно модели

Ввод формул

Временные и фазовые диаграммы

3-D и 2-D анимация, интерактивное вмешательство

Гибридная модель отрывающегося маятника

Компонентное моделирование маятника

AnyLogic AL - это инструментальное средство нового поколения для разработки и исследования имитационных моделей. Программный пакет основан на объектно-ориентированном подходе – лучшем на сегодняшний день методе управления сложностью информации. Модель – набор взаимодействующих, параллельно функционирующих активностей – активных объектов (АО), которые могут включать любое количество других АО, могут динамически порождаться и исчезать. Графическая среда поддерживает проектирование, разработку, документирование модели, проведение компьютерного эксперимента. Визуальное проектирование как принцип разработки моделей. Пакет позволяет разрабатывать модели в соответствии основными парадигмами моделирования – динамические системы, системная динамика, дискретно-событийное моделирование, мультиагентные системы. AL – надстройка над языком Java, фрагменты кода которого используются при разработке компонент моделей.

Окно модели

Структура классов AnyLogic

Таймер, стейтчарт, запись уравнений

Вывод графиков

Окно оптимизации OptQuest

Системная динамика

Агентная модель

Справочные материалы по AnyLogic Карпов Ю.Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5. СПб: БХВ-Петербург с. Борщев А.В. Практическое агентное моделирование и его место в арсенале аналитика //Exponenta Pro, 3-4б 2004

Новые информационные технологии В 80-х годах ХХ века предложен подход, в России получивший название новой информационной технологии [1, 2], на Западе концепции ЭВМ V поколения [3]. 1.Поспелов Г.С. Искусственный интеллект - основа новой информационной технологии. М.: Наука, с. 2.Глушков В.М. Основы безбумажной информатики. М.: Наука, с. 3.Симонс Дж. ЭВМ пятого поколения, компьютеры 90-х годов. М.: Финансы и статистика, с. Суть новой информационной технологии (НИТ) создание программных систем, работающих с конечным пользователем напрямую, минуя посредников в лице математиков и программистов.

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

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

Алгоритмическая сеть (Рис.1(а)) определяется как ориентированный гиперграф без петель при вершинах G(V,X), в котором дуги обозначают модельные переменные x i X, а вершины v j V – функциональные соотношения (операторы), fj F, связывающие модельные значения переменных на интервале времени, соответствующем t [2]. Структура переменных сети X=Xвх Xвых Xвн, где Xвх, Xвых, Xвн – соответственно входные, выходные и внутренние переменные, причем, Xвх Xвых=, Xвх Xвн=, Xвых Xвн=. Формально алгоритмическая сеть (АС) может быть определена следующим образом: AC:= где: P – множество вершин сети, Q – множество дуг сети, Х – множество переменных, при этом X= X i, X i – множество переменных i-ой вершины, I – множество всех индексов вершин, F – множество операторов, P F – изоморфное отображение P на F, Q X – отображение Q на X. Алгоритмические сети

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

P 1 P 2 P 3 P 7 P 4 P 5 P 6 P 1 P 5 P 2 P 6 P 3 P 7 P 4 t P3P3 P3P3 P3P3 P3P3 P3P3 P3P3 P3P3 х6х6 х9х9 х5х5 х 11 х8х8 х 12 х7х7 х4х4 х3х3 х2х2 х1х1 P 1 : х 5 (t)=х 1 +х 2 P 5 : х 6 (t)=х 3 –х 2 P 2 : х 7 =х 5 х 6 P 6 : х 8 =х 6 /х 4 P 3 : х 9 =х 7 +х 12 P 7 : х 11 =х 8 х 7 P 4 : х 1 (t+1)=х 9 (t) б) а) Рис. 2. План вычислений и соответствующая расчетная программа для случая одного процессора (а), план вычислений для случая двух процессоров (б).

Бинарные операции над АС 1. Пересечение АС1 АС2 равно подграфу, состоящему из вершин, совпадающих в обеих сетях. 2. Объединение АС1 АС2 равно пересечению АС и всем остальным вершинам той и другой АС. Особенность операции объединения АС - ее результат пуст, если при объединении нарушается условие однозначности вычисления переменных или возникают контура не содержащих вершин с оператором «задержка». 3. Разность АС1\АС2 равна первой АС без подграфа, соответствующего пересечению исходных АС. Все рассмотренные выше бинарные операции над АС сводятся к аналогичным теоретико-множественным операциям над множествами Fi алгоритмических сетей, над которыми операции выполняются.

Агрегация А{pi}(AC) соответствует замене некоторого подграфа исходной АС одной вершиной содержащей оператор, в котором объединены выражения, соответствующие всем операторам агрегируемого подграфа. Внешние дуги такой вершины соответствуют внешним дугам агрегируемого подграфа. {pi} – множество вершин агрегируемого подграфа. Дезагрегация DApi(AC) операция обратная агрегации, соответствует замене некоторой вершины АС подграфом, построенным на основании выбора выражений, определяющих оператор, приписанный вершине pi. Частичное обращение AC=ObR(AC), результат операции новая АС с множеством входных переменных R. Сеть АС строится путем обращения некоторых из операторов исходной сети на основании R и связей между вершинами. Пример. Исходный оператор х1+х2=х3. Обращение оператора для входных наборов: R=(х1,х3) – набор допустим, обращенный оператор х3-х1=х2; R=(х2) набор недостаточен, обращение невозможно; R=(х1,х2,х3) набор избыточен - оператор переопределен, обращение невозможно. Выделение подграфа по заданным подмножествам входных и выходных дуг AC=S0I(AC)., где 0, I – множество переменных исходной АС, соответствующие которым дуги будут внешними выходными (входными) дугами получаемого подграфа.

Операции объединения и пересечения алгоритмических сетей ассоциативны и дистрибутивны друг относительно друга: (АС1 АС2) АС3=АС1 (АС2 АС3); АС1 АС2) АС3=АС1 (АС2 АС3); (АС1 АС2) АС3=(АС1 АС2) (АС1 АС3); Операция пересечения ассоциативна и дистрибутивна относительно операции пересечения: (АС1\АС2) \АС3=АС1\ (АС2\АС3); (АС1\АС2) АС3=(АС1 АС2) \ (АС1 АС3); (АС1 АС2) \ АС3=(АС1\АС2) (АС1\АС3); Операции пересечения и объединения коммутативны и идемпотентны: АС1 АС2=АС2 АС1, АС1 АС1=АС1, АС1 АС1=АС1. Правила поглощения: (AC1 AC2) AC1=AC1; (AC1\AC2) AC1=AC1; (AC1 AC2) \AC1=AC2; (AC1 AC2) \AC1= ; AC1/AC1= ; (AC1\AC2) AC1=AC1\AC2; (AC1\AC2) AC2=AC1 AC2. Операции с пустой сетью : AC1 = AC1=AC1; AC\ =AC1; \AC1=.

Если считать, что все АС есть подсети всеобщей сети АС, то такая сеть будет единицей для пересечения и нулем для объединения: АС1 АС = АС АС1= АС; АС1 АС = АС АС1= АС1; Дополнение некоторой АС до всеобщей обозначим АС : АС=АС\AC. Свойства дополнения и правило Де Моргана для АС: ( АС)=АС, (АС1 АС2)= АС1 АС2, (АС1 АС2)= АС1 АС2; АС=, АС АС=АС, АС АС=, АС\ АС=AC, АС\AC= АС, АС АС=АС. Множество всех алгоритмических сетей и заданные операции определяют алгебру АС : А= Где {AC} – множество всех возможных АС, - множество операций над АС.

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

Выявление каузальной рассогласованности Выявление каузальной рассогласованности: -построение сокращенного графа причинно-следственных связей на множестве фрагментарных моделей, - переход к древовидному графу, -сравнение цепочек вычисления переменных модели с цепочками событий на графе Ro(x,y) - событие х происходит одновременно с у, R1(x,y) - событие х происходит раньше у, R2(x,y) - событие х происходит не раньше у. у k - общая вычисляемая переменная сетей А и В X1 и Z1 - множества переменных сети А, входящих в конус и дерево вычислимости для у k, X2 и Z2 - множества переменных сети В, входящих в конус и дерево вычислимости для у k. Тогда:R1(X1,y k ), R1(y k,Z1), R1(X1,Z1), R1(X2,y k ), R1(y k,Z2), R1(X2,Z2). Проверка данных соотношений на цепочках событий CT j. Если выполняется условие: ( x X)( z Z)( CT j CT)[(x,z CT j R1(x,z)) (x,yk CTj R1(x,yk)) (yk,z CTj R1(yk,z))], то сеть каузально ориентирована, в противном случае – инверсно ориентирована.

Корректировка моделей Операции корректировки фрагментарных моделей: - каузальное согласование фрагментов с использованием операции обращения для устранения неоднозначности вычисления переменных и восстановления вычислимости, - операции вычитания для устранения неоднозначности вычисления переменных в каузально согласованных фрагментах, - корректировка циклов для устранения «гонок» в комплексной модели. Операция вычитания А В=С. Из сети А удаляются операторы, генерирующие одноименные вычисляемые переменные сетей А и В, а также операторы конусов вычислимости этих переменных, за исключением операторов, генерирующих переменные, которые являются входными для сети В, являются аргументами оставшихся в сети А операторов или имеют статус критериальных. Вместе с операторами удаляются их выходные переменные. В результате обеспечивается взаимная однозначность В и результирующей сети С. Корректировки не-циклов. Особенность процедуры состоит в ее неоднозначности, поскольку статус переменной состояния может быть присвоен различным переменным контура.

Животноводческая ферма Очистные сооружения Поле Озеро Численност ь закупаемых животных Начальны й вес животных Общий прирост биомассы Конечный вес животных Жидкие стоки Кормовые корнеплод ы Органически е удобрения Минеральны е удобрения Жесткая фракция стоков Стоки с полей Вынос фосфора с речным стоком Очищенные стоки Захоронения фосфора в донных отложениях Х11 Х12 Х15 Х10 Х19 Х7Х18 Х1Х1 Х22Х23Х23 Х3 Х26Х26 Х27Х27

Х23 Х1 0 Х1 3 Х1 4 Х1 5 Х1 1 К3Х1 2 Х7 К2К4 Х9 Х1 6 Х1 7 К5 Х1 8 Х1 9 Х2 1 К3 mi n t Х1 8 К4 Х2 0 Х1 Х2 К1 Х3 Х4 Z1Z1Х8 Х6Х2 8 Х5 Х7 Х2 2 t Х2 61 Х2 7 Х2 3 Х3 К7 Х1 9 Х2 5 Z2Z2 Х1 9 К5 Х2 1 К6 Х1 9 Х2 21 Х

X1 Z1 X7 X18 X12 X3 Z2 X22 X19 X23 X26 X27 Минеральны е удобрения Запас фосфора в почве Органически е удобрения Прирост биомассы Кормовые корнеплоды Сток с полей Жесткая фракция стоков Жидкие стоки Запас фосфора в озере Вынос фосфора с речным стоком Захоронение фосфора в донных отложениях Очищенные стоки ПОЛЕ ФЕРМА ОЧИСТКАОЗЕРО

X1 Z1 X7 X1 8 X1 2 X3 Z2 X2 2 X1 9 X2 7 X2 6 Z3Z3 X2 3 X8X8 Z4Z4 X2 5 Х1 0 Х1 3 Х1 4 Х1 5 Х1 1 К3Х1 2 Х7 К2К4 Х9 Х1 6 Х1 7 К4 Х1 8 Х2 1 К3

Методология моделирования на основе АС Концептуальная модель:Язык алгоритмических сетей: Модельные эксперименты:Создание модели:Алгоритмическая сеть модели:

Пример решения задачи методом обращения

Система КОГНИТРОН. Создание модели

Система КОГНИТРОН. Модельный эксперимент