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

(L₁L₃L₅+L₁L₃L₆+L₁L₃L₁₀+L₁L₃L₁₇+L₁L₃L₁₈+L₁L₄L₆+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.

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, а конечные - . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза