Главная | Обратная связь | Поможем написать вашу работу!

Задача о максимальном потоке

Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперегонных заводов. Для перекачки нефти предусмотрены магистральные насосные станции. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты трубопровода могут быть как однонаправленные (осуществляют перекачку нефти только в одном направлении), так и двунаправленные. В однонаправленных сегментах положительная пропускная способность предполагается в одном направлении и нулевая — в другом. На рис. 6.22 показана типовая сеть нефтепроводов. Как определить максимальную пропускную способность (т.е. максимальный поток) между нефтяными скважинами и нефтеперегонными заводами?

При решении данной задачи исходную сеть необходимо свести к сети с одним источником и одним стоком. Этого можно достигнуть путем введения дополнительных дуг с бесконечной пропускной способностью от источника к скважинам и от нефтеперегонных заводов к стоку (на рис. 6.22 эти дуги показаны пунктирными линиями).

Для ребра (i,j), где i<j, используем запись (C_ij, С_ji) для представления пропускных способностей в направлениях i —>j и j ->i соответственно. Во избежание недоразумений на схеме сети С_ij будем располагать на ребре (i,j) ближе к узлу i, а С_ji — ближе к узлу j, как показано на рис.

Перебор разрезов

Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к стоку. Пропускная способность разреза равна сумме пропускных способностей "разрезанных" ребер. Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.

Пример 1

Рассмотрим сеть, показанную на рис. 6.24. На этом рисунке при обозначении пропускных способностей двунаправленных ребер придерживались соглашения, принятого ранее (рис. 6.23). Например, для ребра (3, 4) пропускная способность в направлении 3 —> 4 равна 10, а в направлении 4 —> 3 — 5.

Разрезы, представленные на рис. 6.24, имеют следующие пропускные способности.

Разрез “Разрезанные” ребра Пропускная пособность

1 (1,2), (1,3), (1,4) 10 + 30 + 20=60

2 (1, 3), (1,4), (2, 3), (2, 5) 30 + 10 + 40 + 30 = 110

3 (2, 5), (3, 5), (4, 5) 30 + 20 + 20 =70

Вывод, который можно сделать из этих трех разрезов, заключается в том, что максимальный поток не может превышать 60 единиц. Но мы не можем сказать, какой максимальный поток на самом деле, так как не перебрали все возможные разрезы сети. К сожалению, перебор всех разрезов является непростой задачей. Поэтому для определения максимального потока в сети не используются алгоритмы, основанные на полном переборе разрезов.

Упражнения к лабораторной работе № 3

1. Для сети, показанной на рис. 6.24, проведите еще два разреза и найдите их пропускные способности.

Пример -2

Найдем максимальный поток в сети из примера 6.5-1 (рис. 6.24). На рис. 6.26 предлагается графическая иллюстрация выполнения алгоритма. Считаем полезным сравнить описание выполняемых алгоритмом вычислительных итераций с их графическим представлением.

Итерация 1

Положим остаточные пропускные способности (с_ij, с_ji) всех ребер равными первоначальным пропускным способностям (Ĉ_ij, Ĉ_ji).

Шаг 1. Назначаем а1 = oo и помечаем узел 1 меткой [oo, —]. Полагаем i = 1.

Шаг 2. S₁ = [2, 3, 4] (<> 0).

Шаг 3. k = 3, поскольку c₁₃ = mах{с₁₂, с₁₃, с_!4} = mах{20, 30, 10} = 30. Назначаем a₃ ⁼ с₁₃ = 30 и помечаем узел 3 меткой [30, 1]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. S₂ = [4, 5].

Шаг 3. k = 5 и a₅ ⁼ c₃₅ ~ mах{10, 20} = 20. Помечаем узел 5 меткой [20, 3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: (5) -> [20, 3] -> (3) -> [30,1] -> (1). Таким образом, N₁ = {1, 3, 5}

и f1 = min{a1, a3, a4 } = {oo, 30, 20} = 20. Вычисляем остаточные пропускные способности вдоль пути N1:

(с13,с31) = (30-20,0 + 20) = (10,20),

(с35, с53) = (20 - 20, 0 + 20) = (0, 20).

Итерация 2

Шаг 1. Назначаем а₁ = oo и помечаем узел 1 меткой [oo, —]. Полагаем i= 1.

Шаг 2. S₁ = [2, 3,4].

Шаг 3. k = 2, назначаем а₂ = с₁₂ = mах{20, 10, 10} = 20 и помечаем узел 2 меткой [20, 1]. Полагаем i = 2 и возвращаемся к шагу 2.

Шаг 4. S₂ = [3,5].

Шаг 5. k = 3 и a₃ = с₂₃ = 40. Помечаем узел 3 меткой [40, 2]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. S₃ = [4] (отметим, что с₃₅ = 0, поэтому узел 5 не включается в S₃).

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

Шаг 2. S₄ = [5] (поскольку узлы 1 и 3 уже помечены, они не включаются в S₄).

Шаг 3. k = 5 и а₅ = с₄₅ = 20. Помечаем узел 5 меткой [20, 4]. Получен сквозной путь. Переходим к шагу 5.

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

(c₁₂,c₂₁) = (20-10,0+10) = (10, 10),

(с₂₃,с₃₂) = (40-10,0+10) = (30, 10),

(c₃₄,с₄₃) = (10-10,5+10) = (0, 15),

(с₄₅, с₅₄) = (20 - 10, 0 + 10) = (10, 10).

Итерация 3

Шаг 1. Назначаем а1=oo и помечаем узел 1 меткой [oo, —]. Полагаем i = 1.

Шаг 2. S₁ = [2, 3,4].

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

Шаг 2. S₂ = [3,5].

Шаг 3. k = 3 и a₃ = с₂₃ = 30. Помечаем узел 3 меткой [30, 2]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. Sз = 0 (поскольку с₃₄ = с₃₅ = 0). Переходим к шагу 4.

Шаг 4. Метка [30, 2] узла 3 показывает номер предшествующего узла r = 2. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. Полагаем i = r = 2 и возвращаемся к шагу 2.

Шаг 2. S₄ = [5] (поскольку узел 3 удален из возможного сквозного пути).

Шаг 3. k = 5 и а₅ = c₂₅⁼ 30. Помечаем узел 5 меткой [30,2]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. N₃ = {1, 2, 5} и f₃ = min{oo, 10, 30} = 10. Вычисляем остаточные пропускные способности вдоль пути N₃:

(c_I2,c₂₁) = (10-10, 10+10) = (0,20), (с₂₅,с₅₂) = (30-10,0+10) = (20, 10).

Итерация 4

На этой итерации получен путь N₄ = {1, 3, 2, 5} c f₄= 10 (проверьте!).

Итерация 5

На этой итерации получен путь N₅ = {1, 4, 5} c f₅ - 10 (проверьте!).

Итерация б

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

Шаг 6. Максимальный объем потока в сети равен F=f₁ +f₂ +... +f₅ = 20 + 10 + 10 + 10+ 10 = 60 единиц. Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей (т.е. (c_ij, с_ji)₆) из первоначальных значений пропускных способностей

(C_ij,С_ji). Результаты вычислений приведены в следующей таблице.

Ребро (С_ij, С_ji) - (с_ij с_ji)₆ Величина Направление

потока

(1.2) (20, 0) - (0, 20) = (20, -20) 20 1 -> 2

(1.3) (30, 0) - (0, 30) = (30,-30) 30 1->3

(1.4) (10,0)-(0, 10) = (10,-10) 10 1->4

(2,3) (40, 0) - (40, 0) = (0, 0) 0 —

(2,5) (30,0)-(10, 20) = (20,-20) 20 2-> 5

(3.4) (10, 5)-(0, 15) = (10,-10) 10 3->4

(3.5) (20, 0) - (0, 20) = (20,-20) 20 3-> 5

(4, 5) (20, 0) - (0, 20) = (20, -20) 20 4-> 5

Упражнения

1. В задаче из примера 6.5-2

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

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

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

2. С помощью программы TORA проверьте все вычисления, выполненные в примере 6.5-2 и показанные на рис. 6.26.

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

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

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

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

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

5. Пусть в сети из предыдущего упражнения (рис. 6.28) пропускная способность насосной станции 6 ограничена 60 миллионами баррелей в день. Найдите максимальную пропускную способность сети с учетом этого ограничения.

6. Зерно из трех зернохранилищ доставляется на грузовиках четырем птицеводческим фермам, при этом некоторые зернохранилища не могут непосредственно поставлять зерно определенным фермам. Пропускная способность маршрутов от зернохранилищ до птицеводческих ферм ограничена количеством используемых грузовиков и числом выполняемых ежедневно рейсов. В следующей таблице показаны ежедневные предложения зернохранилищ и ежедневный спрос птицеводческих ферм (в тысячах фунтов), в ячейках таблицы указаны пропускные способности соответствующих маршрутов.

a) Найдите схему транспортировки зерна, обеспечивающую максимальный спрос птицеводческих ферм.

b) Существует ли при данных условиях схема транспортировки, обеспечивающая весь спрос птицеводческих ферм?

7. Пусть в задаче из предыдущего упражнения возможна транспортировка зерна между зернохранилищами 1 и 2, а также 2 и 3. Кроме того, возможна транспортировка между фермами 1 и 2, 2 и 3, 3 и 4. Максимальная пропускная способность в обоих направлениях указанных маршрутов составляет 50 тысяч фунтов. Как данные предположения скажутся на обеспечении пока неудовлетворенного спроса птицеводческих ферм?

8. Родители имеют пять детей подросткового возраста, которых ежедневно привлекают к пяти видам домашней работы. Опыт трудового воспитания детей показал, что принудительное (силовое) назначение на работу чревато конфликтами. Поэтому дети сами составили список своих предпочтений, который приведен в следующей таблице.

Ребенок Предпочтительные работы

Ральф 3,4 или 5

Мэй 1

Бен 1 или 2

Ким 1,2 или 5

Кен 2

Теперь родителям осталось найти такое распределение работ, которое в наибольшей степени учитывало бы предпочтения детей. Найдите максимальное количество таких распределений работ.

11. Максимальный и минимальный потоки в сети с нижними положительными границами пропускных способностей. В этом разделе при выполнении алгоритма нахождения максимального потока в сети неявно предполагалось, что нижние границы пропускных способностей всех ребер равны нулю. В некоторых задачах нижние границы пропускных способностей могут быть строго положительными. В таком случае возникает интерес к нахождению как максимального, так и минимального потоков в сети (см. комплексную задачу 6-3 в конце главы). Наличие положительных нижних границ пропускных способностей вызывает определенные затруднения, так как в этом случае сеть вообще может не иметь допустимого потока. Максимальный и минимальный потоки в сети можно найти, выполняя следующие действия.

Шаг 1. Найдите начальное допустимое решение для сети с положительными нижними границами пропускных способностей.

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

а) Покажите, что поток через дугу (i, j) величина которого ограничена неравенствами l_ij< x_ij < u_ij представим в виде стока со спросом l_ij в узле _i, источником с предложением l_ij в узле j и потоком, ограниченным неравенствами 0 < x`_ij < u_ij - l_ij.

b) Покажите, что нахождение допустимого решения в исходной сети эквивалентно нахождению максимального потока в сети, где (1) поток x_ij через каждую дугу (i,j) заменен потоком х'_ij. с ограничениями

0 < x'_ij < u_ij - l_y (как показано в предыдущем пункте); (2) все источники "слиты" в один с выходящей из него дугой, имеющей пропускную способность l_ij: (3) все стоки "слиты" в один с входящей в него дугой, имеющей пропускную способность l_ij: (4) конечный узел i соединен с узлом источника s исходной сети дугой с бесконечной пропускной способностью. Допустимое решение существует, если максимальный поток в новой сети равен сумме нижних границ пропускных способностей исходной сети. Примените описанную процедуру к следующей сети и найдите допустимое решение (поток).

Дуга (i,j) (lij,u_ij)

(1,2) (5,20)

(1,3) (0,15)

(2,3) (4,10)

(2,4) (3,15)

(3,4) (0,20)

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

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

⇐ Предыдущая 1 23