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

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

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

Суть метода состоит в следующем.

Дана задача: максимизировать целевую функцию

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

Разобьем множество Х на непересекающиеся подмножества Х1,Х2,…,Хn. Способ разбиения может быть любым и выбирается исходя из задачи.

Для каждого из подмножеств ищется оценка верхней границы целевой функции на этом подмножестве такая, что для хХi. При этом для всех i=.

Выбирается подмножество ХI, для которого значение I=max{}, как наиболее перспективное для организации дальнейшего поиска оптимального решения.

На этом подмножестве по определенному правилу ищется т. x'XI, для которой вычисляется значение целевой функции f(x').

Если f(x')= I, то задача решена.

Иначе множество ХIв свою очередь разбивается на подмножества XI1,XI2,…,XIm, для которых ищутся верхние оценкиI1,I2,…,Im.

IоIо=.

Среди всех оценок iI, 1о о= (исключая и I) ищется наилучшая.

Для соответствующего подмножества (ХiiI, или ХIо) ищется точка x''.

Для нее значение целевой функции f(x''). Если оно совпадает с найденной наилучшей оценкой, то решение х*= x'' найдено.

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

Схематически процесс поиска можно представить на рисунке в следующем виде

6. Имитационное моделирование

Модели и методы.

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

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

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

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

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

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

Имитационные модели могут быть реализованы на аналогово-цифровых ЭВМ.

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

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

Классификация имитационных моделей.

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

1. По учету временного фактора они могут быть динамические и статические.

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

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

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

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

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

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

Непрерывные имитационные модели воспроизводят процесс функционирования системы во времени непрерывно, т.е. переменные состояния с изменением модельного времени непрерывно меняются. Т.к. все процессы моделируются на ЦВМ, то фактически время изменяется дискретно с малым шагом t, определяющим точность моделирования. В качестве систем, исследуемых с помощью непрерывных имитационных моделей можно рассматривать некоторые механизмы и электромеханические системы, отдельные объекты, описываемые с помощью систем диф. уравнений (технологические процессы, полет ЛА и т.д.).

В непрерывно-дискретных моделях рассматриваются как дискретные как и непрерывные во времени процессы и явления. Это наиболее универсальные модели, позволяющие промоделировать процессы функционирования систем любой сложности: наприме6р АСУ воздушным движением, где движение отдельного ЛА могут быть описано с помощью системы дифференциальных уравнений, а выработка диспетчерами управляющих команд и их передача на борт ЛА требует дискретного описания.

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

2. По учету случайных факторов имитационные модели делятся на детерминированные и стохастические.

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

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

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

Очевидно, что чем больше при этом мы имеем случайных реализаций, тем выше ( в статистическом смысле ) точность получаемых оценок ( точность оценок ~ 1/ N, здесь N - число реализаций ).

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

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

В основе стохастического имитационного моделирования лежит метод статистического моделирования, получивший название метода Монте-Карло.

7. Этапы проведения имитационных исследований. Процесс имитационного моделирования

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

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

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

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

В противном случае ( отсутствие информации о функционировании реальных систем ) оценка адекватности сводятся к проверкам двух видов: «верификации моделей» и «проверка правильности исходных «посылок», заложенных в модель».

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

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

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

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

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

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

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

Конструирование имитационной модели.

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

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

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

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

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

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

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

В самом сценарии приводится содержательное описание развертывания процесса функционирования моделируемой системы и внешней среды во времени.

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

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

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

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

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

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

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

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

Другим важным принципом формализации является принцип баланса точности, включающий в себя:

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

- соответствие точностей отдельных элементов модели;

- соответствие систематической и статистической погрешностей моделирования.

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

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

- для СМО - выделение источников заявок, очередей, каналов обслуживания;

- в сетевых моделях - выделения работ, событий, ресурсов и др.

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

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

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

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

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

- функциональные (например, изменение координат ЛА во время полета от скорости, ускорений и начального положения его в пространстве);

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

- алгоритмические (например, переключение станка на соответствующий режим работы при определенном сочетании материала, инструмента, числа оборотов и т. д. ).

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

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

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

Агрегативный подход к формализации.

При агрегативном подходе модель представляется в виде нескольких взаимосвязанных математических объектов - агрегатов, отображающих различные части моделируемой системы и внешней среды и задаваемых в виде устройств, преобразующих поступивший на него входной сигнал x X в входной сигнал у У и изменяющей своё состояние z Z.

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

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

A1 - источник заявок

A2 - очередь

A3 - канал обслуживания.

Через обратную связь от А3 к А2 поступает информация об освобождении канала при окончании обслуживания заявки.

Событийный подход к формализации

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

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

Для каждого модельного события задаются:

смысловая формулировка;

код (целое, положительное число, использующееся для идентификации события);

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

условия появления события;

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

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

Пример: рассматривается простейшая одноканальная СМО с ограничением на время ожидания заявки в очереди Т.

Для моделирования такой СМО можно задать следующие временные модельные события:

С1 - вход заявки в СМО (код=1);

С2 - потеря заявки из очереди (код=2);

С3 - окончание обслуживания заявки (код=3).

Блок-схемы алгоритмов обработки этих событий имеют вид:

Обработка события К=1

8. Методы продвижения модельного времени

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

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

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

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

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

Существуют специальные языки и системы имитационного моделирования (например, GASP-1V, GPSS, LISP), в которых реализованы специальные средства организации продвижения модельного времени для непрерывных, дискретных и непрерывно-дискретных систем. В том числе разработанная на кафедре СИСТЕМА ИММИТАЦИОННОГО МОДЕЛИРОВАНИЯ (СИМ), зарегистрированная в РОСПАТЕНТЕ.

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

Метод модельных событий.

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

Все события из “ближайшего будущего” называются совокупностью будущего событий (СБС). События из СБС с наименьшим временем появления tk называется критическим.

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

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

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

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

Достоинство метода - обеспечение любой требуемой точности по регистрации времени наступления событий.

Недостаток - достаточно сложные вычислительные процедуры при работе со списком событий.

Метод фиксированного шага.

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

Более подробно вопросы построения ИМ изложены в работах по имитационному моделированию и будут изучены, в дальнейшем, в отдельном курсе «ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ».

Хахулин Г.Ф. «основы конструирования имитационных моделей» Учебное пособие. М.: НПК «Поток», 2002.

Полляк Ю. Г. “Вероятностное моделирование на ЭВМ” 1971.

Шеннон Р. “Имитационное моделирование искусство и наука” Мир 1978.

Клейнен Д. “Статистические методы в имитационном моделировании” 1978.

Бусленко Н. П. “Моделирование сложных систем” Москва Наука 1978.

И др.

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

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

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

· произошло или нет некоторое событие А;

· какое из событий А1…Аn произошло;

· какое значение приняла С.В.Х и т.д.

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

Розыгрыш “жребия” по любому из законов распределения базируется на розыгрыше случайных чисел R, распределенных равномерно на интервале [0,1], имеющих закон распределения вида

Существуют специальные программы (т.н. датчики случайных чисел), формирующие последовательности чисел, обладающие свойствами случайных величин, равномерно распределенных в интервале [0,1] и удовлетворяющих статистическим тестам. Они основаны, как правило, на рекурсивных процедурах. Например, перемножение двух n-значных различных чисел с последующим формированием на основе результатов перемножения нового числа, которое используется для получения последующего числа и т.д. полученные таким образом числа на самом деле не являются случайными (псевдослучайные) и повторяются с некоторой периодичностью. Однако параметры такой процедуры можно подобрать таким образом, что период повторения будет достаточно большим.

Так, например, на ЭВМ часто используется п/п функция URANP.

Для получения с помощью нее случайного числа R, распределенного по равном. закону на интервале [0,1] достаточно один раз задать начальные значения IX=_____(INT*4) и обратиться

R = URAND (IX) Далее значения IX обновляются самостоятельно.

Розыгрыш события А.

Для того, чтобы разыграть факт появления события А с вероятностью Р необходимо с помощью ДСИ разыграть случайное число R, равномерно распределённое на интервале [0, 1].

Если полученное значение r будет Р, то считаем, что событие А произошло. В противном случае (r > P) - А не произошло.

Розыгрыш группы несовместных событий.

Пусть в результате одного опыта может произойти n несовместных событий А1, А2, …, АN с вероятностями Р1, Р2, …, РN; Pi=1

Разобьём интервал [0, 1] на непересекающиеся участки длиной Рi:

Сгенерируем случайное число R=r. Тогда на какой из участков это число r попадёт, такое событие и считаем произошедшим.

Розыгрыш случайной вершины с заданным законом распределения.

Розыгрыш значений для дискретной случайной вершины аналогичен розыгрышу группы несовместных событий, если в качестве события Аi принять факт, что случайная вершина Х приняла значение, равное хi.

Остановимся более подробно на розыгрыше случайной величины Х (непрерывной) с заданным законом распределения f(x).

Существуют различные способы генерации. Все они в качестве основы используют последовательность чисел R, распределённых равномерно на интервале [0, 1].

Рассмотрим один из этих способов - метод обратной функции:

Пусть необходимо сгенерировать случайную вершину Х, имеющую функцию плотности распределения f(x). Найдём для неё функцию распределения:

F(x) = f(x) dx

По функции распределения вида y = F(x) найдём обратную ей функцию:

x=(y)=F-1(y)

Разыграем случайную вершину R=r и подставим это значение в обратную функцию . Тогда найденное значение X = (r) = F-1(r) будет подчинено заданному закону распределения f(x), F(x).

Пример 1. Получение случайной величины Х, равномерно распределенной в интервале [A, B].

Запишем выражение для f(x) и F(x)

f(x) = F(x) =

Найдем функцию , обратную функции распределения F(x).

X= (y) = F-1(y) = y*(B-A)+A; X = R(B-A)+A

Сгенерировав значение R=r (например, r=0,6) и подставив его значение в X=(r), получим соответствующее значение х, распределенное по закону f(x).

Пример 2. Получение случайной величины Х, распределенной по экспоненциальному закону распределения.

f(x) = * e - x , x 0

F(x) = 1 - e - x , x 0

Обратная функция будет.

Y= 1-e - x

X= (y) = (- 1/)*ln(1-y), x= (- 1/)*ln(1-R)

Поставив вместо у случайную величину R=r, получим Х, распределенный по экспоненциальному закону.

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

Рассмотрим отдельно способ генерации случайной величины Х, распределённой по нормальному закону с параметрами mX и DX.

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

Тогда получаем:

Y = ri

i=1

Где Y - нормально распределённая случайная величина с

mY=12*(1/2)=6 и DY=12*(1/12)=1

Чтобы получить случайную величину Х с заданными параметрами mX и X величину Y преобразуют по формуле:

X = mX + X(Y-6) = mX + X ( ri - 6).

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

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

Обработка результатов моделирования

Как в мат.статистике по множеству реализаций СВ!!!!!

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

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

или по

S2 =

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

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

,

где Wi - значение показателя в i-й реализации при некоторых фиксированных значениях переменной .

Дисперсии

и пр., а также соответствующие им доверительные интервалы

для м.о.

I= [wmin , wmax],

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

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

Например: разыгрывая в одной реализации случайное событие А по значению случайной величины R (равномерно распределенной на [0,1]), а в другой - по значению (1-R) для одного и того же стартового числа ДСЧ. Или проводя дополнительные эксперименты с еще одной, менее детальной моделью, и используя согласованность их результатов.

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

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

,

где - случайное значение показателя W в -м наблюдении за реальной системой.

- среднее значение показателя в точке .

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

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

здесь: wiM, wic - значения показателя w, найденные на модели и реальной системе в соответствующих точках .

По значениям и ищется дисперсионное отклонение.

F=

и соответствующее заданному уровню значимости q, числу степеней свободы rад=N-1 и r0= m-1 критическое значение Fкр. Если вычисленное F<Fкр, то модель считается адекватной.

Величину Fкр ищут из таблиц F-распределения (часто путают распределение Фишера).

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

10. Исследование эффективности сложных технических систем

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

Сложность этих задач при исследовании эффективности СТС определяется следующими причинами:

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

Большое число управляемых переменных, как непрерывных, так и дискретных и, как следствие, высокая размерность оптимизационных задач (до n*1000 переменных)

Векторный показатель эффективности СТС.

Все это вместе взятое приводит к следующим противоречиям:

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

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

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

Эти модели можно условно разбить на 3 группы (уровня):

Модели первого (верхнего) уровня

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

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

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

Модели второго (среднего) уровня.

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

Модели третьего (нижнего) уровня.

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

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

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

На 2-м этапе, используя настроенные модели 1-го уровня, ищутся оптимальные (или близкие к ним) значения глобальных переменных Х0. В качестве оптимизируемого показателя используется векторный критерий эффективности СТС .

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

На 3-ем этапе для найденных оптимальных значений глобальных переменных Х0 ищутся соответствующие им оптимальные значения внутренних (локальных) переменных y(х0). Для этого применяются оптимизационные модели второго уровня.

Затем, на 4-м этапе при найденных оптимальных (близких к ним) значениях глобальных х0 и локальных у0 переменных с использованием детальных моделей 3-го уровня определяются значения показателей эффективности СТС с учетом всех факторов, действующих на систему.

Учитывая грубость моделей 1-го и 2-го уровней, используемых при поиске оптимальных решений необходимо произвести уточнение полученных решений. Для этого проводятся дополнительные исследования эффективности СТС в окрестности найденного решения (х0, у0). В результате среди полученных вариантов выбираются наилучшие с точки зрения ЛПР решения с учетом всех факторов, не поддающихся формализации.

Важно: решение - выбор вида оптимальных моделей на 1-м уровне. Проблема - регрессия модели - настраивается, но не очень точно описывает всю область.

Поиск решений в задачах ИО.

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

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

...