Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Основные подходы к построению математических моделей систем


Математические схемы моделирования систем

Достоинства и недостатки имитационного моделирования

Основные достоинства имитационного моделирования при исследовании сложных систем:

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

· за счет применения ЭВМ существенно сокращается продолжительность испытаний по сравнению с натурным экспериментом;

· результаты натурных испытаний реальной системы или ее частей можно использовать для проведения имитационного моделирования;

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

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

Основные недостатки имитационного моделирования:

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

· большие затраты машинного времени.

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

Эффективность имитационного моделирования может оцениваться рядом критериев:

· точностью и достоверностью результатов моделирования,

· временем построения и работы с моделью М,

· затратой машинных ресурсов (время и память),

· стоимостью разработки и эксплуатации модели.

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

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

 

 

 

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



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

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

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

· совокупность входных воздействий на систему

xi = X, i = ;

· совокупность воздействий внешней среды

vj = V, j = ;

· совокупность внутренних (собственных) параметров систем

hk = H, k = ;

· совокупность выходных характеристик системы

yj = Y, j = .

В общем случае xi, vj, hk, yj являются элементами непересекающихся подмножеств и содержат как детерминированные, так и стохастические составляющие.

Входные воздействия, воздействия внешней среды Е и внутренние параметры системы являются независимыми (экзогенными) переменными, которые в векторной форме имеют соответственно вид (t) = (x1(t), x2(t), …, xnX(t)); (t) = (v1(t), v2(t), …, vnV(t)); (t) = (h1(t), h2(t), …, h(t)), а выходные характеристики являются зависимыми (эндогенными) переменными и в векторной форме имеют вид: (t) = (у1(t), у2(t), …, уnY(t)). Можно выделить управляемые и неуправляемые переменные.

Процесс функционирования системы S описывается во времени оператором FS, который преобразует экзогенные переменные в эндогенные в соответствии с соотношениями вида

(t) = FS(,,, t). (2.1)

Совокупность зависимостей выходных характеристик системы от времени yj(t) для всех видов j = называется выходной траекторией (t). Зависимость (2.1) называется законом функционирования системы FS, который задается в виде функции, функционала, логических условий, в алгоритмической, табличной формах или в виде словесного правила соответствия. Алгоритмом функционирования AS называется метод получения выходных характеристик с учетом входных воздействий (t), воздействий внешней среды (t) и собственных параметров системы (t). Один и тот же закон функционирования FS системы S может быть реализован различными способами, т.е. с помощью множества различных алгоритмов функционирования AS.

Математические модели называются динамическими (2.1), если математические соотношения описывают поведение объекта (системы) моделирования во времени t, т.е. отражают динамические свойства.

Для статических моделей математическая модель представляет собой отображение между двумя подмножествами свойств моделируемого объекта Y и {X, V, H} в определенный момент, что в векторной форме может быть записано как

= f(,,). (2.2)

Соотношения (2.1) и (2.2) могут быть заданы различными способами: аналитически (с помощью формул), графически, таблично и т.д. Эти соотношения могут быть получены через свойства системы S в конкретные моменты времени, называемые состояниями. Состояние системы S характеризуется векторами

' = (z'1, z'2, …, z'k) и '' = (z''1, z''2, …, z''k),

где z'1 = z1(t'), z'2 = z2(t'), …, z'k = zk(t') в момент t' Î (t0, T); z''1 = z1(t''), z''2 = z2(t''), …, z''k = zk(t'') в момент t'' Î (t0, T) и т.д. k = .

Если рассматривать процесс функционирования системы S как последовательную смену состояний z1(t), z2(t), …, zk(t), то они могут быть интерпретированы как координаты точки в k-мерном фазовом пространстве. Причем каждой реализации процесса будет соответствовать некоторая фазовая траектория. Совокупность всех возможных значений состояний {} называется пространством состояний объекта моделирования Z, причем
zk Î Z.

Состояния системы S в момент времени t0 < t* £ T полностью определяются начальными условиями 0 = (z01, z02, …, z0k) [где z01 = z1(t0),
z02 = z2(t0), …, z0k = zk(t0)], входными воздействиями (t), внутренними параметрами (t) и воздействиями внешней среды (t), которые имели место в промежутке времени t*t0, c помощью двух векторных уравнений

(t) = Ф(0, , , , t); (2.3)

(t) = F(, t). (2.4)

Первое уравнение по начальному состоянию 0 и экзогенным переменным , , определяет вектор-функцию (t), а второе по полученному значению состояний (t) – эндогенные переменные на выходе системы (t). Таким образом, цепочка уравнений объекта «вход – состояния – выход» позволяет определить характеристики системы

(t) = F[Ф(0, , , , t)]. (2.5)

В общем случае время в модели системы S может рассматриваться на интервале моделирования (0, Т) как непрерывное, так и дискретное, т.е. квантованное на отрезки длиной Dt временных единиц каждый, когда T = mDt, где m = – число интервалов дискретизации.

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

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

(t) = f(, t). (2.6)

Очевидно, что детерминированная модель является частным случаем стохастической модели.

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

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

Таким образом, при построении математических моделей процессов функционирования систем можно выделить следующие основные подходы: непрерывно-детерминированный (D-схемы); дискретно-детерминированный (F-схемы); дискретно-стохастический (Р-схемы); непрерывно-стохастический (Q-схемы); сетевой (N-схемы); обобщенный или универсальный (а-схемы).

 

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

 

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

Математическое соотношение для детерминированных систем (2.6) в общем виде будет

'(t) = (, t); (t0) = 0, (2.7)

где ' = d/dt, = (y1, y2, …, yn) и = (f1, f2, …, fn) – n-мерные векторы; (, t) – вектор-функция, которая определена на некотором (n+1)-мерном (, t) множестве и является непрерывной.

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

В простейшем случае обыкновенное дифференциальное уравнение имеет вид:

y'(t) = f (y, t). (2.8)

Рассмотрим простейший пример формализации процесса функционирования двух элементарных схем различной природы: механической SM (колебание маятника, рис.2.1, а) и электрической SK (колебательный контур, рис.2.1, б).

а б

 
 

 


Рис. 2.1. Элементарные системы

 

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

mMlM2(d2F(t)/dt2) + mMglMF(t) = 0,

где mM, lM – масса и длина подвеса маятника; g – ускорение свободного падения; F(t) – угол отклонения маятника в момент времени t.

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

TM = 2p.

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

LK(d2q(t)/dt2) + (q(t)/CK) = 0,

где LK, CK – индуктивность и емкость конденсатора; q(t) – заряд конденсатора в момент времени t.

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

TM = 2p.

Очевидно, что введя обозначения h2 = mMlM2 = LK, h1 = 0,
h0 = mMglM = 1/CK, F(t) = q(t) = z(t), получим обыкновенное дифференциальное уравнение второго порядка, описывающее поведение этой замкнутой системы:

h2(d2z(t)/dt2) + h1(dz(t)/dt) + h0z(t) = 0, (2.9)

где h0, h1, h2 – параметры системы; z(t) – состояние системы в момент
времени t.

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

Если изучаемая система S (маятник или контур) взаимодействует с внешней средой Е, то появляется входное воздействие x(t) (внешняя сила для маятника и источник энергии для контура), и непрерывно-детерминированная модель такой системы будет иметь вид:

h2(d2z(t)/dt2) + h1(dz(t)/dt) + h0z(t) = x(t). (2.10)

С точки зрения общей математической модели (см. п. 2.1) x(t) является входным (управляющим) воздействием, а состояние системы S в данном случае можно рассматривать как выходную характеристику, т.е. выходная переменная совпадает с состоянием системы в данный момент времени y = z.

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

(2.11)

где , ,…, – неизвестная функция времени и ее производные; и – известные функции.

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

, (2.12)

где – некоторая искомая функция времени на отрезке [0; Т] при нулевых начальных условиях, примем h3=1, h2=3, h1=1, h0=3:

. (2.13)

Представив заданное уравнение относительно наивысшей из производных, получим уравнение

, (2.14)

которое можно промоделировать, используя набор стандартных блоков пакета VisSim: арифметические блоки – Gain (умножение на константу), Summing-Junction (сумматор); блоки интегрирования – Integrator (численное интегрирование), Transfer Function (задание уравнения, представленного в виде передаточной функции); блоки задания сигналов – Const (константа), Step (единичная функция в виде «ступеньки»), Ramp (линейно нарастающий сигнал); блоки-приемники сигналов – Plot (отображение во временной области сигналов, которые анализируются исследователем в ходе моделирования).

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

Частным случаем динамических систем, описываемых D-схемами, являются системы автоматического управления (САУ) и регулирования (САР). Реальный объект представляется в виде двух систем: управляющей и управляемой (объекта управления). Структура многомерной системы автоматического управления общего вида представлена на рис. 2.3, где обозначены эндогенные переменные: (t) – вектор входных (задающих) воздействий; (t) – вектор возмущающих воздействий; '(t) – вектор сигналов ошибки; ''(t) – вектор управляющих воздействий; экзогенные переменные: (t) – вектор состояния системы S; (t) – вектор выходных переменных, обычно (t) = (t).

 

 

Рис. 2.2. Графическое представление уравнения

 

Управляющая система – это совокупность программно-технических средств, обеспечивающих достижение объектом управления определенной цели. Насколько точно объект достигает заданной цели, можно судить (для одномерной системы) по координате состояния y(t). Разность между заданным yзад(t) и действительным y(t) законом изменения управляемой величины есть ошибка управления '(t) = yзад(t) – y(t). Если предписанный закон изменения управляемой величины соответствует закону изменения входного (задающего) воздействия, т.е. x(t) = yзад(t), то '(t) = x(t) – y(t).

Системы, для которых ошибки управления '(t) = 0 во все моменты времени, называются идеальными. На практике реализация идеальных систем невозможна. Задачей системы автоматического управления является изменение переменной y(t) согласно заданному закону с определенной точностью (с допустимой ошибкой). Параметры системы должны обеспечивать требуемую точность управления, а также устойчивость системы в переходном процессе. Если система устойчива, то анализируют поведение системы во времени, максимальное отклонение регулируемой переменной y(t) в переходном процессе, время переходного процесса и т.п. Порядок дифференциального уравнения и значение его коэффициентов полностью определяются статическими и динамическими параметрами системы.

 
 

 

 


Рис. 2.3. Структура системы автоматического управления:

УC – управляющая система; OУ – объект управления

 

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

 

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

 

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством Х входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z0, z0 Î Z; функцией переходов j(z, x); функцией выходов y(z, x). Автомат, задаваемый F-схемой: F = áZ, X, Y, y, j, z0ñ, функционирует в дискретном времени, моментами которого являются такты, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-му такту при t = 0, 1, 2, …, через z(t), x(t), y(t). При этом по условию z(0) = z0, а z(tZ, x(tX, y(tY.

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, … дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0) = z0. В момент t, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(tX и выдать на выходном канале сигнал y(t) = y[z(t), x(t)], переходя в состояние z(t+1) = j[z(t), x(t)], z(t Z, y(tY. Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного
алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z0, подавать в некоторой последовательности буквы входного алфавита x(0), x(1), x(2), …, т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1), y(2), …, образуя выходное слово.

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

z(t+1) = j[z(t), x(t)], t = 0, 1, 2, …; (2.15)

y(t) = y[z(t), x(t)], t = 0, 1, 2, …; (2.16)

для F-автомата второго рода

z(t+1) = j[z(t), x(t)], t = 0, 1, 2, …; (2.17)

y(t) = y[z(t), x(t – 1)], t = 1, 2, 3,…. (2.18)

Автомат второго рода, для которого

y(t) = y[z(t)], t = 0, 1, 2, …, (2.19)

т.е. функция выхода не зависит от входной переменной x(t), называется автоматом Мура.

Таким образом, уравнения (2.15)-(2.19), полностью задающие
F-автомат, являются частным случаем уравнений (2.3) и (2.4), когда
система S – детерминированная и на её единственный вход поступает дискретный сигнал X.

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

y(t) = y[ x(t)], t = 0, 1, 2, … .

Эта функция называется булевой, если алфавит X и Y, которым принадлежат значения сигналов x и y, состоят из двух букв.

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных F-автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учетом «считанного» и в соответствии с уравнениями (2.15)-(2.19) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Таким образом, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами. Асинхронный F-автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины x, он может, как следует из (2.15)-(2.19), несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое, которое уже не может быть изменено данным входным сигналом.

Возможные приложения F-схемы.Чтобы задать конечный F-автомат, необходимо описать все элементы множества F = <Z, X, Y, y, j, z0>, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z0, в котором автомат находится в состоянии t = 0. Существуют несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный.

В табличном способе задаются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый слева столбец соответствует начальному состоянию z0. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение j(zk, xi) функции переходов, а в таблице выходов – соответствующее значение y(zk, xi) функции выходов. Для F-автомата Мура обе таблицы можно совместить.

Описание работы F-автомата Мили таблицами переходов j и выходов y иллюстрируется табл. 2.1, а описание F-автомата Мура – таблицей переходов (табл. 2.2).

Таблица 2.1

Xi zk
z0 z1 zk
Переходы
x1 j(z0, x1) j(z1, x1) j(zk, x1)
x2 j(z0, x2) j(z1, x2) j(zk, x2)
xi j(z0, xi) j(z1, xi) j(zk, xi)
Выходы
x1 y(z0, x1) y(z1, x1) y(zk, x1)
x2 y(z0, x2) y(z1, x2 ) y(zk, x2)
xi y(z0, xi) y(z1, xi) y(zk, xi)

Таблица 2.2

xi y(zk)
y(z0) y(z1) y(zk)
z0 z1 zk
x1 j(z0, x1) j(z1, x1) j(zk, x1)
x2 j(z0, x2) j(z1, x2) j(zk, x2)
xi j(z0, xi) j(z1, xi) j(zk, xi)

Примеры табличного способа задания F-автомата Мили F1 приведены в табл. 2.3, а для F-автомата Мура F2 – в табл. 2.4.

Таблица 2.3

xi zk
z0 z1 z2
Переходы
x1 z2 z0 z0
x2 z0 z2 z1
Выходы
x1 y1 y1 y2
x2 y1 y2 y1

Таблица 2.4

  Y
xi y1 y1 y3 y2 y3
  z0 z1 z2 z3 z4
x1 z1 z4 z4 z2 z2
x2 z3 z1 z1 z0 z0

При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi c вершиной zj, обозначается xk. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал xk действует на состояние zi, то получается дуга, исходящая из zi и помеченная xk; эту дугу дополнительно отмечают выходным сигналом y = y(zi, xk). Для автомата Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние автомата, вызывает переход в состояние zj, то дугу, направленную в zi и помеченную xk, дополнительно отмечают выходным
сигналом y = y(zj, xk).

На рис. 2.4. а, б приведены заданные ранее таблицами F-автоматы Мили F1 и Мура F2 соответственно.

a

 

 

 
 


б

 

 

Рис. 2.4. Графы автоматов а – Мили и б – Мура

При матричном задании конечного автомата матрица соединений автомата квадратная С=||сij||, строки соответствуют исходным состояниям, а столбцы – состояния перехода. Элемент сij = xk/ys, стоящий на пересечении
i-й строки и j-го столбца, в случае автомата Мили соответствует входному сигналу xk, вызывающему переход из состояния zi в состояние zj, и выходному сигналу ys, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:

x2 / y1 x1 / y1

C1= x1 / y1x2 / y2 .

x1 / y2 x2 /y1

Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар «вход-выход» для этого перехода, соединенных знаком дизъюнкции.

Для F-автомата Мура элемент сij равен множеству входных сигналов на переходе (zi,zj), а выход описывается вектором выходов

y(z0)

y(z1)

……

= y(zk) ,

……

y(zK)

i-я компонента которого – выходной сигнал, отмечающий состояние zi.

Для рассмотренного выше F-автомата Мура F2 матрицы соединений и вектор выходов имеют вид:

x1 x2 у1

x2 x1 у1

C2 = x2 x1 ; = у3

x2 x1 у2

x2 x1 у3

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

Для F-автомата состояние zk называется устойчивым, если для любого входа xiÎX, для которого j(zk, xi) = zk , имеет место j(zk,xi) = уk. F-автомат называется асинхронным, если каждое его состояние zkÎZ устойчиво.

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

 

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

 

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

Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi, zs), где xi и zs – элементы входного подмножества Х и подмножества состояний Z соответственно. Если существуют две такие функции j и y, что с их помощью осуществляются отображения G®Z и G®Y, то говорят, что F = <Z, X, Y, j, y> определяет автомат детерминированного типа.

Рассмотрим более общую математическую схему. Пусть
Ф – множество всевозможных пар вида (zk, yi), где уi – элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:

Элементыиз Ф (z1, y2) (z1, y2) . . . (zk, yJ-1) (zK, yJ)
(xi, zs) b11 b12 . . . bK(J-1) bKJ

При этом bkj = 1, где bkj – вероятности перехода автомата в состояние zk и появления на выходе сигнала yj , если он был в состоянии zs и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P = <Z, X, Y, B> называется вероятностным автоматом
(Р-автоматом).

Возможные приложения P-схемы.Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, что можно представить соответственно в виде:

Элементыиз Y y1 y2 . . . yJ-1 yJ
(xi, zs) q1 q2 . . . qJ-1 qJ
Элементыиз Z z1 z2 . . . zK-1 zK
(xi, zs) z1 z2   zK-1 zK

При этом zk = 1 и qj = 1, где zk и qj - вероятности перехода
Р-автомата в состояние zk и появления выходного сигнала yk при условии, что
Р-автомат находился в состоянии zs и на его вход поступил входной сигнал xi.

Если для всех k и j имеет место соотношение qj zk = bkj, то такой
Р-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.

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

Элементыиз Y y1 y2 . . . yK-1 yK
zk s1 s2 . . . sI-1 sI

Здесь si = 1, где si – вероятность появления выходногосигнала yi при условии, что Р-автомат находился в состоянии zk.

Если для всех k и i имеет место соотношение zk si = bki ,то такой
Р-автомат называется вероятностным автоматом Мура. Понятие
Р-автоматов Мили и Мура введено по аналогии с детерминированным
F-автоматом. Частным случаем Р-автомата, задаваемого как P=<Z, X, Y, B>, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал
Р-автомата определяется детерминированно, то такой автомат называется
Y-детерминированным вероятностным автоматом. Аналогично,
Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

Пример 2.1.Пусть задан Y-детерминированный P-автомат

На рис. 2.5 показан ориентированный граф переходов этого автомата. Вершины графа сопоставляются состояниям автомата, а дуги – возможными переходами из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода pij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями. Требуется оценить суммарные финальные вероятности пребывания этого P-автомата в состояниях z2 и z3.

 

 

Рис. 2.5. Граф вероятностного автомата

 

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

где сk – финальная вероятность пребывания Р-автомата в состоянии zk.

Получаем систему уравнений

Добавим к этим уравнениям условие нормировки с1 + с2 + с3 + с4 = 1. Тогда, решая систему уравнений, получим с1 = 5/23, с2 = 8/23, с3 = 5/23,
с4 = 5/23. Таким образом, с2 + с3 = 13/23 = 0,5652. Другими словами, при бесконечной работе заданного в этом примере Y-детерминированного
Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.

Подобные Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е.

 

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

 

Основные соотношения. Особенности непрерывно-стохастического подхода рассмотрим на примере типовых математических Q-схем – систем массового обслуживания (англ. queueing system).

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

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью {tn} = {0 £ t1 £ t2 ... £ tn £ }, где tn момент наступления п-го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между п-м и (n – 1)-м событиями {tn}, которая однозначно связана с последовательностью вызывающих моментов {tn}, где tn = tn tn-1, п ³ 1, t0 = 0, т.е. t1 = t1. Потоком неоднородных событий называется последовательность {tn, fn}, где tn вызывающие моменты; fnнабор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого i-го прибора обслуживания Пi (рис. 2.6), состоящего из накопителя заявок Hi, в котором может одновременно находиться ji = заявок, где LiH емкость
i-гo накопителя, и канала обслуживания заявок (или просто канала) Ki. На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi, на канал Ki поток обслуживаний иi .

 

 
 

 

 


Рис. 2.6. Прибор обслуживания заявок

Заявки, обслуженные каналом Ki, и заявки, покинувшие прибор Пi по различным причинам необслуженными (например, из-за переполнения накопителя Hi), образуют выходной поток yi Î Y, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Обычно, поток заявок wiÎW, т.е. интервалы времени между моментами появления заявок на входе Ki, образует подмножество неуправляемых переменных, а поток обслуживания uiÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.

Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементоввовремени zi(t). Переход в новое состояние для Пi означает изменение количества заявок, которые в нем находятся (в канале Ki и в накопителе Hi). Таким образом, вектор состояний для Пi имеет вид: , где ziH – состояние накопителя Hi (ziH = 0 – накопитель пуст, ziH = 1 – в накопителе имеется одна заявка, ..., ziH = LiH накопитель полностью заполнен); LiH емкость накопителя Нi, измеряемая числом заявок, которые в нем могут поместиться; zikсостояние канала Ki (zik = 0канал свободен, zik = 1 – канал занят).

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

<== предыдущая лекция | следующая лекция ==>
Возможности и эффективность моделирования систем на вычислительных машинах | Методика разработки и машинной реализации моделей систем

Дата добавления: 2014-01-04; Просмотров: 599; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.056 сек.