Математические основы теории систем (стр. 4 из 5)

Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7

Таблица 7.

x1	x2	x3	x4	x5	x6	x7	x8	x9
x1	6	7	4
x2	-6	0	0	6
x3	-7	0	3	4
x4	-4	0	0	2	2
x5	0	0
x6	-3	0	3
x7	4	2	0	0	6
x8	-6	-2	0	0	8
x9	-3	-6	-8

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

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

.

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

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

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

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

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

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

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

Таблица 1

№варианта	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
m1	0	1	0	1	1	1	1	2	2	0	1	3	0	1	1
m2	1	2	2	2	3	1	2	2	1	2	3	1	1	2	0
m3	2	3	1	0	1	1	1	3	2	1	0	1	2	3	3
m4	3	1	3	4	0	2	1	1	0	1	1	2	1	1	2
m5	1	2	5	1	2	2	3	0	3	3	2	0	3	2	1
№ рисунка	Рис.23				Рис.27				Рис.28				Рис.29

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции 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

№ варианта	11	12	13	14	15	16	17	18	19	20
Тип элементов	ИНЕ	ИИЛИНЕ	ИНЕ	ИЛИНЕ	ИНЕ	ИИЛИНЕ	ИНЕ	ИЛИНЕ	ИИЛИНЕ	ИНЕ
Тип триггера	D	JK	T	D	RS	RSD	D	JK	T	D

Решение:

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