Задача 2. Задача о максимальном потоке и потоке минимальной стоимости
На рисунке приведена транспортная сеть в виде ориентированного графа.
Для заданной сети определить: максимальный поток max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.
Решение:
Первый шаг. 1. Находим какой-либо путь из х1 в х8 с положительной пропускной способностью.
Tаблица 1
|
x1 |
x2(1) |
x3(1) |
x4(2) |
x5(1) |
x6(3) |
x7(4) |
x8(5) |
x1 |
|
5 |
4 |
|
6- |
|
|
|
x2 |
0 |
|
10 |
8 |
18 |
|
|
|
x3 |
0 |
0 |
|
|
|
5 |
|
|
x4 |
|
0 |
|
|
|
3 |
9 |
|
x5 |
0+ |
0 |
|
|
|
6 |
|
16- |
x6 |
|
|
0 |
0 |
0 |
|
|
7 |
x7 |
|
|
|
0 |
|
|
|
15 |
x8 |
|
|
|
|
0+ |
0 |
0 |
|
В результате получен путь l1 = (x1,х5,х8). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji – знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем
остаточные пропускные способности дуг
найденного пути и симметричных ему дуг.
Для этого из элементов
табл. 1 вычитаем C1,
а к элементам
прибавляем C1.
В результате получим новую табл. 2 с
измененными пропускными способностями.
Tаблица 2
|
x1 |
x2(1) |
x3(1) |
x4(2) |
x5(2) |
x6(3) |
x7(4) |
x8(5) |
x1 |
|
5- |
4 |
|
0 |
|
|
|
x2 |
0+ |
|
10 |
8 |
18- |
|
|
|
x3 |
0 |
0 |
|
|
|
5 |
|
|
x4 |
|
0 |
|
|
|
3 |
9 |
|
x5 |
6 |
0+ |
|
|
|
6 |
|
10- |
x6 |
|
|
0 |
0 |
0 |
|
|
7 |
x7 |
|
|
|
0 |
|
|
|
15 |
x8 |
|
|
|
|
6+ |
0 |
0 |
|
Второй шаг. 1. Помечаем столбцы табл. 2, находим второй путь l2 = (x1, x2,х5,х8) и расставляем знаки.
2. Пропускная способность пути l2
Изменим пропускные способности помеченных дуг на С2 в табл. 3.
Tаблица 3
|
x1 |
x2(1) |
x3(1) |
x4(2) |
x5(1) |
x6(3) |
x7(4) |
x8(6) |
x1 |
|
0 |
4- |
|
0 |
|
|
|
x2 |
5 |
|
10 |
8 |
13 |
|
|
|
x3 |
0+ |
0 |
|
|
|
5- |
|
|
x4 |
|
0 |
|
|
|
3 |
9 |
|
x5 |
6 |
5 |
|
|
|
6 |
|
5 |
x6 |
|
|
0+ |
0 |
0 |
|
|
7- |
x7 |
|
|
|
0 |
|
|
|
15 |
x8 |
|
|
|
|
11 |
0+ |
0 |
|
Третий шаг. 1. Пометив столбцы, находим l3 = (x1,х3,х6.x8).
Величина потока по пути l3
Вычислив новые пропускные способности дуг, приходим к табл. 4.
Tаблица 4
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x1 |
|
0 |
0 |
|
0 |
|
|
|
x2 |
5 |
|
10 |
8 |
13 |
|
|
|
x3 |
4 |
0 |
|
|
|
1 |
|
|
x4 |
|
0 |
|
|
|
3 |
9 |
|
x5 |
6 |
5 |
|
|
|
6 |
|
5 |
x6 |
|
|
4 |
0 |
0 |
|
|
3 |
x7 |
|
|
|
0 |
|
|
|
15 |
x8 |
|
|
|
|
11 |
4 |
0 |
|
Четвертый
шаг.
Просматривая строки, убеждаемся в том,
что больше не существует ни одного пути
с положительной пропускной способностью
из вершины x1
в вершину x8.
Подмножество R
образуют помеченные вершины х1,
х4,
х5,
х7,
а подмножество
–
все остальные непомеченные вершины
х2,
х3,
х6,
х8.
Разрез с минимальной пропускной
способностью образуют дуги, начальные
вершины которых принадлежат подмножеству
R,
а конечные –
.
Таким образом, разрез с минимальной
пропускной способностью
.
Удалив дуги этого разреза, блокируем
все пути из источника в сток. Пропускная
способность разреза
Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.4, получим табл.5
Таблица 5
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x1 |
|
5 |
4 |
|
6 |
|
|
|
x2 |
-5 |
|
0 |
0 |
5 |
|
|
|
x3 |
-4 |
-0 |
|
|
|
4 |
|
|
x4 |
|
-0 |
|
|
|
0 |
0 |
|
x5 |
-6 |
-5 |
|
|
|
0 |
|
11 |
x6 |
|
|
-4 |
-0 |
-0 |
|
|
4 |
x7 |
|
|
|
-0 |
|
|
|
0 |
x8 |
|
|
|
|
-11 |
-4 |
-0 |
|
Величина максимального потока равна сумме элементов x1-й строки табл. 5 или сумме элементов x8-го столбца.
Максимальный
поток равен
.
Дуговые потоки:
Стоимость доставки груза по путям, формирующим максимальный поток:
d=6*10+5*7+11*10=205