Представление математической модели в форме графа

Учебные элементы параграфа:

1. Граф, орграф

2. Вершина, ребро (ветвь), дуга

3. Матрица смежности

4. Матрица инцидентности

5. Части орграфа

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

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

Граф — это множество вершин V, связь между которыми определяется множеством ребер E.

Формальное представление графа G = {V,E}, где

p - количество вершин

q - количество ребер.

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

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

На рис. 2.11 показан орграф, который имеет 5 вершин и 7 дуг

Рис. 2.11. Ориентированный граф (орграф)

Вершины и дуги такого графа находятся в определенных отношениях.

Две вершины v_i и v_j, принадлежащих множеству вершин V графа G = {V,E}, получили название смежных, если они являются граничными вершинами ребра l_k принадлежащих множеству ребер E.

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

l_k={v_i,v_j}, где k = 1,2,3... q

v_i — начальная вершина, откуда дуга выходит;

v_j — конечная вершина, куда дуга входит.

Отношение смежности подается в виде матрицы [C_ij]_v= [p x p]. Для орграфа на рис. 2.8. матрица смежности имеет вид:

С_ij элемент матрицы равняется числу ребер, направленных от вершины v_i к вершине v_j.

Отношение инцидентности описывается матрицей A = [a_ij]_V,E = [p x q].

Если вершина v_i является концом (началом) дуги l_k, то говорят, что они инцидентны. Строки матрицы A соответствуют вершинам, а столбцы дугам. a_i,j -й элемент равняется +1, если v_i начальная вершина ребра l_j и равняется -1, если v_i конечная вершина ребра l_j. Если связи нет a_ij = 0.

Для приведенного выше орграфа матрица инцидентности имеет вид:

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

Подграф — часть графа образованная некоторыми дугами и инцидентными им вершинами.

Суграф — часть графа, образованная с исходного изъятием некоторых дуг, при сохранении всех вершин.

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

Связный граф имеет маршрут через все вершины.

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

Примеры подграфа, суграфа и дерева для орграфа рис. 2.11 представленные на рис.2.9.

Рис.2.12. Подграф (а),

суграф (б) и дерево графа (в).

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

б

Рис. 2.13 Граф механической системы «Тягач с прицепом»

Узлом графа является точка, где соединяются два и более компонента. В базовом узле соединяются все компоненты. В узле 1 соединяются три компонента: F, m₁, R₁. В узле 2 соединяются четыре компонента: L₁, m₂, R₂. В узле 3 соединяются три компонента: L₂, m₃, R₃. таким образом модель приобрела более формальный вид.

Вопросы для самоконтроля и подготовки к МК:

Чем граф отличается от орграфа?

5. Как различить маршрут, цикл, цепь, контур в графе?

6. Как получить дерево графа?

7. Чем ветвь дерева графа отличается от хорды?

8. Как закодировать граф для обработки на ЭВМ?

§ 2.3.3. Реализация аналитических математических моделей на ЭВМ

Учебные элементы параграфа:

1. Методика построения формальной ММ.

2. Методика моделирования на макроуровне.

3. Методика моделирования на метауровне.

При построении ММ сложного технического объекта, состоящего из нескольких физических подсистем, нужно:

1. Провести анализ объекта моделирования;

2. Выделить в объекте однородные физические подсистемы;

3. Получить эквивалентную структурную схему для каждой из них;

4. Установить связи между подсистемами;

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

1). (2.11)

где: U — вектор переменных: состояния, моделируемого объекта размерностью n;

F — вектор- функция;

t — время (начальные условия: ). Это явная форма ОДУ.

2). Ф () = 0 (2.12)

где: V — вектор фазовых переменных, достаточных для определения объекта, размерностью n;

— вектор производных фазовых переменных по времени, причём вектор имеет только ненулевых элементов ( n);

Ф — вектор-функция (начальные условия ).

При составлении эквивалентной схемы следует соблюдать следующие правила. Избегать последовательного соединения источника типа I и компонента типа L, поэтому между ними нужно вставлять диссипативный элемент R. Не допустимо параллельное соединение источника типа E и компонента типа C. В этом случае последовательно с C соединяется компонент R.

Построение формальной модели на макро уровне.

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

Рис. 2.3 Математическая макромодель

Система состоит из 5-ти элементов. Один активный – источник потенциала, три пассивных и один вспомогательный – ключ.

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

(2.13)

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

Тогда с учётом того, что:

или

(2.14)

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

На метауровне моделируют сложные технические объекты - системы управления (СУ), системы массового обслуживания (СМО). Подходы к ним различные, поэтому моделирование СМО рассмотрено в разделе 3.

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

Для решения задачи можно использовать программный комплекс MatLab, ПК МВТУ или SciLab.

Методика моделирования основана на установленные соответствия между компонентами исходных уравнений и блоками, реализуемыми на персональном компьютере (например, пакет Simulink, который содержится в составе пакета MatLab).

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

Объект описывается дифференциальным уравнением:

ПИ-регулятор описывается уравнением:

выполнив следующие преобразования, получим систему уравнений

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

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

Рис.2.13. Структурная схема метамодели СУ

Эта схема реализуется в среде Simulink набором соответствующих блоков из библиотеки.

Вопросы для самоконтроля и подготовки к МК:

1. Перечислить составляющие методики построения формальной ММ.

2. Перечислить составляющие методики моделирования на макроуровне.