Контрольная работа: Математические основы теории систем
Максимальный поток j max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:
Первый шаг.1. Находим какой-либо путь из х 1 в х 9 с положительной пропускной способностью.
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 |
В результате получен путь l1 = (x1 , х3 , х6 , х9 ). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов 
табл.1 вычитаем C1 , а к элементам 
прибавляем C1 . В результате получим новую табл.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, находим второй путь l2 = (x1 ,x3 , х7 , х9 ) и расставляем знаки.
2. Пропускная способность пути l2
Изменим пропускные способности помеченных дуг на С2 в табл.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. Пометив столбцы, находим l3 = (x1 , х4 , х7 ,x9 ) .
Величина потока по пути l3
Вычислив новые пропускные способности дуг, приходим к табл.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, находим четвертый путь l4 = (x1 , х2 , х8 , х9 ) и расставляем знаки.
2. Пропускная способность пути l 4
Изменим пропускные способности помеченных дуг на С4 в табл.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, находим четвертый путь l5 = (x1 , х4 , х8 , х9 ) и расставляем знаки.
2. Пропускная способность пути l5
Изменим пропускные способности помеченных дуг на С5 в табл.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 1 в вершину x 9 . Подмножество R образуют помеченные вершины х1 ,х2 , х3 , х4 , х5 , х6 , х7 ,х8 , а подмножество 
- одна непомеченная вершины х9 . Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R , а конечные - . Таким образом, разрез с минимальной пропускной способностью 
. Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза