Свойства вершин релаксаций разрезного многогранника

• Автор: Николаев, Андрей Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Ярославль
• Количество страниц: 138 с. : ил.

Содержание
Введение
1 Корневой полуметрический многогранник
1.1 Разрезной многогранник
1.2 Определение корневого полуметрического многогранника
1.3 Некоторые основные свойства
корневого полуметрического многогранника
1.4 Корневой полуметрический многогранник
как релаксация разрезного многогранника
1.5 Минорные характеристики матрицы
корневого полуметрического многогранника
2 Релаксационный многогранник задачи З-ЯАТ
2.1 Задача 3-ВЫПОЛНИМОСТЬ
и ее релаксационный многогранник
2.2 Фасеты и целочисленные вершины
2.3 Нецелочисленные вершины
2.4 Задача целочисленного программирования на Рт<п
2.5 Задача распознавания целочисленное™
3 Последовательности релаксационных
многогранников задач о разрезе и З-йАТ
3.1 Релаксации многогранника задачи З-БАТ
3.2 Релаксации разрезного многогранника
4 Гиперграфы специального вида и свойства
вершин релаксаций разрезного многогранника
4.1 3-однородные смешанные гиперграфы
4.2 Гиперграфы точек многогранника МП:3
4.3 Свойства точек релаксаций Мп>4 и Мпд
4.4 О классе неинвертируемых гиперграфов
Приложение

Приложение
Список литературы

Введение
Одной из основных задач прикладной математики является задача оптимизации, которая заключается в выборе наилучшего варианта из некоторого набора альтернатив. Область применения оптимизационных алгоритмов безгранична: механика и инженерное дело, практически вся экономическая теория, исследование операций и теория управления, криптография, а также многие и многие другие направления.
Подобные задачи невероятно разнообразны, поэтому по некоторым признакам их разбивают на различные классы. Так, наряду с классическими задачами непрерывной оптимизации можно рассматривать задачи дискретной оптимизации, или выбор оптимального элемента из некоторого множества однотипных дискретных объектов. Примерами таких задач являются: поиск кратчайшего пути в графе, задача о рюкзаке, оптимальное назначение работников на должности, нахождение минимального остовного дерева, задача коммивояжера и многие другие.
Общая постановка задачи дискретной оптимизации звучит следующим образом: задано конечное дискретное множество X и функция /, определенная на этом множестве и принимающая действительные значения. Требуется найти такой элемент х* € X, для которого f(x*) > f(x) для любого х 6 X (задача максимизации), или /(ж) < f(x) (задача минимизации).
На первый взгляд, решение задачи дискретной оптимизация не представляет никакой математической трудности. Достаточно проверить все элементы множества X (перебрать все варианты) и выбрать оптимальный. В силу конечности и дискретности множества X это всегда возможно. Такой алгоритм носит название полного перебора и для некоторых простых задач, как, например, поиск наибольшего простого двухзначного числа, он вполне допустим. Однако, дискретные задачи часто имеют комбинаторную природу, ибо элементы множества X, среди которых ищут подходящие варианты, задаются комбинационно. Рассмотрим, для примера, широко известную и одну из наиболее популярных комбинаторно-оптимизационных задач: задачу коммивояжера [43].
Условие. Задано конечное множество С = {ci,C2
Задача. Найти наиболее выгодный (короткий, дешевый) маршрут, проходящий через указанные города хотя бы по одному разу с последующим возвратом в исход-

любого набора дизъюнкций С:
CUT(n) ~ М„ С Мп С Pm,n 2 ~ 3-SAT(m, п).
Многогранник Ртп назовем релаксационным многогранником задачи 3-SAT.
Тот факт, что Рт,п является релаксационным многогранником сразу для двух комбинаторно-оптимизационных задач представляется интересным, но не удивительным. Задачи о максимальном разрезе графа и 3-SAT являются NP-полными и, соответственно, полиномиально сводятся друг к другу. Существование многогранника Рт,п лишь еще раз подтверждает этот известный результат.
При доказательстве Утверждения 2.1.1. не был полностью учтен тот момент, что сумма координат в блоках равняется единице (уравнение (7)). Вектор с, по построению, содержит ненулевые координаты только в трех блоках и, соответственно:
Vx Є Рт.п /(ж) < 3п,
max f (х) = 3п. хЄР,
Следовательно, для решения задачи 3-SAT не обязательно находить максимум целевой функции / на множестве целых вершин многогранника Рт:П. Достаточно проверить, достигается ли ma,xxspm n f(x) в целой вершине. Это задача распознавания целочисленности.
Утверждение 2.1.3. Задача распознавания целочисленности на многограннике Рщ,п является NР-полной.
Таким образом, для релаксационного многогранника задачи 3-SAT, в отличие от корневого полуметрического многогранника Мп, являющегося его гранью, не только задача целочисленного программирования, но и более простая задача распознавания целочисленности являются АР-трудными (а, если представить задачу целочисленного программирования в форме распознавания, то и АР-полными).
Следует отметить, что многогранник Pm,n можно использовать не только гхри решении общей задачи 3-SAT, но и любых ее вариаций, достаточно построить соответствующую целевую функцию.
Например, рассмотрим задачу точная 3-выполнимость или 3-выполнимость при одном истинном литерале (l-in-3 SAT, X3SAT).
Условие. Задан набор С трехместных дизъюнкций вида с, = а, V bj V с,, где 3 6 Nn. Логические переменные aj,bj,Cj принимают свои значения из множества U = {иг,щ : г Є Nm}-