Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 38
Текст из файла (страница 38)
1. Пусть известно, что величина максимального потока в сети должна быть равной 0', 0' ~ ш Каким образом следует увеличить пропускные способности дуг, чтобы получить этот поток с минимальными затратами? 2. Пусть известно, что суммарные затраты 'на преобразование сети не должны превышать заданной величины с. Как следует увеличить пропускные способности дуг, чтобы в преобразованной сети получить как мох~но ббльшую величину потока) Эти задачи были решены Фалкерсоном [68ь Здесь будет рассмотрен алгоритм их решения, использующий модифицированные стоимости (1081. Обозначим через лы поток по дуге Ань череа Ь;1 — пропускную способность дуги Аы в исходной сети, через Ьм + уы — пропускную способность дуги Аы в преобрааованной сети, где уы — приращение пропускной способности дуги Амь Ог О1 Оз О4 Ое у) О1 Ов О4 Оз Оз Оз От 10Л.
ЗАДАЧИ Ов ОПТИМАЛЬНОМ ПРЕОБРАЗОВАНИИ 219 Задача 1 может быть записана в следующем виде: мннимиаировать ~~~~ смум 0(хм(ЬО+ у11. Задачу 2 можно записать следующим образом: максимизировать и' при условиях ~~~~~ с1;У О = с, — Р', если 1=г, ~~" хы — ~~', х.1, = О, если ! Ф г~ 1~ 1 А Р', если 1.=1, (2) 0(х11(Ь11+ ум. Рассмотрим алгоритм решения поставленных задач. Ш а г О. Положить все х11 — — О.
Ш а г 1. Исходя из имеющегося потока, определить модифицированные дуговые стоимости сг1Т О, если х11(ЬП, — соь если хм) Ьзе — сгь если х;1 ЬП )О. (3) Ш а г 2. Пропустить поток по кратчайшей цепи. Величина пропуснаемого потока ограничивается следующим условием: значения ся, определяемые по правилу (3) и зависящие от дуговых потоков, доля1ны быть такими же, как и на предыдущем шаге 1.
Ш а г 3. Если величина потока равна Р' (при решении задачи 1) или если общая стоимость равна с (при решении аадачи 2), то конец. В противном случае перейти к шагу 1. Рассмотрим сеть, изображенную на рис. 10.15 (а), где числа около дуг означают их пропускные способности Ьы. Стоимости при условиях '," хы — У„хгг= — и', если 1=г, О, если ~'~г, 1 и, если 1=1, 820 Г:1. 10. КРАТЧАЙШИЕ ЦВПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ сы дуг единичных пропускных способностей указаны на рисунке 10.15 (б). Будем решать задачу г при и' = 7. Сначала на шаге 1 определим модифицированные стоимости сЩ.
Так как все хм = О, (61 1иг Р и с. 10.15. (а) Дуговые пропускные способности 5;;; (с) Единичные стоимости с, то с»т = О. Шаги 1 и 2 будут понторентг несколько реа при'с»11 = О, ПОКа ВЕЛИЧИНа МаКСИМаЛЬНОГО ПОтОКа НЗ 11г» В Х1 НЕ СтаНЕт Рааной 6. Полученный поток изображен на рис. А0.16 (а), где в скобках укавапы модифицированные дуговые стоимости с,", (здесь все у'= 7 Р и с. 10Л7. Р и с. 10.16.
с1»1 ) О). Далее находим кратчайнгую цепь, имеющую следующий вид: Аеи Ле1, А1О Таким образом, должна быть увеличена пропускная способность дуги Лиы Получим поток, изображенный и'=! 4 и'=10 Р и с. 10.19. Р и с. 10.18. на рис. $0Л17, где в скобках укаааны модифицированные дуговые стоимости. Заметим, что теперь имеется отрицательная модифицированная стоимость: с,', = — 2 (так как хе1) Ье1 = 2).
Если продолжать упРА жнвнин увеличивать поток и'. и' = 8, 9,..., то яайдепные модифицированные стоимости не будут изменяться, пока и' не станет равным 10 (см. рис. 10.18). Теперь кратчайшая цепь состоит из дуг Ам, Аем Аы и имеет стоимость 3 + ( — 2) + 3 = 4. Предположим, что надо решить задачу 1 при в' = 14. Тогда по цепи Ам, Аж, А„следует направить четыре единицы потока. Получится по~ок, изображенный на рис.
10.19. Заметим,' что когда и' = 7, надо увеличить пропускную способность дуги Аме а когда и' = 14, надо увеличить пропускпые способности дуг А м и Аы, а пропускную способность дуги Аж не менять. Упражнения 1. Найти кратчайшую цепь в сети на рис. 10.20 с помощью алгоритма з 10.1. Будет ли зтот алгоритм работать, если некоторыо Иы «- О? Почему? Найти минимальное связывающее дерево Р к с. 10.20.
для рассматриваемой сети. Считая, что числа на рис. 10.20 означают пропускные способности дуг, найти путь из Л', в?У» максимальной пропускной способности. 2. Построить сеть, в которой дуга с наибольшей длиной входит в кратчайшую цепь, а дуга с наименьшей длиной в нее не входит. 3. Предположим, что в сети все длины дуг Иы ) О.
Будем использовать алгоритм з 10.1, двигаясь одновременно из источника и из стока. Получится ли кратчайшая цепь, когда оба дерева впервые «встретятся» в некотором узле? 1164), И59]. 4. В сети на рис. 10.21 около каждой дуги указаны ее пропускная способность и дуговая стоимость. Найти поток минимальной стоимости величины 4 из Х, в?У,, используя сначала двойственный, а ватам прямой алгоритм из з 10.4.
222 ГЛ, 10 КРАТЧАЙШИЕ ПЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ 5. Пусть д» вЂ” пропускная способность дуги Аы. Путь из Л' в Л'„называется путем максимальной пропускной способности, если величина ш)п (д,ю Ъь, ..., 5„,) является максимальной среди всех путей из Х, в У,. Найти, какой вид имеет тернариая операция для вычисления путей максимальной пропускной Р и с. 10.21.
способности между всеми парами узлов. Выписать соотношения для нахождения всех узлов, входящих в зти пути. 6. В задаче о потоке минимальной стоимости поток является оптимальным тогда и только тогда, когда в сети с модифицированными дуговыми стоимостями не существует отрицательных циклов. Обьяснить, почему, если ищется максимальный поток минимальной стоимости, сеть мохсно разбить на две части и в каждой из них отдельно искать отрицательные циклы.
7. Ориентированная сеть называется ациклической, если она не содержит циклов. Построить алгоритмы для нахождения самой длинной и самой короткой цепи из источника Л", во все остальные узлы в ориентированной ациклической сети. 8. Пусть сеть является (г, З)-плоской. Можно ли так построить максимальный поток, чтобы никакие из дуговых потоков не уничтожали друг друга ([64)). 9. Предположим, что Ыя ~ )О.
Используя алгоритм из 3 (ОА, найти кратчайшие пути из одного узла во все остальные узлы сети с помощью декомпозиции ее на несколько перекрывающихся сетей меньшего размера. МНОГОПРОДУКТОВЫЕ ПОТОКИ (тА. Двухиродуктовые потоки (Ху (106!) В гл. 8 рассматривалась задача нахождения максимального потока из источника Лт, в сток Лтв при наличии ограничений вида хм ( Ьм на пропускные способности дуг. Если в сети имеется несколько источников и несколько стоков и поток может идти из любого источника в любой сток, то задачу можно свести к задаче с одним источником и одним стоком.
Это осуществляется добавлением одного нового источника и одного нового стока. Если ввести ограничение, что поток должен идти из некоторых выделенных источников в некоторые выделенные стоки, то получится задача о многопродуктовом потоке. Пусть имеются источники Л', и стоки Л', (г=1, 2,..., с, г'=Г,2',..., д'), и г-й поток должен идти из источника Л', в сток Л'г.
Пусть хвв— зто г-й поток по дуге Аы т), р' (г, г') — величина г-го потока из Лв в Лт,. Одна из задач, возникающих при анализе многопродуктовых потоков, имеет следующий вид: максимизировать ~~~ /(г, г') при ограничениях — ~(г, г'), если у = г, р', х,';= О, если уФг, г', р(г, г'), если у=г', ~ )х,';)(Ьы (для всех в, у).
в=с В задачах об однопродуктовом потоке одна неориентированная дуга всегда может быть заменена на две ориентированные дуги с противоположными ориентациями. При этом потоки, идущие в) Поток х; 'считается пслсжктельным, если сн идет по дуге АМ от уела Фв к узлу ФП если же он вдет ст уела вут к узлу вум то считается отрицательным; х'.. = — лвч.— Прим.
лврвв. гл, и. многопгодунтовые потоки в противоположных направлениях, можно взаимно уничтожить. Иначе обстоит дело с многопродуктовыми потоками. Два разно- продуктовых потока, идущих по одной дуге в противоположных направлениях, не уничтожают друг друга. В этом заключается одна из основных трудностей многопродуктовых задач. Другая задача, связанная с мпогопродуктовыми потоками,— это так называемая задача о допустимости. Она заключается в следутощем. Заданы неотрицательные целые числа г (г, г') (г.= 1, ..., д, г' = 1', ..., д'). Требуется выяснить, существуют ли допустимые потоки лй, т. е.
удовлетворяющие ограничениям у (г, г') > г (г, г'), — у (г, г'), если у = г, .~ л,'у= О, если у~а, з', у(г, з'), если у=г', ~~ )х;;((Ь;у (для всех у, у) (т. е. требуется выяснить, совместны ли эти ограничения). Как уже говорилось раньше, одпопродуктовую задачу о потоке всегда можно представить как задачу линейного ирограммирования с целевой функцией г = сл и ограничениями вида Ал = 6. Матрица А обладает свойством абсолютной унимодулярпости, и следовательно, базисное оптимальное решение всегда целочисленно. Это, вообще говоря, уже неверно в задачах о многопродуктовом потоке. Большинство многопродуктовых задач не может быть решено методом расстановки пометок или его вариациями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
