|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Типовые математические схемы
2.3.1. Непрерывно-детерминированные модели (D–схемы) Использование D –схем позволяет формализовать процесс функционирования непрерывно-детерминированных систем и оценить их основные характеристики. Математические схемы данного вида отражают динамику изучаемой системы, т.е. её поведение во времени, поэтому называются D –схемами (англ. Dynamic System). В качестве непрерывно-детерминированных моделей динамических систем используются дифференциальные уравнения, передаточные функции и описание в пространстве состояний [13]. Дифференциальные уравнения и передаточные функции образуют математические модели вход-выход (модели типа «ВВ»), описывающие связи входных и выходных сигналов динамической системы. Чтобы получить математическое описание динамической системы, необходимо составить дифференциальные уравнения всех элементов, образующих систему. Таким образом, получим систему дифференциальных уравнений, описывающую исследуемую систему. Полученная система дифференциальных уравнений путём исключения промежуточных переменных может быть разрешена относительно любой координаты системы. Обычно она решается относительно выходной величины y(t). В этом случае получается следующее дифференциальное уравнение
D(p)y(t) = R(p)g(t) + N(p)f(t), (2.2)
где y(t)) – выходная характеристика системы; g(t)) – входное воздействие на систему; f(t) – воздействие внешней среды на систему;
n, m, k от символа дифференцирования p, причём n³ m, k; ai, bi, ci – постоянные коэффициенты. Уравнение, описывающие динамику системы, может быть представлено в другой форме. Для этого перепишем уравнение (2.2) в операторном виде, перейдя от функций времени к их изображениям по Лапласу. В результате получим:
где s – оператор Лапласа; Y(s), G(s), F(s) – изображения по Лапласу выходной характеристики, входного воздействия и воздействия внешней среды на систему;
входному воздействию и воздействию внешней среды;
n, m, k от оператор Лапласа s, причём n³ m, k; ai, bi, ci – постоянные коэффициенты. Таким образом, поведение системы может быть исследовано на основе выражений (2.2) и (2.3), которые представляют собой математические модели динамических систем типа вход-выход. Описание в пространстве состояний образует математические модели вход-состояние-выход (модели типа «ВСВ»). Описание в пространстве состояний представляет собой общий взгляд на любые системы и пригодно для исследования и проектирования сложных систем с многими входами и выходами, то есть многомерных и многосвязных систем. С математической точки зрения анализ систем в пространстве состояний означает использование методов матричного исчисления и векторного анализа. В общем случае обыкновенных линейных систем, описываемых системой дифференциальных уравнений в нормальной форме, рассматриваемая система может быть определена следующей векторно-матричной формой
где X – вектор состояния системы; Y – вектор выходных управляемых величин; U – вектор внешних воздействий (входных и возмущающих); А, В, С, D – матрицы системы. Система уравнений (2.4) является стандартным описанием динамических систем в пространстве состояний и представляет собой математическую модель вход-состояние-выход. Уравнения (2.4) несут большой объём информации о динамических свойствах системы. Первое уравнение из (2.4) определяет динамические характеристики системы, а второе является уравнением выхода. Матрица системы A, элементы которой определяются структурной схемой системы и значениями её параметров, характеризует динамические свойства системы, её свободное движение. Матрица управления B характеризует влияние внешних воздействий на переменные состояния системы, т.е. определяет чувствительность системы к внешним воздействиям (входным и возмущающим). Матрица наблюдения C характеризует связь выходной величины системы с вектором состояния. Обычно не все составляющие вектора состояния являются наблюдаемыми сигналами, т.е. могут быть измерены с помощью каких-либо датчиков, в то время как выходной сигнал всегда наблюдаем. Матрица связи D устанавливает связь выходной величины системы с внешним воздействием. Таким образом, четверка матриц A, B, C, D полностью определяет динамическую систему. 2.3.2. Дискретно-детерминированные модели (F–схемы) Использование F –схем позволяет формализовать процесс функционирования дискретно-детерминированных систем, для которых характерно наличие дискретных состояний и дискретный характер работы во времени [8]. Дискретно-детерминированные модели широко используются в качестве математического аппарата теории автоматов. Теория автоматов – это раздел технической кибернетики, в котором изучаются математические модели – автоматы. На основе этой теории система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Автомат можно представить как некоторое устройство (чёрный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторое внутреннее состояние. Конечным автоматом называется автомат, у которого множества внутренних состояний, входных сигналов и выходных сигналов являются конечными множествами. Абстрактный конечный автомат (англ. Finite Automata) математически задаётся F –схемой: F = < X, Y, Z, φ , ψ , z0 >, (2.5)
где X – конечное множество входных воздействий (входной алфавит); Y – конечное множество выходных величин (выходной алфавит); Z – конечное множество внутренних состояний (алфавит состояний); z0 – начальное состояние, z0 Î Z; φ (z, x) – функция переходов; ψ (z, x) – функция выходов. Автомат, задаваемый F –схемой, функционирует в дискретном времени t = nT, где T – период дискретности (такт, т.е. равный интервал времени); n = 0, 1, 2, 3… – номер такта. На каждом такте дискретного времени F –автомат находится в определённом состоянии z(n) из множества Z состояний автомата, причём в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0) = z0. В момент времени t = nT, будучи в состоянии z(n), автомат способен воспринимать на входе сигнал x(n) Î X и выдавать на выходе сигнал y(n) = ψ [z(n), x(n)], переходя в состояние z(n+1) = φ [z(n), x(n)], z(n) Î Z, y(n) Î Y. Таким образом, работа конечного автомата происходит по следующей схеме: в каждый n-й такт на вход автомата, находящегося в состоянии z(n), подаётся некоторый входной сигнал x(n), на который он реагирует переходом в (n+1)-м такте в новое состояние z(n+1) и выдачей некоторого выходного сигнала y(n). Классификацияконечных автоматов. F –автоматы разделяются по математическому описанию, по числу состояний и по характеру отсчёта дискретного времени. По математическому описанию автоматы делятся на автоматы первого и второго рода. F –автомат первого рода, называемый автоматом Мили, описывается следующими уравнениями:
Для F –автомата второго рода уравнения имеют вид:
Автомат второго рода, для которого функция выходов не зависит от входной переменной x(n), называется автоматом Мура:
По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти обладают лишь одним состоянием. Автоматы без памяти ставят в соответствие каждому входному сигналу x(n) определённый выходной сигнал y(n), реализуя функцию вида y(n) = ψ [x(n)], n = 0, 1, 2, 3…. По характеру отсчёта дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных F –автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учётом считанного входного воздействия и в соответствии с уравнениями (2.6) – (2.8) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Таким образом, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом времени между соседними синхронизирующими сигналами. Асинхронный F –автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины x(n), он может, как следует из (2.6) – (2.8), несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдёт в устойчивое состояние, которое уже не может быть изменено данным входным сигналом [8]. Способы задания работы автоматов. Чтобы задать конечный F –автомат, требуется описать все элементы множества F = < X, Y, Z, φ , ψ , z0 >, т.е. входной, выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Причём среди множества состояний необходимо выделить состояние z0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы F –автоматов, но наиболее часто используются табличный, графический и матричный. Табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию z0. На пересечении i-ой строки и k-го столбца таблицы переходов помещается соответствующее значение φ (zk, xi) функции переходов, а в таблице выходов – соответствующее значение ψ (zk, xi) функции выходов. Для F –автомата Мура обе таблицы совмещаются в отмеченную таблицу переходов, в которой над каждым состоянием zk автомата, обозначающим столбец таблицы, ставится соответствующее этому состоянию значение ψ (zk) выходного сигнала. Описание работы F –автоматов Мили иллюстрируется таблицей 2.1, а пример табличного способа задания F –автомата Мили с тремя состояниями (z0, z1, z2), двумя входными (x1, x2) и двумя выходными (y1, y2) сигналами приведён в таблице 2.2.
Т а б л и ц а 2.1 Таблица переходов и входов автомата Мили
Т а б л и ц а 2.2 Таблица переходов и входов автомата Мили с тремя состояниями (z0, z1, z2), двумя входными (x1, x2) и двумя выходными (y1, y2) сигналами
Описание работы F –автоматов Мура иллюстрируется таблицей 2.3, а пример табличного способа задания F –автомата Мура с пятью состояниями (z0, z1, z2, z3, z4), двумя входными (x1, x2) и тремя выходными (y1, y2, y3) сигналами приведён в таблице 2.4. Графический способ задания конечного автомата использует понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi с вершиной zj, обозначается xk. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами.
Т а б л и ц а 2.3 Отмеченная таблица переходов автомата Мура
Т а б л и ц а 2.4 Отмеченная таблица переходов автомата Мура с пятью состояниями (z0, z1, z2, z3, z4), двумя входными (x1, x2) и тремя выходными (y1, y2, y3) сигналами
Для автоматов Мили эта разметка производится так: если входной сигнал xk действует на состояние zi, то, согласно сказанному, получается дуга, исходящая из zi и помеченная xk; эту дугу дополнительно отмечают выходным сигналом y = ψ (zi, xk). На рис. 2.3 приведён заданный ранее таблицей 2.2 граф F –автомата Мили.
Рис. 2.3. Граф автомата Мили
Для автоматов Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние zi автомата, вызывает переход в состояние zj, то дугу, направленную в zj и помеченную xk, дополнительно отмечают выходным сигналом y = ψ (zj, xk). На рис. 2.4 приведён заданный ранее таблицей 2.4 граф F –автомата Мура.
Рис. 2.4. Граф автомата Мура
Матричный способ задания конечного автомата часто является более удобной формой. При этом матрица соединений автомата есть квадратная матрица C = [cij], строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода. В случае F –автомата Мили элемент cij = xk/ys, стоящий на пересечении i-ой строки и j-го столбца, соответствует входному сигналу xk, вызвавшему переход из состояния zi в состояние zj, и выходному сигналу ys, выдаваемому при этом переходе. Для автомата Мили, рассмотренного выше, матрица соединений имеет вид
Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар «вход-выход» для этого перехода, соединённых знаком дизъюнкции. Для F –автомата Мура элемент cij = xk/ys равен множеству входных сигналов на переходе (zi, zj), а выход описывается вектором выходов, i-я компонента которого – выходной сигнал, отмечающий состояние zi. Для автомата Мура, рассмотренного выше, матрица соединений и вектор выходов имеют вид
Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Это означает, что в графе автомата из любой вершины не могут выходить две и более дуг, отмеченных одним и тем же входным сигналом, а в матрице соединений в каждой строке входной сигнал не должен встречаться более одного раза. Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F –автомата состояние zk называется устойчивым, если для любого входа xi Î X, для которого φ (zk, xi) = zk имеет место ψ (zk, xi) = yk. Таким образом, F –автомат называется асинхронным, если каждое его состояние zk Î Z устойчиво. Ниже приведён пример асинхронного автомата Мура, заданного таблично (табл.2.5) и графически (рис.2.5). Т а б л и ц а 2.5 Отмеченная таблица переходов асинхронного автомата Мура с тремя состояниями (z0, z1, z2), тремя входными (x1, x2, x3) и тремя выходными (1y, y2, y3) сигналами
Рис. 2.5. Граф асинхронного автомата Мура
В таблице переходов асинхронного автомата некоторое состояние zk стоит на пересечении строки xi и столбца zs (s ¹ k), и это состояние zk обязательно должно встретиться в этой же строке в столбце zk. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине zk должна быть петля, отмеченная символами тех же входных сигналов. Понятие F –автоматаявляется математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов, для которых характерно наличие дискретных состояний и дискретный характер работы во времени. Но широта применения не означает универсальности F –схем. Этот подход не пригоден для описания процессов в динамических системах с наличием переходных процессов, для формализации которых используются решётчатые функции и разностные уравнения, Z –преобразование и описание в пространстве состояний [14]. 2.3.3. Дискретно-стохастические модели (P–схемы) Использование P –схем позволяет формализовать процесс функционирования дискретных систем, проявляющих статистически закономерное случайное поведение. Вероятностный автомат (англ. Probabilistic Automata) определяется как дискретный потактовый преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нём и может быть описано статистически [8]. Применение схем вероятностных автоматов ( P –схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям. Введём математическое понятие P –автомата, используя понятия, введённые для F –автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi, zs), где xi и zs – элементы входного множества X и множества состояний Z соответственно. Если существуют две такие функции φ и ψ , что с их помощью осуществляются отображения G®Z и G®Y, то говорят, что F = < X, Y, Z, φ , ψ , z0 > определяет автомат детерминированного типа. Введём в рассмотрение более общую математическую схему. Пусть Ф – множество всевозможных пар вида (zk, yj), где yj – элементы выходного множества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:
При этом Пусть элементы множества G индуцируют некоторые законы распределения на множествах Y и Z, что можно представить соответственно в виде:
При этом Если для всех k и j имеет место соотношение qkzj = bkj, то такой P –автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния P –автомата и его выходного сигнала. Пусть теперь определение выходного сигнала P –автомата зависит лишь от того состояния, в котором находился автомат в данном такте работы. Другими словами, пусть каждый элемент выходного множества Y индуцирует распределения вероятностей выходов, имеющих следующий вид:
Здесь Если для всех k и i имеет место соотношение zksi = bki, то такой P –автомат называется вероятностным автоматом Мура. Понятие P –автоматовМили и Мура введено по аналогии с детерминированным F –автоматом. Частным случаем P –автомата, задаваемого как P = < X, Y, Z, B >, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал P –автоматаопределяется детерминированно, то такой автомат называется Y –детерминированным вероятностным автоматом. Аналогично, Z –детерминированным вероятностным автоматом называется P –автомат, у которого выбор нового состояния является детерминированным. Способы задания работы P –автоматовтакие же, как и для F –автоматов. В качестве примера рассмотрим Y –детерминированный вероятностный автомат, заданный таблицей переходов (табл. 2.6) и таблицей выходов (табл.2.7). До начала работы P –автоматвсегда находится в начальном состоянии z0 и в нулевой такт времени начинает изменять своё состояние в соответствии с заданным распределением.
Т а б л и ц а 2.6 Таблица переходов Y – детерминированного вероятностного автомата
Т а б л и ц а 2.7 Таблица выходов Y – детерминированного вероятностного автомата
Для рассматриваемого P –автомата матрица соединений и вектор выходов имеют вид
В матрице соединений Y–детерминированного вероятностного автомата элемент cij = pij определяется вероятностью перехода P –автомата в состояние zj из состояния zi при поступлении входного сигнала, а выход описывается вектором выходов, i-я компонента которого – выходной сигнал, отмечающий состояние zi. Описанный Y–детерминированный P –автомат можно задать в виде ориентированного графа (рис. 2.6), вершины которого сопоставляются состояниям автомата, а дуги – возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода pij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.
Рис. 2.6. Граф Y –детерминированного вероятностного автомата
Оценим суммарную финальную вероятность пребывания этого P –автомата в состояниях z2 и z3. При этом начальное состояние z0 можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда матрица вероятностей перехода автомата будет иметь вид
откуда получаем систему уравнений, определяющих вероятности финального пребывания автомата в состояниях pj (
Добавим к этим уравнениям условие нормировки p1 + p2 + p3 + p4 = 1. Тогда, решая систему уравнений, получим p1 = p3 = p4 = 5/23, p2 = 8/23. Таким образом, p2 + p3 = 13/23 = 0, 5652. Другими словами, при бесконечной работе заданного в этом примере Y –детерминированного вероятностного автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0, 5652. Для оценки различных характеристик исследуемых систем, представленных в виде P –схем, кроме рассмотренного случая аналитических моделей, можно применять и имитационные модели, реализуемые, например, методом статистического моделирования. 2.3.4. Непрерывно-стохастические модели (Q–схемы) Использование Q –схем позволяет формализовать процессы функционирования систем, которые, по своей сути, являются процессами обслуживания. Q –схемы применяются в качестве типовых математических схем систем массового обслуживания (англ. Queueing System) [8]. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем, например: потоки поставок продукции предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удалённых терминалов и т.д. Характерным для работы подобных объектов является стохастический характер процесса их функционирования, проявляющийся: – в случайном появлении заявок (требований) на обслуживание; – в завершении обслуживания в случайные моменты времени. Рассмотрим основные понятия систем массового обслуживания (СМО), необходимые для использования Q –схем, как при аналитическом, так и при имитационном подходе. Элементы СМО. В СМО фигурируют: 1. Средства обслуживания – обслуживающие аппараты (ОА) или каналы обслуживания (К). Средства обслуживания являются статическими элементами Q –схем. 2. Обслуживаемые заявки – транзакты. Являются динамическими элементами Q –схем. 3. Очереди. Состояние СМО характеризуется: 1. Состояниями всех обслуживающих аппаратов, каждый из которых может находиться в состоянии “занят” или “свободен”. 2. Состояниями всех транзактов, каждый из которых может находиться в состоянии “обслуживание” или “ожидание”. 3. Состояниями всех очередей к обслуживающим аппаратам, определяемыми количеством находящихся в них транзактов. Переменные СМО. Переменные величины разделяются на независимые и системные. Независимые величины СМО характеризуются двумя случайными переменными: а) интервал прибытия – интервал времени между последовательными моментами прибытия заявок в систему; б) время обслуживания – время, требуемое обслуживающему аппарату для выполнения обслуживания. Системные величины СМО являются предметом исследования системы и назначаются исследователем, например: а) число заявок, прибывших на обслуживание за заданный промежуток времени; б) число заявок, которые попали на обслуживание сразу же по прибытии; в) среднее время пребывания заявок в очереди; г) средние длины очередей; д) максимальная длина очереди; е) нагрузка обслуживающего аппарата, являющаяся функцией времени, которое потрачено ОА на обслуживание в течение заданного промежутка времени и т.д. На рис. 2.7 приведён пример системы обслуживания одним обслуживающим аппаратом и очередью. Система функционирует следующим образом. Заявка из источника заявок приходит на обслуживание. Если обслуживающий аппарат свободен, то заявка занимает его, и начинается процесс обслуживания. Если обслуживающий аппарат занят, то заявка поступает в очередь, где ожидает окончания обслуживания предыдущей заявки. Обслуженная заявка освобождает обслуживающий аппарат и покидает систему. Заявки, приходящие на обслуживание, образуют поток заявок; заявки, поступающие на обслуживание, образуют поток обслуживания; а заявки, покидающие систему по окончании обслуживания, образуют выходной поток. Эти потоки характеризуются интенсивностью l прихода заявок на обслуживание, интенсивностью m обслуживания и интенсивностью h ухода заявок из системы.
Рис. 2.7. Система обслуживания одним обслуживающим аппаратом и очередью
Для графического изображения СМО введена символика Q –схем. Для начертания Q –схем используются следующие основные элементы.
1. Источник заявок;
2. Материальные потоки (движение транзактов);
3. Информационные потоки (управляющие сигналы);
4. Клапан;
5. Накопитель;
6. Канал обслуживания;
7. Узел − правило, в соответствии с которым направляются транзакты.
В качестве примера графического изображения Q –схемы на рис. 2.8 приведена система обслуживания со страховым заделом. Движение заявок через Q –схему представляет собой материальные потоки. А для управления системы обслуживания используются информационные потоки.
|
Последнее изменение этой страницы: 2017-04-13; Просмотров: 667; Нарушение авторского права страницы
– алгебраизированный символ дифференцирования; 
; 
; 
– полиномы степени
, (2.3)
; 
– передаточные функции системы по
; 
; 
– полиномы степени
, (2.4)
, n = 0, 1, 2, 3… (2.6)
, n = 0, 1, 2, 3… (2.7)
, n = 0, 1, 2, 3… (2.8)
. (2.9)
; 
. (2.10)
, где bkj – вероятность перехода автомата в состояние zk и появления на выходе сигнала yj, если он был в состоянии zs, и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через B. Тогда четвёрка элементов P = < X, Y, Z, B > называется вероятностным автоматом ( P –автоматом).
и 
, где zk и qk – вероятности перехода P –автомата в состояние zk и появление выходного сигнала yk при условии, что P –автомат находился в состоянии zs и на его вход поступил входной сигнал xi.
, где si – вероятность появления выходного сигнала yi при условии, что P –автомат находился в состоянии zk.
; 
. (2.11)
, 
)
.
