Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 28
Текст из файла (страница 28)
2. Сток 1 не может быть помечен. Это означает, что аугментальный путь потока не может быть найден. Следовательно, построенные дуговые потоки образуют оптимальное решение (максимальный поток). 2.14.2. ПРИМЕР РАБОТЫ АЛГОРИТМА РАССТАНОВКИ ПОМЕТОК Для иллюстрации работы алгоритма расстановки пометок для сети, изображенной на рис. 2.49, а, будет найден максимальный поток, который может протекать из узла и в узел 1. Каждой дуге (1, )) приписывается пометка [!гь Уг!1, где !г! — те- Описаннепроцедуры Шаги на1.д итерации Прнписатьузлуз пометку! ,.! Приписать узлу 2 пометку ! + 3, зт Приписать узлУ Г пометку ! + 2Я Изменение дугоеьм потоков: у =2УИ=2 фвги нет.а гпз~аИК Приписать уалу з пометку !а,.1; приписатьузпу1пометку! 92,з1 Приписатьузлу2пометку! +2,111 и рнписать узлу 3 пометку ! +1, 2! ' Приписатьузлурпометку! +1,3! Изменениедугоеык потокоа: Г 12 -т,ум г,ун 5,6 9 10 Поток 3 ф Рис.
2.49. Пример работы адгоритма расстаиоаки пометок. а — лерзаа итерация; 6 — вторая итерация; е — третья итерацяяг г — четвертая итераядяз д — пятая итерация. 11. 12 13 14 15, 16, 11 12 1Р 25 24 25 Рис. 2.49 (продолккеиие). Шаги на вппИудШ[Шю Шаги на Вп нтврацнн Описание процедуры Прнпнсать услуг пометку [П,.[; п рнпнсвть узлу 1 поьютку [ +1, г[ прнпно ать уюу г пометку [ + 1, 1[ иаменвннв дуговых потоков: .[в1 2.[н 1 Опнсаннв потще~щы Прйпнсатть ь[млуэ пометку [н,.[; и Рнлнсать уэпу 2 поматку [ + 1, 5 [; и Рнпнсвть уапу 1 пометку [-1, 2[ прнпнсат уюугпоме ку[+1 1[ Иамананнвдуговьм потоков: бн Опнседне епрогщдИщ Прнпнсвть уюуэ пометку(мЛ 1 прнпнсатьуапу 3 пометку1+1,3[ прнпнсатьуэпугпоьютку[+1,$[ т Иэнененнедуговьи потоков: 1 н 2 16.
ЯДИИУШ22ШШШДУИЫ Прнпнсвтьуюуг пометку[с .[ Нн один на уэлсе не может быть помечен, поэтому макснмальныд поток равен Е Глава 3 кущее значение дугового потока, а Уи — пропускная способность дуги. Вначале величины всех дуговых потоков полагаются равными нулю. При выполнении каждой итерации нужно пометить сток 1. Эта задача решается в 6 итерациях, результаты каждой из которых приводятся на рис. 2.49. 2.14.3. ТЕОРЕМА О МАКСИМАЛЬНОМ ПОТОКЕ И МИНИМАЛЬНОМ РАЗРЕЗЕ Пусть задана сеть 6=(М, А). Разобьем множество узлов М на два непересекающихся подмножества М, и М,. Эти два подмножества соединены между собой дугами, образующими множество А,.
Множество всех оставшихся дуг обозначим через А,. Предположим далее, что сток 1 принадлежит подмножеству Ма, а источник з — подмножеству М,. Тогда величина любого потока из М, в М„протекающего по дугам из множества А, не может быть больше, чем сумма пропускных способностей всех дуг из А., т.
е. мм Ива Этот абарьер для потока», отделяющий множество М. от М„ будем называть «разрезом» и обозначать его через (М„М.). Очевидно, что величина максимального потока, который может протекать из узла з в узел 1, ограничена сверху величиной этого разреза. Величина разреза (М„ М,) равна сумме пропускных способностей всех дуг из множества А„ по которым поток может протекать из М, в М,. Согласно теореме о максимальном потоке и минимальном разрезе, величина максимального потока из узла з в узел 1 равна величине минимального разреза, отделяющего узел з от узла 1.
Для иллюстрации теоремы о максимальном потоке и минимальном разрезе рассмотрим сеть, изображенную на рис. 2.50. Отметим, что существует несколько разрезов, отделяющих узел 6 от узла 1, и что величина максимального потока равна 8. Пропускные способности разрезов 1, 2 н 3, изображенных на рис. 2.50, равны 9, 12 и 8 соответственно. Поэтому разрез 3 является минимальным. Значение теоремы о максимальном потоке и минимальном разрезе заключается в том, что максимальный поток в сети с ограниченной пропускной способностью можно находить, вычисляя пропускные способности всех разрезов и выбирая среди полученных значений минимальное.
Конечно, при решении зада- Детерминированные лотони в остал чи о максимальном потоке этот результат имеет небольшое практическое значение, поскольку мы не получаем никакой информации о самих потоках ~н по дугам. Однако данный результат важен с теоретической точки зрения и часто используется при разработке сложных потоковых алгоритмов или при анализе решения иа оптимальность. Доказывается данная теорема следующим образом.
Пусть г — величина некоторого до- с 1 ! Раараа 1 (9) ( 1 $ Раареа 2 (12) Рпс. 2.50. Теорема о маклсмальпом потоке и мнпкмальлом раареаа. пустимого потока из узла з в узел й Для любого разреза (Х„Хс) справедливо равенство "-Л [Х вЂ” ХМ сел /си (еи или (ел (ем с Второе слагаемое равно нулю, поэтому (си кис ссис )еле теис Поскольку Х=ХДЛЧ, и узел не может одновременно принадлежать двум подмножествам Х.
и Хс, то Р=1 АМ+2'. ум —.')" 63 — Хб ми ми, (ем мм )енс теис (емс ~с"с 170 Глава л откуда следует, что (2.62) Х 2,"В=О Ы. )еТ. Р =;~',,")'„(уг) ~ ~Ум (2.66) Поэтому (2.67) )еТ. о Здесь предполагается, что поток (1п) максимальный. Разрез (1., 1.) может быть построен с помощью следующей процедуры (см. 1151): а) апре. делить множество 1.=(з); б) если )ш$. и, кроме того, 1ц<Юя нлн 1и)0, то включить 1 в 1. Повторить шаг б) до тек пор, пока мяожество 1.
нельзя будет расширять дальше. Тогда 1шЕ, поскольку в противном случае существовал бы аугментальный путь потока из в в 1 и поток не был бы максимальным.— Прим перва. Р< Х1 ° (2.61) мы )еы поскольку ~гг)0. Следовательно, величина г любого потока ограничена пропускной способностью произвольного разреза (1Ч, Х,), откуда следует, что величина максимального допусти- мого потока ограничена сверху пропускной способностью мини- мального разреза. Из (2.61) и неравенства ~ц~~Уц следует, что Р<~ ~Ц„,.
Геы, )еы, Правая часть неравенства (2.62) равна величине разреза (Г)„М,), отделяющего узел з от узла 1. Обозначая эту величи- ну через Увь запишем (2.62) в следующем виде: то< У„. (2.63) Пусть (Ь, 1) — такой разрез, что (а) зяЬ, 1е-=Ь и (б) )щЬ, если существует 1ыЬ, при котором 1ц< Уц или 1)г>0'>. Как было показано выше, "=Х Х вЂ” Х 1~и. (2.64) Ы3.
)еТ. Ы. )еЬ Из определения множества 1, следует, что если (Ь)) е=(Ь, Ь), то )ц 110, а если (1, 1) ен(Ь, Ь), то Ь=О. Следовательно, ;))', ~ Уг)- ~~",,'~~(уц (2.65) Ге3. /еТ..Ы. )еТ. Детерминированные потоки в сетях Из неравенства (2.63) и (2.67) следует, что Р= Уи. (2.68) 2.14.4. ПРОЕКТИРОВАНИЕ ЦЕНТРАЛИЗОВАННОЙ ВОДООЧИСТНОИ СТАНЦИИ На водоочистную станцию поступают сточные воды с девяти децентрализованных насосных подстанций, расположенных в городе. Разрабатывается проект перестройки города.
В результате реализации этого проекта в существующую очистную систему дополнительно будет поступать большой объем сточных о Рис. 2.о1. Задача распределения сточных вод. вод. Водоочистная станция является относительно новой, но опасаются, что пропускная способность системы сбора сточных вод может оказаться ниже требуемой. Задача состоит в определении максимального объема сточных вод, который может проходить через систему при существующем оборудовании.
Основные элементы системы показаны на рис. 2.51. Узлы соответствуют насосным подстанциям, а дуги — трубопроводам. На рис. 2.52 данная система изображена в виде обычной сети, для всех звеньев которой указаны верхние границы потока, соответствующие их максимальной пропускной способности. Для нахождения решения с помощью алгоритма поиска максимального потока мы воспользуемся начальным решением, указанным на рис.
2.52. На рнс. 2.53, а — е дается последовательность шагов, в результате выполнения которых находится решение,указанное на рис. 2.53,е. На рис. 2.53,е показано, что максимальный поток равен 8 и что в оптимальном решении потоки на участках (6, 7), (5, 8) и (8, 10) трубопровода равны нулю. Это означает, что насосная подстанция 8 не играет никакой Глава 2 172 роли в системе и поэтому она может быть отключена.
Звено (6, 7) также можно исключить из системы. Если величина максимального допустимого потока не достаточна для планируемого расширения города, то очевидно, что трубопроводы больших размеров для звеньев (1, 2) н (2, 5) увеличат пропускную способность системы. И наконец, отметим, что новые трубопроводы для звеньев (1, 4) и (1, 3) не увеличат пропускную способность системы без дополнительных ее изменений. Рис. 2.52. Макснмальныа поток в задаче распределения сточных вод. Результаты, приведенные на рис.
2.53,а, получаются после выполнения следующей последовательности операций: приписать узлу 1 пометку [оо, — ], узлу 2 — пометку [+4, Ц, узлу 5 — пометку [+2, 2], узлу 10 — пометку [+2, 5]. Изменить потоки: 11з=2, Газ=2 и [аде=2. Результаты, приведенные на рис. 2.53, б, получаются после выполнения следующей последовательности операций: приписать узлу 1 пометку [оо, †], узлу 3 — пометку [+ 1, Ц, узлу 6 — пометку [+ 1, 3], узлу 9 — пометку [+ 1, 6], узлу 10 — пометку [+1, 9].
Изменить потоки: 6з=1 ]за=1, Йз=! и !зле=1. Результаты, приведенные иа рнс. 2.53,в, получаются после выполнения следующей последовательности операций: приписать узлу 1 пометку [со, †], узлу 2 — пометку '[+2, Ц, узлу 7 — пометку [+2, 2], узлу 10 — пометку [ +2, 7]. Изменить потоки: [ы=2, ]чт=2 и ]таз 4. Результаты приведенные на рнс. 2.53,г, получаются после выполнения следующей последовательности операций: приписать узлу 1 пометку [оо, †], узлу 4 — пометку [+3, Ц, узлу 7 — пометку [+3, 4], узлу 10 — пометку [+2, 7]. Изменить потоки: [ы=2, [ет=2 и Ьде=4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
