Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 29
Текст из файла (страница 29)
Результаты, приведенные на рис. 2.53,д, получаются после выполнения следующей последовательности операций: приписать узлу 1 пометку [оо, — ], узлу 4 — пометку [+1, Ц, узлу 6 — пометку [+1, 4], узлу 9 — пометку [+1, 6], узлу 1О— [е2, 21 [еа, и 1+1, 61 1+1, З1 [+1, Ц [+2, 1! г Рис. 2.53. Решение задачи распределения сточных вод. а — вервая итерацвв; б — втарая итерация; е — третья итерация; а — четвертая итерация. б — пятая итерация: е — решение. Глава 2 174 [+1, 61 [+1, 41 д апьныя -в е Рис. 2.53 (продолжение). пометку [+1, 91.
Изменить потоки: 114=3, 14в=1, [вв=2 и [в,[о=2. Ни один из узлов сети, изображенной на рис. 2.53,е, не может быть помечен. Поэтому текущее решение является оптимальным, а величина максимального потока равна 8 ед. 2.14.5. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ Назначение: нахождение максимального потока в сети с ограниченной пропускной способностью. Локализация: подпрограмма МАХР[.0% в пакете сетевой оптимизации.
Ограничения: программа позволяет обрабатывать сети, содержащие до 50 узлов н 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме МАХР[.0% и основной программе. Входные данные: Набор 1. Одна карта с именем алгоритма МАХР в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110). 176 Детерминированные потоки е сетях Набор 3.
Общее число карт в данном наборе равно числу ориентированных дуг в сети. С каждой карты считываются следующие величины: 1) номер начального узла дуги, 2) номер конечного узла дуги, 3) пропускная способность дуги, 4) начальный поток по дуге (должно выполняться условие сохранения потока). Если поставлен знак пробела, то начальные потоки по всем дугам полагаются равными нулю.
Формат (4Х, 16, 11О, 2Р10.2). Набор 4. Данный набор состоит из одной карты, содержащей слово тРЕ)ЧЭ' в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. Используемые переменные: 1 — начальный узел дуги, 7— конечный узел дуги, А1 — пропускная способность дуги, А2— текущий поток по дуге. Используемый метод: начиная с произвольного потока, удовлетворяющего условию сохранения, с помощью процедуры расстановки пометок определяются всевозможные аугментальные пути потока. Как только аугментальный путь потока найден, поток увеличивается на столько единиц, на сколько позволяет пропускная способность этого пути.
Затем все пометки стираются. Алгоритм заканчивает работу, когда поток не может быть увеличен. Литература: 13Ц. 2.14.6. ЗАДАЧА О ТРАНСПОРТИРОВКЕ И ХРАНЕНИИ ЗЕРНА Многие развивающиеся страны расходуют большие суммы денег на то, чтобы устранить транспортные заторы и уменьшить затраты на транспортировку и хранение сельскохозяйственной продукции. Для исследования данных проблем полезным оказывается сетевой подход, который позволяет учитывать ограничения на пропускную способность различных звеньев транспортных сетей и давать количественную оценку улучшениям отдельных элементов этих сетей.
Упрощенный вид транспортной сети прибрежной части одного развивающегося района показан на рис. 2.54. Объем поставок зерна, производимого в узле 1, должен соответствовать производительности портового оборудования (расположенного в узле 7), предназначенного для погрузки зерна. Узлы 2, 3, 4, 5 и 6 являются хранилищами илн пунктами перепогрузки продукта.
Автодорожная сеть включает в себя современные автострады, однако в данный момент она является незаконченной. Железнодорожная сеть устаревшая и состоит из нескольких от- Глава 2 176 дельных веток. Числа, приписанные дугам сети, изображенной на рис.
2.54, соответствуют нулевому потоку, взятому в качестве начального решения, и максимально допустимым потокам по звеньям транспортной сети. ННННННН Железная дорога — Автострада Рис. 2.54. Упрощенный вид транспортной сети, предназначенной для перевоз- ки сельскохозяйственной продукции. 1100 Поток = 200 Рис. 2.55. Оптимальное решение в задаче транспортировки сельскохозяйст- венной продукции. Данная сетевая модель может быть легко модифицирована с целью определения влияния пропускных способностей некоторых дуг, или звеньев, транспортной сети на величину максимального потока. Для этого достаточно изменять соответствующие параметры дуг.
Новые транспортные линии обозначаются 177 Дете милироваяяае латали в еетяк дополнительными дугами и узлами. Аналогично при выходе из строя или закрытии транспортных линий соответствующие дуги сети удаляются. Алгоритмы поиска максимального потока являются мощным средством при исследовании альтернативных вариантов капиталовложения в транспортную сеть и систему хранилиш, особенно в тех случаях, когда улучшение отдельных компонентов системы может повлиять на всю систему в целом.
На рис. 2.55 указано оптимальное решение (максимальный поток), а решение, полученное на ЭВМ, показывает шаги вычислений; ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ ПАРАМЕТРЫ СЕТИ И НАЧАЛЬНОЕ РЕШЕНИЕ НАЧАЛЬНЫЙ КОНЕЧНЫЙ ПРОПУСКНАЯ СПО. ДУГОВОЙ УЗЕЛ ДУГИ УЗЕЛ ДУГИ СОБНОСТЬ ДУГИ ПОТОК 1 2 100,00 0,0 1 4 100,00 0,0 2 3 25,00 0,0 2 4 ИЮ,ОО 0,0 3 4 35,00 0,0 3 5 20эОО О,О 4 5 55,00 0,0 4 6 125,00 0,0 5 7 80,00 0,0 6 7 125,00 0,0 МАКСИМАЛЬНЫЙ ПОТОК ПО ПЕРЕЧИСЛЕННЫМ ВЫШЕ ДУГАМ и О О т ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ ПАРАМЕТРЫ СЕТИ И ДОПУСТИМОЕ РЕШЕНИЕ НАЧАЛЬНЫЙ КОНЕЧНЫЙ ПРОПУСКНАЯ СПО- ДУГОВОЙ УЗЕЛДУГИ УЗЕЛ ДУГИ СОБНОСТЬ ДУГИ ПОТОК 1 2 ПЮ,ОО 20,00 1 4 100,00 о,о 2 3 25,00 20,00 2 4 100,00 0,0 3 4 35,00 0,0 3 5 2000 20,00 4 5 55,00 0,0 4 б 125,00 0,0 5 7 80,00 20,00 б 7 125.00 0,0 МАКСИМАЛЬНЫЙ ПОТОК ПО ПЕРЕЧИСЛЕННЫМ ВЫШЕ ДУГАМ и 2О,ЕВ 12 — 1664 Глава 2 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ ПАРАМЕТРЫ СЕТИ И ОПТИМАЛЬНОЕ РЕШЕНИЕ НАЧАЛЬНЫЙ КОНЕЧНЫЙ ПРОПУСКНАЯ СПО" ДУГОВОЙ УЗЕЛ ДУГИ УЗЕЛ ДУГИ СОБНОСТЬ ДУГИ ПОТОК 1 г 100Д0 100,00 1 4 100,00 100,00 2 3 25,00 20,00 2 4 100,00 80,00 3 4 35,00 0,0 3 5 20,00 20 00 4 5 55,00 55,00 4 6 125,00 125,00 5 7 80,00 75,00 6 7 125,00 125,00 ФАКСИМАЛЬНЫЙ ПОТОК ПО ПЕРЕЧИСЛЕННЫМ ВЫШЕ ДУГАМ = 200,06 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ ПАРАМЕТРЫ СЕТИ И ДОПУСТИМОЕ РЕШЕНИЕ НАЧАЛЬНЫЙ КОНЕЧНЫЙ ПРОПУСКНАЯ СПО.
ДУГОВОЙ УЗЕЛ ДУГИ УЗЕЛ ДУГИ СОБНОСТЬ ДУГИ ПОТОК 1 2 100,00 100,00 1 4 100,00 100,00 2 3 25,00 20,00 2 4 100 00 80,00 3 4 35,00 0,0 3 5 20,00 20,00 4 5 55,00 55,00 4 6 125,00 125,00 5 7 80,00 75,00 6 7 125,00 125,00 МАКСИМАЛЬНЫЙ ПОТОК ПО ПЕРЕЧИСЛЕННЫМ ВЫШЕДУГАМ = 200 Г ЕЛ6. ЗАДАЧА О МНОГОПОЛЮСНОМ МАКСИМАЛЬНОМ ПОТОКЕ Существует большой ряд технических и экономических задач, в которых рассматриваемые системы могут быть приближенно описаны в виде детерминированных многополюсных потоковых моделей. Примерами таких систем являются: 1) транспортные сети, где автострады изображаются дугами, пропускные способности которых соответствуют максимально допустимой интенсивности движения; 2) телефонные сети, где телефонные линии представляются дугами, а пропускные способности соответствуют максимальному числу вызовов, которые могут обслуживаться в каждый момент времени; 3) электроэнергетические распределительные системы, где линии электропере- !79 Детерминированные нотохи в сетях дачи представлены дугами, а пропускные способности соответствуют максимальному объему электроэнергии, который может передаваться по линиям в единицу времени.
Во всех этих задачах предполагается существование нескольких источников некоторого продукта. Предполагается также, что величина продукта, который может транспортироваться к нескольким стокам, ограничена только пропускными способностями распределительных звеньев. Рассмотрим неориентированную сеть с ограниченной пропускной способностью, т. е. сеть, в которой потоки по дугам не должны превосходить пропускных способностей соответствующих дуг.
В предыдущем разделе была описана процедура расстановки пометок для решения задачи с одним источником и одним стоком, в которой предполагалось, что из источника может поступать неограниченное количество продукта. Цель задачи состояла в нахождении максимального количества продукта, который может транспортироваться нз источника в сток по дугам сети, не нарушая ограничений на пропускные способности дуг. Несколькими математиками была рассмотрена задача нахождения максимального потока для всех пар узлов в неориентированной сети 17, 15, 251.
Данную задачу можно рассматривать как обобщение задачи с одним источником и одним стоком, и для ее решения можно воспользоваться процедурой, описанной в разд. 2.14.1, применяя ее к каждой паре узлов. Более изящный и более эффективный метод был предложен Гомори н Ху [25). В настоящем разделе используются основные результаты, полученные в работе 1251, и дается обоснование алгоритма.
Если пропускная способность каждой дуги не зависит от направления движения потока по этой дуге и если каждую пару узлов можно рассматривать как пару источник — сток, то общее число задач о максимальном потоке, которое должно быть решено, равно л(л — 1)/2, где п — число узлов в сети. При работе алгоритма Гомори — Ху максимальный поток определяется только и — 1 раз. 2.!5.!. АЛГОРИТМ ГОМОРИ вЂ” ХУ Пусть 6=(й(, А) — неориентированная сеть, где в) — множество узлов„ А — множество дуг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
