Математические основы теории систем

Задача 1. Элементы теории графов

Связный ориентированный граф G (Х, Г) задан множеством вершин X={x₁, x₂, …, x_n} и отображением Гx_i=, i =1, 2,…, n. Здесь i — текущий номер вершины, nколичество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов, , … переменной x в отображении Гx_i = {x, x, x,…}. Если значения индексов, , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гx_i.

Выполнить следующие действия:

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

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами x_i и x_j

i*j при i j;

Kij =

1/ (p+1) при i<j .

Найти передачу между вершинами x₁ и x_n, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;

Таблица 1

Решение:

Множество вершин

X = {x₁, x₂, x₃, x₄, x₅, x₆ }, n = 6 k = 2, l = 1 Гx_i=_Ik.

_{а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:}

_{Определим граф аналитическим способом:}

_{Гx1 = { x1, x3, x2 };}

Гx₂ = { x₄, x₁, x₃ };

Гx₃ = { x₁, x₅, x₂, x₄ };

Гx₄ = { x₂, x₆, x₃, x₅ };

Гx₅ = { x₃, x₄, x₆ };

Гx₆ = {x₄, x₅ }.

Ориентированный граф графическим способом:

Неориентированный граф графическим способом:

Ориентированный граф матричным способом:

R_G — матрица смежности

A_G — матрица инцидентности

Неориентированный граф матричным способом:

R_D — матрица смежности

A_D — матрица инцидентности

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:

— матрица отклонений имеет вид:

— вектор отклонения

=>

х₂, х₃, х₄, х₅ — центры графа с наименьшей удаленностью. Радиус с (G) = 2.

Периферийными вершинами являются вершины х₁, х₆ с наибольшей удаленностью. Диаметр графа D (G) = 3.

в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.

Выделяем два подграфа: G₁ и G₂

X₁ - {x₁, x₂}, Г_1х1 = {x₁, x₂}, Г_1х2 = {x₁},

X₂ - {x₁, x₂, x₃}, Г_2х1 = {x₂}, Г_2х2 = {x₃}, Г_2х3 = {x₂}.

Объединение ,

,, .

G

Пересечение

, .

G

Разность

, .

G

г) Считая, что передача между вершинами x_i и x_j

i*j при i j;

Kij =

1/ (p+1) при i<j .

Сигнальный граф имеет вид Система уравнений, соответствующая сигнальному графу имеет вид

x₁ = x₁ +2x₂ +3x₃

x₂ = x₁ +6 x₃ +8 x₄

x₃ = x₁ + x₂+12x₄ +15x₅

x₄ = x₂ + x₃ +20 x₅ +24x₆

x₅ = x₃ + x₄ +30x₆

x₆ = x₄ +x₅

Определить передачу k₁₆ по правилу Мезона. Формула Мезона имеет вид

P_S - передача пути,

D_S - алгебраическое дополнение,

D — определитель.

Пути из х₁ в х₆ и передаточные функции для каждого из них имеют вид:

Контура:

;

;;

;;

;;

;;

;;

;

;.

;.

Пары несоприкасающихся контуров

L₁L₃, L₁L₄, L₁L₅, L₁L₆, L₁L₈, L₁L₉, L₁L₁₀, L₁L₁₃, L₁L₁₄, L₁L₁₅, L₁L₁₆, L₁L₁₇, L₁L₁₈;

L₂L₄, L₂L₅, L₂L₆, L₂L₈, L₂L₉, L₂L₁₀, L₂L₁₅, L₂L₁₆, L₂L₁₇, L₂L₁₈;

L₃L₅, L₃L₆, L₃L₁₀, L₃L₁₇, L₃L₁₈;

L₄L₆, L₅L₇; L₅L₁₁, L₅L₁₂, L₆L₇, L₆L₈, L₆L₁₁, L₆L₁₂, L₆L₁₃, L₆L₁₄;

L₇L₈, L₇L₁₀, L₇L₁₇, L₇L₁₈;

L₈L₉, L₉L₁₀, L₁₀L₁₁, L₁₀L₁₂, L₁₁L₁₇, L₁₁L₁₈, L₁₂L₁₇, L₁₂L₁₈.

Независимые тройки

L₁L₃L₅, L₁L₃L₆, L₁L₃L₁₀, L₁L₃L₁₇, L₁L₃L₁₈, L₁L₄L₆, L₁L₆L₈, L₁L₆L₁₃, L₁L₆L₁₄, L₁L₈L_9,L₁L₉L₁₀, L₂L₄L₆, L₂L₉L₁₀, L₆L₇L_8.

Отсюда

D = 1 — (L₁ +L₂ +L₃ +L₄ +L₅ + L₆ +L₇ + L₈ +L₉ +L₁₀ +L₁₁ +L₁₂ +

+L₁₃ +L₁₄+L₁₅ +L₁₆+L₁₇ +L₁₈)+ (L₁L₃+L₁L₄+L₁L₅+L₁L₆+L₁L₈+L₁L₉+L₁L₁₀+L₁L₁₃+L₁L₁₄+L₁L₁₅+L₁L₁₆+L₁L₁₇+L₁L₁₈+L₂L₄+L₂L₅+L₂L₆+L₂L₈+L₂L₉+L₂L₁₀+L₂L₁₅+L₂L₁₆+L₂L₁₇+L₂L₁₈ +L₃L₅+L₃L₆+L₃L₁₀+L₃L₁₇+L₃L₁₈ L₄L₆+L₅L₇+L₅L₁₁+L₅L₁₂+L₆L₇+L₆L₈+L₆L₁₁+L₆L₁₂+L₆L₁₃+L₆L₁₄+L₇L₈+L₇L₁₀+L₇L₁₇+L₇L₁₈+L₈L₉+L₉L₁₀+L₁₀L₁₁+L₁₀L₁₂+L₁₁L₁₇+L₁₁L₁₈+L₁₂L₁₇+L₁₂L₁₈) -

(L₁L₃L₅+L₁L₃L₆+L₁L₃L₁₀+L₁L₃L₁₇+L₁L₃L₁₈+L₁L₄L₆+L₁L₆L₈+L₁L₆L₁₃+L₁L₆L₁₄+L₁L₈L₉+L₁L₉L₁₀+L₂L₄L₆+L₂L₉L₁₀+L₆L₇L₈).

D₁ = 1- L₈;

D₂ = 1;

D₃ = 1;

D₄ = 1 - L₉;

D₅ = 1;

D₆ = 1.

.

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

Задача 2. Задача о максимальном потоке и потоке минимальной стоимости

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С () ребра .

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

Решение:

Максимальный поток _max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:

Первый шаг.1. Находим какой-либо путь из х₁ в х₉ с положительной пропускной способностью.

Tаблица 1.

В результате получен путь l₁ = (x₁, х₃, х₆, х₉). Элементы этого пути C_ij помечаем знаком минус, а симметричные элементы C_ji — знаком плюс.

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

Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов табл.1 вычитаем C₁, а к элементам прибавляем C₁. В результате получим новую табл.2 с измененными пропускными способностями.

Tаблица 2

Второй шаг.1. Помечаем столбцы табл.2, находим второй путь l₂ = (x₁, x₃, х₇, х₉) и расставляем знаки.

2. Пропускная способность пути l₂

Изменим пропускные способности помеченных дуг на С₂ в табл.3.

Tаблица 3

Третий шаг.1. Пометив столбцы, находим l₃ = (x₁, х₄, х₇,x₉).

Величина потока по пути l₃

Вычислив новые пропускные способности дуг, приходим к табл.4.

Таблица 4

Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l₄ = (x₁, х₂, х₈, х₉) и расставляем знаки.

2. Пропускная способность пути l₄

Изменим пропускные способности помеченных дуг на С₄ в табл.5.

Таблица 5

Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l₅ = (x₁, х₄, х₈, х₉) и расставляем знаки.

2. Пропускная способность пути l₅

Изменим пропускные способности помеченных дуг на С₅ в табл.6.

Таблица 6

Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x₁ в вершину x₉. Подмножество R образуют помеченные вершины х₁, х₂, х₃, х₄, х₅, х₆, х₇, х₈, а подмножество — одна непомеченная вершины х₉. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные —. Таким образом, разрез с минимальной пропускной способностью. Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7

Таблица 7.

Величина максимального потока равна сумме элементов x₁-й строки табл.7 или сумме элементов x₉-го столбца.

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

Задача 3. Анализ сетей Петри

Сеть Петри задана графически (рис.23…30). В табл.1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.

Выполнить следующие действия:

Описать сеть аналитическим и матричным способами.

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

Построить дерево достижимости заданной сети.

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

Таблица 1

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p₁, p₂, p₃, p₄, p₅} и переходы T = {t₁, t₂, t₃ , t₄ }.

Начальная маркировка сети обозначается вектором м₀ [м₁, м₂, м₃, м₄, м₅], м₀ [1 3 0 1 2]. Отсюда получим:

При аналитическом способе задания сеть Петри задается как C = (P, T, F, H, м₀), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции.

Через F (t_j) обозначается множество входных позиций, а через H (t_j) — множество выходных позиций перехода t_j; м₀ — начальная маркировка сети.

F (t₁) = {p₅}, H (t₁) = {p₁, p₂ },

F (t₂) = {p₁}, H (t₂) = {p₃, p₄},

F (t₃) = {p₃, p₄}H (t₃) = {p₁ },

F (t₄) = {p₂, p₃, p₄}H (t₄) = {p₅ }.

м₀ [1 3 0 1 2]

Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = (P,T,D^-,D⁺, м⁰). Здесь D^- и D⁺ — матрицы входных и выходных инциденций соответственно размером m Ч n, где m — число переходов и n — число позиций.

Элемент d_ij^- матрицы D^- равен кратности дуг, входящих в i-й переход из j-й позиции.

Элемент d_ij⁺ матрицы D⁺ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.

Для рассматриваемой сети Петри Матрица D = D⁺ - D ^- называется матрицей инцидентности сети Петри,

2. При начальной маркировке м₀ [1 3 0 1 2] сети Петри разрешенными являются переходы t₁ и t₂.

Условия срабатывания для перехода t₃ и t₄ не выполняется.

Переход t₁

[м₀] ? [1000]* D^- = · ; [1 3 0 1 2] ? ;

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t₁ равна:

.

Переход t₂

[м₀] ? [0100]* D^- = · ;[1 3 0 1 2] ? ;

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t₂ равна:

.

Переход t₃

[м₀] ? [0010]* D^- = · ;[1 3 0 1 2] ? - условие не

выполняется, переход запрещен.

Переход t₄

[м₀] ? [0001]* D^- = · ;[1 3 0 1 2] ? ;

условие не выполняется, переход запрещен.

Построим дерево достижимости заданной сети.

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

Уравнение принимает вид Перенесем в левую часть и выполним умножение, тогда

.

Приравняем составляющие векторов Система имеет решение x₁ = 1; x₂ = 2; x₃ = 0; x₄ = 2.

Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t₁ срабатывает один раз, переходы t₂ и t₄ - по два раза, переход t₃ не срабатывает.

Задача 4. Элементы математической логики и теории автоматов

Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q₁, q₂ ,…, q_n}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x₁, x₂, x₃, x₄}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.

Автомат позволяет вырабатывать выходные сигналы Y={y₁, y₂, y₃}:

y₁ — переход из состояния q_i в состояние q_i (петля);

y₂ — переход из состояния q_i в q_j при i<j;

y₃ — переход из состояния q_i в q_j при i>j.

Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.

Таблица 1

Решение:

Множество вершин X = {x₁, x₂, x₃, x₄, x₅, x₆},

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q₁, q₂, q₃, q₄, q₅, q₆}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x₁, x₂, x₃, x₄}.

Автомат позволяет вырабатывать выходные сигналы Y={y₁, y₂, y₃}.

На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:

Гq₁ = {q₁ (x₁/y₁), q₃ (x₂/y₂), q₂ (x₃/y₂)},

Гq₂ = {q₄ (x₃/y₂), q₁ (x₄/y₃), q₃ (x₁/y₂)},

Гq₃ = {q₁ (x₁/y₃), q₅ (x₂/y₂), q₂ (x₃/y₃), q₄ (x₄/y₂)},

Гq₄ = {q₂ (x₁/y₃), q₆ (x₂/y₂), q₃ (x₃/y₃), q₅ (x₄/y₂)},

Гq₅ = {q₃ (x₄/y₃), q₄ (x₁/y₃), q₆ (x₂/y₂)}, Гq₆ = {q₄ (x₃/y₃), q₅ (x₄/y₃)}.

Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.2.

Таблица 2

Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.

Количество букв входного алфавита n = 4

Количество входовp? log₂ n = log₂ 4 = 2;

Количество букв выходного алфавита m = 2

Количество выходовe? log₂ m = log₂ 3 = 2;

Количество состояний r = 6

Количество триггеровz? log₂ r = log₂ 6 = 3.

Приступаем к кодированию:

На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.

Таблица 3

Используя таблицу переходов D-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через D₁, D₂, D₃, соответственно.

Таблица 4

По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D₁, D₂, и D₃, зависящих от набора переменных u₁, u₂, w₁ (t), w₂ (t), w₃ (t). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

Минимизируем функции согласно картам Карно:

После минимизации имеем набор функций в базисе И-НЕ

=

.

.

.

Функциональная схема структурного автомата: