Непрерывно-детерминированные модели (D-схемы)

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

.

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

.

где – состояние системы; – детерминированное входное воздействие; – выходная реакция системы. Так как математические схемы такого вида отражают динамику изучаемой системы, т. е. ее поведение во времени, то они называются D-схемами (англ, dynamic system).

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

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

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

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

9.2. Дискретно-детерминированные модели (F -схемы)

При реализации данного подхода характерным является отсутствие возмущений стохастического характера и описание процессов преобразования информации в дискретном времени. Данный подход наиболее тесно связан с использованием типовой математической схемы конечного автомата (finit automat), еще называемой F -схемой. Абстрактный конечный автомат характеризуется тем, что множества значений входных воздействий X, внутренних состояний Z и выходных реакций Y являются конечными:

и имеют, соответственно, I, J, К элементов. Функционирование конечного автомата осуществляется в дискретные моменты времени t = 0,1,2,... Процесс преобразования информации в автомате описывается с помощью двух отображений вида

В начальный момент t₀ = 0 автомат находится в состоянии z( 0) = z ₀. Далее работа конечного автомата осуществляется по следующей схеме: в каждом t -м такте на вход автомата, находящегося в состоянии z{t), подается некоторый сигнал x(t), который приводит к изменению состояния z(t + 1) на новом (t +1) -м шаге и одновременно к выдаче выходного сигнала. Сказанное можно описать следующими уравнениями:

− для автомата первого рода, называемого также автоматом Мили,

− для автомата второго рода

Автомат, у которого , называется автоматом Мура.

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

Таким образом, Τ’-схема определяется совокупностью данных

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

Рисунок 9.1 – Форма таблиц переходов и выходов

Другой распространенный способ задания конечного автомата основан на использовании аппарата направленных графов. Вершины графа (рисунок 9.2) соответствуют состояниям, а дуги – возможным переходам под воздействием тех или иных входных сигналов. Для автомата Мили дуги дополнительно помечаются значениями выхода , реализуемого при подаче воздействия x_i в состоянии z_k. Для автомата Мура значениями выхода помечают вершины графа.

Рисунок 9.2 – Граф переходов и выходов автомата Мили

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

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

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

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

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

9.3. Дискретно-стохастические модели (P -схемы)

Данный подход характеризуется стохастическим характером процессов преобразования информации при сохранении дискретного во времени описания этих процессов. Типовой математической схемой в данном случае является схема вероятностного автомата, или Р -схема (probabilistic automat). P -автомат также определяется множествами значений входных воздействий – X, состояний – Z, выходных реакций – Y, имеющих конечное число элементов. Однако в отличие от F -автомата, в котором все переходы осуществляются однозначно, в данном случае реализуется вероятностный характер переходов: из каждого состояния под воздействием входного сигнала х_k (t) могут осуществляться переходы во все состояния { z_j (t +1)} с определенными вероятностями . Таким образом, P -схему можно рассматривать как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и должно быть описано статистически. В общем случае Р -автоматом называется объект, определяемый четверкой

,

где – семейство I×К матриц размерности J × J. Элементы каждой матрицы В определяются как условные вероятности переходов

,

т. е. событий, состоящих в том, что, находясь в состоянии z_i и получив сигнал х_r, объект переходит в состояние z_j с одновременной выдачей сигнала у_р. Для описания функционирования конкретного автомата должна быть задана совокупность – вероятностей начальных состояний z (0) для момента времени t₀. Если выполняется

,

то говорят, что реализуется вероятностный автомат Мили. Если выполняется

везде, где вероятность , то говорят, что реализуется вероятностный автомат Мура.

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

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

где – непрерывнозначные переменные; – независимые в дискретном времени случайные последовательности с известными вероятностными характеристиками, определяющие возмущения состояний и выходов. Для z₀ в данном случае задается начальное распределение P₀ (z₀). Стохастические конечно-разностные уравнения используются для моделирования объектов в цифровых системах управления при наличии возмущений и помех в каналах управления и наблюдения за состояниями управляемых объектов.

9.4. Непрерывно-стохастические модели (Q -схемы)

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

В качестве стандартного объекта в данном случае рассматривается элементарный прибор обслуживания (ЭПО), который, как это показано на рисунке 9.3, состоит из накопителя (Н) заявок и канала (К) обслуживания (сервера).

Рисунок 9.3 – Схема элементарного прибора обслуживания

На вход ЭПО поступает поток событий (заявок), каждая реализация которого представляет последовательность моментов времени t_n и признаков событий f_n, n = 0, 1, 2,... Кроме того, в ЭПО действует поток обслуживания , каждая реализация которого является подмножеством управляемых переменных и характеризует моменты времени обслуживания заявок t_m и признаки их обслуживания в К. На выходе ЭПО образуется поток заявок, обслуженных в К, или покинувших прибор по разным причинам не обслуженными (например, из-за переполнения Н). Предельная емкость накопителя задается величиной L_H.

Процесс функционирования ЭПО можно представить как процесс изменения его внутренних состояний. Вектор состояний состоит из двух компонентов , где – состояние накопителя (z^H =0 – накопитель пуст, z^H = 1 – в накопителе одна заявка и т. д.); z^K – состояние канала обслуживания (z^K = 0 – канал свободен, z^K = 1 – канал занят).

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

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

Таким образом, стандартная Q -схема описывается набором данных:

.

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

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

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

,

где – случайные многомерные процессы типа белого шума с известными статистическими характеристиками; q(z,t) – матричная функция известного вида. Для z₀ = z(0) аналогично задается начальное распределение . Видно, что данная схема отличается от D -схемы добавлением случайной составляющей возмущения состояния ξ(t) и влиянием случайного воздействия ν (t) (шума наблюдения) на выходе. Подобные схемы также широко используются при синтезе систем оптимального управления, а также измерительных систем, взаимодействующих с недетерминированными объектами.

9.5. Сетевые модели (N -схемы)

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

Сеть Петри задается пятеркой вида:

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

Таким образом, для каждого перехода можно определить множество входных (input) позиций I(d_j) и выходных (output) позиций O(d_j) как

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

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

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

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

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

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

Рисунок 9.4 – Графическое изображение Ν-схемы

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

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

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

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

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