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

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

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

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

Решение:

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

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

Tаблица 1.

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (3)	x8 (2)	x9 (6)
x1		7	9-	4
x2	0			8	3			6
x3	0+			5		8-	4
x4	0	0	0				9	2
x5		0						2
x6			0+				5		3-
x7			0	0		0		7	6
x8		0		0	0		0		8
x9						0+	0	0

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

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

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

Tаблица 2

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (3)	x8 (2)	x9 (7)
x1		7	6-	4
x2	0			8	3			6
x3	3+			5		5	4-
x4	0	0	0				9	2
x5		0						2
x6			3				5		0
x7			0+	0		0		7	6-
x8		0		0	0		0		8
x9						3	0+	0

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

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

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

Tаблица 3

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (4)	x8 (2)	x9 (7)
x1		7	2	4-
x2	0			8	3			6
x3	7			5		5	0
x4	0+	0	0				9-	2
x5		0						2
x6			3				5		0
x7			4	0+		0		7	2-
x8		0		0	0		0		8
x9						3	4+	0

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

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

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

Таблица 4

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (4)	x8 (2)	x9 (8)
x1		7-	2	2
x2	0+			8	3			6-
x3	7			5		5	0
x4	2	0	0				7	2
x5		0						2
x6			3				5		0
x7			4	2		0		7	0
x8		0+		0	0		0		8-
x9						3	6	0+

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

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

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

Таблица 5

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (4)	x8 (4)	x9 (8)
x1		1	2	2-
x2	6			8	3			0
x3	7			5		5	0
x4	2+	0	0				7	2-
x5		0						2
x6			3				5		0
x7			4	2		0		7	0
x8		6		0+	0		0		2-
x9						3	6	6+

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

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

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

Таблица 6

	x1	x2 (1)	x3 (1)	x4 (1)	x5 (2)	x6 (3)	x7 (4)	x8 (5)	x9
x1		1	2	0
x2	6			8	3			0
x3	7			5		5	0
x4	4	0	0				7	0
x5		0						2
x6			3				5		0
x7			4	2		0		7	0
x8		6		2	0		0		0
x9						3	6	8

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

Заключительный шаг. Вычитая из элементов табл.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₆},

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний 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

X	Q	q1	q2	q3	q4	q5	q6
X1		q1/y1	q3/y2	q1/y3	q2/y3	q4/y3	─
X2		q3/y2	─	q5/y2	q6/y2	q6/y2	─
X3		q2/y2	q4/y2	q2/y3	q3/y3	─	q4/y3
X4		─	q1/y3	q4/y2	q5/y2	q3/y3	q5/y3

Осуществим структурный синтез автомата, заданного табл.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.

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

x

u

u1

u2

x1	1	0	5
x2	1	1	4
x3	0	0	5
x4	0	1	5

v1

v2

y1	1	0	1
y2	0	1	9
y3	0	0	9

q

w

w1

w2

w3

q1	0	0	1	3
q2	0	1	0	3
q3	0	0	0	4
q4	1	0	0	4
q5	0	1	1	3
q6	1	1	0	2

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

Таблица 3

u1u2	w1w2w3	001	010	000	100	011	110
10		001/10	000/01	001/00	010/00	100/00	─
11		000/01	─	011/01	110/01	110/01	─
00		010/01	100/01	010/00	000/00	─	100/00
01		─	001/00	100/01	011/01	000/00	011/00

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

Таблица 4

u1	u2	w1 (t)	w2 (t)	w3 (t)	w1 (t+1)	w2 (t+1)	w3 (t+1)	v1	v2	D1	D2	D3
1	0	0	0	1	0	0	1	1	0	0	0	1
1	1	0	0	1	0	0	0	0	1	0	0	0
0	0	0	0	1	0	1	0	0	1	0	1	0
0	1	0	0	1	*	*	*	*	*	*	*	*
1	0	0	1	0	0	0	0	0	1	0	0	0
1	1	0	1	0	*	*	*	*	*	*	*	*
0	0	0	1	0	1	0	0	0	1	1	0	0
0	1	0	1	0	0	0	1	0	0	0	0	1
1	0	0	0	0	0	0	1	0	0	0	0	1
1	1	0	0	0	0	1	1	0	1	0	1	1
0	0	0	0	0	0	1	0	0	0	0	1	0
0	1	0	0	0	1	0	0	0	1	1	0	0
1	0	1	0	0	0	1	0	0	0	0	1	0
1	1	1	0	0	1	1	0	0	1	1	1	0
0	0	1	0	0	0	0	0	0	0	0	0	0
0	1	1	0	0	0	1	1	0	1	0	1	1
1	0	0	1	1	1	0	0	0	0	1	0	0
1	1	0	1	1	1	1	0	0	1	1	1	0
0	0	0	1	1	*	*	*	*	*	*	*	*
0	1	0	1	1	0	0	0	0	0	0	0	0
1	0	1	1	0	*	*	*	*	*	*	*	*
1	1	1	1	0	*	*	*	*	*	*	*	*
0	0	1	1	0	1	0	0	0	0	1	0	0
0	1	1	1	0	0	1	1	0	0	0	1	1

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

.

.

.

.

.

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

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

=

.

.

.

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