Геометрическая интерпретация задач оптимизации. Задача герона методы оптимизации

Задачи Герона

Разделы: Математика

«Хороший учитель обязан понимать, что никакую задачу нельзя исчерпать до конца. Этот взгляд он должен прививать и своим ученикам».

Д.Пойа

При изучении в школе на уроках физики раздела «Оптика», учащиеся изучают законы отражения и преломления света, которые открыли несколько учёных, в частности, П.Ферма. Оказывается, Ферма при формулировке закона преломления света развивал задачу Герона, которую Герон решил ещё в I в. до н.э. Получается Герон, известный нам как математик, механик и изобретатель, сделал значительные открытия в физике. Поближе познакомимся с работами Герона, а именно: исследуем его задачу, решённую им в работе «О зеркалах», а также по новому докажем известную нам формулу Герона – формулу для нахождения площади треугольника.

Герон Александрийский (годы рождения и смерти неизвестны, вероятно, I в. до н.э.) – древнегреческий учёный, работавший в Александрии. Автор работ, в которых систематизировал и изложил основные знания античного мира в области прикладной механики и математики. В математических работах Герон дал описания многих правил, геометрических фигур, расчётов, формул и др. по широте охвата его труды считаются энциклопедией античной математики, несмотря на то, что приводимые сведения носят догматичный характер, т.к. не сопровождаются выводами, только поясняются на примерах.

Из его работ, имеющих значение для математики, можно отметить «Метрику», «О диоптре» и «О зеркалах». В «Метрике» приводятся правила и указания для точного и приближенного вычисления площадей и объемов различных фигур и тел; среди них имеется и формула для определения площади треугольника по трем его сторонам, вошедшая в математику под именем формулы Герона. Кроме того, в этой работе указываются примеры решения квадратных уравнений и приближенного вычисления квадратных и кубических корней. Характерной особенностью «Метрики», выделяющей её из ряда работ других греческих геометров, предшествовавших Герону, служит то обстоятельство, что в ней обычно правила даются без доказательств, а лишь выясняются на отдельных примерах. Это значительно снижает достоинства работы и, несомненно, является признаком недостаточной научной подготовки её автора. Но в области практических, приложений математики Герон превосходит многих своих предшественников. Лучшей иллюстрацией этого является его работа «О диоптре». В этом труде излагаются методы различных работ геодезического характера, причем землемерная съемка производится с помощью изобретенного Героном прибора диоптры. Этот прибор является прообразом современного теодолита. Главной его частью служила линейка с укрепленными на концах ёе визирами. Эта линейка вращалась по кругу, который мог занимать и горизонтальное, и вертикальное положение, что давало возможность намечать направления, как в горизонтальной, так и в вертикальной плоскости. Для правильности установки прибора к нему присоединялись отвес и уровень. Пользуясь этим прибором и вводя фактически в употребление прямоугольные координаты, Герон мог решать на местности различные задачи: измерить расстояние между двумя точками, когда одна из них или обе недоступны наблюдателю; провести прямую, перпендикулярную к недоступной прямой линии; найти разность уровней между двумя пунктами; измерить площадь простейшей фигуры, не вступая на измеряемую площадку. О времени написания книги «О зеркалах» до сих пор идут споры, но большинство исследователей сходятся на том, что это I в. до н.э. Сам труд Герона не сохранился, и о нём известно из комментариев к нему, написанных позже. Герон исследует в своей книге законы отражения света и прилагает итоги своих размышлений к вопросам, связанным со свойствами зеркал. В частности, он доказывает, что параболическое зеркало фокусирует пучок лучей, параллельных оси параболы. В ту пору законы природы старались постичь умозрительно, с помощью логических рассуждений, не прибегая к эксперименту. Первым экспериментатором в истории науки был Галилео Галилей, Герон же при объяснении законов отражения искал для них логические основания. Он высказывал предположение, что природа действует кратчайшим путём. Идею Герона развил Ферма, который вывел известный к тому времени закон преломления света, исходя из допущения, что траектория распространения света от одной точки до другой в неоднородной среде характеризуется тем, что вдоль неё тратится наименьшее время.

Формулы Герона и их практическое применение

Литература.

Большая Российская энциклопедия. М., «Научное издательство», 2007.
Д. Пойа. Математика и правдоподобные рассуждения. М., « Наука», 1975.
В.М. Тихомиров. Рассказы о максимумах и минимумах. М., «Наука»,1986.
С.Г.Гиндикин. Рассказы о физиках и математиках. М., «Наука»,1985.
Журнал «Математика в школе», № 3, 1981.
Перельман Я.И. Занимательная алгебра. М., АО «Столетие», 1994.

Поделиться страницей:

xn--i1abbnckbmcl9fb.xn--p1ai

Геометрическая интерпретация задач оптимизации

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

Рассмотрим задачу оптимизации, заключающуюся в отыскании точек минимума или максимума функции, заданной на некотором множестве.

Общая задача теории оптимизации может быть сформулирована следующим образом.

Дана система неравенств и уравнений с n переменными.

(2.1)

и функция .

В области решений системы ограничений (2.1) требуется найти такое решение, при котором целевая функция z принимает наибольшее или наименьшее значение.

Для геометрической интерпретации задач оптимизации рассмотрим двухмерный случай. Изобразим на плоскости множество X решений системы (2.1) и несколько линий уровня целевой функции , k = 1,2,3…

Рис. 2.1

Задача оптимизации сводится к нахождению максимального (минимального) z* среди всех zk, для которых линии уровня пересекаются с областью X. При этом любая точка , лежащая в X на линии уровня , является оптимальным решением задачи.

На геометрическом толковании основан соответствующий метод решения задач оптимизации. В качестве примера рассмотрим линейную задачу:

→ min(max) (2.2)

(2.3)

Область решений системы (2.3) представляет собой гипермногогранник (полиэдр) в n – мерном пространстве, а целевая функция задает в этом пространстве гиперплоскость. Если n=2, то решение системы (2.3) есть плоский многогранник, а целевая функция при каждом фиксированном значении z описывает прямую на плоскости. В случае n=3 решение системы (2.3) образует многогранник в пространстве. При этом целевая функция (2.2) при различных значениях z образует семейство параллельных плоскостей в трехмерном пространстве.

Применим графический метод для решения задачи.

С целью обеспечения высокого объема перевозок железная дорога имеет возможность рекламировать свою деятельность, используя местные радио и телевизионные сети. Затраты на рекламу ограничены величиной 3000 условных денежных единиц. Каждая минута радиорекламы обходится в 20 условных денежных единиц, а минута телерекламы – в 60 единиц. Исходя из своих конъюнктурных соображений, железная дорога хотела бы использовать радиосеть по крайней мере в 2 раза чаще, чем телесеть. Радиокомпания согласна предоставить рекламное время в объеме не более 100 минут. Одна минута телерекламы обеспечивает объем перевозок в 6 раз превышающий объем перевозок, обеспечиваемый радиорекламой. Найти оптимальное распределение финансовых средств между телевизионной и радиорекламой.

Обозначим за х1 и х2 количество времени, затрачиваемого на радио и телерекламу, соответственно. Если W – объем перевозок, обеспечиваемый 1 мин. радиорекламы, а z – общий объем перевозок, то целевая функция может быть записана в виде

Так как величина W считается постоянной, вместо функции можно рассматривать функцию

максимум которой в некоторой области достигается в тех же точках, что и функцией .

Из условия задачи можно записать ограничения в виде неравенств, связанные с ограниченностью средств на рекламу

а так же с конъюнктурными интересами железной дороги

Кроме того, имеются ограничения, связанные с объемом времени на рекламу

; ; .

Таким образом, рассматриваемая задача записывается в виде

(2.4)

(2.5)

Каждое из неравенств описывает полуплоскость, и областью решений системы будет многоугольник, являющийся пересечением всех пяти полуплоскостей. Границы полуплоскостей описываются равенствами.

20х1+60х2=3000

х1-2х2=0

х1=100 (2.6)

х1=0

х2=0

Рис. 2.2.

Решение системы неравенств (2.5) образует на плоскости четырехугольник OPRS, а целевая функция при различных значениях у образует на плоскости параллельные прямые (рис. 2.2). При этом значение у возрастет в направлении вектора

Отыскав направление возрастания функции у, будем перемещать вдоль этого вектора прямую, соответствующую целевой функции у, до тех пор, пока она не выйдет за пределы области OPRS. Это происходит в точке P, в которой и достигается максимальное значение функции у (а вместе с ней и z) в области OPRS.

Уточним координаты точки Р. Для этого учтем, что она является точкой пересечения прямых, описываемых уравнениями

Решив систему, найдем координаты точки Р (60;30). Это означает, что для получения наибольшего объема перевозок необходимо выделить средства на 60 мин. радиорекламы в размере 1200 условных единиц и на 30 мин. телерекламы в размере 1800 условных единиц.

Замечание. Иногда задача имеет не одно оптимальное решение. Это возможно, когда прямая, изображающая целевую функцию, параллельна одной из границ области допустимых значений.

1.9. Приближенные и эвристические методы решения задач комбинаторной оптимизации

Методы перебора и все их усовершенствования имеют один, но очень серьезный недостаток: время работы, экспоненциально растущее при увеличении размерности задачи. Для решения практических задач это часто бывает неприемлемо. За редкими исключениями, эффективными можно считать только алгоритмы, имеющие не более чем полиномиальные оценки трудоемкости. Ясно, что такие алгоритмы не могут сводиться к полному перебору планов (ввиду того, что количество планов растет экспоненциально). Других же подходов, пригодных сразу для всех задач комбинаторного поиска, не имеется. Значит, можно надеяться только на алгоритмы, учитывающие специфику конкретных задач.

Исследования в области методов дискретной оптимизации позволили найти некоторое количество задач, для которых действительно существуют эффективные (т.е. полиномиальные с невысокой степенью полинома) алгоритмы решения. К ним относятся, например, такие задачи, как отыскание кратчайшего пути между вершинами графа, максимизация потока в сети при заданной пропускной способности ребер и др. Однако для большей части задач, возникающих на практике, неизвестны эффективные алгоритмы точного решения. Поскольку решать задачи все равно надо, а на перебор надежда плохая, очень часто приходится жертвовать точностью определения экстремума ради сокращения времени его определения. Вместо строгого доказательства того, что полученный план будет давать точный минимум или максимум целевой функции, приходится опираться на соображения здравого смысла, которые позволяют считать, что полученный план с достаточно большой вероятностью либо оптимален, либо хотя бы близок к оптимальному. Конечно, это неприятно, ибо противоречит неуемной тяге человеческого духа к совершенству. Но с другой стороны, много ли вещей мы в жизни делаем оптимальным образом? И ничего, живем.

Относительно более приятна ситуация, когда точно известна хотя бы степень возможной неоптимальности. Алгоритмы оптимизации, для которых имеются нетривиальные оценки возможного отклонения решения от оптимума, называются приближеннымиилисубоптимальными.

Хороший пример приближенного алгоритма известен для задачи о многопроцессорном расписании (см. п.1.3.5). Алгоритм прост донельзя: нужно лишь упорядочить задачи по убыванию их длительности, а затем каждую следующую задачу назначать на наименее загруженный процессор. Оказывается, что отношение времени выполнения набора задач, получаемого по этому алгоритму (T), к минимально возможному времени выполнения, которое можно найти в результате перебора (T0), всегда удовлетворяет неравенству:T/T0  4/3 – 1/3n. Например, приn=3 из этого получается оценка:T0  9/11T. Если, к примеру, по данному алгоритму получилось время выполнения 220с, то нет гарантии, что это наилучшее возможное распределение, однако можно быть уверенным, что минимальное возможное время не может быть меньше 180с.

К сожалению, далеко не во всех случаях можно подобным образом оценить погрешность. Вполне типична ситуация, когда используемый алгоритм дает достаточно приличные решения, однако нет никаких гарантий, что эти решения всегда близки к оптимальным. Алгоритмы, основанные на нестрогих соображениях «здравого смысла» и не имеющие никаких гарантий близости к оптимальным, называются эвристическими алгоритмами. Некоторые авторы, правда, вообще отказывают им в праве называться алгоритмами (поскольку под сомнением такое важное свойство любого алгоритма, как результативность) и используют вместо этого термин «эвристики».

Не существует универсальных рецептов построения эвристических алгоритмов для любых задач. В то же время имеется несколько хорошо зарекомендовавших себя подходов, которые оказываются полезными для разных типов задач.

Алгоритмы локальной пошаговой оптимизацииосновываются на следующих соображениях. В большинстве комбинаторных задач построение плана можно организовать как пошаговый процесс. Например, на каждом шаге решения может определяться значение очередной переменной. К сожалению, в большинстве случаев трудно сказать, какое решение нужно принять на очередном шаге, чтобы в конце концов придти к оптимальному плану задачи. Зато очень часто бывает легко выбрать решение, которое выглядит наилучшим для данного шага, без учета отдаленных последствий.

Простейшим видом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного выбора.

Рассмотрим в качестве примера задачу о коммивояжере. Произвольно выберем начальный город и зададимся вопросом, в какой город следует ехать в первую очередь. Очевидный ответ – в ближайший. На втором шаге и на последующих шагах по той же логике следует выбирать ближайший из еще не посещенных городов. Конечно, такой алгоритм не гарантирует оптимальность построенного плана, ибо не исключено, что выигрыш на первых шагах приведет к большим потерям на последующих (можно и вообще заехать в тупик, откуда нет дороги). Однако можно аккуратными вероятностными рассуждениями подтвердить и без того очевидный факт: при выборе на каждом шаге ближайшего города ожидаемая длина всего маршрута будет меньше, чем при любом другом выборе.

Для задачи о рюкзаке можно предложить такой алгоритм последовательного выбора: отсортировать товары по убыванию отношения стоимости единицы товара к ее объему, а затем на каждом шаге брать максимальное количество очередного товара, умещающееся в оставшемся объеме.

Можно улучшить качество работы алгоритмов последовательного выбора, если разрешить ограниченный перебор, т.е. выбирать решение на данном шаге, учитывая результаты двух, трех или более шагов. Например, перебрать все варианты двух первых поездок коммивояжера, выбрать из них тот вариант, который имеет минимальную длину, и на основании этого выбора сделать первый шаг. Затем так же перебрать варианты второго и третьего шагов, сделать второй шаг и т.д. Если число перебираемых шагов ограничено, то алгоритм, хотя и будет работать значительно медленнее, все же сохранит полиномиальную сложность. Конечно, в силу ограниченности глубины перебора получение оптимального плана не гарантируется. Не гарантируется даже, что при увеличении глубины перебора качество полученных планов будет всегда возрастать, можно только надеяться на это.

Другим типом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного улучшения плана. Предположим, некоторый (не оптимальный) план задачи уже построен тем или иным способом (например, при помощи алгоритма последовательного выбора). Иногда бывает возможно предложить процедуру несложной модификации плана, при которой он остается допустимым планом задачи. Если для модифицированного плана значение целевой функции лучше, чем для исходного, то новый, улучшенный план следует взять вместо исходного и попытаться еще раз применить к нему улучшающую модификацию. Процесс прекратится, когда все возможные модификации будут только ухудшать план.

Рассмотрим, например, некоторый маршрут коммивояжера, проходящий последовательно через города A,B,C,D. В качестве модификации рассмотрим маршрут, в котором те же города посещаются в порядкеA,C,B,D. Очевидно, такая перестановка сохраняет допустимость маршрута, а длина нового маршрута может оказаться меньше, чем у исходного.

Основным недостатком алгоритмов локальной оптимизации является то, что они совсем не обязательно приводят к глобально оптимальному плану задачи. В частности, для алгоритмов последовательного улучшения очень важен удачный выбор исходного плана. (Представьте себе альпиниста, который «локально оптимально» выбирает всегда путь, ведущий вверх. В конце концов он доберется до какой-нибудь вершины, но это может быть вершина маленького холмика, а не вершина самой высокой горы). Полезную роль может сыграть использование случайного выборадля построения исходного плана. Случайно выбранный план будет, скорее всего, сам по себе хуже, чем план, построенный по алгоритму последовательного выбора (хотя и не обязательно), но при многократном повторении комбинации «случайный выбор + последовательное улучшение» возрастает вероятность хотя бы раз оказаться «на склоне нужной горы» и придти к глобальному оптимуму.

Интересной разновидностью эвристических алгоритмов являются популярные в последнее время генетические алгоритмы. Они основаны на использовании биологических аналогий, использующих такие понятия, как популяция, ген, мутация, кроссинговер, отбор.

При разработке генетического алгоритма важную роль играет удачный выбор способа кодирования допустимых планов задачи. Каждый план представляется в виде линейной цепочки («хромосомы»), состоящей из некоторых символов или чисел, играющих роль генов. Для хромосом определяются операции мутации (изменения одного или сразу нескольких генов) и кроссинговера (получения новой хромосомы как комбинации двух имеющихся). Важно суметь так определить эти операции, чтобы хромосомы, получающиеся в результате, также кодировали допустимые планы задачи. Дальнейшее понятно: случайным или иным образом выбирается «начальная популяция» хромосом, новые хромосомы образуются с помощью случайных мутаций и кроссинговера, по правилам отбора формируется новое поколение популяции и т.д., смотри учебник биологии.

По сути дела, генетические алгоритмы являются оригинальной разновидностью алгоритмов случайного выбора с последовательным улучшением. Тот факт, что аналогичная схема дала неплохие результаты при эволюции живой природы, дает надежду на достаточную эффективность этих алгоритмов при решении задач комбинаторной оптимизации.

В некоторых случаях эвристический алгоритм производит впечатление настолько естественного для данной задачи, настолько самоочевидного, что неопытному человеку кажется, будто этот алгоритм должен всегда давать оптимальный план задачи. Проверка на двух-трех простых примерах укрепляет уверенность. Однако если нет строгого доказательства оптимальности, алгоритм приходится считать эвристическим. Интуиция в таких случаях не аргумент, она очень часто обманывает.

В качестве иллюстрации сказанного рассмотрим следующий пример. Задача о минимальном доминирующем множестве графа формулируется следующим образом. В данном неориентированном графе G=(V,E)найти минимальное по мощности подмножество вершинV0такое, что каждая из остальных вершинGсмежна хотя бы с одной вершиной изV0.

После небольших размышлений в голову обычно приходит следующий алгоритм решения этой задачи. Упорядочим вершины графа по убыванию их степени (т.е. количества ребер, инцидентных вершине). Будем на каждом шаге включать в множество V0вершину максимальной степени из тех, которые не смежны ни с одной вершиной изV0. В случае равенства степеней будем брать вершину с меньшим номером.

Другой напрашивающийся алгоритм выглядит чуть похитрее. После включения вершины с максимальной степенью в множество V0удалим эту вершину из графаGвместе с инцидентными ей ребрами, уменьшим на 1 степени смежных ей вершин, найдем максимум степени среди оставшихся вершин и т.д.

Оба алгоритма являются полиномиальными. Но дают ли они точное решение?

Для большинства простых примеров оба алгоритма действительно находят минимальное доминирующее множество. Рассмотрим, однако, простой контрпример, показанный на рис.1.5.

Рис.1.5

В данном случае оба алгоритма включат в доминирующее множество вершину 1, после чего придется включить туда еще как минимум три вершины. В то же время три вершины 2, 3 и 4 образуют минимальное доминирующее множество.

Таким образом, для данной задачи очевидные алгоритмы, как оказалось, не всегда находят оптимальный план. Это не случайная неудача. В следующем разделе курса будут рассмотрены теоретические результаты, из которых следует, что для рассмотренной выше задачи построение точного полиномиального алгоритма явилось бы открытием мирового класса.

studfiles.net

Методы Оптимизации, Теормин — eSyr's wiki

Материал из eSyr's wiki.

(Перенаправлено с Теормин)

[править] Введение в теорию сложности

[править] Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма.

Методичка, стр. 4-8

Массовая задача Π:

список свободных параметров;
формулировка свойств, которым должно удовлетворять решение задачи.

Π есть множество индивидуальных задач . Индивидуальная задача получается, если всем параметрам присвоить конкретные значения.

Пусть Σ — конечный алфавит, а Σ * — множество слов в этом алфавите. Отображение e: называется кодировкой задачи Π.

Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи :

A применим к I, то есть останавливается за конечное число шагов
A дает решение I

Кодировка задачи P — такое отображение , обладающее следующими свойствами:

Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
e,e − 1 — полиномиально вычислимы
Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:

Язык массовой задачи — это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):

Язык алгоритма — множество слов, принимаемых A, то есть таких, на которых алгоритм останавливается в состоянии qY, что соответсвует "да":

Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = L(A) и А останавливается

Число шагов алгоритма A для входа — это tA(s).

Временная сложность .

[править] Задачи распознавания свойств. Классы P и NP.

Методичка, стр. 8-11

Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.

D(Π) -- множество всех возможных значений параметров массовой задачи.
Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".

Класс полиномиально разрешимых задач (P) -- это такие задачи, временная сложность алгоритма решения которых ограниченна полиномом:

такой, что A решает массовую задачу Π с кодировкой e
-- полином такой, что

Примеры неполиномиальных задач:

алгоритмически неразрешимые задачи: такая, что A не применим к I, например,
- 10-я проблема Гильберта: по данному многочлену g с целыми коэффициентами выяснить, имеет ли уравнение g = 0 целочисленное решение
задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
- найти все маршруты в задаче коммивояжёра
∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: tA(e(I)) > p( | e(I) | )

Класс недетерминированно полиномиальных задач (NP) -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:

для НДМТ такой, что решает массовую задачу Π с кодировкой e
-- полином такой, что

[править] Теорема об экспоненциальной временной оценке для задач из класса NP.

Методичка, стр. 11

Для любой существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: .

[править] Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

Методичка, стр. 12-14

Дополнительная задача к массовой задаче Π -- задача, получаемая из Π путем введения альтернативного вопроса. То есть если в Π спрашиваем "верно ли x", то в спрашиваем "верно ли, что "

Класс co-P --

Класс co-NP -- .

co-NP = NP пока не удалось ни доказать, ни опровергнуть, но это вряд ли верно.

Массовая задача Π допускает хорошую характеризацию, если

пример такой задачи -- это задача определения простоты числа.

Массовая задача Π' с кодировкой e' полиномиально сводится к задаче Π с кодировкой e, если любая индивидуальная задача может быть сведена за полиномиальное от её длины время к некоторой задаче с сохранением ответа.

Массовая задача Π называется NP-полной (универсальной), если

принадлежит классу NP:
любая задача из NP полиномиально сводится к Π:

Класс NPC (NP-complete) -- множество всех NP-полных задач.

[править] Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН

Методичка, стр. 15

Критерий NP-полноты. Массовая задача Π NP-полна тогда и только тогда, когда она принадлежит классу NP и к ней полиномиально сводится какая-либо NP-полная задача.

[править] Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи

Методичка, стр. 17-18

Класс NP-трудных задач содержит:

задачи распознавания свойств Π, для которых
- не доказано, что
задачи оптимизации, для которых соответствующие задачи распознавания свойств
любые задачи, к которым сводятся по Тьюрингу хотя бы одна NP-полная задача

[править] Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE

Легко показать, что . Рабочая гипотеза, что .

Если для некоторой NP-полной задачи Π дополнительная к ней задача , то NP = co-NP

Класс PSPACE массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти.

Гипотеза. (то есть, не факт, что вложение строгое, но скорее всего так). При этом NP-полные, NP-трудные, NP-эквивалентные задачи

[править] Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке

Псевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.

Пусть M(I) -- некоторая функция, задающая значение числового параметра индивидуальной задачи I. Если таких параметров несколько, в качестве M(I) можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то M(I) = 0. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости Tmax(I) = O(p( | I | ,M(I))), где -- некоторый полином от двух переменных.

en-wiki

[править] Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения

Полиномиальное сужение массовой задачи Π -- множество таких индивидуальных задач I, числовые параметры которых не превосходят полинома от длины входа:

Массовая задача Π называется сильно NP-полной, если её полиномиальное сужение является NP-полным. Примеры:

задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями
задача булевых линейных неравенств -- ВЫП сводится к её полиномиальноу сужению, где числовые параметры (правая часть неравенств) линейны.
задача о целочисленном решении системы линейных уравнений -- , т.к. БЛН сводится к ней
задача коммивояжёра (TSL) -- совпадает со своим сужением

Задача о рюкзаке -- слабо-NPC.

Теорема. Если NP не совпадает с P, то ни для какой сильно-NPC задачи не существует псевдополиномиального решения.

[править] Определение ε-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью

Методичка, стр. 22-24

Задача дискретной оптимизации -- решение каждой индивидуальной задачи является произвольная реализация оптимума , где

SΠ(I) -- область допустимых значений дискретной переменной z
fΠ -- целевая функция задачи оптимизации
max вообще говоря вполне может быть заменён на min

Алгоритм A называется приближённым алгоритмом решения массовой задачи Π, если для любой задачи он находит точку , лежащую в области допустимых значений, принимаемую за приближённое решение.

Утверждение. Если , то ни для какой константы C > 0 не существует полиномиального приближённого алгоритма решения задачи о рюкзаке с оценкой .

Приближённый алгоритм A решения массовой задачи Π называется -приближённым алгоритмом решения задачи, если .

[править] Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания

Методичка, стр. 24

Теорема Если для Π оптимизации

соответствующая ей задача распознавания свойств является сильно NP-полной
существует полином

то при условии, что для Π не существует ПППС

[править] Основы линейного программирования

[править] Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП

ЛП (линейное программирование) -- теория, приложения и методы решения системы линейных неравенств с конечным числом неизвестных : , существует ли , удовлетворяющий данной системе линейных неравентсв

озЛП (основная задача линейного программирования) : найти такой вектор -- решение задачи линейного программирования , максимизирующее линейную функцию

Утверждение (принцип граничных решений). Если озЛП имеет решение, то найдется такая подматрица AI матрицы A, что любое решение системы уравнений AIx = bI реализует максимум .

Алгебраическая сложность -- количество арифметических операций.

Битовая сложность -- количество операций с битами. Битовая сложность задач ЛП, ЛН полиномиальна.

Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым.

[править] Геометрическое описание симплекс-метода

(Копипаста из [ru.wiki], там-же есть хорошая иллюстрация.)Симплекс-метод -- метод решения озЛП.

Каждое из линейных неравенств в ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

[править] Теорема о границах решений задач ЛП с целыми коэффициентами

Методичка, стр. 28-29

Δ(D) = max | det(D1) | , где D1 — квадратная подматрица D.

Теорема (о границах решений). Если задача озЛП размерности (n, m) с целыми коэффициентами разрешима, то у нее существует рациональное решение x * в шаре: и

[править] Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами

Методичка, стр. 29

-- -приближенное решение системы ЛН, если

в строчной записи:
в матричной записи: , где e -- вектор-столбец из единиц

Теорема. Если система линейных неравенств имеет приближенное решение (), то эта система разрешима, то есть имеет точное решение.

[править] Описание метода эллипсоидов

Решает задачу линейного программирования за полиномиальное число шагов.

Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.

Лемма1. Если система совместна, то в шаре найдется ее решение.

Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений

Введем функцию невязки в точке x -- t(x) = maxi((Ax)i − bi). Точка -- это центр шара E0. Если , то x0 -- решение. Если это не так, то возьмем s: , значит x0 не удовлетворяет s-ому неравенству системы. Всякий вектор x, удовлетворяющий неравенству s, должен лежать в полупространстве . Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.

[править] Теория двойственности ЛП

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.

Двойственной задачей к задаче линейного программирования на максимум (в форме ОЗЛП можно записать: ) называется задача линейного программирования на минимум:

Утверждение Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования.

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

[править] Сведение озЛП к однородной системе уравнений с огрничением x>0

Методичка, стр 36-37

Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных неравенств.

Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных.

Утверждение. Задача ЛП эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений.

[править] Идея метода Кармаркара

Метод Кармаркара.

На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП к поиску решения СЛАУ , которая, в свою очередь, сводится к однородной СЛАУ:
Введем функцию Кармаркара: , где
- N -- число столбцов в P
- K -- число строк в P
- -- строки матрицы P
применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой , для которого
при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается.

[править] Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства)

Система линейных неравенств называется разрешимой, если

Линейное неравенство является следствием разрешимой системы ЛН , если для всех x, для которых выполняется сама система, выполняется и следствие:

Афинная лемма Фаракша. Линейное неравентсво является следствием разрешимой в вещественный переменных ЛН , тогда и только тогда, когда существуют :

[править] Лемма Фаркаша о неразрешимости

Методичка, стр. 35

Лемма. Система линейных неравенств неразрешима тогда и только тогда, когда разрешима система:

(нулевой вектор)

[править] Элементы математического программирования

[править] Классификация задач математического программирования. Преимущества выпуклого случая

Методичка. стр 39-41

Задача математического программирования (ЗМП) -- по заданной f(x) найти , то есть:

найти -- решение
f * = f(x * ) -- (оптимальное) значение целевой функции f(x)
где X -- допустимое множество (множество ограничений)

Классификация проводится по типу допустимого множества X:

дискретные (комбинаторные) -- множество X конечно или счётно
целочисленные --
булевы --
непрерывные --
бесконечномерные
функциональные

Задачи оптимизации бывают:

условные --
безусловные --

Классификация по свойствам целевой функции: выпуклость, гладкость и т.п.

Классификация по результату:

локальная оптимизация
глобальная оптимизация

Выпуклое множество (вики) -- такое множество, которое содержит вместе с любыми двумя своими точками еще и отрезок, их соединяющий.

Функция f называется выпуклой, если её надграфик (множество точек над графиком: ) является выпуклым множеством.

Утверждение. Любая точка локального минимума выпуклой функции является точкой её глобального минимума.

Преимущества выпуклых задач:

применим метод эллипсоидов, причем сложность - полиномиальна
для острых задач (целевая функция убывает в окрестности минимума не медленнее некоторой линейной функции) можно получить точное решение

[править] Формула градиентного метода в задаче безусловной минимизации

Методичка. стр 41-42

Основная идея:

берем некоторое начальное значение
итеративно вычисляем градиент целевой функции
двигаемся в обратном направлении
и так постепенно приходим к (локальному) минимуму функции

Формула градиентного метода -- xt + 1 = xt − αtgradf(xt), где αt -- шаговый множитель:

пассивный способ: {αt} выбирается заранее
адаптивный способ: {αt} выбирается в зависимости от реализующейся xt
- метод скорейшего спуска --
- метод дробления (деления пополам) -- если f(xt + 1) > f(xt), то возвращаемся к шагу t с новым значением αt = αt / 2

[править] Идея метода Ньютона

Методичка, стр. 43

Метод ньютона -- это фактически градиентный спуск с адаптивыным коэффициентом, который берется, как 2 производная целевой функции.

Реально можно вывести формулу Ньютона из разложения по Тейлору до 2 производной в окрестности точки минимума.

[править] Формула метода Ньютона в задаче безусловной минимизации

Методичка. стр 43

Формула Ньютона -- , при этом начальное приближение должно находиться достаточно близко к искомой точке минимума.

Метод ньютона имеет квадратичную скорость сходимости: , где Q - некоторая константа

Ограничения:

невырожденность матрицы 2 производных (гессиана)
близость начального приближения к точке минимума ()

[править] Идея метода штрафов

Методичка. стр 44

Смысл метода в том, чтобы свести задачу условной оптимизации к задаче безусловной оптимизации, то есть избавится от ограничения на область, в которой ищем минимум.

Для этого вводится так называемая функция штрафа, которая равна нулю в той области, в которой мы "условно оптимизируем" целевую функцию, а в остальных точках добавляет к значению целевой функции некоторое значение (собственно, штраф).

Пример. Пусть область задаётся следующим образом: , где g(x) -- некоторая функция. Тогда рассмотрим задачу безусловной минимизации целевой функции f(x) со штрафом: , где C -- некоторая константа [??], а -- параметр штрафа

[править] Способы решения переборных задач

[править] Методы глобальной минимизации

Методичка. стр. 52 (52-55)

[править] Метод ветвей и границ для глобальной минимизации Липшицевых функций

Методичка. стр. 54

[править] Метод ветвей и границ для ЦЛП. Различные стратегии метода

Методичка. стр. 57

[править] Идея метода ветвей и границ. Пример для задачи БЛП

Методичка. стр. 59

[править] Теорема оптимальности для разложимых функций

Методичка. стр 60

Опр. Функция f называется разделяемой на f1 и f2, если она представима в виде f(x,y) = f1(x,f2(y)).

Опр. Функция f называется разложимой на f1 и f2, если:

она разделяема на f1 и f2
f1 монотонно не убывает по последнему аргументу

Теорема оптимальности для разложимых функций: minx,y(f(x,y)) = minx(f1(x,miny(f2(y)))).

Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП.

[править] Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи

Методичка. стр. 62

[править] Метод динамического программирования для БЛП с неотрицательными коэффициентами

Методичка. стр. 63-64

[править] Неотсортировано

Полиномиальный алгоритм округления ε1-приближенного решения системы линейных неравенств
Понятие о временной сложности алгоритмов
Понятие о недетерминированно-полиномиальных задачах
Оценка сложности метода эллипсоидов ε2-приближенного решения озЛП

esyr.org