Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 27
Текст из файла (страница 27)
7.9. Прямо-двойственная процедура ЛЛЬ. ФЛБЕТА для задачи Хичкока. веден в общих чертах весь описанный алгоритм, который мы будем называть АЛЬФАБЕТА. Закончим этот параграф общим замечанием о том, к чему привела нас методология прямо-двойственности. Комбшгаториализация стоимости в задаче Хичкока приводит к задаче о максимальном потоке в каКомбииаториатпзовчп, с~оп ~о гь честве подзадачи. Задача о максимальном потоке решается пугем комбинаториализации пропускных Г:''-""~ способностей, что приводит к чисто комбинаторной подзадаче нахождения пути, увеличивающего поток.
Та- ким образом, идея прямоРис. 7.10. Схематическое представление ал. двойственности использогорнтма АЛЬФАБЕТЛ в виде двух вло- вана важ ы я зам женных циклов. ны двух численных векторов, стоимости и пропускных способностей, двумя вложенными циклами, в которых решается очень простая комбинаторная задача, что проиллюстрировано на рис. 7.10. Если использовать вариант алгоритма Дейкстры, работающий с дугами отрицательной стоимости, для решения подзадач в алгоритмах Ц!1К.'! или ДОСТРОЙКА, то аналогичную интерпретацию можно применить и к этила алгоритмам.
7.5. Лреобрил)мим)ае в задачу Хичкока 7.5 Преобразование задачи о потоке минимальном стоимости в задачу Хичкока Задача о Нотона | мииимальной стоимости Задача Хичноиа дуга ()', 1) першина 1 стоимость с)1 пункт отпраалеипя 11 пункт нааиаченпя 1 луга (1(, й со стоимостью с)1 и Гесконеч. иой пропускной способностью д) га ()(, )) с нулевой стоимостью и беско.
неччой пропускной способностью аапас б)1 а пункте отправления 11 пропускная способность а)1 Чтобы задать потребности, введем обозначение Ьм = ~ Ьг). и. леа (7.15) Таким образом, 6„, — это общая пропускная способность из вер- шины 1'. Потребность в пункте назначения 1' определяется теперь формулами йп,— г)„( = з, йг„(ФЗ, (. (7.16) Описанное построение проиллюстрировано на рис, 7.11. То, что задача Хичкока явлются частным случаем задачи о по. токе минимальной стоимости, очевидно из конструкции, приведенной на рис. 7.8 для случая, когда все дуги допустимы.
Мы просто снабжаем все пункты отправлеп))я из одного обобщенного пункта отправления и собираем поток из всех пунктов назначения в одном обобщенном пункте назначения. Но что здесь кажется поразительным: задача о потоке минимальной стоимости является частным случаем задачи Хичкока! Под этим мы имеем в виду, что для любой индивидуальной задачи о потоке минимальной стоимости можно построить индивидуальную задачу Хпч;ока, имеющую то же самое решение. Позднее в этой книге эта идея будет играть важную роль в понимании труднорешаемых задач, и мы будем говорить, что «задача о потоке минимальной стоим)мчи пргобпазугшгя в задачу Хичкока».
Описываемое ниже преобразование принадлежит Вагнеру (%а, ЕТ1. Пусть дана индивидуальная задача о потоке кн)ннмальпой стоимости. Построим индивидуальную задачу Хичкока, используя следующее соответствие: т"л. 7. Зпдттчн о потоке мнннмояоной сптоимости !54 Задача Хичкока будет состоять в нахождении такого потока 1ц ю что Р„п у+)у,=Ь, (7.17) (запас в пункте отправления ц полностью используется); Ь, — о„для 1= з, Х ()уб т+1М, у) = Ьп +и для е'=1, (7.18) Ье, для (~з, 1 (потребность в вершине е' удовлетворяется); и )е..~ г0 для всех 1, 1, А, и такого, что достигается ш1п 2п.
7.7 . с, (7.19) (7.20) по «сея пунктам отпряпяеяяя Н Заметим, что в этой задаче Хичкока суммарный запас совпадает с суммарной потребностью Теперь получим требуемый результат. Пункты Пункты т~яп>та имия отирая пения о Пропуекппя 1спноеп,п ынкоеоот~ь Ь,т. ," 1", оу Пропускная оп о у' Рнс. 7.11. Задача Хичкока, построенная по аа. даче о потоке минимальной стоимости Лемма 7.2.
Исходная индивидуальная задача о потоке минимальной стпоимости и построенная индивидуальная задача Хичкока эквивалентны в том смысле, что допустимыи поток в одной из них соответствует допустимому потоку той же стоимости в другой. Докааутельсп1во Пусть сначала );, — допустимый поток в задаче о потоке минимальной стоимости. Тогда, если положить в задаче Хичкока » «о, (7.21) (7.22) 7.6. Здключежм то эти потоки будет удовлетворять (7.17). Подставляя их в (7.!8), получаем '.Р(Ь;,— )и+)„) =-Ьо +~Ц?,— ),?) = Ь;, — о„для ~'=-з, Ьо + и„для ( =- (, Ьги для !~з, 1, (7.23) что и требовалось. Пусть теперь дан допустимый поток )», „ я задаче Хичкока. Он отличен от О только тогда, когда я=( или Ь=/ Положим в исходной задаче о потоке минимальной стоимости (7 24) )м=)п з Тогда, учитывая запас в пункте отправления 1, 1, имеем О()ы.- Ьм.
Кроме того, используя равенства (7.17) и (7 18), получаем, что чис- тый поток из вершины 1 в задаче о потоке минимальной стоимости равен ХР;, ! Х)л,;=Х (Ь, )со;) Х)ы, '= о, для (=з, =- Ь,, — ~„'();,, + У;,,) = — и, для ( = — (, О для ( ~ь з, (. (?.25) Таким образом, все ограничения выполнеьы. Легко видеть, что стоимости (в соотв: тствующих задачах) по- гоков, связанных равенствами (7.21) и (7.24), одинаковы. () У.б Заключение Мы использовали идею прямо-двойственности для построения множества алгоритмоя для задач о путях и потоках и еще исполь зуем зту идею в дальнейшем для задач о иаросочетациях. В случае задачи о кратчайшем пути нетрудно было видеть, что алгоритм Дейкстры требует не более 1РР шагов Однако даже для следующего прост.йшего прямо-двойственного алгоритма — алгоритма Форда — Фалкерсона для задачи о максимальном потоке — ве так легко получить верхнюю оценку времени его работы; зто придется отложить до гл.
9. Мы же обратим пока наше внимание на более общие задачи определения и предсказания временнбй сложности алгоритмов. 156 Гл. 7. Задача о потока минимальной стоимости Задачи 1. Понажите, как можно легко модифицировать алгоритм АЛЬФАБЕТА так, чтобы все участвующие в ием числа были целыми. 2. Докажите, что преобразование задачи о патоне минимальной стоимости в задачу Хичкока эффективно в следующем смысле, общее число элементарных щагов, необходимых для построения индивидуальной задачи Хичкока, ограничено полиномом от числа двои !ных разрядов, гребуемых дли представления входной информаш»и в исходной ладлче о потоке минимальной стоимости. 3.
Почему сужение задачи Хичкока иа случай ограничений в виде равенств опирается на предположение о неотрнцатсльнасти стоимостей? Исследуйте зависимость алгоритмов ЦИКЛ, ДОСТРОЙКА И АЛЬФАБЕТА от этого предположения. 4. Докажите лемму 7 1, дающую оптимальное решение задачи ДОП в алгоритме АЛЬФАБЕТА. Единственно ли это решение? 5. Выведите непосредственно из алгоритма АЛЪФАБЕТА, что только пустые дуги могут стать иедопустил»ыми Вытекает ли этот результат из теоремы 5.3, в котарой аналогичный факт устанавливлется для базисных сзолбцов в задаче ОП? Постройте пример, в котором некоторая дуга действительно становится иедопу. стимой.
6. Донажите, что циркуляпии отрицательной стоимости содержит цикл отрицательной стоимости. 7 Решите '""' ующую 3> ачу Х «ока используя алгоритмь! ЦИКЛ ДО СТРОЙКА п АЛЪФАБРЛлн Здесь эллненты матрикы задают стоимости с; .. 8 (Ха1). Покажите, как преобразова»ь задачу о циркулиции минимальной стоимости с нижними и верхними границами дуговых потоков и исходным потоком, в котором нарушаются некшарые веркине и нижние границы, к обычной задаче о потоке минимальной стоимости.
(Указание: постройте сеть приращения с нулевым потоком, который, естественно, не будет удовлетворять только нижним границам. Сделайте замену потоковых переменных и введите фиктивные источник и сток ) Как осуществит! эго преобразование так, чтобы все стоимости были не отрицательны? 9 (задача о постав!цике (Ер)), Поставщику нужно поставлять г; салфеток, ! =-1...,, Н, в течение»Н последовательных дней Поставщик может либо покупать новые салфетни по р цен гав за каждую, либо стирать их в срочной прачечной, чзо занимает т дней и стоит ( центов за салфетку, либо стирать их в обычной прачечной, чга занимает п,лт дней и стоит зк( центов за салфетку.
В конце каждого дни поставщик должен репгить, скальпа грязных салфеток послать в срочную прачечиу»о, сколько в обычную прачечную и сколько ликвидировать Потребность г, на любой день покрывается теми чистыми салфетками, которые можно по. лучить из обеих прачечных, плюс новые салфетки, которые необходимо докупить. а) Сформулируйте эту задачу нак задачу о потоке минимальной стоимости. (Указание, используйте Н «снабжающих» вершин и У «потребляющих> вершин плюс некоторые другие вершины.) Обьяснпге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
