Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация, страница 4

Пусть х и у — точки из 5о Тогда их выпуклая комбинация Лх+(1 — Х)у принадлежит 5 и с(лх+ (! — Х)у)(Хс(х)+ (1 — Х)с(у)(11+(! — Х)1(й откуда следует, что выпуклая комбинация Хх+(1 — Х)у также при- надлежит 5и () Гл. Л Задачи оптимизации Пример 1.17, Когда функция с определена на )с'-', границы множеств Я, представляют собой линии уровней, подобные тем, которые чертятся на топографических картах (см. рис.

!.9). Наконец, функции, в некотором смысле противоположные выпуклым функциям, называются вогнутыми. с=1 Рис. 1кк Линии упновней выпуклой функции, определенной не й . Определение 1.9. Функция с, определенная на выпуклом множестве 5с:-Йч, называетсявогнутой, если функция — с выпукла на Я.

Г) Пример 1.18. Каждая линейная функция является как выпуклой, так и вогнутой Грубо говоря, линейная функция не изгибается ни вниз, ни вверх и проходит, таким образом, по границе между выпуклостью и вогнутостью. [) За!!ачм выпукпого программирования Важный класс задач оптимизации связан с минимизацией выпуклой функции на выпуклом множестве. Эти задачи обладают тем удобным свойством (упомянутым выше), что их локальный оптимум есть оптимум глобальный. Точнее говоря, верна Теорема 1.1. Рассмотрим индивидуальную задачу оптимизации (Р, с), где Рс:-17а — выпуклое множество и с — выпуклая функция.

Тогда система окрестностей, определяемая евклидовым расстоянием, Ме (х)=(у; уЕР и 1х — у)(е) точная для любого е)0. !.б. Задача аыауклсго программировании Доказательство. Обратимся к рис. 1.10. Пусть х — локальный оптимум относительно й(е для произвольного фиксированного е)0 и пусть уег — любая другая допустимая точка, не обязатель- М(х! Рис. !.!О. Точки, участиующие и доказательстве теоремы !.!.

но из й1,(х). Мы всегда можем выбрать Х достаточно близким к 1 так, чтобы строгая выпуклая комбинация а=ах+(! — Х)у, ОС) (1 принадлежала окрестности й(,(х). Вычисляя функцию стоимости с в этой точке, получаем в силу выпуклости с с (г) =-с (),х+ (1 — Х)у) (Хс (х)+ (1 — Цс (у). Отсюда с(у))[с(г) — ас(х))у(1 — Х). Но с(г))с(х), так как ай й1,(х), поэтому с (у)) [с (х) — Хс (х) )! ( ! — Х) =с (х). Отметим, что не делалось никаких дополнительных предположений о функции с.

Она, например, не обязана быть дифференцируемой. Д В дальнейшем выпуклая допустимая область будет всегда задаваться множеством неравенств, содержащих вогнутые функции. Задачи такого типа принято называть задачами выпуклого программирования. Определение 1.10. Индивидуальная задача оптимизации (р, с) называется задачей выпуклого программирования, если с — выпуклая функция и Гс: — й' определяется неравенствами д, (х)'=иО, з=1, ...

..., т, где д!. 'Йа — ь !т' суть вогнутые функции. д Нетрудно видеть, что определяемое таким образом множество является на самом деле выпуклым. Лемма 1.3. Допустимое множество и в задаче выпук ого програм- мирования является выпуклым. Гл, 1, Задачи опглимиэаиии 22 Доказательствгь Функции — д, выпуклы, поэтому по лемме 1.2 множества гг=(х: дг(х))0) выпуклые. Следовательно, согласно лемме 1.1, мчожес во р= Г) г, гл также выпукло.

( ) В результате доказана Теорема 1.2. В произвольной задаче выпуклого программирования любая точка, локально оптимальная относительно системы окрестностей й ю определяемой евклидовым расстоянием, является также глобально оптимальной. Пример 1.19. Как показано на рис, !.11, выпуклая функция с(х), определенная на (О, 1)с=)лл, может иметь много локальных оптимумов, но все они должны быть глобальными.

() г(к) ) к Рис. ).) ). Задача выпуклого программирования с многими локальными оптимумами, которые все глобально оптимальны. Пример 1.20. Любая индивидуальная задача ЛП представляет собой задачу выпуклого программирования, поскольку линейные функции и выпуклые, и вогнутые, Таким образом, локальный оптимум в произвольной индивидуальной задаче ЛП должен также быть глобальным опгимумом.

() Задачи ') ). Сформулируйте следуюшие задачи как индивидуальные задачи оптими- зации, определяя в каждом случае область допустимых решений Р и функцию стоимости с. (а) Найти кратчайший путь между двулля вершинами графа, а котором расстояния представлены весами ребер. (б) Решлпь задачу о Ханойской бшинг, Имеются грн алмазных стержня и 64 золотых диска возрастающего диаметра.

В центре дисков сделаны отверстия, так что их можно нанизывать на стержни. Вначале все диски находятся на первом сгержне, причем сверху — самый маленький, под нии больший по величине и так далее, в самом низу лежит самый большой диск. Разрешается переносить верхний диск с любого стержня на любой другой, при этом никакой диск нельзл класгль на л) Всюду в этой книге звездочкой отмечены относительно трудные задачи. Зоб Диск меыьикго раэлгера Требуется путем последовательности разрешенных пере- кладываний перенести все диски с первого стержня на второй.

(Говорят, что, когда задание будет выполнено, наступит конец света [Кг), и это, пожалуй, до- вольно оптимистический прогноз.) Обобщить на я золотых дисков (в) Выиграть партию в шахматы. Скол~ко индивидуальных задач в этой задаче? (г) Найти цилкндр наибольшего объема г* с данной площадью поверхно- сти А. (д) Найти замкнутую плоскую кривую данного периметра, ограничивающую наибольшую площадь. 2*.

Приведите пример, показывающий, что 2-замена не определяет точную систему окрестностей для ЗК. То же самос для 3-замены и (гг — 3)-замены, где л — число городов 3*. Покажите, что система окрестностей, определенная в примере 1.5 для МОД, точная. 4. Задача о моменте состои~ в нахождении перестановки и нз л весов шь 'кти 1=1,, и, такой, что моиелт ~„г ., !шпа,=ш!и. Покажиге, что система окрест. настей, определяемая всевозможными перестановками двух соседних весов, точная. 5. Канона мощность окрестности М,(1) обхода Г, определяемой 2-заменой, в ЗК с л городами? Какова мощность Уз(()? 6. Предположим, что иам дано множество 3, содержащее 2л целых чисел, н мы хотим разбить его на два множества, 3, и Бм так, чтобы выполнялось условие [8,[= [3з)=гг и суммы чисел в Ю, и 3, отличались как можно меньше друг от друга Пусть система окрестностей Д! определяется всевозможными перестанов- ками двух целых чисел, при которых одно число переходит из 5, в Бм а второе— из Зз в Яь Является ли Д! точной? 7.

Является лн произведение двух выпуклых функций выпуклой функцией? Если да, докажите, если нет, приведите коитрпрпмер. 8. Пустьг(х) выпукла на )?". Будет ли )(х+Ь), где Ь вЂ” константа, выпуклой иа )?я? 9. Пусть ) (х) выпукла на )?". Зафиксируем х,, ..., х„и рассмотрим функцию 3(хз)=)(х,, ..., х„). Будет ли д выпуклой на )?'? 10. Пусть )(хг) — выпуклая функция одной переменной хь Тогда 3(х)= =1(х!) можно также рассматривать как функцию переменной хц)?".

Будет ли д(х) выпуклой на )?и? 11. Покажите, что сумма двух выпуклых функций явлвется выпуклой функцией. 12. Оправдайте включение целочисленного линейного программирования в класс задач нелинейного программирования на рис. 1 1, 13. Следующий критерий очень полезен для проверки выпуклости функции [ЯЧ, т. 1, с.

152); Пусть С вЂ” открытое выпуклое множество в йя и пусть функция Г обладает непрерывными вторыми частными производными в С Тогда ! выпукла на С в том и только в том случае, если матрица вторых частных производных Н(х) = =[де)?ДхДх?)г? положительно полуопределена для всех х из С Определите, выпуклы ли следующие функции в указан~ "ггластях: (а) (=х,хз, С=)?з; (б) ) ех,юхд С Дз, (в) )=х',+хзч — х,'х,', С=)?а; (г) г'=ха+зле, С= [х ~ )?а: х)0); (д) /=13 хп С= [х,: 0(х,(!).

14. Рясслютрите задачу нелинейного программировании ш!п )=к,хз при условии д=(х,— 1)'+(хз — !)'= 1, Найдите все глобальные и локальные минимумы. Га. 1. Задачи аплгимизации 16*. Сформулируйте задачу о минимальном остовном дереве дяя графа с л вершинами в виде задачи линейного программирования с (»ь) переменными (по одной для каждого ребра), обобщив тем самым пример !.3. (Лгкоэанив. зто может потребовать много ограничений.) Комментарии и ссылал Дальнейшее обсуждение задач нелинейного программирования и условий оптимальности можно найти в )РМ! Р!асса А.

Ч., МсСоггысй О. Р. й)оп!!пеаг Ргойгаппп!пйр Яейпеп(!а! Опсопь1га[пед М!п!ппга1!оп Тесйп!9пеь. Кем Тигра Лойп \Чйеу бг 5опь,!пс., 1966. [Над!) Наб!еу О. Иопнпеаг апб Оупаппс Ргойгаппп!пй. 1(еаб!пй, Мазь.: Адд!ьопУреь!еу РпЫИЫпй Со., !пс., 1964. (Имеется перевод: Хедли Дж. Нелинейное и динамическое программирование.— Мл Мир, !967.) [Ао) АоЫ М.

1п1гобпс!!оп 1о Ор1ппыаноп Тес!гп!9пеь. !чечг Уаттс: Масппнап, [- 1пс., !97!. (Имеется перевод: Аоки М. Введение в методы оптнмнзации.— Мл Наука, !977.! [5Чу) 5!оег Л., %!1хйа!1 С. Сопчехлу апд Орнппханоп 1п Р!пле Оппепь!опь. Вег!гп: Зрг!пйег-Чег!ай, 1970. Идея окрестностей относительно Ф.замены для ЗК содержится в [ь)п!! )йп 5. Сотри!ег Боынопь 1о ййе Тгаче!!пй За!емпап РгоЫепт, ВБТЛ, 44, [4о. 10 (!965), 2245 — 2269. Происхождение задачи о Ханойской башне (задача !) описано в [Кг) КгансЫй М. Маййешанса) Йесгеа!!опь. Иегч Уогы %.%. Гьог1оп апб Соч 1942. Приложение Терминология и обозначения пл Линейнаа алгебра Через Аг (или иногда Агг! обозначается действительная прямал и через )7» обозначается и-мерное действительное векторное пространство, т. е.

мно. жество упорядоченных наборов из» действительных чисел Другие фиксированные множества — это множество )7» неотрицательных действительных чисел, множество 2 целых чисел, множество йе неотрицательных целых чисел и множество 2» упорядоченных наборов из и целых чисел, Множество элементов ь„ьь, ьь, ...

записывается в виде 5=(ь„зь, ьь, ..., и множество, содержащее все элементы х, удовлетворяющие условию Р, задается выражением 5=(х; Р(х)). Например, Е+ можно определить следующим образок 2+ =(г: !цЕ и !ум0), Мощность конечного множества 5 обозначается [5). Отображение р из множества 5 в множество Т записывается в виде Р: 5 Т, и 2з обозначает множество всех подмножеств 5. Матрица размера тХп, в которой на пересечении строки г и столбца ! стоит элемент агг, чзписываегся в виде А=[а;г). Вектор длины п, сов. падающий с г-й строкой матрицы А, обозначается через ап а вектор длины т, являющийся )-м столбцом А, обозначается АР Буквой х (без штриха) Прилояггяие.