Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 69
Текст из файла (страница 69)
Данная величина используется при оценке погрешности, вызванной агрегированием. Однако не следует забывать, что действительная погрешность, вообще говоря, меньше этой границы. Двойственная задача линейного программирования по отношению к агрегированной задаче формулируется следующим об- м Данный раздел может быть опущен без ущерба длн понимания последующего материала. 424 Глава б Таблица б.12. Решение задачи о транспортировке фруктов Таблица б.18. Решение агрегированной задачи разом: максимизировать ~~~~~ ~~ аз,аз,+ ~~ ~~~~~ Ьзтрз1 — ~~)' ~ ицу,1 (5.59) а з 1 1 при условии, что ссзг+()з1 — 7и < сц для всех 1, ), й, (5.60) уц вО для всех 1,1.
(5.61) Предположим, что а, ф и у образуют оптимальное решение двойственной задачи (5.59) — (5.61), а значение целевой функ- 425 Новыв воловом ции равно г. Пусть х — оптимальное решение исходной много- продуктовой транспортной задачи (5.23) — (5.27), а а' — значение целевой функции. Тогда хв ~ '~' '~' '~' свцхвс/+,'~~ ~(Ьв/ ~хвц) ~Тв/+ в с / / в с +~~~ ~)~~ ~'(авс — '~~хвс/) а",— ~~~~~ ~~)' ~~)'(ис/ — ~~~х"ц) уц. с с ьзс в Прибавляя и вычитая в правой части полученного неравенства величину ХХ ицуц, производя перегруппировку слагаемых и с / используя определение величин агрегированного предложения, получаем, что гв ) [~»' ~~ а'савс+~~ ~~)'Ьф/ — ~~~ ~~~)'йс/Уц~— Ф с в / с / —;» ~:~;~.'с,( ',+В,— „— "ц)+ "зс с +.'» '„~ (иц — ~~ иц) ус/.
с / "зс Отметим, что величина в квадратных скобках равна г. Следовательно, г — зв < ~~~~ ~псах ~а"с+~'/ — уц — с"ц) ~~~~ '~'хвс/— сь зс / в — ~~~' ~'„(ис/ — ~~~~,ис/) ус/- с / свес Поскольку ХЕ х';/=Х а'ь то /Ф ' в г — гв < ~~~~ ~~тах~авс+~Р/ — уц — свс/) ')' авс— с мз,/в в — ~~)' ~с~' [ийс/ — ~~)~ ~иц ) уц е.
с / "зс Величина е представляет собой максимальное отклонение стоимости агрегированного решения от действительно минимальной стоимости. Поскольку г является верхней границей минимальной стоимости, то г — е(гв<г. 426 Глава 5 5.22. МАКСИМАЛЬНЫЕ МНОГОПРОДУКТОВЫЕ ПОТОКИ Для задач об однопродуктовом потоке было показано, что величина максимального потока равна величине минимального разреза.
Кроме того, для этих задач известен изящный и эффек. тинный алгоритм нахождения максимального потока. На первый взгляд может показаться, что эти результаты обобщаются на случай многопродуктовых потоков. Однако, если не считать Рис. 5.30. Задача о максимальном многопродуктовом потоке. некоторых частных примеров, это не так. Рассмотрим пример, изображенный на рис. 5.30.
Узлы з» и 1» являются соответственно источником и стоком продукта Й; пропускная способность каждой дуги равна 1. Требуется максимизировать сумму пото- ожет бы ображен в виде Рис. 5.3Ь Плоская и не являющаяся плоской сети. ков трех продуктов из их источников в соответствующие стоки. Если, например, из з1 в Г, по единственно возможному пути посылается единица потока, то никакой другой продукт протекать по сети не сможет. Этот поток не является максимальным, так как можно из з» в 1» послать 1/2 единиц потока продукта к.
427 Наине вопросы В задачах о многопродуктовом потоке аналогом разреза является разделяющее множество, определяемое как совокупность дуг, исключение которых нз сети разрывает все цепи из источников в соответствующие стоки. В рассматриваемом примере минимальное разделяющее множество состоит из любых двух Рис. 5.32. Структура вполне плоских сетей. дуг, соединяющих узлы 1, 2 и 3, и его величина равна 2.
Следовательно, величина максимального многопродуктового потока может быть меньше величины минимального разделяющего множества. Рис. 5.33. Двухпролуктовая вполне плоская сеть. Вообще задача о максимальном многопродуктовом потоке, так же как и задача о многопродуктовом потоке минимальной стоимости, является весьма сложной. Рассмотрение большинства алгоритмов решения данной задачи выходит за рамки нашей книги. Однако для специальных типов сетей максимальный поток равен величине минимального разделяющего множества и потоки по всем дугам являются целочисленными. Можно показать, что данный результат имеет место для сетей, называемых вполне плоскими. Сеть называется плоской, если она Глава Ю может быть изображена таким образом, что никакие две ее дуги не пересекаются.
Например, сеть, изображенная на рис. 5.31,а, является плоской, а сеть на рнс. 5.31,б не является плоской. Сеть называется вполне плоской, если она может быть изображена так, как показано на рис. 5.32, так что полученная в результате сеть является плоской.
Пример сети, по которой протекает двухпродуктовый поток, дан на рис. 5.33. Рис. 5.34. Существует очень простой алгоритм решения данного типа задач. Начать с рассмотрения продукта 1. Выбрать самую верхнюю цепь из з| в Г~ и приписать ей максимально возможный поток. По крайней мере одна дуга будет насыщенной. Исклю- Рис.
5.35. чить из сети эту дугу, а также все остальные дуги, поток по которым равен их пропускной способности. Изменить пропускную способность каждой дуги выбранной цепи, вычитая величину потока по ней. Если аугментальных цепей потока из з1 в й не существует, то повторять данную процедуру для каждого из продуктов 2, 3 и т. д. до тех пор, пока нельзя будет послать дополнительный поток из источника в сток. Полученный поток будет максимальным.
Найдем решение задачи, сеть для которой изображена на рис. 5.33. Самой верхней цепью из з| в 1, является следующая цепь: ® О1 — ОЗ вЂ” © Новьье вопросы По этой цепи может протекать 15 единиц потока. Изменяя пропускные способности дуг и исключая насыщенную дугу, получаем сеть, изображенную на рис. 5.34. Далее в качестве самой верхней выберем цепь зь — 1 — 2 — 3 — (ь и припишем ей поток величиной 5 единиц.
Новая сеть изображена на рис. 5.35. В моди- 10 Рпс, 5.36, О ь5 Продукт 1 П Л~ Продукт 2 Рис..5.37. Максимальный двукпродуктовый поток, фицированной сети (рис. 5.35) не существует аугментальных путей потока из зь в 1ь. Рассмотрим продукт 2. Выберем цепь за — 1 — 2 — 4 — 1е, по которой может протекать поток величиной 5 единиц. Модифицированная сеть изображена на рис. 5.36.
Наконец, по цепи за — 2 — 4 — уа может протекать поток величиной 10 единиц. С помощью полученных результатов определяется максимальный поток (рис. 5.37). Величина максимального двухпродуктового потока равна 35, а минимальное разделяющее множество задается дугами (1, 3), (2, 3) и (2, 4). 5.23. МНОГОПРОДУКТОВЫЕ ПОТОКИ В НЕОРИЕНТИРОВАННЫХ СЕТЯХ В сетях с неориентированными дугами поток по дуге может протекать в любом направлении. В случае когда поток одно- продуктовый, неориентированную дугу можно заменить двумя Глава б противоположно направленными дугами. Это можно сделать благодаря тому, что потоки, протекающие по противоположным направлениям, поглощают друг друга. Однако в случае, когда поток многопродуктовый, такую замену произвести нельзя, так как потоки различных продуктов, протекающие по противоположным направлениям, не поглощают друг друга, а суммируются, и суммарная величина потока не должна превосходить пропускной способности дуги.
Как и для ориентированных сетей, максимальные потоки могут быть нецелочисленными и, кроме того, теорема о максимальном потоке и минимальном разрезе Рис. 8.38. Двухпродуктовая сеть. Рис. 3.39. Трехпродуктовая сеть. Про- пускные способности всех дуг равны К не всегда справедлива. В качестве примеров рассмотрим сети, изображенные на рис. 5.38 и 5.39. На рис. 5.38 изображена сеть, по которой протекает двухпродуктовый поток. Пропускные способности всех дуг равны 1. Читателю предлагается найти максимальный поток.
(Указаниег максимальный поток не является целочисленным.) На рис. 5.39 изображена сеть, по которой протекает трехпродуктовый поток. Читателю предлагается проверить, что величина максимального потока строго меньше величины минимального разделяющего множества.
Общая задача о многопродуктовом максимальном потоке является весьма сложной. Мы опишем алгоритмы решения специального класса задач о двухпродуктовом потоке. Можно показать, что оптимальные потоки по дугам в задачах из этого класса всегда кратны 1/2. Кроме того, величина максимального потока равна величине минимального разделяющего множества. Для описания алгоритма необходимо ввести несколько новых понятий и определений. Поток продукта Й по дуге (1, 1) будем обозначать через ~аи. Поскольку поток может протекать по лю- 4З~ Новые вопросы бому направлению, то положительный поток из 1 в 1 можно рассматривать как отрицательный поток из 1 в й Следовательно, )еи= — ~ьи. Независимо от направления потока чистую величину продукта я, протекающего по дуге (1, )), будем обозначать через ~~'и~. Как и раньше, через з" и (ь будем обозначать соответственно источник и сток продукта я, а через ии — пропускную способность дуги (1, /).
Предполагается, что ии — целая величина. Предположим, что по сети протекает некоторый поток, который удовлетворяет условию сохранения. По данному потоку построим два множества узлов Г и В, следующим образом: 1. зе~ Г. Если сенГ и Рн+~'и<йи, то фГ. 2. з'яВ. Если (енВ и ~'ц+~'и<ил, то )енВ. Предположим, что из 1 в 1 посылается дополнительный поток продукта 1. Если ~'и)0, то остаточная пропускная способность определяется следующим образом: иты-им — Ры — ~ Рц~. Если дополнительный поток посылается из 1 в 1 и ~'и)0, то остаточная пропускная способность определяется как и'„= иы+~'и — ~ ~ы), (5.63) поскольку однородные потоки противоположных направлений поглощают друг друга.
Аналогично если ~'п)0, то для продукта 2 остаточная пропускная способность в направлении от 1 к / равна (5.64) 'а= — Р ~ — 'ген. а в направлении от / к 1 и'м —— им — ~ ~'ы~+~'ы. (5.65) Рассмотрим произвольный путь, соединяющий з' с (е и содержащий дугу (1, 1). Если при движении от з' к (е узел 1 достигается раньше, чем узел 1, то говорят, что дуга (с, 1) имеет положительное направление по отношению к данному пути. В этом случае также говорят, что поток протекает из 1 в / в прямом направлении, а из 1 в ~ — в обратном направлении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
