Дискретно непрерывные модели. Статические и динамические, дискретные и непрерывные модели

При b i - "рыб(а)", с i - "н(ый)", получаем по этой модели p i - "рыбный", z i - "приготовленный из рыбы".

Система клеточных автоматов

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

Клеточный автомат - дискретная динамическая система, аналог физического (непрерывного) поля. Клеточно-автоматная геометрия - аналог евклидовой геометрии. Неделимый элемент евклидовой геометрии - точка, на основе ее строятся отрезки, прямые, плоскости и т.д.

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

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

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

Фрактальные модели

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

Если физический объект однородный (сплошной), т.е. в нем нет полостей, то можно считать, что его плотность не зависит от размера. Например, при увеличении параметра объекта R до 2R масса объекта увеличится в R 2 раз, если объект- круг и в R 3 раз, если объект - шар, т.е. существует связь массы и длины. Пусть n - размерность пространства. Объект, у которого масса и размер связаны называется "компактным". Его плотность можно рассчитать по формуле:

Если объект (система) удовлетворяет соотношению M(R) ~ R f(n) , где f(n) < n, то такой объект называется фрактальным.

Его плотность не будет одинаковой для всех значений R, то она масштабируется согласно формуле:

Так как f(n) - n < 0 по определению, то плотность фрактального объекта уменьшается с увеличением размера R, а ρ(R) является количественной мерой разряженности объекта.

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

Рис. 1.4. Множество Кантора для 3-х делений

Генетические алгоритмы

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

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

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

Данные алгоритмы адаптивны, они развивают решения и развиваются сами.

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

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

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

Генетические алгоритмы эффективны в комбинации с другими классическими алгоритмами и эвристическими процедурами.

Статические и динамические, дискретные и непрерывные модели

Классификацию моделей проводят по различным критериям.

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

Пример. Закон Ньютона F=a*m - это статическая модель движущейся с ускорением a материальной точки массой m. Эта модель не учитывает изменение ускорения от одной точки к другой.

Модель динамическая, если среди ее параметров есть временной параметр, т.е. она отображает систему (процессы в системе) во времени.

Пример. Динамическая модель закона Ньютона будет иметь вид:

Модель дискретная, если она описывает поведение системы только в дискретные моменты времени.

Пример. Если рассматривать только t=0, 1, 2, …, 10 (сек), то модель

или числовая последовательность: S0=0, S1=g/2, S2=2g, S3=9g/2, :, S10=50g может служить дискретной моделью движения свободно падающего тела.

Модель непрерывная, если она описывает поведение системы для всех моментов времени некоторого промежутка времени.

Пример. Модель S=gt2/2, 0 < t < 100 непрерывна на промежутке времени (0;100).

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

Пример. Пусть модель экономической системы производства товаров двух видов 1 и 2, в количестве x1 и x2 единиц и стоимостью каждой единицы товара a1 и a2 на предприятии описана в виде соотношения:

a1x1 + a2x2 = S,

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

Процессы в линейных импульсных и цифровых системах автоматического управления описываются дискретно – разностными уравнениями вида:

где x(n) –решетчатая функция входного сигнала; y(n) –решетчатая функция выходного сигнала, которая определяется решением уравнения (1.2); b k – постоянные коэффициенты;
– разность к – го порядка; t=nT , где nT – n– ый момент времени, T – период дискретности (в выражении (1.2) он условно принят за единицу).

Уравнение (1.2) можно представить в другом виде:

Уравнение (1.3) представляет собой рекуррентное соотношение, которое позволяет вычислить любой (i+1) –й член последовательности по значениям предыдущих её членов i,i-1,... и значению x(i+1).

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

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

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

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

Для Р – автомата вводится аналогичное математическое понятие, как и для F – автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (x i ,z s ) , где x i и z s элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции и
, что с их помощью осуществляется отображение
и
, то говорят, чтоопределяет автомат детерминированного типа.

Функция переходов вероятностного автомата определяет не одно конкретное состояние, а распределение вероятностей на множестве состояний

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

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

элементы из Ф...

...

...

где – вероятности перехода автомата в состояние z k и появления на выходе сигнала y j , если он был в состоянии z s и на его вход в этот момент времени поступал сигнал x i .

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

Частным случаем Р– автомата, задаваемого как
являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминировано(Z– детерминированный вероятностный автомат, Y– - детерминированный вероятностный автомат соответственно).

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

Марковские последовательности , согласно теореме Маркова, –это последовательность случайных величин, для которой справедливо выражение

,

где N – количество независимых испытаний; D– - дисперсия.

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

Y – детерминированный Р– автомат можно задать двумя таблицами: переходов (табл.1.1) и выходов (табл.1.2).

Таблица 1.1

Таблица 1.2

Где P ij – вероятность перехода Р– автомата из состояния z i в состояние z j , при этом
.

Таблицу 1.1 можно представить в виде квадратной матрицы размерности
. Такую таблицу будем называть матрицей переходных вероятностей или просто матрицей переходов Р- автомата , которую можно представить в компактной форме:

Для описания Y– детерминированного Р–автомата необходимо задать начальное распределение вероятностей вида:

где d k– вероятность того, что в начале работы Р– автомат находится в состоянии z k , при этом
.

И так, до начала работы Р– автомат находится в состоянии z 0 и в начальный (нулевой) такт времени меняет состояние в соответствии с распределением D. После этого смена состояний автомата определяется матрицей переходов Р. С учетом z 0 размерность матрицы Р р следует увеличить до
, при этом первая строка матрицы будет (d 0 ,d 1 ,d 2 ,...,d k ) , а первый столбец будет нулевым.

Пример. Y– детерминированный Р– автомат задан таблицей переходов:

Таблица 1.3

и таблицей выходов

Таблица 1.4

С учетом таблицы 1.3 граф переходов вероятностного автомата представлен на рис.1.2.

Требуется оценить суммарные финальные вероятности пребывания этого автомата в состоянии z 2 и z 3 , т.е. когда на выходе автомата появляются единицы.

Рис. 1.2. Граф переходов

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

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

В результате получаем систему уравнений:

(1.4)

К данной системе следует добавить условие нормировки:

(1.5)

Теперь решая систему уравнений (1.4) совместно с (1.5), получаем:

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

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

Отображения в пространстве.

Трехмерное вращение.

Сдвиг.

Основы преобразований.

Трехмерное изменение масштаба.

Данное преобразование производит частное изменение масштаба. Общее изменение масштаба получается за счет использования четвертого диагонального элемента.

Не диагональные элементы левой верхней подматрицы 3*3 в общем матричном преобразование размером 4*4 осуществляется сдвиг в трех измерениях, то есть:

В предыдущем случае было показано, что матрица 3*3 обеспечивает комбинацию операций измерения масштаба и сдвига. Однако, если определенная матрица 3*3 = 1, то имеет место чистое вращение около начала координат.

Рассмотрим несколько частных случаев вращения.

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

Угол Ө - угол вращения вокруг оси х;

Вращение предполагается положительным по часовой стрелке, если смотреть с начала координат вдоль оси вращения.

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

Матрица имеет вид:

Аналогично матрица преобразований для вращения на угол ψ вокруг оси Z:

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

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

Рассмотрим частный случай отображения. Матрица преобразования относительно плоскости XYимеет вид:

И отображение YZ или отображение XZприотображение относительно других плоскостей можно получить путем комбинации вращения и отображения.

Для отображения yz:

Для отображения xz:

Тв.модели

При каркасном моделировании хотя оно и является объемным, мы не учитываем, что является телом, а что внутренностью.

Поэтому появляется термин – твердотельная модель.

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

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

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

Преимущества:

1. Разработан математический аппарат на основе булевой алгебры и математической логики.

2. Простота задания геометрического объекта.

Недостатки:

1. Геометрический объект задается дискретно, возникает вопрос математической модели о точности задания геометрического объекта по гладкости, по возможности построения нормали к геометрическому объекту.

2. Для данной модели существуют проблемы в уравнении и масштабировании геометрического объекта.

Эффект масштабирования - нельзя ни растянуть ни сжать, делаем от и до.

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

Удобство числового множества как модели реальных совокупностей объектов состоит в том, что на нем естественным образом определяются несколько отношений, формализующих реально встречающиеся отношения между реальными объектами. Например, отношения близости, сходимости формализуют понятия похожести, сходства объектов и могут быть заданы посредством функции расстояния (метрики) d(x, у) (например, d(x, у) = |х - у |). Числовые множества являются упорядоченными: отношение порядка следования (х ≤ у ) формализует предпочтение одного объекта другому. Наконец, над элементами числовых множеств определены соответствующие операции, например, линейные: х + у , х*у . Если для реальных объектов на входе и выходе также имеют смысл аналогичные операции, то естественным образом возникают требования к моделям (1) – (3): быть согласованными с этими операциями, сохранять их результаты. Таким образом, приходим, например, к линейным моделям: y = au + b , dy/dt = ay + bu и т.д., являющихся простейшими моделями многих процессов.

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

Таблица 2

ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ СИСТЕМ

Примечание: U - множество входов, Y - множество выходов системы

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

Модели общего вида

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

В общем случае уравнения состояния – это системы дифференциальных или разностных уравнений первого порядка вместе с уравнениями для выходных величин. Начальное состояние представляет, «память» системы о прошлом. Модель состояния непрерывной динамической системы записывается в виде

(4)

(5)

где u 1 , …, u m - входные переменные, y 1 , …, y l - выходные переменные, x 1 , …, x n -переменные состояния. Вводя векторные обозначения, можно записать (5) в более компактном виде:

(6)

где , , .

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

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

(7)

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

(8)

Линейные модели

Часто вместо (5) используют упрощенные ММ, основанные на том, что процессы в системе протекают, мало отклоняясь от некоторой так называемой опорной траектории удовлетворяющей уравнениям

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

(10)

Если расчетный режим является установившимся, т.е. не зависит от времени, то коэффициенты в (10) также не зависят от времени: A(t)=A , B(t)=B и т.д. Такие системы называются стационарными. Особенно часто на практике встречаются стационарные линейные непрерывные системы, описываемые более простыми уравнениями

, у = Сх . (11)

Матрицы А, В, С являются параметрами модели (11).

Если линеаризация приводит к большим погрешностям, то стараются, по возможности, выбрать ММ линейную по параметрам:

где А - матрица параметров порядка n × N , - нелинейная функция. К этому классу относятся, в частности, билинейные объекты.

Сказанное выше относится и к уравнениям дискретных по времени систем. Уравнения дискретной системы в общем случае имеют вид

, . (12)

Дискретным аналогом уравнений линейной стационарной системы (20) являются уравнения:

(13)

Наряду с уравнениями состояния широкое применение находят также модели в переменных «вход-выход» и модели, описываемые передаточными функциями. Для непрерывного времени уравнение «вход-выход» имеет вид

A(p)y(t)=B(p)u(t), (14)

где р = d/dt - символ дифференцирования по времени, , , причем в (14) всегда m < n . Дробно-рациональная функция называется передаточной функцией системы (14), а полином А(λ) - ее характеристическим полиномом . Если уравнение (14) получено из (11), то

(15)

Они справедливы и в случае, когда вход и выход системы (11) являются векторами, при этом - матрица. Пользуясь (15), можно показать, что замена переменных состояния в (11) по формуле , где Т - неособая n×n матрица (det T = 0), не приводит к изменению передаточной функции (15). Это значит, что обратный переход от описания «вход-выход» к уравнениям состояния (11) неоднозначен: при сохранении передаточной функции базис в пространстве состояний можно выбирать по-разному. На практике применяются несколько типовых способов перехода от передаточной функции к уравнениям состояния. Эти способы соответствуют так называемым каноническим представлениям системы. Опишем один из них, приводящий к управляемому каноническому представлению . Вместо (13) вводятся два уравнения.

ДИСКРЕТНЫЕ МОДЕЛИ, модели, переменные и параметры которых являются дискретными величинами, т. е. величинами, принимающими конечное или счётное число значений; в задачах, связанных с такими моделями, множество допустимых решений также дискретно. При построении и анализе дискретных моделей используются математические методы дискретной математики, алгебраические и другие известные математические методы, а иногда требуется разработка новых.

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

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

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

Лит.: Лихтенштейн В. Е. Модели дискретного программирования. М., 1971; Вагнер Г. Основы исследований операций: В 3 т. М., 1972-1973; Пропой А. И. Элементы теории оптимальных дискретных процессов. М., 1973; Финкельштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. М., 1976; Моисеев Н. Н. Математические задачи системного анализа. М., 1981; Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М., 2000; Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: Модели и вычислительные алгоритмы. М., 2002.