Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 88
Текст из файла (страница 88)
Покажите, что алгоритм 1 для графов с и вершинами всегда выдает вершинное покрытие, размер которого не более чем в 1п л раз больше оптимального. 3. Гамильтонов маршрут в графе 6.=()з, Е) — это замкнутый маршрут, который проходит через каждую вершиву па крайней мере один раз. а) Покажите, что задача нахождения кратчайшего гамильтонова маршрута в графе МР-польза (т. е.
МР-полным является ее вариант распознавания). б) Приведите 112-приближенный алгоритм для этой задачи. 4. Ниже приведен оптимизационный вариант задачи РАЗБИЕНИЕ (вспомните следствие 1 из теоремы !5.8) Для данных л целых чисел сз, ..., с„найти разбиение множества (1, 2, ..., л) на два подмножества Зз, 3,, прн котором достигается минимум величины 'кз шах (хз(еь ср ~(ез с1) Рассмотрим следузащую эврнстику для некоторого фиксированнога целого числа М 1. Выбираем Д самых больпзнх чисел сг.
2, Находим оптнмалз нос разбиение этих й целых чисел (Примечание! используем какой-нибудь переборный метод). 3 Достраиваем это разбиение до разбиения множества (1, 2, „., л), рассматривая каждое из оставшихся с1 и добавляя его к тому подмножеству, которое в этот момент имеет меньшую сумму. а*) Докажите, что этот алгоритм с временем работы 0(2Н+л) является 11(2+3)-приблизкенным. б) Используя п. а), придумайте приближенную схему для этой задачи. Какова сложность вашей ППС относительно л и 1Й7 5.
Докажите теорему 17,9, 6. Покажите, что если РФ(з'Р, то для задачи МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ невозможен полиномиальный е-приближенный алгоритм для любого а<113. (Укизиниез вспомните доказательство теоремы 15.5.) 7. Опишите полнномиальный 112-приближенный алгори~м для задачи о бродячем торговце (задача 8 из гл, !2) при наличии неравенства треугольника, Комментарии и ссылки Приближенное решение дзр-полнззх задач в настоящее время является очень активной областью исследований. Несмотря на богатсгво впечатляющих результатов, в данной области пока почти нет упорядочения илн обобщающей теории, О состоянии исследований в этой области в 1976 г.
лает представление работа (ОЗ!) Оагеу М. К., Зойпьоп О. 3. Арргохппа1юп А)йои1!ппа 1ог СогпЬзпа!оиа1 РгоЫешю Ап Аппо!а!ей ВзЫюйгарйу, рр. 41 — 52 зп А)йоз КЬпзз апд Совр!ехиу: Неж Гигес1юпь апб Ресеп! 1(сап!)з, еб. 1. Р. ТгааЬ. )Чезч Уогй: Асаг(епз!с Ргею, )пс. 1976. Обзор приближенных алгоритмов лля задач о расписании составлен Грэхемом и опубликован а гл. 5 в книге (Со) СоВшап Е. О., )г., еб. Сотрп1ег аззб Зобзйор Зсйебпкпй ТЬеогу. знеа Уог!зз %1)еу 1п(егзс!енсе. !976. Комментарии и ссылки 445 Там можно найти решение задачи 4.
Алгоритм 1 (й 17.! и задача 2) анализируется в статье [йо[ йойпзоп В. 5. Арргох!таИоп А!йоНйвз 1ог СовЫпа1ола) РгоЫевз, 3СББ, 9 (1974), 256 — 278. Алгоритм 2 обнаружили независимо Ф. Гаврил и М. Яяяакакяс. Алгоритм Кристофидеса взят из работы [СЬ[ Сйы)о1йв Л). Юогз(-сазе Апа!уяз о1 а )йехч НепНзИс 1ог йе Тгаче!!пй Ба!еяпап РгоЫегп, Тесйп!са! Рерог1, ОБ!А, Сагпьйге-Мейоп ()и!ч., !976. Алгоритм дерева известен исследователям давно. Детальный вариант его опубликован в статье [)1Я.) йозепйгап1х О. 3,, 51еагпз )1.
Е., Ьеж!з Р. М. Ап Апа!уз!з о1 Бечега! Непг!з. 1йз 1ог йе Тгаче)!пй Ба!езгпап РгоЫетз, 3. 5!АЛ) Согпр., 6 (1977), 563 — 581. ПППС можно найти в работах [1К[ )Ьагга О. Н., К!гп С. Е. Раз1 АрргохггпаИоп А!йог!!Ьвз 1ог йе Кпарзас!г апб Бшп о1 БпЬзе1 РгоЫегпз, 1. АСМ, 22 (!975), 463 — 468. [Ьа) Ьаччег Е. 1., Раз) Арргох!гпа1юп 5сйегпез 1ог Кпарзасй РгоЫегпз, Ргос. !8й Апп.
5утр. оп РоппбаИопз о1 СоврЫег 5с!епсе, 1ЕЕЕ Согпрп1ег Бос. (1977), 206 — 2!3. [Ба) БаЬп) 5. Оепега) Тесйпгйпез (ог СовЫпа1ог)а! АрргохппаИоп, 09, 25 (!977), 920 — 936 Теорема !730 опубликована в [БО) БаЬп) 5., Оопха1ы Т. Р-сотр!е1е АрргохппаИоп РгоЫевз, Я.
АСМ, 23 (1976), 555 — 565, Теорема !7.11 упоминается в [О32) Оагеу М. 9., йойпзоп В, 5. ТЬе Совр!ехйу о1 Л)еаг-ОрИгпа) ОгарЬ Со!ог!пй, 3. АСМ, 23 (1976), 43 — 49. Теорема !7.12 взята из [О33[ Оагеу М. 9., Войпзоп О. 5. 5!гопй КР-совр!е(епезз Рези!(з: МоИчаИоп, Ехавр)в апб 1пгрИсаИопз, ) АСМ, 25 (!978), 499 — 508. Теорема 17.2 — из [Еп) Еп!ег 1.. Бо!пИо РгоЫеваИз аб Сгеоте)Пав 5!!пз РегИпепИз, Сопппеп1аг)1 Асабеппае Ре1горо!1!апае, 8 (!736), !28 — !40 (!п 1.аИп). !8 Метод ветвей и границ и динамическое программирование 18.1 Метод ветвей и границ дпя целочисленного линейного программирования (.1 8.2) Метод ветвей и границ основан на идее разумного перечисления всех допустимых точек комбинаторной задачи оптимизации. Ого- ворка разумного имеет важное значение, поскольку, что должно быть уже ясно, безнадежно пытаться просто просмотреть все допу- стимые решения Для более точнрго описания этого подхода можно сказать, что мы пытаемся построить доказательство оптимальности некоторого решения на основе последовательного разбиения про.
странства решений. Слово ветвей в названии «метод ветвей и границ: относится к этому процессу разбиения; слово границ относится к нижним оценкам, которые используются прн построении доказа- тельства оптимальности без полного перебора. В данном параграфе мы разовьем этот метод для задачи ЦЛП, а затем перейдем к более абстрактному изложению. Рассмотрим задачу ЦЛП пип г = с' х = с (х), Задача 0: Ах<6, (18.1) х ) 0 целочислеино, Если мы решим задачу ЛП, являющуюся ослаблением данной за- дачи, то получим решение х", которое, вообще говоря, не будет це. лочисленным.
Однако стоимость с(х") этого решения является нижней границей оптимальной стоимости с(х') (где х' — опти- мальное решение задачи 0), и если бы х' было целочисленным, то задача была бы решена. В алгоритме отсекающей плоскости мы бы сейчас добавили ограничение к ослабленной задаче, при котором не исключаются допустимые решения задачи (18.1). Вместо этого те- перь мы хотим разбить задачу на две подзадачи, добавляя два взаимоисключа ощих и исчерпывающих все возможностпи ограничения.
Пусть, например, компонента х'; в х' не целочисленна. Тогда соот. ветствующие две подзадачи имеют вид П31пе=с «=с (х) Ах< Ь, Задача 1; х ) 0 целочисленно, х;~ ( х";1, !8./. Целочисленное хинеаное программирование 447 пп'и и = о'х = с (х), Ах</т, Задача 2: х) 0 целочисленно, х ) ( х"; ~ + 1. Пример 18.1.Простой пример задачи ЦЛП приведен на рис.!8.1(а); решением является точка х*=(2, 1) и с(хв)= — (х,+х,)=- — 3. «2 ппп- (х|+хт) хз /б) Гв) хх аб х, хг /в) Сг) Рис . ) 8. ) .
Зт апы решения задачи !(ЛП методом ветвей и границ. Исходная ослабленная задача имеет решение х" = (3/2, б/2) со стоимостью с(х')=- — 4. На рис. 18.1(б) приведены две подзадачи, получаемые при выборе нецелочисленной компоненты х,"=3/2 и добавлении ограничений х,«1 и х,)2. Решение исходной задачи должно лежать в допустимой области одной из этих двух задач, поскольку одно из неравенств х,'е ~ х',:~, в должно быть верным. Выберем одну из подзадач, например задачу 1, и решим ее как задачу ЛП. Ее решение к', вообще говоря, не будет целочисленным, и задачу 1 можно разбить на две подзадачи так же, как мы раз- Гг. И. Метод вешеей и границ били задачу О, получив в результате задачи 3 и 4.
Этот неограниченно продолжающийся процесс можно представить себе как последовательное все более мелкое разбиение допустимой области, что проиллюстрировано на рис. Задача О 18.2. Каждое подмножество в Задача 3 Задача 5 данном разбиении представляет х <(х'! х ч. '(ххт) некоторую подзадачу ! с ослабз ! l!.
ленным решением х' и нижней границей х,= — с(х') для стоимости произвольного решения в данЗадача 4 Задача б ной области разбиения. а;. ) ~х,'] 4! х ) '(ххт1+1 Этот пРоцесс можно пРедставить также в виде дерева, что Р г"г "" " Р 18.3.
Корень этого дерева пред- Задача 1 ставляет исходную допустимую область, а каждая вершина представляет подзадачу. Разбиение допустимой области в некоторой вершине с помощью добавления неравенств так, как это сделано в (18.2) и (!8.3), представляется разветвлением данной вершины на двух ее сыновей Если допустимая область в исходной задаче ЦЛП ограничена, то этот процесс не может продолжаться бесконечно, поскольку в конце 0 Задача 2 х,> (х".1+! Рис. !8лй Последовательные подразбиения допустимой области задачи ЦЛП путем добаадения неравенств. хг'- 1' > („т) 4 3 4 5 б Рнс. !8.3. Представление подразбиеиий пространства решений бинарным деревом.
концов неравенства в некоторой вершине дерева ветвлений приведут к целочисленному решению соответствующей задачи ЛП, которое является оптимальным решением исходной задачи ЦЛП (см. задачу !). Процесс ветвления в некоторой вершине может нарушаться по одной из двух причин: (1) решение задачи ЛП может оказаться целочисленным или (2) задача ЛП может оказаться недопустимой. И.л.
Целочисленное линейное программирование 449 Пример 18.1 (продолжение). Если в примере, представленном на рис. И.1, продолжить ветвление задачи 2, то получим дерево ветвлений, изображенное на рис. 18.4 В правом поддереве получаем три листа, соответствующие двум недопустимым задачам ЛП и одной задаче ЛП с целочисленным решением х'=(2, !) со стоимостью г,=с(х')= — 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
