[Ю, 3]

д)/5 = 10 е) Сквозных путей нет

Рис. 6.31. Последовательное выполнение алгоритма нахождения максимального потока

Шаг 2. = {4} (отметим, что с35 = 0, поэтому узел 5 не включается в S3).

Шаг 3. k = 4, назначаем я4 = с34 = 10 и помечаем узел 4 меткой [10, 3]. Полагаем / = 4 и возвращаемся к шагу 2.

Шаг 2. ШагЗ.

4= {5} (поскольку узлы 1 и 3 уже помечены, они не включаются в 54).

к - 5 и а& = с45 = 20. Помечаем узел 5 меткой [20, 4]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. N2 = {1, 2, 3, 4, 5} и/2 = min{oo, 20, 40,10, 20} = 10. Вычисляем остаточные пропускные способности вдоль пути N2:

(с12, с21) - (20 - 10, 0 + 10) = (10, 10),

(ся, с32) = (40 - 10, 0 + 10) = (30, 10),

(cM,cJ-(10-10, 5+ 10)-(0,15),

(с4б, cj = (20 - 10, 0 + 10) - (10, 10).

Итерация 3

Итерация 4. На этой итерации получен путь N4 = {1, 3, 2, 5} с/4 = 10 (проверьте!).

Итерация 5. На этой итерации получен путь Ns = {1, 4, 5} с/5 = 10 (проверьте!).

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

Шаг6. Максимальный объем потока в сети равен F = /, +/2 + ... +/5 = 20 + 10 + 10 + 10 + 10 = 60 единиц. Значения потоков по различным ребрам вычисляются путем вычитания последних значений оста-

точных пропускных способностей (т.е. (с/( с.()6) из первоначальных значений пропускных способностей (С,у,С\). Результаты вычислений приведены в следующей таблице.

Ребро (CjpCV) - (с,у, Су,)6 Величина потока Направление

Программа TORA позволяет найти максимальный поток или в автоматическом режиме, или последовательно - так, как показано ранее. В меню SOLVE/MODIFY выберите команду Solve problem. После задания выходного формата перейдите в выходное окно и выберите команду Maximum Flows (Максимальный поток) или Iterations. На рис. 6.32 показано выходное окно TORA с первыми двумя итерациями решения задачи из примера 6.4.2 (файл ch6ToraMaxFlowEx6-4-2.txt).

УПРАЖНЕНИЯ 6.4.2

1. В задаче из примера 6.4.2

a) для всех ребер определите величины неиспользованных пропускных способностей;

b) найдите величину потока, проходящего через узлы 2, 3 и 4;

c) можно ли увеличить максимальный поток в сети путем повышения пропускных спесобностей в направлениях 3 -> 5 и 4 -> 5?

2. Найдите максимальный поток и значения потоков, проходящих через каждое ребро сети, показанной на рис. 6.33.

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

a) Определите ежедневную производительность каждого нефтеперегонного завода, соответствующую максимальной пропускной способности сети трубопроводов.

b) Определите ежедневную потребность каждого распределительного терминала, соответствующую максимальной пропускной способности сети трубопроводов.

c) Определите ежедневную пропускную способность каждой насосной станции, соответствующую максимальной пропускной способности сети трубопроводов.