Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 70
Текст из файла (страница 70)
Если (в~В, то сУществУет такой пУть из з' в Р, что ии+ +)'и — ~'и)0 для всех дуг этого пути и положительноенаправление каждой дуги (й /) — это направление от 1 к). Будем называть этот путь обратным путем из в~ в Р. Аналогично если РенГ, то ни+~'и — ~'и)0 для всех дуг этого пути, который называется прямым путем.
Пара, состоящая из прямого и обратного пу- 432 Глава в тей, называется двойным путем. Если положительным направ- лением всех дуг некоторого пути является направление от 1 к /, то пропускная способность обратного пути равна ав — — ппп [им+/'и — /зц), (5.66) а пропускная способность прямого пути равна (5.67) Эти величины равны максимальным потокам, которые могут протекать по данным путям.
Пусть Л'т=ш[п[/'ц)0), где /'ц — поток прямого направления по дуге прямого пути; Ь'в =ш[п[/'ц)0), где '/'ц — поток обратного направления по дуге обратного пути. Для каждого двойного пути введем обозначения ЛР=ш[пФт Ь'в) а пап[аз ат). (5.68) (5.69) 3.23.1. ПРИМЕР ЗАДАЧИ О ДВУХПРОДУКТОВОМ ПОТОКЕ Решим задачу о двухпродуктовом потоке для сети, изображенной на рис. 5.38. Шаг О. Максимальный поток продукта 1 равен 1 (символом — про- [ [- обозначается продукт 1, а символом дукт 2). Перейдем к описанию алгоритма нахождения максимального двухпродуктового потока в неориентированной сети. Шаг О. С помощью алгоритма для однопродуктовых потоков найти максимальный поток продукта 1. Шаг 1. Вычислить остаточные пропускные способности и'ц и определить максимальный поток продукта 2.
Шаг 2. Построить двойной путь из зв в гв. Если такого пути не существует, то максимальный поток найден. В противном случае положить з=ш[п[Л', 1/2а1. Послать з единиц продукта 1 из з' в /в по обратному пути и из /в в з' по прямому пути. Шаг 3. Увеличить общий поток продукта 2, посылая з единиц его из з' в /в по прямому и обратному путям. По существу при работе данного алгоритма поток продукта 1 перераспределяется по двойному пути так, что поток продукта 2 по прямому и обратному путям может быть увеличен. Новые волвосы Шаг 1.
Ниже указаны остаточные пропускные способности и'и. Максимальный поток из з' в 1е равен О. Шаг 2. Для построения двойных путей определим множества Г и В:Г=(з', 2, Р, Р1, В=18', 2, 1, Р). Поскольку Р~Г и Р~В, то мы имеем пару двойных путей. Прямой путь задается последовательностью узлов з' — 2 — Р— Р, и его пропускная способность равна аз ††пг, 2, 1] = 1. Обратный путь задается последовательностью узлов з' — 2 — 1 — ге, и его пропускная способность равна ав =гп1п11, 2, 1]= 1. Таким образом, а=ппп1ав, Глава 5 ав1 =1.
Кроме того А'„=1, А'в=1. Поэтому Ь'=ш1п[о'р, А'в1=1 и е=1/2. Для завершения шага 2 следует послать 1/2 единиц продукта 1 из з' в 1а по обратному пути и из Гв в з' по прямому пути: Шаг 3. Послать 112 единиц продукта 2 из з' в 1в по обоим путям: Текущий поток выглядит следующим образом: Возвращаясь на шаг 2, мы определяем, что двойных путей не существует. Следовательно, полученное решение является оптимальным: Отметим, что величина е является либо целой, либо кратной 1/2.
Поэтому величины всех потоков по дугам также целые или кратные 1/2. Если пропускные способности всех дуг задаются четными числами, то максимальный поток является целочисленным. 5.24. МАКСИМАЛЬНЫЕ ПОТОКИ И ВОРОНКООБРАЗНЫЕ УЗЛЫ Нередко решаемая в области перевозок и снабжения, и в частности в военном деле, задача может быть описана следующим образом. Из пункта снабжения в пункт сбыта должен пе- Новые еоороое! ревозиться товар. Транспортные средства, предназначенные для перевозки товара, располагаются по различным паркам.
Предполагается, что транспортная сеть имеет ограниченную пропускную способность. Требуется определить оптимальный маршрут движения транспортных средств с мест их первоначального расположения к пункту снабжения и затем к пункту сбыта. Аналогичную структуру имеет также следующая задача. Для сушествующей коммуникационной сети требуется построить центральный пункт связи, через который проходила бы вся информация.
Необходимо получить максимально возможный поток информации. В обоих этих примерах выбирается специальный узел, через который должен протекать весь поток из источника в сток. Этот узел называется воронкообразным. Обозначим через 1!!! поток из узла ! в 1, протекающий по направлению к воронкообразному узлу, а через 1»!! — поток из ! в 1 после прохождения воронкообразного узла. Тогда рассматриваемая задача может быть сформулирована следующим образом: минимизировать о при условии, что о'," еслий!=з, '~ ~(1гм — 1 я) = Г 'О, если ! чь'з, а, — в!," если г=а, (5.7!) оч если !=а, если !~а,(, если !=Е, 'Еу!1Г~:"1«л) = 0 мв.а. ! — о (5.72) ~1'м!+~1!0! < им длЯ всех !',1, о=о!=о', 1м) О.' (5.73) (5.74) (5.75) 28* Через з, а и г обозначены источник, воронкообразный узел и сток соответственно. Отметим, что данная задача аналогична задаче о двухпродуктовом потоке в неориентированной сети. Однако в рассматриваемом случае мы имеем не два вида продукта, а два различных типа потока.
Кроме того, требуется, чтобы потоки «продуктов» ! и 2 были равными. В задаче о двухпродуктовом потоке требуется максимизировать суммарный поток продуктов; теперь же максимизируется величина !/ (о! ! ое) Можно показать, что максимальный поток через воронкообразный узел равен пни[о', о', !1»гпах[о!+о'Ц, где о' и о! — это максимальные потоки из з в а и из а в ~ соответственно. Дан- Г»а«а 5 ный результат лежит в основе простого алгоритма, в котором последовательно решаются обычные задачи о максимальном потоке.
Шаг 1. С помощью алгоритма решения задачи о максимальном однопродуктовом потоке найти величины о' и о'. Шаг 2. Построить новую сеть 6', вводя дополнительный узел з' и дуги (з', з), (з' 1) с неограниченной пропускной способностью. Пусть о — максимальный поток из з' в а в построенной сети.
Шаг 3. Вычислить величину п*=ш1п(п', п2, 1(з п1. Если о*=О, то алгоритм прекращает работу. Допустимого потока не существует. Шаг 4. Построить новую сеть б", добавляя к исходной сети узел з" и дуги (з", з) и (з", 1), пропускная способность каждой из которых равна и*. Найти максимальный поток из з" в а в построенной сети. Разложить этот поток на поток из 5« в а, протекающий через з, и поток из а в з", протекающий через Г. Исключить из сети дополнительные узлы и дуги. В результате будет найден максимальный поток, протекающий через воронкообразный узел а.
Отметим, что на шаге 2 величина о= =шах(п'+и'1 определяется путем решения задачи об однопродуктовом потоке. Для того чтобы различать между собой «продукты», можно каждый поток по пути из з' в а, проходящему через з, рассматривать как поток «продукта 1», а поток по пути из з' в а, проходящему через 1, рассматривать как поток «продукта 2». На шаге 4 строится такой поток, что величина той его части, которая протекает через а, равна о*. 5.25. ПРИЛОЖЕНИЯ ЗАДАЧ О МНОГОПРОДУКТОВОМ ПОТОКЕ Задачи о многопродуктовом потоке находят широкое применение при проектировании коммуникационных систем, осуществлении железнодорожных перевозок, планировании производства и распределения, в военном деле, а также в других областях. В настоящем разделе мы остановимся на нескольких приложениях многопродуктовых сетевых моделей и дадим новые формулировки некоторых задач о многопродуктовом потоке.
5.255. СОСТАВЛЕНИЕ РАСПИСАНИЯ ДВИЖЕНИЯ СУДОВ Одной из наиболее часто возникающих задач в области планирования перевозок является задача составления оптимального расписания движения транспортных средств. Предположим, что компания располагает фиксированным числом разнотипных судов, которые отличаются друг от друга скоростью передви- Новые вооросы при условии, что 2 Х теыхдм ( Ь., е А (5.77) с=з", с,-ьзе,г, с(е О, с(е ~~)'„х'м — ~ х',, = (5.78) (5.79) О ( хен < и"м.
Здесь через с'и обозначена величина полезности, соответствующая отдельному судну, перевозимому грузу н маршруту. А,— это множество допустимых маршрутов для данного груза; геи — грузоподъемность судна й-го типа на маршруте (с !). Суммарная величина перевозимого груза не может превышать спроса на него.
Ограничения (5.78) описывают условие сохранения потока по числу судов, а величина и"н равна О нли оо в зависимости от того, может лн быть использовано на дуге (с, )) ження, грузоподъемностью и эксплуатационными расходами, Функция полезности определяется размерами поставки груза' отдельным судном к заданному сроку н затратами на осуществление соответствующей перевозки. Кроме того, существуют затраты (отрицательная полезность), связанные с перегоном судна нз порта, в котором оно было разгружено, в порт погрузки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
