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

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

Связный ориентированный граф G (Х, Г) задан множеством вершин X={x₁, x₂,…,x_n} и отображением Гx_i={x_|I±k|,x_|I±l|},i =1, 2,…,n. Здесь i- текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов a,b, g… переменной x в отображении Гx_i = {x_a,x_b,x_g,…}. Если значения индексов a, b,g… переменной 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={x_|I±k|,x_|I±l|}.

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

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

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

Г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. Задача о максимальном потоке и потоке минимальной стоимости

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

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

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

Решение:

Максимальный поток j_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^- = [1000] · ; [1 3 0 1 2] ≥ [00001] –

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

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

.

Переход t₂

[μ₀] ≥ [0100]* D^- = [0100]·;[1 3 0 1 2] ≥ [10000] –

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

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

.

Переход t₃

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

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

Переход t₄

[μ₀] ≥ [0001]* D^- = [0001]·;[1 3 0 1 2] ≥ [01110] –

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

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

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

Уравнение принимает вид

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

.

Приравняем составляющие векторов

Система имеет решение 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). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

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

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

=

.

.

.

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