Шаг 2. Используя допустимое решение, найденное на первом этапе, определите максимальный и минимальный потоки в сети.

a) Покажите, что поток через дугу (i, j), величина которого ограничена неравенствами 1Ц < хц < иц, можно представить в виде стока со спросом J. в узле i, источником с предложением lif в узле j и потоком, ограниченным неравенствами 0 < xtj < иц - 1Ц.

b) Покажите, что нахождение допустимого решения в исходной сети эквивалентно нахождению максимального потока в сети, где 1) поток х через каждую дугу (£, заменен потоком x{j с ограничениями 0 < хч < иц - l,j (как показано в предыдущем пункте); 2) все источники слиты в один с выходящей из него дугой, имеющей пропускную способность I ; 3) все стоки слиты в один с входящей в него дугой, имеющей пропускную способность /,.; 4) конечный узел t соединен с узлом источника s исходной сети дугой с бесконечной пропускной способностью. Допустимое решение существует, если максимальный поток в новой сети равен сумме нижних границ пропускных способностей исходной сети. Примените описанную процедуру к следующей сети и найдите допустимое решение (поток).

С/у. Щ)

(5, 20) (0, 15) (4, 10) (3, 15) (0, 20)

Дуга (/,./)

(1,2) (1,3) (2, 3) (2, 4) (3, 4)

c) Чтобы вычислить минимальный поток в исходной сети, используйте допустимое решение, найденное в предыдущем пункте, совместно с алгоритмом поиска максимального пото-кд. (Совет. Сначала на основе имеющегося допустимого решения найдите остаточную сеть. Далее определите максимальный поток от конечного узла сети к начальному. Теперь, комбинируя допустимый и максимальный потоки, найдите минимальный поток в исходной сети.)

d) Используя алгоритм нахождения максимального потока с допустимым решением, найденным в п. Ь, определите максимальный поток в исходной сети. {Совет. Начните с определения остаточной сети. Далее примените алгоритм поиска сквозных путей к этой сети.)

6.4.3. Формализация задачи поиска максимального потока как задачи ЛП

Обозначим через * . величину потока, проходящего по дуге (£, j), пусть с,. - пропускная способность этой же дуги. Предположим, что необходимо найти максимальный поток между начальным узлом s и конечным узлом t.

Ограничениями задачи ЛП будут уравнения баланса входного и выходного потоков для каждого узла. Целевая функция максимизирует или величину общего потока, выходящего из начального узла, или величину общего потока, входящего в конечный узел.

Пример 6.4.3

В задаче вычисления максимального потока в сети, показанной на рис. 6.29 (пример 6.4.2), s=l и f=5. В следующей таблице приведена соответствующая задача ЛП с двумя различными целевыми функциями, одна из которых максимизирует поток, выходящий из узла 1 (функция zt), вторая максимизирует поток, входящий в узел 5 (функция гг).

УПРАЖНЕНИЯ 6.4.3

1. Решите задачу из упражнения 6.4.2.2 как задачу линейного программирования.

2. Решите задачу из упражнения 6.4.2.5 как задачу линейного программирования.

6.4.4. Решение задачи определения максимального потока в Excel

Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно немного модифицировать, чтобы найти максимальный поток. Максимальный размер сети - 10 узлов. На рис. 6.35 показан рабочий лист, на котором решается задача из примера 6.4.2 (файл ch6SolverMaxFlow.xls). Матрица пропускных способностей записана в диапазоне В6:К15.4 Незаполненные ячейки матрицы пропускных способностей показывают, что соответствующие дуги имеют бесконечную пропускную способность. Нулевое значение пропускных способностей вводится для несуществующих дуг.

После того как будут введены значения пропускных способностей, рабочий лист пе-ресчитывается автоматически. Выделенные столбцы В, С, F и G содержат исходные данные задачи, необходимые для использования средства Поиск решения. Диапазон В20:В39 (изменяемые ячейки для средства Поиск решения) содержит величины потоков, проходящие по каждой дуге. Столбец С содержит значение пропускных способ-

4 На рис. 6.35 строки от 11 до 16 скрыты для экономии места.

ностей дуг (диапазон С20:С39). Все эти вычисления выполняются автоматически. Все, что необходимо сделать вам для решения задачи, - это указать диапазон изменяемых ячеек и задать ограничения в диалоговом окне средства Поиск решения. На рис. 6.35 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются как F20:F22=G20:G22 (баланс потоков для узлов 2, 3 и 4) и В20:В39<=С20:С39 (ограничения пропускных способностей дуг). Отметим, что целевая ячейка устанавливается автоматически и ее не надо изменять. Следует установить переключатель Равной максимальному значению, поскольку решается задача максимизации.

Задача нахождения максимального йотой

Входные данные

17 Оптимальное решение

i Общая стоимость : 60

От-в

N1 -N2 N1 -N3 N1-N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2-N5 N3-N1 N3-N2 N3-N4 N3-N5 N -N1

Поток

20 30 10 0 0 0 0 20 0 0 10 20 0

П: сп0с

20 30 10

40 0 30

10 20 0

Промежуточные ычиелонии

Имя Узел Поток Спрос От В Единичный поток

N1 К

N2 Я

N3 Т а

N4 1 4

N5 1 Sl -60

о о о

1 1 1 1

2 2 2 2 3

3 2 3 4

4 1 4 2

2 1

3! 1

3 4 5 1

Поиск решении

Установить целевую ячейку: Равной: <? детальному значению

г медиальному значению Имняя ячейки

Значению: (Г

Вьполнить ) Закрыть

ftB$20-$8$39 Ограничения:

$8$20,$В$39 <= $С$20:$С$Э9 tF$20:tFt22 = $GJ20:$G$22

Гзедполщкить

Добавить Изменить {

Параметры

Удалить

Восстановить Слравка

Рис. 6.35. Определение максимального потока в Excel

Решение N1-N2 = 20, Nl-N3 = 30, N1-N4 = 10, N2-N5 = 20, N3-N4=10, N3-N5 = 20 и N4-N5 = 20, показанное на рис. 6.35, дает максимальный поток, равный 60 единицам.