Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 3
Текст из файла (страница 3)
Интуитивно понятно, что минимум всегда достигается водном из углов о„о„о„ указанных иа рисунке. Допустив это, мы решим задачу, аг найдя все вершины и вычис- лив с'х в каждой из них. Это Хг может оказаться тяжелой за- дачей в большем примере, ио Рис. !.4. Допустимое множество т для главное что оиа крлечлп простой задачи оо остовном дереве. Именно в агом смысле задача ЛП комбииаториа. Д Во многих случаях удается сделать обратное: выразить чисто комбииаториую задачу в ниде задачи ЛП, Пример 1.3 (продолжеиие). Рассмотрим задачу МОД с л=З точками.
На иих имеются три остовиых дерева, изображенные иа рис. 1.3. Их можно считать |акже точками в 3-мериом пространстве, если положить х,=1, когда ребро е, содержится в рассматриваемом дереве, и хг=0 в противном случае (1=-1, 2, 3). Тогда эти три остовиых дерева совпадают с вершинами ьо о„оа допустимого множества г", показанного ва рис.
1.4 и определяемого ограничениями х,+ха+ха=2, х,)0, х,)0, х,)0, (В задаче ЛП будем допускать как равенства, так и неравенства,) Найти мииимальиое остовиое дерево с матрицей расстояний с(та=с„ с(„=с, и г(а!=се — это в точности то же, что решить задачу ЛП с допустимым множеством, показанным иа рис. 1,4. Таким образом, эту чисто комбииаториую задачу можно в принципе решить с помощью ЛП. Такая точка зрения окажется очень полезной при разрабогке алгоритмов для некоторых комбинаториых задач. Д 1.8.
Окресткоаии 4.З Окрестности Если дана допустимая точка 1 Е г" в некоторой конкретной задаче, то во многих случаях полезно определить множество М (1) точек, которые в некотором смысле «близки» к данной точке 1. Определение 1.3. Пусть дана задача оптимизации с набором индивидуальных задач (г, с). Тогда система окрестностей (или окрестностная функция) — это отображение М: г — 2", определенное для каждой индивидуальной задачи.
() б (а) (б) Рис. Кб, а) Индиаидуальная задача ЗК и неко. тарый обход б) Другой обход, получаемый 2-заменой из обхода на рис. а). Если с=ухе, то множество точек, лежащих в пределах фиксированного евклидова расстояния от данной точки, образует естественную окрестность. Во многих комбинаторных задачах выбор М может существенно зависеть от структуры г. Пример 1.4 () !п1) В ЗК можно следующим образом определить окрестностную функцию, называемую 2-заменой: Мз(1) =(у; дЕг и д можно получить из 1 удалением двух ребер из обхода и заменой их двумя ребрами). На рис.
1.5 показан пример обхода ~ и другого обхода дЕ Мз(1) для индивидуальной ЗК с семью городами и матрицей расстояний, определяемой евклидовым расстоянием между точками на плоскости. Очевидным обобщением этой окрестностной функции является функция Мы называемая к-валеном, при которой заменяются не более й связей. Такие окрестностные функции приводят к очень эффективным эвристикам для ЗК. () га Гл. 1.
Задачи оп«лима»аиии Пример 1.5. В МОД важная система окрестностей определяется следующим образом: М(1)=(йч дар и д можно получить из 1 следующим образом: добавляем ребро е к дереву 1, при этом образуется цикл; затем удаляем любое ребро из этого цикла). ( ) Пример 1.б. В задаче ЛП можно определить систему окрестностей следующим образом: М, (х)=(у Ау=Ь, у' 0 и !~у — х(<е). Это просто множество всех допустимых точек в пределах евклидова расстояния е от х для некоторого е)0.
[3 1.4 Лонапьные м глобальные оптимумы Для некоторых индивидуальных задач может оказаться исключительно грудно найти глобально оптимальное решение. Однако часто удается найти решение 1, наилучшее в том смысле, что в его окрестности М(1) ничего лучшего нет. Определение !.4. Пусть дана индивидуальная задача оптимизации (г, с) и система окрестностей М, тогда допустимое решение 1Е г называется локальнооптимальным относительно М (или просто локально оптимальным, когда М очевидно из контекста), если с(1) (с (д) для всех уб М(1) Е) Пример 1.7. Рассмотрим индивидуальную задачу оптимизации (г", с), в которой г"=[О, !)ы)(' и функция стоимости с показана на рис. !.6.
Пусть, далее, система окрестностей определяется близостью в евклидовой метрике для некоторого е)0, т. е. М«(()=(х; хЕГ и (х — ~)(е). Тогда, если е достаточно мало, все точки А, В и С будут локально оптимальными, и только В глобально оптимальна. () Пример 1.8. Решения ЗК, локально оптимальные относительно системы окрестностей Мю порожденной й-заменами, называются л-оптимальными (Е!п1), Для нахождения й-оптимального обхода в индивидуальной ЗК следующим образом определим функцию !гпргоче(1), где 1Е Г: !'любое зЕ М (1), такое, что с(з) (с(1), 'пиргоче (1) = ! если такое а существует, 1 «нет» в противном случае.
Таким образом, спрогоче(1) ищет более хороший обход з в М„(1). Если таковой находится, она выдает улучшенный обход; в против- !7 !.4, Локальныг и ггобпгьныг ьпглимумы ном случае она выдает значение гнет». Алгоритм для нахождения (г-оптимального обхода будет тогда иметь вид ') ргосебнге й-ор1 Ьей!в 1. некоторый начальный обход; вЫ!е 'ппргоче(1) Ф «нет» бо 1: = !горгоче(1); геилгп 1 епб Так как обычно нас интересует нахождение глобального оптимума, а многие алгоритмы способны найти лишь локальный оптимум, то важно знать, является ли некоторый локальный оптимум Г Рис.
!.6. Одномерная евклидова задача 2.оп. тимизацин. глобальным. Разумеется, это зависит от системы окрестностей А!. Следующий термин отражает то благоприятное стечение обстоятельств, когда каждый локальный оптимум еще и глобальный. Определение 1.5. Пусть дана задача оптимизации с допустимым множеством Р и системой окрестностей А!. Если любая точка /Е Р, локально оптимальная относительно А(, будет глобально оптимальной, мы говорим, что система окрестностей АГ является точной. ( ) Пример 1.9.
На рис. ).6 система окрестностей А!е точная, если е)1, но она не будет точной для достаточно малых в >О. Е3 Пример 1.10. В ЗК А!я не будет точной„а Аг„, где а — число городов, точная (см. задачу 2). Е) Пример 1.11. В МОД система окрестностей, описанная в примере !.5, точная (см. задачу 3). П ') Алгоритмы записаны в неформальной нотации, называемой Упрощенным Алголом. См. приложение в конце главы, Гл. 1. Задачи опаеимиэации !8 $.5 Выпуклые множества и функции Сосредоточим теперь внимание иа классе задач, в которых ге=!си. В частности, хотелось бы найти классы задач, в которых окрестностная функция й1, точная для любого е)0, так как в таких задачах любой найденный локальный оптимум обязательно будет глобальным. Таким свойством обладае! класс задач выпуклого программирования, среди которых задача линейного программирования— частный случай.
Начнем с ряда важных определений. Определение 1.6. Пусть даны две точки х, уЕКч; тогда их выпуклой комбинацией будет любая точка вида г=Лх+ (! — Л)у, ЛЕ й' и 0(Л(1. Если Лчь0, 1, будем говорить, что г есть строгая выпуклая комбинация х и у. П Определение 1.7. Множество Яс: — Йч выпукло, если оно содержит все выпуклые комбинации пар точек х, уЕ 5. Пример 1.12. Множество Я" выпукло, равно как и пустое множество йз и любое одноточечное множее!во. «е х, Рнс. !.7, Выпуклое множество А н неныпуклое множество В. Пример 1.!3. В Й' любой интервал — выпуклое множество и любое выпуклое множество есть интервал. Пример 1.1"..
В К'выпуклое множеств~ — это, грубо говоря, множество без вырезов. Таким образом, множество А на рис. 1.7 выпукло, а В не выпукло. !) Важное свойство выпуклых множеств выражено в следующей лемме. Лемма 1.1. Пересечение любого числа выпуклых множеств 5, выпукло. Доказательство. Если х и у — точки из П Яи то они принадлежат каждому Яь Тогда любая их выпуклая комбинация принадлежит каждому 5, и, следовательно, 0 Яь де. Выну«лиг множества и функции Введем геперь понятие выпуклой функции, определенной на выпуклом множестве. Определение 1.8.
Пусть 5 с: — й" — выпуклое множество. Функция с: 5 - )с' выпукла на 5, если для любых двух точек х, у Е 5 с(кв+ (1 — Х)у)(кс(х)+ (1 — к)с(у), ХЕ !с' и 0(Х(1. Если 5=!ск, будем просто говорить, что с выпукла. () Пример 1.18. Любая линейная функция выпукла на любом выпуклом множестве 5. П Пример 1.16. Грубо говоря, выпуклая функция «изгибается вверх». На рнс !.8 показана выпуклая функция с на (О, 1):-)сл, лк «!) — л))' Рнс, !.8. Функння с, выпуклая на !О, )!. где с: (О, !) -» !с'.
Из условия выпуклости вытекает, что хорды всегда лежат выше атой функции. Множество точек, в которых выпуклая функция меньше данного значения или равна ему, выпукло. Более точно, справедливо следующее утверждение. Лемма 1.2. Пусть с(х) — выпуклая функция на выпуклом множестве 5. Тогда для мобого действительного числа 1 5, =(х: с(х)(1, х Е 5) есть выпуклое множество, Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
