Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 68
Текст из файла (страница 68)
3. Покажите, что любой элемент в Ьй оптимальной нецелочисленной таблице А' в алгоритме отсекающей плоскости можно представить в виде Ь(Р, где ив целое число и Р— определитель соответствующего оптимального базиса. 4*. Обобщите доказательство конечности дробного двойственного метода на случай, когда строка и столбеп, соответствующие переменной недостатка з, выбрасываются, если ч входит в базис. 5. Опишите, как дробный двойственный алгоритм щсекающей плоскости может обнаружить и различить случаи, когда ослабленная задача неограниченна и пелочисленная задача нли неограниченна, или недопустима.
(Как показано в лемме )3.2, если ослабленная задача неограниченна, то целочисленная задача не может иметь конечного оп~нмума,) В. Понажите, что предположение в теореме 14.3 о том, что стоимость г дану. стнмого решения ограничена сверху, несущественно (Указание: вспомните ~нареку 2.2.) Комментарии и ссылки 7. х[окажите следующие свойства отношения лексикографического порядка; г д) х<у н у<г=фх<г; ь б) к<у=.,'> [(у<х); в) [(х < х); !. !. г) х<у и г<ы=дьх+г<у+ш. 8. Докажите теорему 14.2: хексикографический двойственный симплекс.
алгоритм конечен 9. Покажите, чаи сделать з начале леисикографичесиого алгоритма все строки или столбцы леисииографичесии положигельнымн. 1О. Покажите, каи спела|ь выбор лекснкографичесхого максимума в операции двойственного леисикографическога симплехс-алгоритма однозначным. 11. Покажите, что дробный двойственный алгоритм отсекающей плоскости, в котором переменные недостатка, соответствую|цне отсечениям, выбрасываются, если становятся базиснымн, требует не более чем зкспоненииального числа итераций. (Здесь под экспоненннальным мы имеем в виду 2рггЬ где р(Е) — полинам от длины ахала.) Комментарии и ссыпки Дробный двойственный алгоритм принадлежит Гомари: [Оо![ Оовогу И. Е Онн!пе о1 ап А!йоп!Ьгп 1ог 1п1ейег БойИоп (о 1лпеаг Рго. дгавь, Вцценп Лвег.
Май. Бас., 64, Ь]о. 5 (1958). [Оо2) Оовогу И. Е Лп А!йапйв 1ог!и1ейег Бонн]опь (о !лпеаг Ргойгавь, рр. 269 — 302 !п Весен! Лбчапсеь ]п МайеваИса1 Ргойгагпгп!пй, еб. )1. 1.. Огачеь апб Р. Тт'оПе. Ь]еьч Уогй: МсОгагч.НИ] Воой Сатрапу, 1963 Лексииографичесиий метод устранения зацикливания взят из работы [РО]й*) Рап(г!8 С. В., Огбеп Л„)чо]!е Р ТЬе Оепегангеб сывр1ех Мейаб 1ог М!пнпцбпй а Е]пеаг Ропп цпбег 1.!пеаг !пейна!Иу Сонь]га]п(ь, Рас!Ис 3.
Май., 5, Ио 2 (!955], !83 — !95 Имевши несколько учебников, детально описывающих множество алгоритмов отсеиающей плоскости; среди ннх: [ОН[ ОагИп1ге1 И. 5,, ]4евйацьег О. !.. !и!ейег Ргайгаппп!пй. Негч Уог!и Лойп байеу уг Вонь, !пс., 1972. [Нц[ Нц Т. С.
1п1ейег Ргойгавв!пй апб Нейчогй Р]очгь. Иеагйпй, Мамб АИ1ьоп. ]чеь]еу Рг1Ы!ьЬ]пй Со., 1пс., 1969. [Имеется перевод: Ху Т. Целочисленное программирование и потоки в сетях.— Мл Мнр, 1974.1 [Ва) Ба]й!п Н. М. !п!ейег Ргойгавв!пй. Иеаанпй, Мазал Лбб]ьоп-%еь]еу РиЫВЬ]пй Со., 1пс., 1975.
Ленстра изложил замечательный результат в лекции !7 декабря 1980 г. в Ам. стердаме (записано Талменом и передано нам Сиарфом и ван Эмде Боасом]. Рассмотрим в задаче ЦЛП ограничения допустимости Ах~у, х~7ь. Для любого фиксированного и Ленстра описал алгоритм, полиномиальный относительно входных данных, который определяет, допустимы ли эти ограничения, н, если ответ положителен, находит допустимую точку х.
Естественно, и входит н показатель соответствующей полиномнальной опенки. См. [[.е) [.епь1га Н. %. Зг. 1п1ейег Ргойгапнп!пй гчИЬ а Р!хеб Ь]цгпйег о1 Тгаг!аЫеь, Иерее! 81-03, (]и!чегьйу о1 Лвь!егбав, Арп] 1981. !$ ЙР-полные задачи $ 5.1 Введение В предыдущих главах нашей основной целью было построение эффективных алгоритмов для решения разного рода комбинаторных задач оптимизации. В гл. 8 мы приняли тезис, согласно которому под «эффективным алгоритмом» имеет смысл понимать «алгоритм, для которого число требуемых шагов растет как полинам от размера входа».
До сих пор мы были свидетелями основных достижений в области комбинаторных алгоритмов оптимизации: мы построили эффективные (в нашем техническом смысле) алгоритмы для решения заких сложных задач, как задача о взвешенном паросочетании, задача о пересеченйи матроидов и задача ЛП. Теперь настало время познакомиться с явными неудачалш этого подхода, т. е. с задачами, для которых не известно эффективного алгоритма С ягой целью мы строим красивую теорию, позволяющую выдвинуть глубокую математическую гипотезу, которая объясняет все эти неудачи. Принципиальным результатом этого исследования является понятие г(Р-полной задачи. Интуитивно (ч* Р-полная задача — это вычислительная задача, которая так ж« трудна, как любая разула ная задача (все эги понятия будут гочпо определены).
Ьудег покззано, что задача коммивоя»кера (ЗК), над ко~арой безуспешно бьются уже два поколения математиков, МР-полна Также ИР- полны такие «твердые орешки», как задача целочисленного линейного программирования (ЯЛП), задача о выполнимости, задача о пересечении трех матрондов и множество других хорошо известных трудных вычислительных задач, многие из которых имеют оптимизационный характер. Этот класс МР-полных задач обладает следующими очень интересными свойствами. !. Никакую МР-полную задачу нельзя репппь никаким извест. ным полиномиальным алгоритмом (и это несмотря на настойчивые усилия многих блестящих исследователей в»ечение целых десятилетий). 2.
Если существует полиномиальный ал«оритм для какой- нибудь МР-полной задачи, то существуют полиномиальные алгоритмы для всех МР-полных задач. Ссноаываясь на этих двух фактах, многие высказывают гн. потезу, что ни для какой МР-полной задачи не может существова»ь О.з. Задача аатамаээцаа — эта тра задача полиномиального алгоритма; однако никому пока не удалось доказать этого. В настоящее время исследователи склоняются к мнению, что без развития совершенно новых математических методов доказать эту гипотезу не удастся. Практическое значения понятия А'Р-полной задачи лежит именно в широко распространенном мнении, что такие задачи по сузцестэу труднорешаемы с вычислительной точки зрения, что они не поддаются эффективному алгоритмическому решению и что для любого алгоритма, корректно решающего ЖР-полную задачу, потребуется в худшем случае экспоненциальное количество времени, и, следовательно, он не будет применим на практике ни к каким, за исключением очень малых, индивидуальным задачам, Таким об.
разом, исследователь, который сталкивается с новой комбинаторной задачей оптимизации и не может найти для нее эффективного алгоритма, имеет теперь возможность попытаться доказать, что задача АГР-полна. Конечно, в большинстве случаев вряд ли это будет его так же вдохновлять, как нахождение эффективного алгоритма. Тем не менее такой подход имеет определенные достоинства. Во-первых, он убережет исследователя — и очень возможно некоторых его или ее коллег — от дальнейших тщетных попыток алгоритмически решить задачу. Кроме того, если о задаче известно, что она ФР-полна, то обычно появляется желание добиться менее амбициозных целей, чем построение алгоритма, который всегда находит точное решение и время работы которого никогда не превышает данной полиномиальной оценки. Прн этом можно воспользоваться одним из нескольких возможных подходов.
Именно такие подходы и служат предметом дальнейшего обсуждения. 15.2 Задача оптимизации — это три задачи В гл. ) задача оптимизации была определена как множество индивидуальных задач. Каждая индивидуальная задача — это пара (Р, с), где Р— множество допустимых решений и с — функция стоимости: с: Р- эк'. Поскольку в этой главе задачи оптимизации будут рассматриваться в вычислительном аспекте, полезно вначале договориться, как будет представляться индивидуальная комбинаторная задача оптимизации на входе вычислительной машины. Можно, разумеется, выписать все допустимые решения и для каждого указать значение с. Однако для большинства интересных задач некоторые индивидуальные задачи будут иметь непропорционально большое число допустимых решений, и поэтому такой метод представления крайне нежелателен.
В качестве примеров подобных ситуаций читатель может вспомнить ЗК и МОД. В дальнейшем будет предполагаться, что Е и с заданы неявно с помощью двух алгоритмов А„и А,. Алгоритм Ае по данным комбинаторному объекту ~ и множеству параметров Я будет решать, з2 и заза Гл. 1З. НР-полные эадаыи является ли ! элементом множества допустимых решений Е, определяемого данными параметрами. В свою очередь А, по данным допустимому решению ! и другому множеству параметров Я выдает значение с(г).
Тогда индиеидуальную комбинаторную задачу можно определить как представление параметров из 5 и 6 с использованием фиксированного конечного алфавита и некоторого стандартного разумного кодирования, как описано в гл. 8 и далее в настоящей главе. Пример 15.!. В индивидуальнойЗК с л городами параметром 5 является целое число п, а параметрами Я вЂ” элементы симметричной (ихп)-матрицы расстояний [йы!. Алгоритм А„по данному объекту 7 и параметру и будет проверять, является ли ! обходом л городов — т. е. циклической перестановкой на множестве (1, 2,, л).
Алгоритм А, по данным обходу !' и матрице (йы! вычисляет стоимость с()), суммируя все элементы матрицы (с(ы), соответствующие расстояниям, проходимым вдоль этого обхода. Д Пример 1б.2. Рассмотрим следующую комбинаторную задачу оптимизации, называемую задачей о максимальной клике. Для данного графа 6=()г, Е) найти наибольшее подмножество Сс:-)Г, такое, что (и, о! Е Е для любых различных и, оЕС. Параметром 5 в данном случае является граф 6. По данному графу 6=(1', Е) алгоритм А определяет, образует ли Г клику в 6, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
